1.4.23 # 解答 # 根据书中的提示，将二分查找中判断相等的条件改为两个数的差小于等于 $1/N^2$。 代码 # // 将二分查找中的相等判定条件修改为差值小于 x，其中 x = 1/N^2。 /// <summary> /// 二分查找。 /// </summary> /// <param name="a">查找范围。</param> /// <param name="key">关键字。</param> /// <returns>结果的下标，没有结果时返回 -1。</returns> static int BinarySearch(double[] a, double key) { var lo = 0; var hi = a.Length - 1; var threshold = 1.0 / (a.Length * a.Length); while (lo <= hi) { var mid = lo + (hi - lo) / 2; if (Math. ...
1.4.24 # 解答 # 第一问：二分查找即可。 第二问： 按照第 1, 2, 4, 8,…, 2^k 层顺序查找，一直到 2^k > F， 随后在 [2^(k - 1), 2^k] 范围中二分查找。 代码 # 这里建立了一个结构体用于返回测试结果： internal struct TestResult { public int F; // 找到的 F 值。 public int BrokenEggs; // 打碎的鸡蛋数。 } 用于测试的方法： /// <summary> /// 扔鸡蛋，没碎返回 true，碎了返回 false。 /// </summary> /// <param name="floor">扔鸡蛋的高度。</param> /// <returns></returns> static bool ThrowEgg(int floor) { return floor <= f; } /// <summary> /// 第一种方案。 /// </summary> /// <param name="a">大楼。</param> /// <returns></returns> static TestResult PlanA(int[] a) { var lo = 0; var hi = a. ...
1.4.25 # 解答 # 第一问： 第一个蛋按照 √(N), 2√(N), 3√(N), 4√(N),…, √(N) * √(N) 顺序查找直至碎掉。这里扔了 k 次，k <= √(N)。 k-1√(N) ~ k√(N) 顺序查找直至碎掉，F 值就找到了。这里最多扔 √(N) 次。 第二问： 按照第 1, 3, 6, 10,…, 1/2k^2 层顺序查找，一直到 1/2k^2 > F， 随后在 [1/2k^2 - k, 1/2k^2] 范围中顺序查找。 代码 # 这里我们同样定义了一个结构体： internal struct TestResult { public int F; // 测试得出的 F 值 public int BrokenEggs; // 碎掉的鸡蛋数。 public int ThrowTimes; // 扔鸡蛋的次数。 } 之后是测试用的方法： /// <summary> /// 扔鸡蛋，没碎返回 true，碎了返回 false。 /// </summary> /// <param name="floor">扔鸡蛋的高度。</param> /// <returns></returns> static bool ThrowEgg(int floor) { return floor <= f; } /// <summary> /// 第一种方案。 /// </summary> /// <param name="a">大楼。</param> /// <returns></returns> // 第一种方案。 static TestResult PlanA(int[] a) { var lo = 0; var hi = 0; var eggs = 0; var throwTimes = 0; var result = new TestResult(); while (ThrowEgg(hi)) { throwTimes++; lo = hi; hi += (int)Math. ...
1.4.26 # 解答 # 首先，我们将问题转化为证明三点 $$ A(a,a^3),B(b,b^3),C(c,c^3) $$ 共线，当且仅当满足 $$ a+b+c=0 $$ 证明： 若 $A,B,C$ 三点共线，则直线 $AB$ 和 $BC$ 的斜率必定相等，有方程： $$ \frac{b^3-a^3}{b-a}=\frac{c^3-b^3}{c-b} $$ 由立方差公式： $$ \frac{(b-a)(b^2+ba+a^2)}{b-a}=\frac{(c-b)(c^2+cb+b^2)}{c-b} $$ 化简有： $$ b^2+ba+a^2=c^2+cb+b^2\newline ba+a^2=c^2+cb $$ 移项，将 $c$ 视为未知数： $$ c^2+cb-ba-a^2=0 $$ 利用十字相乘法进行因式分解： $$ (a+b+c)(c-a)=0 $$ 解得： $$ c_1=-a-b,c_2=a $$ 显然 $c\ne a$ ，因此当且仅当 $a+b+c=0$ 时 $A,B,C$ 三点共线。 证毕。
1.4.27 # 解答 # 实现比较简单，想象两个栈背靠背接在一起，左侧栈负责出队，右侧栈负责入队。 当左侧栈为空时就把右侧栈中的元素倒到左侧栈，这个过程是 O(n) 的。 但在这个过程之前必然有 n 个元素入栈，均摊后即为 O(1)。 代码 # internal class StackQueue<TItem> { private readonly Stack<TItem> _h;// 用于保存出队元素 private readonly Stack<TItem> _;// 用于保存入队元素 /// <summary> /// 构造一个队列。 /// </summary> public StackQueue() { _h = new Stack<TItem>(); _ = new Stack<TItem>(); } /// <summary> /// 将栈 T 中的元素依次弹出并压入栈 H 中。 /// </summary> private void Reverse() { while (!_.IsEmpty()) { _h.Push(_.Pop()); } } /// <summary> /// 将一个元素出队。 /// </summary> /// <returns></returns> public TItem Dequeue() { // 如果没有足够的出队元素，则将 T 中的元素移动过来 if (_h. ...
1.4.28 # 解答 # 每次入队的时候将队列倒转，这样入队的元素就是第一个了。 代码 # internal class QueueStack<TItem> { private readonly Queue<TItem> _queue; /// <summary> /// 初始化一个栈。 /// </summary> public QueueStack() { _queue = new Queue<TItem>(); } /// <summary> /// 向栈中添加一个元素。 /// </summary> /// <param name="item"></param> public void Push(TItem item) { _queue.Enqueue(item); var size = _queue.Size(); // 倒转队列 for (var i = 0; i < size - 1; i++) { _queue.Enqueue(_queue.Dequeue()); } } /// <summary> /// 从栈中弹出一个元素。 /// </summary> /// <returns></returns> public TItem Pop() { return _queue. ...
1.4.29 # 解答 # 和用两个栈实现队列的方法类似。 push 的时候把右侧栈内容倒到左侧栈，之后再入栈。 pop 的时候也做相同操作，右侧栈内容进左侧栈，之后再出栈。 enqueue 的时候则将左侧栈内容倒到右侧栈，之后再入队。 代码 # internal class StackSteque<TItem> { private readonly Stack<TItem> _h; private readonly Stack<TItem> _t; /// <summary> /// 初始化一个 Steque /// </summary> public StackSteque() { _h = new Stack<TItem>(); _t = new Stack<TItem>(); } /// <summary> /// 向栈中添加一个元素。 /// </summary> /// <param name="item"></param> public void Push(TItem item) { ReverseT(); _h.Push(item); } /// <summary> /// 将 T 中的元素弹出并压入到 H 中。 /// </summary> private void ReverseT() { while (! ...
1.4.30 # 解答 # steque 作为队列的头部，stack 作为队列的尾部。 pushLeft：直接 push 到 steque 中即可。 pushRight：如果 stack 为空，则直接 enqueue 到 steque 中，否则就 push 到 stack 中。 popLeft：如果 steque 为空，则将 stack 中的元素倒到 steque 中去（steque.push(stack.pop())），然后再从 steque 中 pop。 popRight：如果 stack 为空，则将 steque 中的元素倒到 stack 中去，然后再从 stack 中 pop。 代码 # internal class Deque<TItem> { private readonly Stack<TItem> _stack; // 代表队列尾部 private readonly Steque<TItem> _steque;// 代表队列头部 /// <summary> /// 创建一条空的双向队列。 /// </summary> public Deque() { _stack = new Stack<TItem>(); _steque = new Steque<TItem>(); } /// <summary> /// 在左侧插入一个新元素。 /// </summary> /// <param name="item">要插入的元素。</param> public void PushLeft(TItem item) { _steque. ...
1.4.31 # 解答 # 三个栈分别命名为左中右。 左侧栈和右侧栈负责模拟队列，和用两个栈模拟队列的方法类似。 由于是双向队列，左栈和右栈会频繁的倒来倒去，因此每次都只倒一半的元素可以有效减少开销。 有一侧栈为空时，另一侧栈中上半部分先移动到中间栈中，下半部分倒到另一侧栈里，再从中间栈拿回上半部分元素。 这样可以确保接下来的 pop 操作一定是常数级别的。 代码 # internal class Deque<TItem> { private readonly Stack<TItem> _left; private readonly Stack<TItem> _middle; private readonly Stack<TItem> _right; /// <summary> /// 构造一条新的双向队列。 /// </summary> public Deque() { _left = new Stack<TItem>(); _middle = new Stack<TItem>(); _right = new Stack<TItem>(); } /// <summary> /// 向双向队列左侧插入一个元素。 /// </summary> /// <param name="item">要插入的元素。</param> public void PushLeft(TItem item) { _left.Push(item); } /// <summary> /// 向双向队列右侧插入一个元素。 /// </summary> /// <param name="item">要插入的元素。</param> public void PushRight(TItem item) { _right. ...
1.4.32 # 解答 # 首先，不需要扩容数组的的操作都只需访问数组一次，$M$ 次操作就是 $M$ 次访问。 随后我们有性质， $M$ 次栈操作后额外复制访问数组的次数小于 $2M$。 这里简单证明，设 $M$ 次操作之后栈的大小为 $n$，那么额外访问数组的次数为： $S = \frac{n}{2} + \frac{n}{4} + \frac{n}{8} +…+ 2 < n$ 为了能使栈大小达到 $n$，$M$ 必须大于等于 $\frac{n}{2}$ 因此 $2M \ge n > S$，得证。 因此我们可以得到 $M$ 次操作后访问数组次数的总和 $S’ = S + M < 3M$。