2018-5-31
1.4.43 # 解答 # 代码 # 修改后的 DoublingRatio
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="a">测试用的数组。</param> /// <returns>耗时（毫秒）。</returns> public static double TimeTrialLinkedStack(int[] a) { var stack = new LinkedStack<int>(); var n = a.
...
2018-5-31
1.4.44 # 解答 # 每生成一个随机数都和之前生成过的随机数相比较。
代码 # var random = new Random(); const int n = 10000; var a = new int[n]; var dupNum = 0; int times; for (times = 0; times < 500; times++) { for (var i = 0; i < n; i++) { a[i] = random.Next(n); if (IsDuplicated(a, i)) { dupNum += i; Console.WriteLine($"生成{i + 1}个数字后发生重复"); break; } } } Console.WriteLine($"√(πN/2)={Math.Sqrt(Math.PI * n / 2.0)}，平均生成{dupNum / times}个数字后出现重复"); // 检查是否有重复的数字出现。 static bool IsDuplicated(int[] a, int i) { for (var j = 0; j < i; j++) { if (a[j] == a[i]) { return true; } } return false; }
2018-5-31
1.4.45 # 解答 # 建立一个布尔数组，将每次随机出来的数作为下标，将相应位置的布尔值改为 true，每次随机都检查一遍这个数组是否都是 true。
代码 # // HN 指的是调和级数 var random = new Random(); var n = 10000; var a = new bool[n]; var randomSize = 0; int times; for (times = 0; times < 20; times++) { for (var i = 0; i < n; i++) { a[i] = false; } for (var i = 0; true; i++) { var now = random.Next(n); a[now] = true; if (IsAllGenerated(a)) { randomSize += i; Console.
...
2018-6-22
1.5.1 # 解答 # quick-find 的官方实现：QuickFindUF.java。
只要实现相应并查集，然后输入内容即可。
增加一个记录访问数组次数的类成员变量，在每次访问数组的语句执行后自增即可。
样例输出：
1 2 3 4 5 6 7 8 0 数组访问：13 1 2 4 4 5 6 7 8 0 数组访问：13 1 2 4 4 8 6 7 8 0 数组访问：13 1 2 4 4 8 6 2 8 0 数组访问：13 1 1 4 4 8 6 1 8 0 数组访问：14 1 1 4 4 1 6 1 1 0 数组访问：14 1 1 4 4 1 6 1 1 4 数组访问：14 1 1 1 1 1 6 1 1 1 数组访问：16 代码 # QuickFindUF.
...
2018-6-22
1.5.2 # 解答 # quick-union 的官方实现：QuickUnionUF.java。
和上题一样的方式，增加一个记录访问数组次数的类成员变量，在每次访问数组的语句执行后自增即可。
程序输出的森林，用缩进表示子树：
|---- 0 |---- 9 |---- 1 |---- 2 |---- 3 |---- 4 |---- 5 |---- 6 |---- 7 |---- 8 数组访问：1 |---- 0 |---- 9 |---- 1 |---- 2 |---- 4 |---- 3 |---- 5 |---- 6 |---- 7 |---- 8 数组访问：1 |---- 0 |---- 9 |---- 1 |---- 2 |---- 4 |---- 3 |---- 6 |---- 7 |---- 8 |---- 5 数组访问：1 |---- 0 |---- 9 |---- 1 |---- 2 |---- 7 |---- 4 |---- 3 |---- 6 |---- 8 |---- 5 数组访问：1 |---- 0 |---- 9 |---- 1 |---- 2 |---- 7 |---- 4 |---- 3 |---- 6 |---- 8 |---- 5 数组访问：1 |---- 0 |---- 9 |---- 1 |---- 2 |---- 7 |---- 8 |---- 5 |---- 4 |---- 3 |---- 6 数组访问：7 |---- 1 |---- 2 |---- 7 |---- 8 |---- 5 |---- 4 |---- 0 |---- 9 |---- 3 |---- 6 数组访问：3 |---- 1 |---- 2 |---- 7 |---- 4 |---- 0 |---- 9 |---- 3 |---- 8 |---- 5 |---- 6 数组访问：3 代码 # QuickUnionUF.
...
2018-6-22
1.5.3 # 解答 # 加权 quick-union 的官方实现：WeightedQuickUnionUF.java。
样例输出：
1 2 3 4 5 6 7 8 9 数组访问：3 1 2 3 3 5 6 7 8 9 数组访问：3 1 2 3 3 5 6 7 5 9 数组访问：3 1 7 3 3 5 6 7 5 9 数组访问：3 7 7 3 3 5 6 7 5 9 数组访问：5 7 7 3 3 7 6 7 5 9 数组访问：3 7 7 9 3 7 6 7 5 9 数组访问：5 7 7 9 3 7 6 7 5 7 数组访问：9 代码 # WeightedQuickUnionUF.
...
2018-6-22
1.5.4 # 解答 # 对照输入和最坏输入均在书中出现，中文版见：P146，英文版见：P229。
样例输出：
3 index: 0 1 2 3 4 5 6 7 8 9 parent: 0 1 2 4 4 5 6 7 8 9 size: 1 1 1 1 2 1 1 1 1 1 parent visit count:3 size visit count:4 8 index: 0 1 2 3 4 5 6 7 8 9 parent: 0 1 2 4 4 5 6 7 4 9 size: 1 1 1 1 3 1 1 1 1 1 parent visit count:5 size visit count:4 5 index: 0 1 2 3 4 5 6 7 8 9 parent: 0 1 2 4 4 6 6 7 4 9 size: 1 1 1 1 3 1 2 1 1 1 parent visit count:3 size visit count:4 4 index: 0 1 2 3 4 5 6 7 8 9 parent: 0 1 2 4 4 6 6 7 4 4 size: 1 1 1 1 4 1 2 1 1 1 parent visit count:3 size visit count:4 1 index: 0 1 2 3 4 5 6 7 8 9 parent: 0 2 2 4 4 6 6 7 4 4 size: 1 1 2 1 4 1 2 1 1 1 parent visit count:3 size visit count:4 9 index: 0 1 2 3 4 5 6 7 8 9 parent: 0 2 2 4 4 6 6 7 4 4 size: 1 1 2 1 4 1 2 1 1 1 parent visit count:6 size visit count:0 0 index: 0 1 2 3 4 5 6 7 8 9 parent: 6 2 2 4 4 6 6 7 4 4 size: 1 1 2 1 4 1 3 1 1 1 parent visit count:5 size visit count:4 2 index: 0 1 2 3 4 5 6 7 8 9 parent: 6 2 2 4 4 6 6 2 4 4 size: 1 1 3 1 4 1 3 1 1 1 parent visit count:3 size visit count:4 1 index: 0 1 2 3 4 5 6 7 8 9 parent: 6 2 6 4 4 6 6 2 4 4 size: 1 1 3 1 4 1 6 1 1 1 parent visit count:5 size visit count:4 0 index: 0 1 2 3 4 5 6 7 8 9 parent: 6 2 6 4 4 6 6 2 4 4 size: 1 1 3 1 4 1 6 1 1 1 parent visit count:8 size visit count:0 7 index: 0 1 2 3 4 5 6 7 8 9 parent: 6 2 6 4 4 6 6 2 4 4 size: 1 1 3 1 4 1 6 1 1 1 parent visit count:6 size visit count:0 ------------------------------------- 1 index: 0 1 2 3 4 5 6 7 8 9 parent: 0 0 2 3 4 5 6 7 8 9 size: 2 1 1 1 1 1 1 1 1 1 parent visit count:3 size visit count:4 2 index: 0 1 2 3 4 5 6 7 8 9 parent: 0 0 0 3 4 5 6 7 8 9 size: 3 1 1 1 1 1 1 1 1 1 parent visit count:3 size visit count:4 3 index: 0 1 2 3 4 5 6 7 8 9 parent: 0 0 0 0 4 5 6 7 8 9 size: 4 1 1 1 1 1 1 1 1 1 parent visit count:3 size visit count:4 4 index: 0 1 2 3 4 5 6 7 8 9 parent: 0 0 0 0 0 5 6 7 8 9 size: 5 1 1 1 1 1 1 1 1 1 parent visit count:3 size visit count:4 5 index: 0 1 2 3 4 5 6 7 8 9 parent: 0 0 0 0 0 0 6 7 8 9 size: 6 1 1 1 1 1 1 1 1 1 parent visit count:3 size visit count:4 6 index: 0 1 2 3 4 5 6 7 8 9 parent: 0 0 0 0 0 0 0 7 8 9 size: 7 1 1 1 1 1 1 1 1 1 parent visit count:3 size visit count:4 7 index: 0 1 2 3 4 5 6 7 8 9 parent: 0 0 0 0 0 0 0 0 8 9 size: 8 1 1 1 1 1 1 1 1 1 parent visit count:3 size visit count:4 8 index: 0 1 2 3 4 5 6 7 8 9 parent: 0 0 0 0 0 0 0 0 0 9 size: 9 1 1 1 1 1 1 1 1 1 parent visit count:3 size visit count:4 9 index: 0 1 2 3 4 5 6 7 8 9 parent: 0 0 0 0 0 0 0 0 0 0 size: 10 1 1 1 1 1 1 1 1 1 parent visit count:3 size visit count:4 代码 # Main 方法：
...
2018-6-22
1.5.5 # 解答 # $10^6$ 条连接 = $10^6$ 组输入。
对于 quick-find 算法，每次 union() 都要遍历整个数组。
因此总共进行了 $10^9 \times 10^6 = 10^{15}$ 次 for 循环迭代。
每次 for 循环迭代都需要 $10$ 条机器指令，
因此总共执行了 $10 \times10^{15} = 10^{16}$ 条机器指令。
已知计算机每秒能够执行 $10^9$ 条机器指令，
因此执行完所有指令需要 $10^{16} / 10^9 = 10^7$ 秒 = $115.74$ 天。
2018-6-22
1.5.6 # 解答 # 加权 quick-union 算法最多只需要 $lgN $次迭代就可以完成一次 union()。
因此按照上题思路，总共需要 $(lg(10^9) \times 10^6 \times 10) / 10^9 = 0.299$ 秒。
2018-6-22
1.5.7 # 解答 # 见 1.5.1 和 1.5.2 的解答。