-
编程语言
站-
热门城市 全国站>
-
其他省市
-
-
400-636-0069
小标
2019-01-15
来源 ：
阅读 1273
评论 0
摘要：本文主要向大家介绍了C#编程之算法（第四版）C#题解——1.5，通过具体的内容向大家展示，希望对大家学习C#编程有所帮助。
本文主要向大家介绍了C#编程之算法（第四版）C#题解——1.5，通过具体的内容向大家展示，希望对大家学习C#编程有所帮助。
写在前面整个项目都托管在了 Github 上：https://github.com/ikesnowy/Algorithms-4th-Edition-in-Csharp这一节内容可能会用到的库文件有 Measurement 和 TestCase，同样在 Github 上可以找到。善用 Ctrl + F 查找题目。习题&题解
1.5.1题目使用 quick-find 算法处理序列 9-0 3-4 5-8 7-2 2-1 5-7 0-3 4-2 。对于输入的每一对整数，给出 id[] 数组的内容和访问数组的次数。解答quick-find 的官方实现：QuickFindUF.java。只要实现相应并查集，然后输入内容即可。增加一个记录访问数组次数的类成员变量，在每次访问数组的语句执行后自增即可。样例输出：0 1 2 3 4 5 6 7 8 0 数组访问：13
0 1 2 4 4 5 6 7 8 0 数组访问：13
0 1 2 4 4 8 6 7 8 0 数组访问：13
0 1 2 4 4 8 6 2 8 0 数组访问：13
0 1 1 4 4 8 6 1 8 0 数组访问：14
0 1 1 4 4 1 6 1 1 0 数组访问：14
4 1 1 4 4 1 6 1 1 4 数组访问：14
1 1 1 1 1 1 6 1 1 1 数组访问：16代码QuickFindUF.cs，这个类继承了 UF.cs，重新实现了 Union() 和 Find() 等方法。关于 UF.cs 可以参见原书中文版 P138 或英文版 P221 的算法 1.5。namespace UnionFind
{
///
public class QuickFindUF : UF
{
public int ArrayVisitCount { get; private set; } //记录数组访问的次数。
///
///
并查集的大小。
public QuickFindUF(int n) : base(n) { }
///
public void ResetArrayCount()
{
this.ArrayVisitCount = 0;
}
///
///
需要寻找的结点。
///
public override int Find(int p)
{
Validate(p);
this.ArrayVisitCount++;
return this.parent[p];
}
///
///
需要判断的结点。
///
需要判断的另一个结点。
///
public override bool IsConnected(int p, int q)
{
Validate(p);
Validate(q);
this.ArrayVisitCount += 2;
return this.parent[p] == this.parent[q];
}
///
///
需要合并的结点。
///
需要合并的另一个结点。
public override void Union(int p, int q)
{
Validate(p);
Validate(q);
int pID = this.parent[p];
int qID = this.parent[q];
this.ArrayVisitCount += 2;
// 如果两个结点同属于一个连通分量，那么什么也不做。
if (pID == qID)
{
return;
}
for (int i = 0; i < this.parent.Length; ++i)
{
if (this.parent[i] == pID)
{
this.parent[i] = qID;
this.ArrayVisitCount++;
}
}
this.ArrayVisitCount += this.parent.Length;
this.count--;
return;
}
///
///
public int[] GetParent()
{
return this.parent;
}
}
}Main 方法：using System;
using UnionFind;
namespace _1._5._1
{
/*
* 1.5.1
*
* 使用 quick-find 算法处理序列 9-0 3-4 5-8 7-2 2-1 5-7 0-3 4-2 。
* 对于输入的每一对整数，给出 id[] 数组的内容和访问数组的次数。
*
*/
class Program
{
static void Main(string[] args)
{
string[] input = "9-0 3-4 5-8 7-2 2-1 5-7 0-3 4-2".Split(‘ ‘);
var quickFind = new QuickFindUF(10);
foreach (string s in input)
{
quickFind.ResetArrayCount();
string[] numbers = s.Split(‘-‘);
int p = int.Parse(numbers[0]);
int q = int.Parse(numbers[1]);
int[] id = quickFind.GetParent();
quickFind.Union(p, q);
foreach (int root in id)
{
Console.Write(root + " ");
}
Console.WriteLine("数组访问：" + quickFind.ArrayVisitCount);
}
}
}
}
1.5.2题目使用 quick-union 算法（请见 1.5.2.3 节代码框）完成练习 1.5.1。另外，在处理完输入的每对整数之后画出 id[] 数组表示的森林。解答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.cs，这个类继承了 UF.cs，重新实现了 Union() 和 Find() 等方法。关于 UF.cs 可以参见原书中文版 P138 或英文版 P221 的算法 1.5。namespace UnionFind
{
///
public class QuickUnionUF : UF
{
public int ArrayVisitCount { get; private set; } //记录数组访问的次数。
///
///
并查集的大小。
public QuickUnionUF(int n) : base(n) { }
///
public virtual void ResetArrayCount()
{
this.ArrayVisitCount = 0;
}
///
///
public int[] GetParent()
{
return this.parent;
}
///
///
需要寻找的结点。
///
public override int Find(int p)
{
Validate(p);
while (p != this.parent[p])
{
p = this.parent[p];
this.ArrayVisitCount += 2;
}
return p;
}
///
///
需要合并的结点。
///
需要合并的另一个结点。
public override void Union(int p, int q)
{
int rootP = Find(p);
int rootQ = Find(q);
if (rootP == rootQ)
{
return;
}
this.parent[rootP] = rootQ;
this.ArrayVisitCount++;
this.count--;
}
}
}Main 方法using System;
using UnionFind;
namespace _1._5._2
{
/*
* 1.5.2
*
* 使用 quick-union 算法（请见 1.5.2.3 节代码框）完成练习 1.5.1。
* 另外，在处理完输入的每对整数之后画出 id[] 数组表示的森林。
*
*/
class Program
{
static void Main(string[] args)
{
string[] input = "9-0 3-4 5-8 7-2 2-1 5-7 0-3 4-2".Split(‘ ‘);
var quickUnion = new QuickUnionUF(10);
foreach (string s in input)
{
quickUnion.ResetArrayCount();
string[] numbers = s.Split(‘-‘);
int p = int.Parse(numbers[0]);
int q = int.Parse(numbers[1]);
quickUnion.Union(p, q);
int[] parent = quickUnion.GetParent();
for (int i = 0; i < parent.Length; ++i)
{
if (parent[i] == i)
{
Console.WriteLine("|---- " + i);
DFS(parent, i, 1);
}
}
Console.WriteLine("数组访问：" + quickUnion.ArrayVisitCount);
}
}
static void DFS(int[] parent, int root, int level)
{
for (int i = 0; i < parent.Length; ++i)
{
if (parent[i] == root && i != root)
{
for (int j = 0; j < level; ++j)
{
Console.Write(" ");
}
Console.WriteLine("|---- " + i);
DFS(parent, i, level + 1);
}
}
}
}
}
1.5.3题目使用加权 quick-union 算法（请见算法 1.5）完成练习 1.5.1 。解答加权 quick-union 的官方实现：WeightedQuickUnionUF.java。样例输出：9 1 2 3 4 5 6 7 8 9 数组访问：3
9 1 2 3 3 5 6 7 8 9 数组访问：3
9 1 2 3 3 5 6 7 5 9 数组访问：3
9 1 7 3 3 5 6 7 5 9 数组访问：3
9 7 7 3 3 5 6 7 5 9 数组访问：5
9 7 7 3 3 7 6 7 5 9 数组访问：3
9 7 7 9 3 7 6 7 5 9 数组访问：5
9 7 7 9 3 7 6 7 5 7 数组访问：9代码WeightedQuickUnionUF.cs，这个类继承了 QuickUnion.cs，重新实现了 Union() 和 Find() 等方法。关于 QuickUnion.cs 可以参见 1.5.2 的代码部分。namespace UnionFind
{
///
public class WeightedQuickUnionUF : QuickUnionUF
{
protected int[] size; // 记录各个树的大小。
public int ArrayParentVisitCount { get; private set; } // 记录 parent 数组的访问次数。
public int ArraySizeVisitCount { get; private set; } //记录 size 数组的访问次数。
///
///
并查集的大小。
public WeightedQuickUnionUF(int n) : base(n)
{
this.size = new int[n];
for (int i = 0; i < n; ++i)
{
this.size[i] = 1;
}
this.ArrayParentVisitCount = 0;
this.ArraySizeVisitCount = 0;
}
///
public override void ResetArrayCount()
{
this.ArrayParentVisitCount = 0;
this.ArraySizeVisitCount = 0;
}
///
///
public int[] GetSize()
{
return this.size;
}
///
///
需要寻找的结点。
///
public override int Find(int p)
{
Validate(p);
while (p != this.parent[p])
{
p = this.parent[p];
this.ArrayParentVisitCount += 2;
}
this.ArrayParentVisitCount++;
return p;
}
///
///
需要合并的结点。
///
需要合并的另一个结点。
public override void Union(int p, int q)
{
int rootP = Find(p);
int rootQ = Find(q);
if (rootP == rootQ)
{
return;
}
if (this.size[rootP] < this.size[rootQ])
{
this.parent[rootP] = rootQ;
this.size[rootQ] += this.size[rootP];
}
else
{
this.parent[rootQ] = rootP;
this.size[rootP] += this.size[rootQ];
}
this.ArrayParentVisitCount++;
this.ArraySizeVisitCount += 4;
this.count--;
}
}
}Main 方法using System;
using UnionFind;
namespace _1._5._3
{
/*
* 1.5.3
*
* 使用加权 quick-union 算法（请见算法 1.5）完成练习 1.5.1 。
*
*/
class Program
{
static void Main(string[] args)
{
string[] input = "9-0 3-4 5-8 7-2 2-1 5-7 0-3 4-2".Split(‘ ‘);
var weightedQuickUnion = new WeightedQuickUnionUF(10);
foreach (string s in input)
{
weightedQuickUnion.ResetArrayCount();
string[] numbers = s.Split(‘-‘);
int p = int.Parse(numbers[0]);
int q = int.Parse(numbers[1]);
weightedQuickUnion.Union(p, q);
int[] parent = weightedQuickUnion.GetParent();
for (int i = 0; i < parent.Length; ++i)
{
Console.Write(parent[i] + " ");
}
Console.WriteLine("数组访问：" + weightedQuickUnion.ArrayParentVisitCount);
}
}
}
}
1.5.4题目在正文的加权 quick-union 算法示例中，对于输入的每一对整数（包括对照输入和最坏情况下的输入），给出 id[] 和 sz[] 数组的内容以及访问数组的次数。解答对照输入和最坏输入均在书中出现，中文版见：P146，英文版见：P229。样例输出：4 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
3 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
6 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
9 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
2 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
8 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
5 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
7 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
6 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
1 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
6 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
-------------------------------------
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
0 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
0 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
0 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
0 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
0 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
0 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
0 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
0 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 方法：using System;
using UnionFind;
namespace _1._5._4
{
/*
* 1.5.4
*
* 在正文的加权 quick-union 算法示例中，
* 对于输入的每一对整数（包括对照输入和最坏情况下的输入），
* 给出 id[] 和 sz[] 数组的内容以及访问数组的次数。
*
*/
class Program
{
static void Main(string[] args)
{
char[] split = { ‘\n‘, ‘\r‘ };
string[] inputReference = TestCase.Properties.Resources.tinyUF.Split(split, StringSplitOptions.RemoveEmptyEntries);
string[] inputWorst = TestCase.Properties.Resources.worstUF.Split(split, StringSplitOptions.RemoveEmptyEntries);
RunTest(inputReference);
Console.WriteLine("-------------------------------------");
RunTest(inputWorst);
}
static void RunTest(string[] input)
{
var weightedQuickUnion = new WeightedQuickUnionUF(10);
int n = int.Parse(input[0]);
int[] parent = weightedQuickUnion.GetParent();
int[] size = weightedQuickUnion.GetSize();
for (int i = 1; i < input.Length; ++i)
{
string[] unit = input[i].Split(‘ ‘);
int p = int.Parse(unit[0]);
int q = int.Parse(unit[1]);
Console.WriteLine($"{p} {q}");
weightedQuickUnion.Union(p, q);
Console.Write("index:\t");
for (int j = 0; j < 10; ++j)
{
Console.Write(j + " ");
}
Console.WriteLine();
Console.Write("parent:\t");
foreach (int m in parent)
{
Console.Write(m + " ");
}
Console.WriteLine();
Console.Write("size:\t");
foreach (int m in size)
{
Console.Write(m + " ");
}
Console.WriteLine();
Console.WriteLine("parent visit count:" + weightedQuickUnion.ArrayParentVisitCount);
Console.WriteLine("size visit count:" + weightedQuickUnion.ArraySizeVisitCount);
Console.WriteLine();
weightedQuickUnion.ResetArrayCount();
}
}
}
}
1.5.5题目在一台每秒能够处理 10^9 条指令的计算机上，估计 quick-find 算法解决含有 10^9 个触点和 10^6 条连接的动态连通性问题所需的最短时间（以天记）。假设内循环 for 的每一次迭代需要执行 10 条机器指令。解答106 条连接 = 106 组输入。
对于 quick-find 算法，每次 union() 都要遍历整个数组。
因此总共进行了 109 * 106 = 1015 次 for 循环迭代。
每次 for 循环迭代都需要 10 条机器指令，
因此总共执行了 10 * 1015 = 1016 条机器指令。
已知计算机每秒能够执行 109 条机器指令，
因此执行完所有指令需要 1016 / 109 = 107 秒 = 115.74 天
1.5.6题目使用加权 quick-union 算法完成练习 1.5.5 。解答加权 quick-union 算法最多只需要 lgN 次迭代就可以完成一次 union()。因此按照上题思路，总共需要 (lg(109) * 106 * 10) / 109 = 0.299 秒。
1.5.7题目分别为 quick-find 算法和 quick-union 算法实现 QuickFindUF 类和 QuickUnionUF 类。解答见 1.5.1 和 1.5.2 的解答。
1.5.8题目用一个反例证明 quick-find 算法中的 union() 方法的以下直观实现是错误的：public void union(int p, int q)
{
if (connected(p, q)) return;
for (int I = 0; I < id.length; I++)
{
if (id[i] == id[p]) id[i] = id[q];
}
count--;
}解答当有多个元素需要修改的时候，这个直观算法可能会出现错误。
例如如下情况：
index 0 1 2 3 4 5 6 7 8 9
id 0 0 0 0 0 5 5 5 5 5
输入 0, 5
i = 0 时，id[i] == id[p]，此时 id[i] = id[q]。
数组变为 5 0 0 0 0 5 5 5 5 5
i = 1 时，id[i] != id[p]，算法出现错误。如果在 id[p] 之后还有需要修改的元素，那么这个算法就会出现错误。
1.5.9题目画出下面的 id[] 数组所对应的树。这可能是加权 quick-union 算法得到的结果吗？解释为什么不可能，或者给出能够得到该数组的一系列操作。 i 0 1 2 3 4 5 6 7 8 9
------------------------------------------------------------------------------------------------
id[i] 1 1 3 1 5 6 1 3 4 5解答不可能。
树如下所示。
由于加权 quick-union 算法任意节点的最大深度为 lgN （节点总数为 N）。 （这个结论可以在中文版 P146，或者英文版 P228 找到） 上面这个树的最大深度为 4 > lg10因此这棵树不可能是通过加权 quick-union 算法得到的。
1.5.10题目在加权 quick-union 算法中，假设我们将 id[find(p)] 的值设为 q 而非 id[find[q]]，所得的算法是正确的吗？答：是，但这会增加树的高度，因此无法保证同样的性能。解答本题答案已经给出，也很好理解。如果合并时只是把子树挂到结点 q 上而非其根节点，树的高度会明显增加，进而增加每次 Find() 操作的开销。
1.5.11题目实现加权 quick-find 算法，其中我们总是将较小的分量重命名为较大分量的标识符。这种改变会对性能产生怎样的影响？解答类似于加权 quick-union 的做法，新增一个 size[] 数组以记录各个根节点的大小。每次合并时先比较一下两棵树的大小，再进行合并。这样会略微减少赋值语句的执行次数，提升性能。代码WeightedQuickFindUF.csusing System;
namespace _1._5._11
{
///
public class WeightedQuickFindUF
{
private int[] size; // 记录每个连通分量的大小。
private int[] id; // 记录每个结点的连通分量。
private int count;// 连通分量总数。
public int ArrayVisitCount { get; private set; } //记录数组访问的次数。
///
///
并查集的大小。
public WeightedQuickFindUF(int n)
{
this.count = n;
this.id = new int[n];
this.size = new int[n];
for (int i = 0; i < n; ++i)
{
this.id[i] = i;
this.size[i] = 1;
}
}
///
public void ResetArrayCount()
{
this.ArrayVisitCount = 0;
}
///
///
public int Count()
{
return this.count;
}
///
///
需要寻找的结点。
///
public int Find(int p)
{
Validate(p);
this.ArrayVisitCount++;
return this.id[p];
}
///
///
需要判断的结点。
///
需要判断的另一个结点。
///
public bool IsConnected(int p, int q)
{
Validate(p);
Validate(q);
this.ArrayVisitCount += 2;
return this.id[p] == this.id[q];
}
///
///
需要合并的结点。
///
需要合并的另一个结点。
public void Union(int p, int q)
{
Validate(p);
Validate(q);
int pID = this.id[p];
int qID = this.id[q];
this.ArrayVisitCount += 2;
// 如果两个结点同属于一个连通分量，那么什么也不做。
if (pID == qID)
{
return;
}
// 判断较大的连通分量和较小的连通分量。
int larger = 0;
int smaller = 0;
if (this.size[pID] > this.size[qID])
{
larger = pID;
smaller = qID;
this.size[pID] += this.size[qID];
}
else
{
larger = qID;
smaller = pID;
this.size[qID] += this.size[pID];
}
// 将较小的连通分量连接到较大的连通分量上，
// 这会减少赋值语句的执行次数，略微减少数组访问。
for (int i = 0; i < this.id.Length; ++i)
{
if (this.id[i] == smaller)
{
this.id[i] = larger;
this.ArrayVisitCount++;
}
}
this.ArrayVisitCount += this.id.Length;
this.count--;
return;
}
///
///
public int[] GetID()
{
return this.id;
}
///
///
需要验证的结点。
///
private void Validate(int p)
{
int n = this.id.Length;
if (p < 0 || p > n)
{
throw new ArgumentException("index " + p + " is not between 0 and " + (n - 1));
}
}
}
}Main 方法using System;
using UnionFind;
namespace _1._5._11
{
/*
* 1.5.11
*
* 实现加权 quick-find 算法，其中我们总是将较小的分量重命名为较大分量的标识符。
* 这种改变会对性能产生怎样的影响？
*
*/
class Program
{
static void Main(string[] args)
{
char[] split = { ‘\n‘, ‘\r‘ };
string[] input = TestCase.Properties.Resources.mediumUF.Split(split, StringSplitOptions.RemoveEmptyEntries);
int size = int.Parse(input[0]);
QuickFindUF quickFind = new QuickFindUF(size);
WeightedQuickFindUF weightedQuickFind = new WeightedQuickFindUF(size);
int p, q;
string[] pair;
for (int i = 1; i < size; ++i)
{
pair = input[i].Split(‘ ‘);
p = int.Parse(pair[0]);
q = int.Parse(pair[1]);
quickFind.Union(p, q);
weightedQuickFind.Union(p, q);
}
Console.WriteLine("quick-find: " + quickFind.ArrayVisitCount);
Console.WriteLine("weighted quick-find: " + weightedQuickFind.ArrayVisitCount);
}
}
}
1.5.12题目使用路径压缩的 quick-union 算法。根据路径压缩修改 quick-union 算法（请见 1.5.2.3 节），在 find() 方法中添加一个循环来将从 p 到根节点的路径上的每个触点都连接到根节点。给出一列输入，使该方法能够产生一条长度为 4 的路径。注意：该算法的所有操作的均摊成本已知为对数级别。解答QuickUnionPathCompression 的官方实现：QuickUnionPathCompressionUF.java在找到根节点之后，再访问一遍 p 到根节点这条路径上的所有结点，将它们直接和根节点相连。重写过后的 Find() 方法：///
///
需要寻找的结点。
///
public override int Find(int p)
{
int root = p;
while (root != this.parent[root])
{
root = this.parent[root];
}
while (p != root)
{
int newp = this.parent[p];
this.parent[p] = root;
p = newp;
}
return p;
}由于路径压缩是在 Find() 方法中实现的，只要输入保证是根节点两两相连即可构造较长的路径。代码QuickUnionPathCompressionUF.cs 直接从 QuickUnionUF.cs 继承而来。关于 QuickUnionUF.cs，参见 1.5.2 的解答。namespace UnionFind
{
///
public class QuickUnionPathCompressionUF : QuickFindUF
{
///
///
新建并查集的大小。
public QuickUnionPathCompressionUF(int n) : base(n) { }
///
///
需要寻找的结点。
///
public override int Find(int p)
{
int root = p;
while (root != this.parent[root])
{
root = this.parent[root];
}
while (p != root)
{
int newp = this.parent[p];
this.parent[p] = root;
p = newp;
}
return p;
}
}
}Main 方法using System;
using UnionFind;
namespace _1._5._12
{
/*
* 1.5.12
*
* 使用路径压缩的 quick-union 算法。
* 根据路径压缩修改 quick-union 算法（请见 1.5.2.3 节），
* 在 find() 方法中添加一个循环来将从 p 到根节点的路径上的每个触点都连接到根节点。
* 给出一列输入，使该方法能够产生一条长度为 4 的路径。
* 注意：该算法的所有操作的均摊成本已知为对数级别。
*
*/
class Program
{
static void Main(string[] args)
{
var UF = new QuickUnionPathCompressionUF(10);
// 使用书中提到的最坏情况，0 连 1，1 连 2，2 连 3……
for (int i = 0; i < 4; ++i)
{
UF.Union(i, i + 1);
}
int[] id = UF.GetParent();
for (int i = 0; i < id.Length; ++i)
{
Console.Write(id[i]);
}
Console.WriteLine();
}
}
}
1.5.13题目使用路径压缩的加权 quick-union 算法。修改加权 quick-union 算法（算法 1.5），实现如练习 1.5.12 所述的路径压缩。给出一列输入，使该方法能产生一棵高度为 4 的树。注意：该算法的所有操作的均摊成本已知被限制在反 Ackermann 函数的范围之内，且对于实际应用中可能出现的所有 N 值均小于 5。解答官方实现：WeightedQuickUnionPathCompressionUF。加权 quick-union 中，两个大小相等的树合并可以有效增加高度，同时输入必须保证是根节点以规避路径压缩。代码WeightedQuickUnionPathCompressionUF.cs 从 WeightedQuickUnionUF.cs 继承，详情参见 1.5.3 的解答。namespace UnionFind
{
///
public class WeightedQuickUnionPathCompressionUF : WeightedQuickUnionUF
{
///
///
新建并查集的大小。
public WeightedQuickUnionPathCompressionUF(int n) : base(n)
{
this.size = new int[n];
for (int i = 0; i < n; ++i)
{
this.size[i] = 1;
}
}
///
///
需要寻找的结点。
///
public override int Find(int p)
{
Validate(p);
int root = p;
while (root != this.parent[p])
{
root = this.parent[p];
}
while (p != root)
{
int newP = this.parent[p];
this.parent[p] = root;
p = newP;
}
return root;
}
}
}Main 方法using System;
using UnionFind;
namespace _1._5._13
{
/*
* 1.5.13
*
* 使用路径压缩的加权 quick-union 算法。
* 修改加权 quick-union 算法（算法 1.5），
* 实现如练习 1.5.12 所述的路径压缩。给出一列输入，
* 使该方法能产生一棵高度为 4 的树。
* 注意：该算法的所有操作的均摊成本已知被限制在反 Ackermann 函数的范围之内，
* 且对于实际应用中可能出现的所有 N 值均小于 5。
*
*/
class Program
{
static void Main(string[] args)
{
var UF = new WeightedQuickUnionPathCompressionUF(10);
// 见中文版 P146 或英文版 P229 中加权 quick-union 的最坏输入。
UF.Union(0, 1);
UF.Union(2, 3);
UF.Union(4, 5);
UF.Union(6, 7);
UF.Union(0, 2);
UF.Union(4, 6);
UF.Union(0, 4);
int[] id = UF.GetParent();
for (int i = 0; i < id.Length; ++i)
{
Console.Write(id[i]);
}
Console.WriteLine();
}
}
}
1.5.14题目根据高度加权的 quick-union 算法。给出 UF 的一个实现，使用和加权 quick-union 算法相同的策略，但记录的是树的高度并总是将较矮的树连接到较高的树上。用算法证明 N 个触点的树的高度不会超过其大小的对数级别。解答WeightedQuickUnionByHeight 的官方实现：WeightedQuickUnionByHeightUF.java。证明：
一次 Union 操作只可能发生如下两种情况。
1.两棵树的高度相同，这样合并后的新树的高度等于较大那棵树的高度 + 1。
2.两棵树的高度不同，这样合并后的新树高度等于较大那棵树的高度。
现在证明通过加权 quick-union 算法构造的高度为 h 的树至少包含 2h 个结点。
基础情况，高度 h = 0, 结点数 k = 1。
为了使高度增加，必须用一棵高度相同的树合并，而 h = 0 时结点数一定是 1，则：
h = 1, k = 2
由于两棵大小不同的树合并，最大高度不会增加，只会增加结点数。因此，每次都使用相同高度的最小树进行合并，有：
h = 2, k = 4
h = 3, k = 8
h = 4, k = 16
......
递推即可得到结论，k ≥ 2h
因此 h <= lgk
代码namespace UnionFind
{
public class WeightedQuickUnionByHeightUF : QuickUnionUF
{
private int[] height;
///
///
新建并查集的大小。
public WeightedQuickUnionByHeightUF(int n) : base(n)
{
this.height = new int[n];
for (int i = 0; i < n; ++i)
{
this.height[i] = 0;
}
}
///
///
需要合并的结点。
///
需要合并的另一个结点。
public override void Union(int p, int q)
{
int rootP = Find(p);
int rootQ = Find(q);
if (rootP == rootQ)
{
return;
}
if (this.height[rootP] < this.height[rootQ])
{
this.parent[rootP] = rootQ;
}
else if (this.height[rootP] > this.height[rootQ])
{
this.parent[rootQ] = rootP;
}
else
{
this.parent[rootQ] = rootP;
this.height[rootP]++;
}
this.count--;
}
}
}
1.5.15题目二项树。请证明，对于加权 quick-union 算法，在最坏情况下树中的每一层的结点数均为二项式系数。在这种情况下，计算含有 N=2^n 个节点的树中节点的平均深度。解答首先证明在最坏情况下加权 quick-union 算法生成的树中的每一层结点数均为二项式系数。最坏情况下，每次 union 操作都是合并相同大小的树，如下图所示：设第 i 层的结点数为 ki，那么最坏情况下每次合并后的 ki’ = ki + ki-1 。这符合二项式系数的构造特点（详情可以搜索杨辉三角），第一个结论证明完毕。接下来求平均深度，首先根据二项式的求和公式，一棵深度为 n 的树（根结点的深度为零）结点总数为：每层结点数 × 该层深度后的和为：这里用到了这个公式化简：相除可以求得平均深度：
1.5.16题目均摊成本的图像。修改你为练习 1.5.7 给出的实现，绘出如正文所示的均摊成本的图像。解答给出绘图结果样例：代码仅给出绘图相关的代码，窗体部分见 github 上的代码：using System;
using System.Linq;
using System.Windows.Forms;
using System.Drawing;
using UnionFind;
namespace _1._5._16
{
/*
* 1.5.16
*
* 均摊成本的图像。
* 修改你为练习 1.5.7 给出的实现，
* 绘出如正文所示的均摊成本的图像。
*
*/
static class Program
{
[STAThread]
static void Main()
{
Application.EnableVisualStyles();
Application.SetCompatibleTextRenderingDefault(false);
Compute();
Application.Run(new Form1());
}
static void Compute()
{
char[] split = { ‘\n‘, ‘\r‘ };
string[] input = TestCase.Properties.Resources.mediumUF.Split(split, StringSplitOptions.RemoveEmptyEntries);
int size = int.Parse(input[0]);
QuickFindUF quickFind = new QuickFindUF(size);
QuickUnionUF quickUnion = new QuickUnionUF(size);
string[] pair;
int p, q;
int[] quickFindResult = new int[size];
int[] quickUnionResult = new int[size];
for (int i = 1; i < size; ++i)
{
pair = input[i].Split(‘ ‘);
p = int.Parse(pair[0]);
q = int.Parse(pair[1]);
quickFind.Union(p, q);
quickUnion.Union(p, q);
quickF
本文由职坐标整理并发布，希望对同学们有所帮助。了解更多详情请关注职坐标编程语言C#.NET频道！
喜欢 | 0
不喜欢 | 0
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了，明天再试试吧！
我们会在第一时间安排职业规划师联系您！
您也可以联系我们的职业规划师咨询：
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com，All Rights Reserved.
沪公网安备 31011502005948号
索取资料
答疑解惑
技术交流
职业测评
面试技巧
高薪秘笈
