写在前面
整个项目都托管在了 Github 上：
这一节内容可能会用到的库文件有 Measurement 和 TestCase，同样在 Github 上可以找到。
善用 Ctrl + F 查找题目。
习题&题解
1.4.1
解答
即为证明组合计算公式：
C(N, 3)
= N! / [(N - 3)! × 3!]
= [(N - 2) * (N - 1) * N] / 3!= N(N - 1)(N - 2) / 6显然 N 必须大于等于 3。
N = 3 时公式正确，只有一种组合。N = 4 时公式正确，只有四种组合。 扩展到 N+1 个数，将 N = N + 1 代入，可得：(N + 1)N(N - 1) / 6N + 1 个数能组成的三位数组合可以这样理解前 N 个数中取三个数的所有组合 +多出的一个数和前 N 个数中的任意取两个数的所有组合即为 N(N-1)(N - 2) / 6 + C(N, 2)变形后即为(N + 1)N(N - 1) / 6得证。
1.4.2
解答
将 a[i] + a[j] + a[k] 改为 (long)a[i] + a[j] + a[k] 即可。
此时整个式子将按照精度最高（也就是 long）的标准计算。
long.MaxValue = 9223372036854775807 > int.MaxValue * 3 = 6442450941
代码
namespace Measurement{ /// /// 用暴力方法寻找数组中和为零的三元组。 /// public static class ThreeSum { /// /// 输出所有和为零的三元组。 /// /// 输入数组。 public static void PrintAll(int[] a) { int n = a.Length; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { for (int k = j + 1; k < n; ++k) { if ((long)a[i] + a[j] + a[k] == 0) { Console.WriteLine($"{a[i]} + {a[j]} + {a[k]}"); } } } } } /// /// 计算和为零的三元组的数量。 /// /// 输入数组。 /// 1.4.3
解答
见代码，这里贴出绘图函数，窗体只是在得到测试结果之后简单调用以下这两个函数。
代码
public static void PaintLinear(double[] testResult) { //新建一个绘图窗口 Form2 linear = new Form2(); linear.Show(); //新建画布 Graphics canvas = linear.CreateGraphics(); //获取窗口区域 Rectangle rect = linear.ClientRectangle; //计算单位长度（十等分） int unitY = rect.Height / 10; int unitX = rect.Width / 10; //获取中心区域（上下左右增加 10% 的内补） Rectangle center = new Rectangle(rect.X + unitX, rect.Y + unitY, unitX * 8, unitY * 8); //绘制坐标系 canvas.DrawLine(Pens.Black, center.X, center.Y, center.X, center.Y + center.Height); canvas.DrawLine(Pens.Black, center.X, center.Y + center.Height, center.X + center.Width, center.Y + center.Height); //对 X 轴 10 等分，对 Y 轴 10 等分 int xaxisUnit = center.Width / 10; int yaxisUnit = center.Height / 10; //标记 X 轴坐标值 for (int i = 1; i <= 8; i += i) { canvas.DrawString(i + "N", linear.Font, Brushes.Black, center.X + i * xaxisUnit, center.Y + center.Height); } //反转坐标系 canvas.TranslateTransform(0, linear.ClientRectangle.Height); canvas.ScaleTransform(1, -1); //计算单位长度 double Unit = center.Height / testResult[3]; //标记 PointF[] result = new PointF[4]; for (int i = 0, j = 1; i < 4 && j <= 8; ++i, j += j) { result[i] = new PointF(center.X + j * xaxisUnit, (float)(center.Y + Unit * testResult[i])); } //链接 canvas.DrawLines(Pens.Black, result); canvas.Dispose(); } public static void PaintLogarithm(double[] testResult) { //新建一个绘图窗口 Form2 log = new Form2(); log.Show(); //新建画布 Graphics canvas = log.CreateGraphics(); //获取窗口区域 Rectangle rect = log.ClientRectangle; //计算单位长度（十等分） int unitY = rect.Height / 10; int unitX = rect.Width / 10; //获取中心区域（上下左右增加 10% 的内补） Rectangle center = new Rectangle(rect.X + unitX, rect.Y + unitY, unitX * 8, unitY * 8); //绘制坐标系 canvas.DrawLine(Pens.Black, center.X, center.Y, center.X, center.Y + center.Height); canvas.DrawLine(Pens.Black, center.X, center.Y + center.Height, center.X + center.Width, center.Y + center.Height); //对 X 轴 10 等分，对 Y 轴 10 等分 int xaxisUnit = center.Width / 10; int yaxisUnit = center.Height / 10; //标记 X 轴坐标值 for (int i = 1; i <= 8; i += i) { canvas.DrawString(i + "N", log.Font, Brushes.Black, center.X + i * xaxisUnit, center.Y + center.Height); } //反转坐标系 canvas.TranslateTransform(0, log.ClientRectangle.Height); canvas.ScaleTransform(1, -1); //计算单位长度 double Unit = center.Height / testResult[3]; //标记 PointF[] result = new PointF[4]; for (int i = 0, j = 1; i < 4 && j <= 8; ++i, j += j) { result[i] = new PointF(center.X + j * xaxisUnit, (float)(center.Y + Unit * testResult[i])); } //链接 canvas.DrawLines(Pens.Black, result); canvas.Dispose(); } 1.4.4
解答
代码分块↑
时间分析↓
1.4.5
解答
类似于取极限的做法。
a. N
b. 1
c. 1
d. 2N3
e. 1
f. 2
g. N100
1.4.6
解答
a. N + N/2 + N/4 + … = ~2N，线性。
b. 1 + 2 + 4 + … = ~2N，线性。
c. logN * N，线性对数。
1.4.7
解答
最外层循环进行了 N 次比较。
次外层循环进行了 N^2 次比较。
最里层循环进行了 N^3 次比较。
内部 if 语句进行了 N^3 次比较。
if 内部进行了 N(N-1) 次加法。
加起来，~2N^3。
1.4.8
解答
平方级别：直接二层循环遍历一遍。
线性对数：只遍历一遍数组，在遍历过程中用二分查找确认在剩余数组中是否有相等的整数。
代码
////// 暴力查找数组中相等的整数对。/// /// 需要查找的数组。///static int CountEqual(int[] a){ int n = a.Length; int count = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (a[i] == a[j]) count++; } } return count;}
暴力算法↑
二分查找算法↓
////// 利用 Array.Sort 进行优化的查找相等整数对算法。/// /// 需要查找的数组。///static int CountEqualLog(int[] a){ int n = a.Length; int count = 0; Array.Sort(a); int dup = 0; // dup = 重复元素数量-1 for (int i = 1; i < n; i++) { while (a[i - 1] == a[i]) { dup++; i++; } count += dup * (dup + 1) / 2; dup = 0; } return count;}
1.4.9
解答
1.4.10
解答
修改二分查找的结束条件，找到后仍然向左侧寻找，如果还能找到更小的，则返回较小的下标；否则返回当前下标。
代码
namespace _1._4._10{ /// /// 二分查找。 /// public class BinarySearch { /// /// 用递归方法进行二分查找。 /// /// 关键字。 /// 查找范围。 /// 查找的起始下标。 /// 查找的结束下标。 /// 返回下标，如果没有找到则返回 -1。 public static int Rank(int key, int[] a, int lo, int hi) { if (hi < lo) return -1; int mid = (hi - lo) / 2 + lo; if (a[mid] == key) { int mini = Rank(key, a, lo, mid - 1); if (mini != -1) return mini; return mid; } else if (a[mid] < key) { return Rank(key, a, mid + 1, hi); } else { return Rank(key, a, lo, mid - 1); } } }} 1.4.11
解答
这里给出官网上的 Java 实现：。
howMany() 可以用二分查找实现，在找到一个值后继续向两侧查找，最后返回找到的次数。
代码
using System;namespace Measurement{ /// /// 有序数组，能够快速查找并自动维护其中的顺序。 /// public class StaticSETofInts { private int[] a; /// /// 用一个数组初始化有序数组。 /// /// 源数组。 public StaticSETofInts(int[] keys) { this.a = new int[keys.Length]; for (int i = 0; i < keys.Length; ++i) { this.a[i] = keys[i]; } Array.Sort(this.a); } /// /// 检查数组中是否存在指定元素。 /// /// 要查找的值。 /// 存在则返回 true，否则返回 false。 public bool Contains(int key) { return Rank(key, 0, this.a.Length - 1) != -1; } /// /// 返回某个元素在数组中存在的数量。 /// /// 关键值。 /// 返回某个元素在数组中存在的数量。 public int HowMany(int key) { int hi = this.a.Length - 1; int lo = 0; return HowMany(key, lo, hi); } /// /// 返回某个元素在数组中存在的数量。 /// /// 关键值。 /// 查找起始下标。 /// 查找结束下标。 /// 返回某个元素在数组中存在的数量。 private int HowMany(int key, int lo, int hi) { int mid = Rank(key, lo, hi); if (mid == -1) return 0; else { return 1 + HowMany(key, lo, mid - 1) + HowMany(key, mid + 1, hi); } } /// /// 二分查找。 /// /// 关键值。 /// 查找的起始下标。 /// 查找的结束下标。 /// 返回关键值的下标，如果不存在则返回 -1。 public int Rank(int key, int lo, int hi) { while (lo <= hi) { int mid = (hi - lo) / 2 + lo; if (key < this.a[mid]) hi = mid - 1; else if (key > this.a[mid]) lo = mid + 1; else return mid; } return -1; } }}
1.4.12
解答
由于两个数组都是有序的，可以同时进行比较。
设 i, j 分别为两个数组的下标。
如果 a[i] == a[j]，i 和 j 都向后移动一位。如果 a[i] != a[j]，比较小的那个向后移动一位。循环直到某个数组遍历完毕。这样最后的时间复杂度 ~2N
代码
using System;namespace _1._4._12{ /* * 1.4.12 * * 编写一个程序，有序打印给定的两个有序数组（含有 N 个 int 值） 中的所有公共元素， * 程序在最坏情况下所需的运行时间应该和 N 成正比。 * */ class Program { static void Main(string[] args) { int[] a = new int[4] { 2, 3, 4, 10 }; int[] b = new int[6] { 1, 3, 3, 5, 10, 11 }; //2N 次数组访问，数组 a 和数组 b 各遍历一遍 for (int i = 0, j = 0; i < a.Length && j < b.Length; ) { if (a[i] < b[j]) { i++; } else if (a[i] > b[j]) { j++; } else { Console.WriteLine($"Common Element:{a[i]}, First index: (a[{i}], b[{j}])"); i++; j++; } } } }}
1.4.13
解答
对象的固定开销用 Object 表示。
a. Accumulator
使用 1.2.4.3 节给出的实现。
= int * 1 + double + Object * 1= 4 * 1 + 8 + 16 * 1 = 32
b. Transaction
= string * 1 + Date * 1 + double * 1 + Object * 1
= (40 + 16 + 4 + 4 + 2N) * 1 + (8 + 32) * 1 + 8 * 1 + 16 * 1
= 128 + 2N
c. FixedCapacityStackOfStrings
= string[] * 1 + string * N + int * 1 + Object * 1
= 24 * 1 + N * (64 + 2C) + 4 * 1 + 16 * 1
= N * (64 + 2C) + 44
= N * (64 + 2C) + 48（填充）
d.Point2D
= double * 2 + Object * 1
= 8 * 2 + 16 * 1
= 32
e.Interval1D
= double * 2 + Object * 1
= 8 * 2 + 16 * 1
= 32
f.Interval2D
= Interval1D * 2 + Object * 1
= (8 + 24) * 2 + 16 * 1
= 80
g.Double
= double * 1 + Object * 1
= 8 * 1 + 16 * 1
= 24
1.4.14
解答
这里给出暴力方法，将最内侧循环换成二分查找即为优化版本。
代码
using System;namespace Measurement{ /// /// 用暴力方法查找数组中和为零的四元组。 /// public static class FourSum { /// /// 输出数组中所有和为 0 的四元组。 /// /// 包含所有元素的数组。 public static void PrintAll(long[] a) { int N = a.Length; for (int i = 0; i < N; ++i) { for (int j = i + 1; j < N; ++j) { for (int k = j + 1; k < N; ++k) { for (int l = k + 1; l < N; ++l) { if (a[i] + a[j] + a[k] + a[l] == 0) { Console.WriteLine($"{a[i]} + {a[j]} + {a[k]} + {a[l]} = 0"); } } } } } } /// /// 计算和为零的四元组的数量。 /// /// 包含所有元素的数组。 ///
1.4.15
解答
由于数组已经排序（从小到大），负数在左侧，正数在右侧。
TwoSumFaster 设最左侧下标为 lo，最右侧下标为 hi。 如果 a[lo] + a[hi] > 0, 说明正数太大，hi--。 如果 a[lo] + a[hi] < 0，说明负数太小，lo++。 否则就找到了一对和为零的整数对，lo++, hi--。ThreeSumFaster
对于数组中的每一个数 a，ThreeSum 问题就等于求剩余数组中所有和为 -a 的 TwoSum 问题。 只要在 TwoSumFaster 外层再套一个循环即可。代码
////// TwoSum 的快速实现。（线性级别） /// /// 需要查找的数组范围。 ///数组中和为零的整数对数量。 static int TwoSumFaster(int[] a) { int lo = 0; int hi = a.Length - 1; int count = 0; while (lo < hi) { if (a[lo] + a[hi] == 0) { count++; lo++; hi--; } else if (a[lo] + a[hi] < 0) { lo++; } else { hi--; } } return count; } ////// ThreeSum 的快速实现。（平方级别） /// /// 需要查找的数组范围。 ///数组中和为零的三元组数量。 static int ThreeSumFaster(int[] a) { int count = 0; for (int i = 0; i < a.Length; ++i) { int lo = i + 1; int hi = a.Length - 1; while (lo <= hi) { if (a[lo] + a[hi] + a[i] == 0) { count++; lo++; hi--; } else if (a[lo] + a[hi] + a[i] < 0) { lo++; } else { hi--; } } } return count; }
1.4.16
解答
先将数组从小到大排序，再遍历一遍即可得到差距最小的两个数。
排序算法需要消耗 NlogN，具体见 MSDN：。
代码
using System;namespace _1._4._16{ /* * 1.4.16 * * 最接近一对（一维）。 * 编写一个程序，给定一个含有 N 个 double 值的数组 a[]， * 在其中找到一对最接近的值：两者之差（绝对值）最小的两个数。 * 程序在最坏情况下所需的运行时间应该是线性对数级别的。 * */ class Program { //总运行时间： NlogN + N = NlogN static void Main(string[] args) { double[] a = new double[5] { 0.1, 0.3, 0.6, 0.8, 0 }; Array.Sort(a);//Nlog(N) 具体见 https://msdn.microsoft.com/zh-cn/library/6tf1f0bc(v=vs.110).aspx 备注部分 double minDiff = double.MaxValue; double minA = 0; double minB = 0; for (int i = 0; i < a.Length - 1; ++i)//N { if (a[i + 1] - a[i] < minDiff) { minA = a[i]; minB = a[i + 1]; minDiff = a[i + 1] - a[i]; } } Console.WriteLine($"Min Pair: {minA} {minB}, Min Value: {minDiff}"); } }}
1.4.17
解答
遍历找到最小值和最大值即可。
代码
using System;namespace _1._4._17{ /* * 1.4.17 * * 最遥远的一对（一维）。 * 编写一个程序，给定一个含有 N 个 double 值的数组 a[]， * 在其中找到一对最遥远的值：两者之差（绝对值）最大的两个数。 * 程序在最坏情况下所需的运行时间应该是线性级别的。 * */ class Program { static void Main(string[] args) { double[] a = new double[5] { 0.1, 0.3, 0.6, 0.8, 0 }; double min = int.MaxValue; double max = int.MinValue; for (int i = 0; i < a.Length; ++i) { if (a[i] > max) { max = a[i]; } if (a[i] < min) { min = a[i]; } } Console.WriteLine($"MaxDiff Pair: {min} {max}, Max Difference: {Math.Abs(max - min)}"); } }}
1.4.18
解答
和二分查找的方式类似，先确认中间的值是否是局部最小，如果不是，则向较小的一侧二分查找。
代码
using System;namespace _1._4._18{ class Program { static void Main(string[] args) { var a = new int[5] { 1, 2, 5, 3, 5 }; Console.WriteLine(LocalMinimum(a)); } /// /// 寻找数组的局部最小元素。 /// /// 寻找范围。 /// 局部最小元素的值。 static int LocalMinimum(int[] a) { int lo = 0; int hi = a.Length - 1; while (lo <= hi) { int mid = (hi - lo) / 2 + lo; int min = mid; // 取左中右最小值的下标 if (mid != hi && a[min] >= a[mid + 1]) min = mid + 1; if (mid != lo && a[min] >= a[mid - 1]) min = mid - 1; if (min == mid) return mid; if (min > mid) lo = min; else hi = min; } return -1; } }} 1.4.19
解答
算法过程类似于 “滑雪”，从数值较高的一侧向周围数值较小的一侧移动，直到到达“山谷”（局部最小）。
首先在中间行搜索最小值，再将最小值与其上下两个元素比较，如果不满足题意，则“滑向”较小的一侧，矩阵被分为了两半（上下两侧）。
在较小的一侧，找到中间列的最小值，再将最小值与其左右两个元素比较，如果不满足题意，类似的移动到较小的一侧（左右两侧）。
现在查找范围缩小到了原来矩阵的四分之一，递归的进行上述操作，最后可以得到答案。
每次查找最小值都是对行/列进行遍历，遍历耗时和 N 成正比。
代码
using System;namespace _1._4._19{ /* * 1.4.19 * * 矩阵的局部最小元素。 * 给定一个含有 N^2 个不同整数的 N×N 数组 a[]。 * 设计一个运行时间和 N 成正比的算法来找出一个局部最小元素： * 满足 a[i][j] < a[i+1][j]、a[i][j] < a[i][j+1]、a[i][j] < a[i-1][j] 以及 a[i][j] < a[i][j-1] 的索引 i 和 j。 * 程序运行时间在最坏情况下应该和 N 成正比。 * */ class Program { // 先查找 N/2 行中的最小元素，并令其与上下元素比较， // 如果不满足题意，则向相邻的最小元素靠近再次查找 static void Main(string[] args) { int[,] matrix = new int[5, 5] { { 26, 3, 4 , 10, 11 }, { 5, 1, 6, 12, 13 }, { 7, 8, 9 , 14, 15 }, { 16, 17, 18, 27, 20 }, { 21, 22, 23, 24, 25 } }; Console.WriteLine(MinimumRow(matrix, 0, 5, 0, 5)); } /// /// 在矩阵中间行查找局部最小。 /// /// 矩阵。 /// 实际查找范围的行起始。 /// 实际查找范围的行结尾。 /// 实际查找范围的列起始。 /// 实际查找范围的列结尾。 /// 矩阵中的局部最小元素。 static int MinimumRow(int[,] matrix, int rowStart, int rowLength, int colStart, int colLength) { int min = int.MaxValue; if (rowLength < 3) return int.MaxValue; int mid = rowStart + rowLength / 2; int minCol = 0; // 获取矩阵中间行的最小值 for (int i = 0; i < colLength; ++i) { if (min > matrix[mid, colStart + i]) { min = matrix[mid, colStart + i]; minCol = i; } } // 检查是否满足条件 if (matrix[mid, minCol] < matrix[mid - 1, minCol] && matrix[mid, minCol] < matrix[mid + 1, minCol]) { return matrix[mid, minCol]; } // 如果不满足则向较小一侧移动 if (matrix[mid - 1, minCol] > matrix[mid + 1, minCol]) { return MinimumCol(matrix, rowStart, rowLength, mid + 1, colLength / 2 + 1); } else { return MinimumCol(matrix, rowStart, rowLength, colStart, colLength / 2 + 1); } } /// /// 在矩阵中间列查找局部最小。 /// /// 矩阵。 /// 实际查找范围的行起始。 /// 实际查找范围的行结尾。 /// 实际查找范围的列起始。 /// 实际查找范围的列结尾。 /// 矩阵中的局部最小元素。 static int MinimumCol(int[,] matrix, int rowStart, int rowLength, int colStart, int colLength) { int min = int.MaxValue; int n = matrix.GetLength(0); int mid = n / 2; int minRow = 0; // 获取矩阵中间列最小值 for (int i = 0; i < n; ++i) { if (min > matrix[i, mid]) { min = matrix[i, mid]; minRow = i; } } // 检查是否满足条件 if (matrix[minRow, mid] < matrix[minRow, mid - 1] && matrix[minRow, mid] < matrix[minRow, mid + 1]) { return matrix[minRow, mid]; } // 如果不满足则向较小一侧移动 if (matrix[minRow, mid - 1] > matrix[minRow, mid + 1]) { return MinimumRow(matrix, mid + 1, rowLength / 2 + 1, colStart, colLength); } else { return MinimumRow(matrix, rowStart, rowLength / 2 + 1, colStart, colLength); } } }} 1.4.20
解答
首先给出 BitMax 类的官方 Java 实现：。
我们使用这个类生成双调数组，并使用其中的 Max() 方法找到双调数组的最大值。
找到最大值之后分别对左右两侧进行二分查找，注意对于升序和降序的数组二分查找的实现有所不同。
代码
BitonicMax 类
using System;namespace _1._4._20{ /// /// 双调查找类。 /// public class BitonicMax { /// /// 生成双调数组。 /// /// 数组的大小。 /// /// 寻找数组中的最大值。 /// /// 查找范围。 /// 查找起始下标。 /// 查找结束下标。 /// 返回数组中最大值的下标。 public static int Max(int[] a, int lo, int hi) { if (lo == hi) { return hi; } int mid = lo + (hi - lo) / 2; if (a[mid] < a[mid + 1]) { return Max(a, mid + 1, hi); } if (a[mid] > a[mid + 1]) { return Max(a, lo, mid); } return mid; } }} 主程序
using System;namespace _1._4._20{ /* * 1.4.20 * * 双调查找。 * 如果一个数组中的所有元素是先递增后递减的，则称这个数组为双调的。 * 编写一个程序，给定一个含有 N 个不同 int 值的双调数组，判断它是否含有给定的整数。 * 程序在最坏情况下所需的比较次数为 ~3lgN * */ class Program { static void Main(string[] args) { int[] a = BitonicMax.Bitonic(100); int max = BitonicMax.Max(a, 0, a.Length - 1); int key = a[50]; int leftside = BinarySearchAscending(a, key, 0, max); int rightside = BinarySearchDescending(a, key, max, a.Length - 1); if (leftside != -1) { Console.WriteLine(leftside); } else if (rightside != -1) { Console.WriteLine(rightside); } else { Console.WriteLine("No Result"); } } /// /// 对升序数组的二分查找。 /// /// 升序数组。 /// 关键值。 /// 查找的左边界。 /// 查找的右边界。 /// 返回找到关键值的下标，如果没有找到则返回 -1。 static int BinarySearchAscending(int[] a, int key, int lo, int hi) { while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (a[mid] < key) { lo = mid + 1; } else if (a[mid] > key) { hi = mid - 1; } else { return mid; } } return -1; } /// /// 对降序数组的二分查找。 /// /// 升序数组。 /// 关键值。 /// 查找的左边界。 /// 查找的右边界。 /// 返回找到关键值的下标，如果没有找到则返回 -1。 static int BinarySearchDescending(int[] a, int key, int lo, int hi) { while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] > key) { lo = mid + 1; } else if (a[mid] < key) { hi = mid - 1; } else { return mid; } } return -1; } }}
1.4.21
解答
直接将 Contains() 实现为二分查找即可。
代码
////// 检查数组中是否存在指定元素。 /// /// 要查找的值。 ///存在则返回 true，否则返回 false。 public bool Contains(int key) { return Rank(key, 0, this.a.Length - 1) != -1; } ////// 二分查找。 /// /// 关键值。 /// 查找的起始下标。 /// 查找的结束下标。 ///返回关键值的下标，如果不存在则返回 -1。 public int Rank(int key, int lo, int hi) { while (lo <= hi) { int mid = (hi - lo) / 2 + lo; if (key < this.a[mid]) hi = mid - 1; else if (key > this.a[mid]) lo = mid + 1; else return mid; } return -1; }
1.4.22
解答
普通二分查找是通过除法不断减半缩小搜索范围。
这里我们用斐波那契数列来缩小范围。
举个例子，例如数组大小是 100，比它大的最小斐波那契数是 144。
斐波那契数列如下：0 1 1 2 3 5 8 13 21 34 55 89 144
我们记 F(n) = 144,F(n-1) = 89, F(n-2) = 55。
我们先查看第 0 + F(n-2) 个数，如果比关键值小则直接将范围缩小到 [55, 100]；否则则在[0, 55]之间查找。
之后我们令 n = n-1。
递归上述过程即可完成查找。
代码
////// 使用斐波那契数列进行的查找。 /// /// 查找范围。 /// 关键字。 ///返回查找到的关键值下标，没有结果则返回 -1。 static int rank(int[] a, int key) { // 使用斐波那契数列作为缩减范围的依据 int Fk = 1; int Fk_1 = 1; int Fk_2 = 0; // 获得 Fk，Fk需要大于等于数组的大小，复杂度 lgN while (Fk < a.Length) { Fk = Fk + Fk_1; Fk_1 = Fk_1 + Fk_2; Fk_2 = Fk - Fk_1; } int lo = 0; // 按照斐波那契数列缩减查找范围，复杂度 lgN while (Fk_2 >= 0) { int i = lo + Fk_2 > a.Length - 1 ? a.Length - 1 : lo + Fk_2; if (a[i] < key) { lo = lo + Fk_2; } else if (a[i] == key) { return i; } Fk = Fk_1; Fk_1 = Fk_2; Fk_2 = Fk - Fk_1; } return -1; }
1.4.23
解答
根据书中的提示，将二分查找中判断相等的条件改为两个数的差小于等于 1/N2。
代码
// 将二分查找中的相等判定条件修改为差值小于 x，其中 x = 1/N^2。 ////// 二分查找。 /// /// 查找范围。 /// 关键字。 ///结果的下标，没有结果时返回 -1。 static int BinarySearch(double[] a, double key) { int lo = 0; int hi = a.Length - 1; double threshold = 1.0 / (a.Length * a.Length); while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (Math.Abs(a[mid] - key) <= threshold) { return mid; } else if (a[mid] < key) { lo = mid + 1; } else { hi = mid - 1; } } return -1; }
1.4.24
解答
第一问：二分查找即可。
第二问：
按照第 1, 2, 4, 8,..., 2^k 层顺序查找，一直到 2^k > F，
随后在 [2^(k - 1), 2^k] 范围中二分查找。代码
这里建立了一个结构体用于返回测试结果：
struct testResult{ public int F;// 找到的 F 值。 public int BrokenEggs;// 打碎的鸡蛋数。} 用于测试的方法：
////// 扔鸡蛋，没碎返回 true，碎了返回 false。 /// /// 扔鸡蛋的高度。 ///static bool ThrowEgg(int floor) { return floor <= F; } /// /// 第一种方案。 /// /// 大楼。 ///static testResult PlanA(int[] a) { int lo = 0; int hi = a.Length - 1; int mid = 0; int eggs = 0; testResult result = new testResult(); while (lo <= hi) { mid = lo + (hi - lo) / 2; if (ThrowEgg(mid)) { lo = mid + 1; } else { eggs++; hi = mid - 1; } } result.BrokenEggs = eggs; result.F = hi; return result; } /// /// 第二种方案。 /// /// 大楼。 ///static testResult PlanB(int[] a) { int lo = 0; int hi = 1; int mid = 0; int eggs = 0; testResult result = new testResult(); while (ThrowEgg(hi)) { lo = hi; hi *= 2; } eggs++; if (hi > a.Length - 1) { hi = a.Length - 1; } while (lo <= hi) { mid = lo + (hi - lo) / 2; if (ThrowEgg(mid)) { lo = mid + 1; } else { eggs++; hi = mid - 1; } } result.BrokenEggs = eggs; result.F = hi; return result; }
1.4.25
解答
第一问：
第一个蛋按照 √(N), 2√(N), 3√(N), 4√(N),..., √(N) * √(N) 顺序查找直至碎掉。这里扔了 k 次，k <= √(N)。
k-1√(N) ~ k√(N) 顺序查找直至碎掉，F 值就找到了。这里最多扔 √(N) 次。第二问：
按照第 1, 3, 6, 10,..., 1/2k^2 层顺序查找，一直到 1/2k^2 > F，
随后在 [1/2k^2 - k, 1/2k^2] 范围中顺序查找。代码
这里我们同样定义了一个结构体：
struct testResult{ public int F;// 测试得出的 F 值 public int BrokenEggs;// 碎掉的鸡蛋数。 public int ThrowTimes;// 扔鸡蛋的次数。} 之后是测试用的方法：
////// 扔鸡蛋，没碎返回 true，碎了返回 false。 /// /// 扔鸡蛋的高度。 ///static bool ThrowEgg(int floor) { return floor <= F; } /// /// 第一种方案。 /// /// 大楼。 ///static testResult PlanA(int[] a) { int lo = 0; int hi = 0; int eggs = 0; int throwTimes = 0; testResult result = new testResult(); while (ThrowEgg(hi)) { throwTimes++; lo = hi; hi += (int)Math.Sqrt(a.Length); } eggs++; if (hi > a.Length - 1) { hi = a.Length - 1; } while (lo <= hi) { if (!ThrowEgg(lo)) { eggs++; break; } throwTimes++; lo++; } result.BrokenEggs = eggs; result.F = lo - 1; result.ThrowTimes = throwTimes; return result; } /// /// 第二种方案。 /// /// 大楼。 ///static testResult PlanB(int[] a) { int lo = 0; int hi = 0; int eggs = 0; int throwTimes = 0; testResult result = new testResult(); for (int i = 0; ThrowEgg(hi); ++i) { throwTimes++; lo = hi; hi += i; } eggs++; if (hi > a.Length - 1) { hi = a.Length - 1; } while (lo <= hi) { if (!ThrowEgg(lo)) { eggs++; break; } lo++; throwTimes++; } result.BrokenEggs = eggs; result.F = lo - 1; result.ThrowTimes = throwTimes; return result; }
1.4.26
解答
1.4.27
解答
实现比较简单，想象两个栈背靠背接在一起，左侧栈负责出队，右侧栈负责入队。
当左侧栈为空时就把右侧栈中的元素倒到左侧栈，这个过程是 O(n) 的。
但在这个过程之前必然有 n 个元素入栈，均摊后即为 O(1)。
代码
namespace _1._4._27{ /// /// 用两个栈模拟的队列。 /// /// 队列中的元素。 class StackQueue - { Stack
- H;//用于保存出队元素 Stack
- T;//用于保存入队元素 ///
/// 构造一个队列。 /// public StackQueue() { this.H = new Stack - (); this.T = new Stack
- (); } ///
/// 将栈 T 中的元素依次弹出并压入栈 H 中。 /// private void Reverse() { while (!this.T.IsEmpty()) { this.H.Push(this.T.Pop()); } } /// /// 将一个元素出队。 /// /// /// 将一个元素入队。 /// /// 要入队的元素。 public void Enqueue(Item item) { this.T.Push(item); } }}
1.4.28
解答
每次入队的时候将队列倒转，这样入队的元素就是第一个了。
代码
namespace _1._4._28{ /// /// 用一条队列模拟的栈。 /// /// 栈中保存的元素。 class QueueStack - { Queue
- queue; ///
/// 初始化一个栈。 /// public QueueStack() { this.queue = new Queue - (); } ///
/// 向栈中添加一个元素。 /// /// public void Push(Item item) { this.queue.Enqueue(item); int size = this.queue.Size(); // 倒转队列 for (int i = 0; i < size - 1; ++i) { this.queue.Enqueue(this.queue.Dequeue()); } } /// /// 从栈中弹出一个元素。 /// /// /// 确定栈是否为空。 /// ///
1.4.29
解答
和用两个栈实现队列的方法类似。
push 的时候把右侧栈内容倒到左侧栈，之后再入栈。
pop 的时候也做相同操作，右侧栈内容进左侧栈，之后再出栈。
enqueue 的时候则将左侧栈内容倒到右侧栈，之后再入队。
代码
namespace _1._4._29{ /// /// 用两个栈模拟的 Steque。 /// /// Steque 中的元素类型。 class StackSteque - { Stack
- H; Stack
- T; ///
/// 初始化一个 Steque /// public StackSteque() { this.H = new Stack - (); this.T = new Stack
- (); } ///
/// 向栈中添加一个元素。 /// /// public void Push(Item item) { ReverseT(); this.H.Push(item); } /// /// 将 T 中的元素弹出并压入到 H 中。 /// private void ReverseT() { while (!this.T.IsEmpty()) { this.H.Push(this.T.Pop()); } } /// /// 将 H 中的元素弹出并压入到 T 中。 /// private void ReverseH() { while (!this.H.IsEmpty()) { this.T.Push(this.H.Pop()); } } /// /// 从 Steque 中弹出一个元素。 /// /// /// 在 Steque 尾部添加一个元素。 /// /// public void Enqueue(Item item) { ReverseH(); this.T.Push(item); } /// /// 检查 Steque 是否为空。 /// ///
1.4.30
解答
steque 作为队列的头部，stack 作为队列的尾部。
pushLeft：直接 push 到 steque 中即可。
pushRight：如果 stack 为空，则直接 enqueue 到 steque 中，否则就 push 到 stack 中。
popLeft：如果 steque 为空，则将 stack 中的元素倒到 steque 中去（steque.push(stack.pop())），然后再从 steque 中 pop。
popRight：如果 stack 为空，则将 steque 中的元素倒到 stack 中去，然后再从 stack 中 pop。
代码
namespace _1._4._30{ /// /// 用一个栈和一个 Steque 模拟的双向队列。 /// /// 双向队列中保存的元素类型。 class Deque - { Stack
- stack;//代表队列尾部 Steque
- steque;//代表队列头部 ///
/// 创建一条空的双向队列。 /// public Deque() { this.stack = new Stack - (); this.steque = new Steque
- (); } ///
/// 在左侧插入一个新元素。 /// /// 要插入的元素。 public void PushLeft(Item item) { this.steque.Push(item); } /// /// 将栈中的内容移动到 Steque 中。 /// private void StackToSteque() { while (!this.stack.IsEmpty()) { this.steque.Push(this.stack.Pop()); } } /// /// 将 Steque 中的内容移动到栈中。 /// private void StequeToStack() { while (!this.steque.IsEmpty()) { this.stack.Push(this.steque.Pop()); } } /// /// 从双向队列左侧弹出一个元素。 /// /// /// 向双向队列右侧添加一个元素。 /// /// 要插入的元素。 public void PushRight(Item item) { if (this.stack.IsEmpty()) { this.steque.Enqueue(item); } else { this.stack.Push(item); } } /// /// 从双向队列右侧弹出一个元素。 /// /// /// 判断队列是否为空。 /// /// /// 返回队列中元素的数量。 /// ///
1.4.31
解答
三个栈分别命名为左中右。
左侧栈和右侧栈负责模拟队列，和用两个栈模拟队列的方法类似。
由于是双向队列，左栈和右栈会频繁的倒来倒去，因此每次都只倒一半的元素可以有效减少开销。
有一侧栈为空时，另一侧栈中上半部分先移动到中间栈中，下半部分倒到另一侧栈里，再从中间栈拿回上半部分元素。
这样可以确保接下来的 pop 操作一定是常数级别的。
代码
namespace _1._4._31{ /// /// 用三个栈模拟的双向队列。 /// /// 双向队列中的元素。 class Deque - { Stack
- left; Stack
- middle; Stack
- right; ///
/// 构造一条新的双向队列。 /// public Deque() { this.left = new Stack - (); this.middle = new Stack
- (); this.right = new Stack
- (); } ///
/// 向双向队列左侧插入一个元素。 /// /// 要插入的元素。 public void PushLeft(Item item) { this.left.Push(item); } /// /// 向双向队列右侧插入一个元素。 /// /// 要插入的元素。 public void PushRight(Item item) { this.right.Push(item); } /// /// 当一侧栈为空时，将另一侧的下半部分元素移动过来。 /// /// 不为空的栈。 /// 空栈。 private void Move(Stack - source, Stack
- destination) { int n = source.Size(); // 将上半部分元素移动到临时栈 middle for (int i = 0; i < n / 2; ++i) { this.middle.Push(source.Pop()); } // 将下半部分移动到另一侧栈中 while (!source.IsEmpty()) { destination.Push(source.Pop()); } // 从 middle 取回上半部分元素 while (!this.middle.IsEmpty()) { source.Push(this.middle.Pop()); } } ///
/// 检查双端队列是否为空。 /// /// /// 从右侧弹出一个元素。 /// /// /// 从左侧弹出一个元素。 /// /// /// 返回双端队列的大小。 /// ///
1.4.32
解答
首先，不需要扩容数组的的操作都只需访问数组一次，M 次操作就是 M 次访问。
随后我们有性质， M 次栈操作后额外复制访问数组的次数小于 2M。这里简单证明，设 M 次操作之后栈的大小为 n，那么额外访问数组的次数为：S = n/2 + n/4 + n/8 +...+ 2 < n为了能使栈大小达到 n，M 必须大于等于 n/2因此 2M >= n > S，得证。 因此我们可以得到 M 次操作后访问数组次数的总和 S' = S + M < 3M
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
String = 8(对象开销) + 3*4(int * 3) + 4(字符数组的引用) = 24
Node = 8(对象开销) + 4*2(引用*2) = 16
Stack = 8(对象开销) + 4(引用) + 4(int) = 16
1.4.34
解答
1. 第一种方案，类似于二分查找，先猜测左边界(lo)，再猜测右边界(hi)，如果边界值猜中的话直接返回，否则：
如果右边界比较热，那么左边界向右边界靠，lo=mid；否则，右边界向左边界靠，hi=mid。其中，mid = lo + (hi – lo)/2。
每次二分查找都要猜测两次，~2lgN。
2. 第二种方案，假设上次猜测值为 lastGuess，本次即将要猜测的值为 nowGuess，通过方程：
(lastGuess + nowGuess)/2 = (lo + hi)/2
可以求得 nowGuess，具体可以查看示意图：
数字是猜测顺序，黑色范围是猜测值的范围（lastGuess 和 nowGuess），绿色的是实际查找的范围（lo 和 hi）。
代码
首先是 Game 类
using System;namespace _1._4._34{ /// /// 某次猜测的结果。 /// enum GuessResult { Hot = 1, // 比上次猜测更接近目标。 Equal = 0, // 猜中目标。 Cold = -1, // 比上次猜测更远离目标。 FirstGuess = -2 // 第一次猜测。 } /// /// 游戏类。 /// class Game { public int N { get; } // 目标值的最大范围。 public int SecretNumber { get; } // 目标值。 public int LastGuess { get; private set; } // 上次猜测的值 /// /// 构造函数，新开一局游戏。 /// /// 目标值的最大范围。 public Game(int N) { Random random = new Random(); this.N = N; this.SecretNumber = random.Next(N - 1) + 1; this.LastGuess = -1; } /// /// 猜测，根据与上次相比更为接近还是远离目标值返回结果。 /// /// 本次的猜测值 /// 接近或不变返回 Hot，远离则返回 Cold，猜中返回 Equal。 public GuessResult Guess(int guess) { if (guess == this.SecretNumber) { return GuessResult.Equal; } if (this.LastGuess == -1) { this.LastGuess = guess; return GuessResult.FirstGuess; } int lastDiff = Math.Abs(this.LastGuess - this.SecretNumber); this.LastGuess = guess; int nowDiff = Math.Abs(guess - this.SecretNumber); if (nowDiff > lastDiff) { return GuessResult.Cold; } else { return GuessResult.Hot; } } /// /// 重置游戏，清空上次猜测的记录。目标值和最大值都不变。 /// public void Restart() { this.LastGuess = -1; } }} 之后是实际测试的方法：
using System;namespace _1._4._34{ /* * 1.4.34 * * 热还是冷。 * 你的目标是猜出 1 到 N 之间的一个秘密的整数。 * 每次猜完一个整数后，你会直到你的猜测距离该秘密整数是否相等（如果是则游戏结束）。 * 如果不相等，你会知道你的猜测相比上一次猜测距离秘密整数是比较热（接近），还是比较冷（远离）。 * 设计一个算法在 ~2lgN 之内找到这个秘密整数，然后设计一个算法在 ~1lgN 之内找到这个秘密整数。 * */ class Program { /// /// 某种方案的测试结果，包含猜测结果和尝试次数。 /// struct TestResult { public int SecretNumber;// 猜测到的数字。 public int TryTimes;// 尝试次数。 } static void Main(string[] args) { Game game = new Game(1000); TestResult A = PlayGameA(game); game.Restart(); TestResult B = PlayGameB(game); Console.WriteLine($"SecretNumber:{game.SecretNumber}"); Console.WriteLine("TestResultA:"); Console.WriteLine($"SecretNumber:{A.SecretNumber}, TryTimes:{A.TryTimes}"); Console.WriteLine(); Console.WriteLine("TestResultB:"); Console.WriteLine($"SecretNumber:{B.SecretNumber}, TryTimes:{B.TryTimes}"); } /// /// 方案一，用二分查找实现，需要猜测 2lgN 次。 /// /// 用于猜测的游戏对象。 /// 返回测试结果，包含猜测结果和尝试次数。 static TestResult PlayGameA(Game game) { TestResult result; result.TryTimes = 0; result.SecretNumber = 0; GuessResult guessResult; int hi = game.N; int lo = 1; // 利用二分查找猜测，2lgN while (lo <= hi) { int mid = lo + (hi - lo) / 2; guessResult = game.Guess(lo); result.TryTimes++; if (guessResult == GuessResult.Equal) { result.SecretNumber = lo; return result; } guessResult = game.Guess(hi); result.TryTimes++; if (guessResult == GuessResult.Equal) { result.SecretNumber = hi; return result; } else if (guessResult == GuessResult.Hot) { lo = mid; } else { hi = mid; } } return result; } /// /// 方案二，根据 (lastGuess + nowGuess)/2 = (lo + hi) / 2 确定每次猜测的值。 /// /// 用于猜测的游戏对象。 /// 返回测试结果，包含猜测结果和尝试次数。 static TestResult PlayGameB(Game game) { TestResult result; result.TryTimes = 0; result.SecretNumber = 0; GuessResult guessResult; int hi = game.N; int lo = 1; bool isRightSide = true; // 第一次猜测 guessResult = game.Guess(1); result.TryTimes++; if (guessResult == GuessResult.Equal) { result.SecretNumber = 1; return result; } while (lo < hi) { int mid = lo + (hi - lo) / 2; int nowGuess = (lo + hi) - game.LastGuess; guessResult = game.Guess(nowGuess); result.TryTimes++; if (guessResult == GuessResult.Equal) { result.SecretNumber = nowGuess; break; } else if (guessResult == GuessResult.Hot) { if (isRightSide) { lo = mid; } else { hi = mid; } } else { if (isRightSide) { hi = mid; } else { lo = mid; } } isRightSide = !isRightSide; if (hi - lo <= 1) { break; } } if (game.Guess(lo) == GuessResult.Equal) { result.TryTimes++; result.SecretNumber = lo; } else if (game.Guess(hi) == GuessResult.Equal) { result.TryTimes++; result.SecretNumber = hi; } return result; } }}
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 = ~5N4. 创建引用和上题一样，创建对象则多出了装箱过程，每次 push 都会新建一个 Integer 对象，N + lgN = ~N。
1.4.36
解答
1. N 个 Node<int> 对象的空间开销
= N * (16(对象开销) + 4(int) + 8(下一个 Node 的引用) + 4(填充字节)) = 32N2. 比起上一题来说，空间开销变为
= 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，根据 FixedCapacityOfString 修改而来：
using System;using System.Collections;using System.Collections.Generic;namespace _1._4._37{ /// /// 固定大小的整型数据栈。 /// class FixedCapacityStackOfInts : IEnumerable { private int[] a; private int N; /// /// 默认构造函数。 /// /// 栈的大小。 public FixedCapacityStackOfInts(int capacity) { this.a = new int[capacity]; this.N = 0; } /// /// 检查栈是否为空。 /// /// /// 检查栈是否已满。 /// /// /// 将一个元素压入栈中。 /// /// 要压入栈中的元素。 public void Push(int item) { this.a[this.N] = item; this.N++; } /// /// 从栈中弹出一个元素，返回被弹出的元素。 /// /// /// 返回栈顶元素（但不弹出它）。 /// /// FixedCapacityStack<Item>
using System;using System.Collections;using System.Collections.Generic;namespace _1._4._37{ /// /// 固定大小的栈。 /// class FixedCapacityStack - : IEnumerable
- { private Item[] a; private int N; ///
/// 默认构造函数。 /// /// 栈的大小。 public FixedCapacityStack(int capacity) { this.a = new Item[capacity]; this.N = 0; } /// /// 检查栈是否为空。 /// /// /// 检查栈是否已满。 /// /// /// 将一个元素压入栈中。 /// /// 要压入栈中的元素。 public void Push(Item item) { this.a[this.N] = item; this.N++; } /// /// 从栈中弹出一个元素，返回被弹出的元素。 /// /// /// 返回栈顶元素（但不弹出它）。 /// /// - GetEnumerator() { return new ReverseEnmerator(this.a); } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } private class ReverseEnmerator : IEnumerator
- { private int current; private Item[] a; public ReverseEnmerator(Item[] a) { this.current = a.Length; this.a = a; } Item IEnumerator
- .Current => this.a[this.current]; object IEnumerator.Current => this.a[this.current]; void IDisposable.Dispose() { this.current = -1; this.a = null; } bool IEnumerator.MoveNext() { if (this.current == 0) return false; this.current--; return true; } void IEnumerator.Reset() { this.current = this.a.Length; } } }}
测试函数：
using System;using Measurement;namespace _1._4._37{ /// /// FixedCapacityStackOfInts 测试类。 /// public static class DoubleTest { private static readonly int MAXIMUM_INTEGER = 1000000; /// /// 返回对 n 个随机整数的栈进行 n 次 push 和 n 次 pop 所需的时间。 /// /// 随机数组的长度。 /// /// 返回对 n 个随机整数的栈进行 n 次 push 和 n 次 pop 所需的时间。 /// /// 随机数组的长度。 /// 主函数：
using System;namespace _1._4._37{ /* * 1.4.37 * * 自动装箱的性能代价。 * 通过实验在你的计算机上计算使用自动装箱所付出的性能代价。 * 实现一个 FixedCapacityStackOfInts， * 并使用类似 DoublingRatio 的用例比较它和泛型 FixedCapacityStack 在进行大量 push() 和 pop() 时的性能。 * */ class Program { static void Main(string[] args) { Console.WriteLine("测试量\t非泛型耗时（毫秒）\t泛型耗时（毫秒）\t差值"); for (int n = 250; true; n += n) { double time = DoubleTest.TimeTrial(n); double timeGeneric = DoubleTest.TimeTrialGeneric(n); Console.WriteLine($"{n}\t{time}\t{timeGeneric}\t{Math.Abs(time - timeGeneric)}"); } } }}
1.4.38
解答
把 DoublingTest 中调用的函数稍作修改即可。
代码
ThreeSum 测试类
using System;namespace _1._4._38{ /// /// ThreeSum 测试类。 /// public static class DoubleTest { private static readonly int MAXIMUM_INTEGER = 1000000; /// /// 返回对 n 个随机整数的数组进行一次 ThreeSum 所需的时间。 /// /// 随机数组的长度。 ///
ThreeSum
using System;namespace _1._4._38{ /// /// 用暴力方法寻找数组中和为零的三元组。 /// public static class ThreeSum { /// /// 输出所有和为零的三元组。 /// /// 输入数组。 public static void PrintAll(int[] a) { int n = a.Length; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { for (int k = 0; k < n; ++k) { if (i < j && j < k) { if ((long)a[i] + a[j] + a[k] == 0) { Console.WriteLine($"{a[i]} + {a[j]} + {a[k]}"); } } } } } } /// /// 计算和为零的三元组的数量。 /// /// 输入数组。 ///
1.4.39
解答
执行 N 次后取平均即可。
代码
修改后的 DoublingTest：
using System;using Measurement;namespace _1._4._39{ /// /// ThreeSum 测试类。 /// public static class DoubleTest { private static readonly int MAXIMUM_INTEGER = 1000000; /// /// 返回对 n 个随机整数的数组进行一次 ThreeSum 所需的时间。 /// /// 随机数组的长度。 /// 重复测试的次数。 ///
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) * (3M^2 + 3M + 1) * (2M+1)^(N-3) 种可能性平均值为：[((N^3)/6) * (3M^2 + 3M + 1) * (2M+1)^(N-3)] / (2M+1)^N
N^3/16M
代码
using System;namespace _1._4._40{ /* * 1.4.40 * * 随机输入下的 3-sum 问题。 * 猜测找出 N 个随机 int 值中和为 0 的整数三元组的数量所需的时间并验证你的猜想。 * 如果你擅长数学分析，请为此问题给出一个合适的数学模型， * 其中所有值均匀的分布在 -M 和 M 之间，且 M 不能是一个小整数。 * */ class Program { // 数学模型 // // 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) * (3M^2 + 3M + 1) * (2M+1)^(N-3) 种可能性 // 平均值为： // [((N^3)/6) * (3M^2 + 3M + 1) * (2M+1)^(N-3)] / (2M+1)^N // (N^3) * (3M^2 + 3M + 1) / 6 * (2M+1)^3 // ~ N^3 * 3M^2 / 6 * 8M^3 // N^3/16M static void Main(string[] args) { int M = 10000; for (int n = 125; n < 10000; n += n) { Random random = new Random(); int[] a = new int[n]; for (int i = 0; i < n; ++i) { a[i] = random.Next(2 * M) - M; } Console.WriteLine($"N={n}, 计算值={Math.Pow(n, 3) / (16 * M)}, 实际值={ThreeSum.Count(a)}"); } } }}
1.4.41
解答
代码
这里使用了委托来简化代码。
DoublingRatio
using System;using Measurement;namespace _1._4._41{ public delegate int Count(int[] a); static class DoublingRatio { /// /// 从指定字符串中读入按行分割的整型数据。 /// /// 源字符串。 /// 读入的整型数组 private static int[] ReadAllInts(string inputString) { char[] split = new char[1] { '\n' }; string[] input = inputString.Split(split, StringSplitOptions.RemoveEmptyEntries); int[] a = new int[input.Length]; for (int i = 0; i < a.Length; ++i) { a[i] = int.Parse(input[i]); } return a; } /// /// 使用给定的数组进行一次测试，返回耗时（毫秒）。 /// /// 要测试的方法。 /// 测试用的数组。 /// 耗时（秒）。 public static double TimeTrial(Count Count, int[] a) { Stopwatch timer = new Stopwatch(); Count(a); return timer.ElapsedTimeMillionSeconds(); } /// /// 对 TwoSum、TwoSumFast、ThreeSum 或 ThreeSumFast 的 Count 方法做测试。 /// /// 相应类的 Count 方法 /// 随着数据量倍增，方法耗时增加的比率。 public static double Test(Count Count) { double ratio = 0; double times = 3; // 1K int[] a = ReadAllInts(TestCase.Properties.Resources._1Kints); double prevTime = TimeTrial(Count, a); Console.WriteLine("数据量\t耗时\t比值"); Console.WriteLine($"1000\t{prevTime / 1000}\t"); // 2K a = ReadAllInts(TestCase.Properties.Resources._2Kints); double time = TimeTrial(Count, a); Console.WriteLine($"2000\t{time / 1000}\t{time / prevTime}"); if (prevTime != 0) { ratio += time / prevTime; } else { times--; } prevTime = time; // 4K a = ReadAllInts(TestCase.Properties.Resources._4Kints); time = TimeTrial(Count, a); Console.WriteLine($"4000\t{time / 1000}\t{time / prevTime}"); if (prevTime != 0) { ratio += time / prevTime; } else { times--; } prevTime = time; // 8K a = ReadAllInts(TestCase.Properties.Resources._8Kints); time = TimeTrial(Count, a); Console.WriteLine($"8000\t{time / 1000}\t{time / prevTime}"); if (prevTime != 0) { ratio += time / prevTime; } else { times--; } prevTime = time; return ratio / times; } public static double TestTwoSumFast(Count Count) { double ratio = 0; double times = 2; // 8K int[] a = ReadAllInts(TestCase.Properties.Resources._8Kints); double prevTime = TimeTrial(Count, a); Console.WriteLine("数据量\t耗时\t比值"); Console.WriteLine($"8000\t{prevTime / 1000}\t"); // 16K a = ReadAllInts(TestCase.Properties.Resources._16Kints); double time = TimeTrial(Count, a); Console.WriteLine($"16000\t{time / 1000}\t{time / prevTime}"); if (prevTime != 0) { ratio += time / prevTime; } else { times--; } prevTime = time; // 32K a = ReadAllInts(TestCase.Properties.Resources._32Kints); time = TimeTrial(Count, a); Console.WriteLine($"32000\t{time / 1000}\t{time / prevTime}"); if (prevTime != 0) { ratio += time / prevTime; } else { times--; } prevTime = time; return ratio / times; } }}
主方法：
using System;using Measurement;namespace _1._4._41{ /* * 1.4.41 * * 运行时间。 * 使用 DoublingRatio 估计在你的计算机上用 TwoSumFast、TwoSum、ThreeSumFast 以及 ThreeSum 处理一个含有 100 万个整数的文件所需的时间。 * */ class Program { static void Main(string[] args) { int[] a = new int[977]; Random random = new Random(); for (int i = 0; i < 977; ++i) { a[i] = random.Next(977) - 489; } // ThreeSum Console.WriteLine("ThreeSum"); double time = DoublingRatio.TimeTrial(ThreeSum.Count, a); Console.WriteLine($"数据量：977 耗时：{time / 1000}"); double doubleRatio = DoublingRatio.Test(ThreeSum.Count); Console.WriteLine($"数据量：1000000 估计耗时：{time * doubleRatio * 1024 / 1000}"); Console.WriteLine(); //// ThreeSumFast Console.WriteLine("ThreeSumFast"); time = DoublingRatio.TimeTrial(ThreeSumFast.Count, a); doubleRatio = DoublingRatio.Test(ThreeSumFast.Count); Console.WriteLine($"数据量：977 耗时：{time / 1000}"); Console.WriteLine($"数据量：1000000 估计耗时：{time * doubleRatio * 1024 / 1000}"); Console.WriteLine(); //// TwoSum Console.WriteLine("TwoSum"); time = DoublingRatio.TimeTrial(TwoSum.Count, a); doubleRatio = DoublingRatio.Test(TwoSum.Count); Console.WriteLine($"数据量：977 耗时：{time / 1000}"); Console.WriteLine($"数据量：1000000 估计耗时：{time * doubleRatio * 1024 / 1000}"); Console.WriteLine(); // TwoSumFast // 速度太快，加大数据量 a = new int[62500]; for (int i = 0; i < 977; ++i) { a[i] = random.Next(62500) - 31250; } Console.WriteLine("TwoSumFast"); time = DoublingRatio.TimeTrial(TwoSumFast.Count, a); doubleRatio = DoublingRatio.TestTwoSumFast(TwoSumFast.Count); Console.WriteLine($"数据量：62500 耗时：{time / 1000}"); Console.WriteLine($"数据量：1000000 估计耗时：{time * doubleRatio * 16 / 1000}"); Console.WriteLine(); } }}
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 数据。
1.4.43
解答
代码
修改后的 DoublingRatio
using System;using Measurement;namespace _1._4._43{ static class DoublingRatio { /// /// 从指定字符串中读入按行分割的整型数据。 /// /// 源字符串。 /// 读入的整型数组 private static int[] ReadAllInts(string inputString) { char[] split = new char[1] { '\n' }; string[] input = inputString.Split(split, StringSplitOptions.RemoveEmptyEntries); int[] a = new int[input.Length]; for (int i = 0; i < a.Length; ++i) { a[i] = int.Parse(input[i]); } return a; } /// /// 使用给定的数组对链栈进行一次测试，返回耗时（毫秒）。 /// /// 测试用的数组。 /// 耗时（毫秒）。 public static double TimeTrialLinkedStack(int[] a) { LinkedStack stack = new LinkedStack (); int n = a.Length; Stopwatch timer = new Stopwatch(); for (int i = 0; i < n; ++i) { stack.Push(a[i]); } for (int i = 0; i < n; ++i) { stack.Pop(); } return timer.ElapsedTimeMillionSeconds(); } /// /// 使用给定的数组对数组栈进行一次测试，返回耗时（毫秒）。 /// /// 测试用的数组。 /// 耗时（毫秒）。 public static double TimeTrialDoublingStack(int[] a) { DoublingStack stack = new DoublingStack (); int n = a.Length; Stopwatch timer = new Stopwatch(); for (int i = 0; i < n; ++i) { stack.Push(a[i]); } for (int i = 0; i < n; ++i) { stack.Pop(); } return timer.ElapsedTimeMillionSeconds(); } /// /// 对链栈和基于大小可变的数组栈做测试。 /// public static void Test() { double linkedTime = 0; double arrayTime = 0; Console.WriteLine("数据量\t链栈\t数组\t比值\t单位：毫秒"); // 16K int[] a = ReadAllInts(TestCase.Properties.Resources._16Kints); linkedTime = TimeTrialLinkedStack(a); arrayTime = TimeTrialDoublingStack(a); Console.WriteLine($"16000\t{linkedTime}\t{arrayTime}\t{linkedTime / arrayTime}"); // 32K a = ReadAllInts(TestCase.Properties.Resources._32Kints); linkedTime = TimeTrialLinkedStack(a); arrayTime = TimeTrialDoublingStack(a); Console.WriteLine($"32000\t{linkedTime}\t{arrayTime}\t{linkedTime / arrayTime}"); // 1M a = ReadAllInts(TestCase.Properties.Resources._1Mints); linkedTime = TimeTrialLinkedStack(a); arrayTime = TimeTrialDoublingStack(a); Console.WriteLine($"1000000\t{linkedTime}\t{arrayTime}\t{linkedTime / arrayTime}"); } }}
1.4.44
解答
每生成一个随机数都和之前生成过的随机数相比较。
代码
using System;namespace _1._4._44{ /* * 1.4.44 * * 生日问题。 * 编写一个程序， * 从命令行接受一个整数 N 作为参数并使用 StdRandom.uniform() 生成一系列 0 到 N-1 之间的随机整数。 * 通过实验验证产生第一个重复的随机数之前生成的整数数量为 ~√(πN/2)。 * */ class Program { static void Main(string[] args) { Random random = new Random(); int N = 10000; int[] a = new int[N]; int dupNum = 0; int times = 0; for (times = 0; times < 500; ++times) { for (int 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}个数字后出现重复"); } /// /// 检查是否有重复的数字出现。 /// /// 需要检查的数组。 /// 当前加入数组元素的下标。 /// 有重复则返回 true，否则返回 false。 static bool IsDuplicated(int[] a, int i) { for (int j = 0; j < i; ++j) { if (a[j] == a[i]) { return true; } } return false; } }}
1.4.45
解答
建立一个布尔数组，将每次随机出来的数作为下标，将相应位置的布尔值改为 true，每次随机都检查一遍这个数组是否都是 true。
代码
using System;namespace _1._4._45{ /* * 1.4.45 * * 优惠券收集问题。 * 用和上一题相同的方式生成随机整数。 * 通过实验验证生成所有可能的整数值所需生成的随机数总量为 ~NHN。 * （这里的 HN 中 N 是下标） * */ class Program { // HN 指的是调和级数 static void Main(string[] args) { Random random = new Random(); int N = 10000; bool[] a = new bool[N]; int randomSize = 0; int times = 0; for (times = 0; times < 20; ++times) { for (int i = 0; i < N; ++i) { a[i] = false; } for(int i = 0; true; ++i) { int now = random.Next(N); a[now] = true; if (IsAllGenerated(a)) { randomSize += i; Console.WriteLine($"生成{i}次后所有可能均出现过了"); break; } } } Console.WriteLine($"\nNHN={N * HarmonicSum(N)}，平均生成{randomSize / times}个数字后所有可能都出现"); } /// /// 计算 N 阶调和级数的和。 /// /// 调和级数的 N 值 /// N 阶调和级数的和。 static double HarmonicSum(int N) { double sum = 0; for (int i = 1; i <= N; ++i) { sum += 1.0 / i; } return sum; } /// /// 检查所有数字是否都生成过了。 /// /// 布尔数组。 /// 全都生成则返回 true，否则返回 false。 static bool IsAllGenerated(bool[] a) { foreach (bool i in a) { if (!i) return false; } return true; } }}