1.4.33 # 解答 # Integer = 4(int) + 8(对象开销) = 12 Date = 3 × 4(int × 3) + 8(对象开销) = 20 Counter = 4(String 的引用) + 4(int) + 8(对象开销) = 16 int[] = 8(对象开销) + 4(数组长度) + 4N = 12 + 4N double[] = 8(对象开销) + 4(数组长度) + 8N = 12 + 8N double[][] = 8(对象开销) + 4(数组长度) + 4M(引用) + M(12 + 8N)(M 个一维数组) = 12 + 16M + 8MN ...
1.4.34 # 解答 # 第一种方案，类似于二分查找，先猜测左边界(lo)，再猜测右边界(hi)，如果边界值猜中的话直接返回，否则： 如果右边界比较热，那么左边界向右边界靠，lo=mid；否则，右边界向左边界靠，hi=mid。其中，mid = lo + (hi – lo)/2。 每次二分查找都要猜测两次，~2lgN。 第二种方案，假设上次猜测值为 $lastGuess$，本次即将要猜测的值为 $nowGuess$，通过方程： $(lastGuess + nowGuess)/2 = (lo + hi)/2$ 可以求得 $nowGuess$，具体可以查看示意图： 数字是猜测顺序，黑色范围是猜测值的范围（$lastGuess$ 和 $nowGuess$），绿色的是实际查找的范围（lo 和 hi）。 代码 # 首先是 Game 类 internal class Game { public int N { get; } // 目标值的最大范围。 public int SecretNumber { get; } // 目标值。 public int LastGuess { get; private set; } // 上次猜测的值 /// <summary> /// 构造函数，新开一局游戏。 /// </summary> /// <param name="n">目标值的最大范围。</param> public Game(int n) { var random = new Random(); N = n; SecretNumber = random. ...
1.4.35 # 解答 # 1. 一个 Node 对象包含一个 int(泛型 Item) 的引用和下一个 Node 对象的引用。push 操作创建新 Node 对象时会创建一个引用。 因此对于第一种情况，压入 n 个 int 类型的元素创建了 N 个 Node 对象，创建了 2N 个引用。 2. 比起上一种情况，每个 Node 对象多包含了一个指向 Integer 的引用。 因此对于第二种情况，压入 n 个 int 类型的元素创建了 N 个 Node 对象和 N 个 Integer 对象，比起第一种情况多创建了 N 个引用。 3. 对于数组来说，创建对象只有扩容时重新创建数组对象一种情况，对于 N 次 push 操作只需要 lgN 次扩容，因此创建的对象为 lgN 个。 每次扩容都需要重新创建引用，(4 + 8 +…+ 2N)(扩容) + N(每次 push 操作) = 5N - 4 = ~5N ...
1.4.36 # 解答 # 1. N 个 Node 对象的空间开销 = N * (16(对象开销) + 4(int) + 8(下一个 Node 的引用) + 4(填充字节)) = 32N 2. 比起上一题来说，空间开销变为 = N * (16(Node 对象开销) + 8(Integer 对象引用) + (16(Integer 对象开销) + 4(int) + 4(填充字节)) + 8(下一个对象的引用) = 32N + 24N = 56N。 3. 如果不扩容则是 4N，N 个元素最多可以维持 4N 的栈空间（少于四分之一将缩小）。 4. 比起上一题，数组元素变成了引用每个占用 8 字节，还要额外加上 Integer 对象的每个 24 字节。 = (8 + 24)N ~ (8 * 4 + 24)N
1.4.37 # 解答 # 数据量比较大时才会有比较明显的差距。 代码 # FixedCapacityStackOfInts /// <summary> /// 固定大小的整型数据栈。 /// </summary> internal class FixedCapacityStackOfInts : IEnumerable<int> { private readonly int[] _a; private int _n; /// <summary> /// 默认构造函数。 /// </summary> /// <param name="capacity">栈的大小。</param> public FixedCapacityStackOfInts(int capacity) { _a = new int[capacity]; _n = 0; } /// <summary> /// 检查栈是否为空。 /// </summary> /// <returns></returns> public bool IsEmpty() { return _n == 0; } /// <summary> /// 检查栈是否已满。 /// </summary> /// <returns></returns> public bool IsFull() { return _n == _a. ...
1.4.38 # 解答 # 把 DoublingTest 中调用的函数稍作修改即可。 代码 # ThreeSum 测试类 public static class DoubleTest { private static readonly int MaximumInteger = 1000000; /// <summary> /// 返回对 n 个随机整数的数组进行一次 ThreeSum 所需的时间。 /// </summary> /// <param name="n">随机数组的长度。</param> /// <returns></returns> public static double TimeTrial(int n) { var a = new int[n]; var random = new Random(DateTime.Now.Millisecond); for (var i = 0; i < n; i++) { a[i] = random.Next(-MaximumInteger, MaximumInteger); } var timer = new Measurement. ...
1.4.39 # 解答 # 执行 N 次后取平均即可。 代码 # 修改后的 DoublingTest： public static class DoubleTest { private static readonly int MaximumInteger = 1000000; /// <summary> /// 返回对 n 个随机整数的数组进行一次 ThreeSum 所需的时间。 /// </summary> /// <param name="n">随机数组的长度。</param> /// <param name="repeatTimes">重复测试的次数。</param> /// <returns></returns> public static double TimeTrial(int n, int repeatTimes) { var a = new int[n]; double sum = 0; var random = new Random(DateTime.Now.Millisecond); for (var i = 0; i < n; i++) { a[i] = random. ...
1.4.40 # 解答 # N 个数可组成的三元组的总数为： $C(N, 3) = N(N-1)(N-2)/3! = ~ (N^3)/6$ （组合数公式） $[-M, M]$ 中随机 $N$ 次，有 $(2M+1)^N$ 种随机序列（每次随机都有 $2M+1$ 种可能） 按照分步计数方法，将随机序列分为和为零的三元组和其余 $N-3$ 个数 这些序列中，和为零的三元组有 $3M^2 + 3M + 1$ 种可能。 其他不为零的 $N-3$ 个位置有 $(2M+1)^{(N-3)}$ 种可能。 总共有 $((N^3)/6) \times (3M^2 + 3M + 1) \times (2M+1)^{(N-3)}$ 种可能性 平均值为： $[((N^3)/6) \times (3M^2 + 3M + 1) \times (2M+1)^{(N-3)}] / (2M+1)^N$ $=N^3/16M$ $3M^2 + 3M + 1$ 的推导： 在 $[-M,M]$ 中取三个数，和为零的序列有几个？ 假设第一个数取 $0$， 取 $(0, 0, 0)$ 的情况最后加上。 ...
1.4.41 # 解答 # 代码 # 这里使用了委托来简化代码。 DoublingRatio public delegate int Count(int[] a); internal static class DoublingRatio { /// <summary> /// 从指定字符串中读入按行分割的整型数据。 /// </summary> /// <param name="inputString">源字符串。</param> /// <returns>读入的整型数组</returns> private static int[] ReadAllInts(string inputString) { var split = new[] { '\n' }; var input = inputString.Split(split, StringSplitOptions.RemoveEmptyEntries); var a = new int[input.Length]; for (var i = 0; i < a.Length; i++) { a[i] = int.Parse(input[i]); } return a; } /// <summary> /// 使用给定的数组进行一次测试，返回耗时（毫秒）。 /// </summary> /// <param name="count">要测试的方法。</param> /// <param name="a">测试用的数组。</param> /// <returns>耗时（秒）。</returns> public static double TimeTrial(Count count, int[] a) { var timer = new Stopwatch(); count(a); return timer. ...
1.4.42 # 解答 # 这里我们把时限设置为一小时，使用上一题的数据估计。 1.ThreeSum 暴力方法在输入倍增时耗时增加 2^3 = 8 倍。 1K 数据耗费了 1.15 秒，在一小时内（3600 秒）可以完成 2^3 = 8K 数据。 2.ThreeSumFast 方法在输入倍增时耗时增加 2^2 = 4 倍。 1K 数据耗费了 0.05 秒，在一小时内（3600 秒）可以完成 2^8 = 256K 数据。 3.TwoSum 暴力方法在输入倍增时耗时增加 2^2 = 4 倍。 8K 数据耗费了 0.14 秒，在一小时内（3600 秒）可以完成 2^10 = 1024K 数据。 4.TwoSumFast 在输入倍增时耗时增加 2^1 = 2 倍。 32K 数据耗费了 0.008 秒，在一小时内（3600 秒）可以完成 2^16 = 65536K 数据。