3.1.11
2019-2-20
3.1.11 # 解答 # 键的轨迹如下图所示： 键查找使用二分查找优化，插入新的键时不必与每个键都进行比较。 共进行了 0 + 1 + 2 + 2 + 2 + 3 + 3 + 3 + 3 + 3 + 3 + 4 = 29 次比较。
Searching
3.1.12
2019-2-23
3.1.12 # 解答 # 建立类 Item： public class Item<TKey, TValue> : IComparable<Item<TKey, TValue>> where TKey : IComparable<TKey> { public TKey Key { get; set; } public TValue Value { get; set; } public int CompareTo(Item<TKey, TValue> other) { return Key.CompareTo(other.Key); } } 之后修改 BinarySearchST，将其中的 TKey[] keys 和 TValue[] values 数组用 Item[] items 数组代替。 例如 keys[i] 变为 items[i].Key，values[i] 变为 items[i].Value。 添加一个构造函数，调用之前编写的归并排序实现。 /// <summary> /// 根据已有的键值对构造一个符号表。 /// </summary> /// <param name="items">已有的键值对。</param> public ItemBinarySearchSt(Item<TKey, TValue>[] items) { _items = new Item<TKey, TValue>[items. ...
3.1.13
2019-2-23
3.1.13 # 解答 # Get() 调用次数比 Put() 调用次数多了三个数量级， BinarySearchST 和 SequentialSearchST 的平均 Put() 开销是一样的， 因此选择平均 Get() 开销更小的 BinarySearchST。
3.1.14
2019-2-23
3.1.14 # 解答 # 根据上题给出的结论，选择 BinarySearchST。 由于 BinarySearchST 和 SequentialSearchST 执行 Put() 的开销相同 因此选择 Get() 开销更低的 BinarySearchST。
3.1.15
2019-2-23
3.1.15 # 解答 # 假设先全部 Put()，再进行查找操作。 即分别进行 $1$, $10 ^ 3$, $10 ^ 6$ 次插入 $N = 1$ 时，可以直接得出比例 $0.1 %$。 $N = 10 ^ 3$ 时， 插入耗时 $= 1 + 2 + … + 10 ^ 3 = 500500$， 查询耗时 $= 10 ^ 6 * \lg(10 ^ 3) = 9965784$， 比例为 $4.782 %$。 $N = 10 ^ 6$ 时 插入耗时 $= 1 + 2 + … + 10 ^ 6 = 500000500000$， ...
3.1.16
2019-2-24
3.1.16 # 解答 # 官方实现：https://algs4.cs.princeton.edu/31elementary/BinarySearchST.java.html 先通过二分查找获得下标，然后后面的元素依次向前移动一位。 public void Delete(TKey key) { if (key == null) throw new ArgumentNullException(nameof(key), "argument to Delete() is null"); if (IsEmpty()) return; var i = Rank(key); if (i == _n && _keys[i].CompareTo(key) != 0) return; for (var j = i; j < _n - 1; j++) { _keys[j] = _keys[j + 1]; _values[j] = _values[j + 1]; } _n--; _keys[_n] = default; _values[_n] = default; if (_n > 0 && _n == _keys. ...
3.1.17
2019-2-24
3.1.17 # 解答 # 官方实现：https://algs4.cs.princeton.edu/31elementary/BinarySearchST.java.html 先通过二分查找大于等于 key 的键下标 i， 如果 keys[i] 和 key 相等则直接返回 keys[i]， 否则返回 keys[i-1]。 public TKey Floor(TKey key) { if (key == null) throw new ArgumentNullException(nameof(key), "argument to Floor() is null"); var i = Rank(key); if (i < _n && _keys[i].CompareTo(key) == 0) return _keys[i]; if (i == 0) return default; return _keys[i - 1]; } 另请参阅 # SymbolTable 库
3.1.18
2019-2-24
3.1.18 # 解答 # 设 key 为目标键。 算法初始时 lo = 0, hi = n - 1，数组已排序。 当找到目标键时，返回的下标 mid 显然是正确的。 （0…a[mid - 1] 都小于 a[mid]，同时 a[mid] = key） 接下来证明：当目标键不存在时，lo 可以代表小于 key 的键的个数。 由算法内容，当循环退出时，一定有 lo 和 hi 交叉，即 lo > hi。 考虑最后一次循环，必然执行了 lo = mid + 1 或者 hi = mid - 1。 即最后一次循环之后 lo = mid + 1 > hi 或 hi = mid - 1 < lo。 又由于 mid = (lo + hi) / 2，代入有： ...
3.1.19
2019-2-25
3.1.19 # 解答 # 将频率和当前最大频率相同的单词都放到一个队列里即可。 var max = ""; var queue = new Queue<string>(); st.Put(max, 0); foreach (var s in st.Keys()) { if (st.Get(s) > st.Get(max)) { max = s; queue.Clear(); queue.Enqueue(s); } else if (st.Get(s) == st.Get(max)) { queue.Enqueue(s); } } 另请参阅 # SymbolTable 库
3.1.20
2019-2-26
3.1.20 # 解答 # 国内的书中关于命题 B 的证明有错误，新版的证明结论已经改为： $$ C(n)=C(2^k-1) \le k = \lg (n+1) \le \lg n +1 $$ 其中 $n=2^k - 1 $ 。 先证单调性，利用数学归纳法： 已知对于 $N=0$，满足 $C(0) \le C(1)$。 假设对于 $N=n$，满足 $C(n) \le C(n+1)$。 根据递归式，有： $$ \begin{eqnarray*} & C(n) & \le C(\lfloor n/2 \rfloor) + 1 \newline \newline & C(n+1) & \le \begin{cases} C(\lfloor n/2 \rfloor) +1 & \text{$n$ 是偶数} \newline C(\lfloor n/2 \rfloor + 1) + 1 & \text{$n$ 是奇数} \end{cases}\newline \newline & C(n+2) & \le C(\lfloor n/2 \rfloor + 1) + 1 \end{eqnarray*} $$ ...