2018-6-22
1.5.18 # 解答 # 具体生成的连接样式见下题，这里给出 RandomGrid 的实现，需要使用 1.3 节中的随机背包辅助。
代码 # RandomGrid.cs
public class RandomBag<TItem> : IEnumerable<TItem> { private TItem[] _bag; private int _count; /// <summary> /// 建立一个随机背包。 /// </summary> public RandomBag() { _bag = new TItem[2]; _count = 0; } /// <summary> /// 检查背包是否为空。 /// </summary> /// <returns></returns> public bool IsEmpty() { return _count == 0; } /// <summary> /// 返回背包中元素的数量。 /// </summary> /// <returns></returns> public int Size() { return _count; } /// <summary> /// 向背包中添加一个元素。 /// </summary> /// <param name="item">要向背包中添加的元素。</param> public void Add(TItem item) { if (_count == _bag.
...
2018-6-22
1.5.19 # 解答 # 最后绘出的图像：
代码 # 给出绘图部分的代码，窗体部分见 GitHub。
using System; using System.Drawing; using System.Collections.Generic; using System.Windows.Forms; using UnionFind; namespace _1._5._19 { /* * 1.5.19 * * 动画。 * 编写一个 RandomGrid（请见练习 1.5.18）的用例， * 和我们开发用例一样使用 UnionFind 来检查触点的连通性并在处理时用 StdDraw 将它们绘出。 * */ static class Program { static RandomBag<Connection> bag; static Graphics graphics; static TextBox logBox; static PointF[] points; static Timer timer; static List<Connection> connections; static int count = 0; /// <summary> /// 应用程序的主入口点。 /// </summary> [STAThread] static void Main() { Application.
...
2018-6-28
1.5.20 # 解答 # 将 parent 数组和 size 数组用链表代替即可，很容易实现。
代码 # 修改后的 WeightedQuickUnionUF.cs
public class WeightedQuickUnionUf { protected LinkedList<int> Parent; // 记录各个结点的父级。 protected LinkedList<int> Size; // 记录各个树的大小。 protected int Count; // 分量数目。 /// <summary> /// 建立使用加权 quick-union 的并查集。 /// </summary> public WeightedQuickUnionUf() { Parent = new LinkedList<int>(); Size = new LinkedList<int>(); } /// <summary> /// 获取 parent 数组。 /// </summary> /// <returns>parent 数组。</returns> public LinkedList<int> GetParent() { return Parent; } /// <summary> /// 获取 size 数组。 /// </summary> /// <returns>返回 size 数组。</returns> public LinkedList<int> GetSize() { return Size; } /// <summary> /// 在并查集中增加一个新的结点。 /// </summary> /// <returns>新结点的下标。</returns> public int NewSite() { Parent.
...
2018-6-28
1.5.21 # 解答 # 给出我电脑上的结果：
实验结果：16 1/2NlnN：11.51292546497023 实验结果：38 1/2NlnN：29.957322735539908 实验结果：89 1/2NlnN：73.77758908227872 实验结果：194 1/2NlnN：175.28106538695525 实验结果：455 1/2NlnN：406.0139052187061 实验结果：1050 1/2NlnN：922.9313593270035 实验结果：2300 1/2NlnN：2067.6698164331897 实验结果：4918 1/2NlnN：4578.953828424745 实验结果：10812 1/2NlnN：10045.136047966218 实验结果：23478 1/2NlnN：21864.728878165897 代码 # for (var n = 10; n < 10000; n *= 2) { var total = 0; for (var i = 0; i < 100; i++) { var uf = new Uf(n); total += ErdosRenyi.Count(uf); } Console.WriteLine("实验结果：" + total / 100); Console.WriteLine("1/2NlnN：" + Math.
...
2018-6-28
1.5.22 # 解答 # 平方级别算法在输入加倍后耗时应该增加四倍，线性则是两倍。
下面给出我电脑上的结果，数据量较大时比较明显：
N:16000 quick-find 平均次数：8452 用时：143 比值：4.46875 quick-union 平均次数：7325 用时：202 比值：3.25806451612903 weighted-quick-union 平均次数：6889 用时：1 N:32000 quick-find 平均次数：15747 用时：510 比值：3.56643356643357 quick-union 平均次数：15108 用时：801 比值：3.96534653465347 weighted-quick-union 平均次数：17575 用时：3 比值：3 N:64000 quick-find 平均次数：33116 用时：2069 比值：4.05686274509804 quick-union 平均次数：38608 用时：4635 比值：5.78651685393258 weighted-quick-union 平均次数：34850 用时：6 比值：2 代码 # long lastTimeQuickFind = 0; long lastTimeQuickUnion = 0; long lastTimeWeightedQuickUnion = 0; for (var n = 2000; n < 100000; n *= 2) { Console.
...
2018-6-28
1.5.23 # 解答 # 先用速度最快的 WeightedQuickUnionUF 生成一系列连接，
保存后用这些连接进行测试，生成连接的方法见 1.5.17 的解答。
下面给出我电脑上的结果：
N:2000 quick-find 耗时（毫秒）：4 quick-union 耗时（毫秒）：5 比值：0.8 N:4000 quick-find 耗时（毫秒）：19 quick-union 耗时（毫秒）：24 比值：0.791666666666667 N:8000 quick-find 耗时（毫秒）：57 quick-union 耗时（毫秒）：74 比值：0.77027027027027 N:16000 quick-find 耗时（毫秒）：204 quick-union 耗时（毫秒）：307 比值：0.664495114006515 N:32000 quick-find 耗时（毫秒）：1127 quick-union 耗时（毫秒）：1609 比值：0.700435052827843 代码 # var n = 2000; for (var t = 0; t < 5; t++) { var input = ErdosRenyi.Generate(n); var quickFind = new QuickFindUf(n); var quickUnion = new QuickUnionUf(n); Console.
...
2018-6-28
1.5.24 # 解答 # 根据上题的代码略作修改即可，路径压缩大概可以快 1/3。
N:10000 加权 quick-find 耗时（毫秒）：9 带路径压缩的加权 quick-union 耗时（毫秒）：6 比值：1.5 N:20000 加权 quick-find 耗时（毫秒）：12 带路径压缩的加权 quick-union 耗时（毫秒）：8 比值：1.5 N:40000 加权 quick-find 耗时（毫秒）：18 带路径压缩的加权 quick-union 耗时（毫秒）：12 比值：1.5 N:80000 加权 quick-find 耗时（毫秒）：36 带路径压缩的加权 quick-union 耗时（毫秒）：30 比值：1.2 N:160000 加权 quick-find 耗时（毫秒）：67 带路径压缩的加权 quick-union 耗时（毫秒）：41 比值：1.63414634146341 代码 # var n = 10000; for (var t = 0; t < 5; t++) { var input = ErdosRenyi.Generate(n); var weightedQuickUnionUf = new WeightedQuickUnionUf(n); var weightedQuickUnionPathCompressionUf = new WeightedQuickUnionPathCompressionUf(n); Console.
...
2018-6-28
1.5.25 # 解答 # 略微修改 1.5.22 的代码即可。 我电脑上的结果：
Quick-Find N:1600 平均用时（毫秒）：4 N:6400 平均用时（毫秒）：67 比值：16.75 N:25600 平均用时（毫秒）：1268 比值：18.9253731343284 N:102400 平均用时（毫秒）：20554 比值：16.2097791798107 Quick-Union N:1600 平均用时（毫秒）：5 比值：0.000243261652233142 N:6400 平均用时（毫秒）：66 比值：13.2 N:25600 平均用时（毫秒）：1067 比值：16.1666666666667 N:102400 平均用时（毫秒）：18637 比值：17.4667291471415 Weighted Quick-Union N:1600 平均用时（毫秒）：0 比值：0 N:6400 平均用时（毫秒）：2 N:25600 平均用时（毫秒）：12 比值：6 N:102400 平均用时（毫秒）：64 比值：5.33333333333333 代码 # var n = 40; var t = 4; // quick-find Console.WriteLine("Quick-Find"); long last = 0; long now; for (var i = 0; i < t; i++, n *= 2) { Console.
...
2018-6-28
1.5.26 # 解答 # 和 1.5.16 的程序类似，将测试的内容改为 Erdos-Renyi 即可。
样例输出：
代码 # using System; using System.Linq; using System.Windows.Forms; using System.Drawing; using UnionFind; namespace _1._5._26 { static class Program { /// <summary> /// 应用程序的主入口点。 /// </summary> [STAThread] static void Main() { Application.EnableVisualStyles(); Application.SetCompatibleTextRenderingDefault(false); Compute(); Application.Run(new Form1()); } static void Compute() { int size = 200; QuickFindUF quickFind = new QuickFindUF(size); QuickUnionUF quickUnion = new QuickUnionUF(size); WeightedQuickUnionUF weightedQuickUnion = new WeightedQuickUnionUF(size); Connection[] connections = ErdosRenyi.
...