2019-1-25
2.5.31 # 解答 # 编写代码进行实验即可，实验结果如下，可以发现十分接近：
代码 # var T = 10; // 重复次数 var n = 1000; // 数组初始大小 var nMultipleBy10 = 4; // 数组大小 ×10 的次数 var mMultipleBy2 = 3; // 数据范围 ×2 的次数 var random = new Random(); for (var i = 0; i < nMultipleBy10; i++) { Console.WriteLine("n=" + n); Console.WriteLine("\tm\temprical\ttheoretical"); var m = n / 2; for (var j = 0; j < mMultipleBy2; j++) { var distinctSum = 0; for (var k = 0; k < T; k++) { var data = new int[n]; for (var l = 0; l < n; l++) data[l] = random.
...
2019-1-26
2.5.32 # 解答 # （前置知识：提前了解 Dijkstra 算法能够降低理解 A* 算法的难度。）
A* 算法是 Dijkstra 算法和最佳优先算法的一种结合。
Dijkstra 算法需要遍历所有结点来找到最短路径，唯一的优化条件就是路径长度。
建立队列 queue ，把所有的结点加入 queue 中；建立数组 d，d[v] 代表起点到点 v 的距离。
开始时只有起点到起点的距离为 0，其他都为无穷大，然后重复如下步骤：
从队列中取出已知距离最短的结点 u，检查该结点的所有边。
如果通过这个点能够以更近的距离到达 v，更新起点到 v 的距离 d[v] = d[u] + distance(u, v)。
等到队列为空之后数组 d 中就存放着起点到其他所有结点的最短距离。
Dijkstra 算法会计算起点到所有点的最短路径，因此会均匀的遍历所有结点，效率较低。
很多时候，我们只需要找到起点到某一终点的最短路径即可，为此遍历整个图显然是不必要的。
通过修改算法，使得比较接近终点的结点优先得到搜索，我们就可能在遍历完全部结点之前获得结果。
在 Dijkstra 算法中，离起点最近的点会被优先搜索，记结点离起点的距离为 g[n] 。
现在引入新的条件，用于估计结点和终点的接近程度，记结点离终点的估计距离为 h[n] 。
令 f[n] = g[n] + h[n]，我们按照 f[n] 对等待搜索的结点进行排序。
同时令 h[n] 始终小于 g[n] ，保证离起点的距离 g[n] 权重大于离终点的估计距离 h[n] 。 （h[n]也被称之为容许估计）
...
2019-1-27
2.5.33 # 解答 # 编写代码实验即可，结果如下：
代码 # 随机交易生成器 TransactionGenerator
internal class TransactionGenerator { private static readonly Random Random = new(); /// <summary> /// 生成 n 条随机交易记录。 /// </summary> /// <param name="n">交易记录的数量。</param> /// <returns></returns> public static Transaction[] Generate(int n) { var trans = new Transaction[n]; for (var i = 0; i < n; i++) { trans[i] = new Transaction (GenerateName(), GenerateDate(), Random.NextDouble() * 1000); } return trans; } /// <summary> /// 获取随机姓名。 /// </summary> /// <returns></returns> private static string GenerateName() { var nameLength = Random.
...