首页 / 算法 / 算法（第四版）C#题解——1.4
算法（第四版）C#题解——1.4
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法（第四版）C#题解——1.4，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含62660字，纯文字阅读大概需要90分钟。
内容图文
写在前面
整个项目都托管在了 Github 上：https://github.com/ikesnowy/Algorithms-4th-Edition-in-Csharp
这一节内容可能会用到的库文件有 Measurement 和 TestCase，同样在 Github 上可以找到。
善用 Ctrl + F 查找题目。
习题&题解
1.4.1
题目
证明从 N 个数中取三个整数的不同组合总数为 N(N - 1)(N - 2) / 6。
解答
即为证明组合计算公式：
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) / 6
N + 1 个数能组成的三位数组合可以这样理解
前 N 个数中取三个数的所有组合 +多出的一个数和前 N 个数中的任意取两个数的所有组合
即为 N(N-1)(N - 2) / 6 + C(N, 2)
变形后即为(N + 1)N(N - 1) / 6
得证。
1.4.2
题目
修改 ThreeSum，正确处理两个较大 int 值相加可能溢出的情况。
解答
将 a[i] + a[j] + a[k] 改为 (long)a[i] + a[j] + a[k] 即可。
此时整个式子将按照精度最高（也就是 long）的标准计算。
long.MaxValue = 9223372036854775807 > int.MaxValue * 3 = 6442450941
代码
namespace
Measurement
{
///
<summary>
///
用暴力方法寻找数组中和为零的三元组。
///
</summary>
public
static
class
ThreeSum
{
///
<summary>
///
输出所有和为零的三元组。
///
</summary>
///
<param name="a">
输入数组。
</param>
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]}");
}
}
}
}
}
///<summary>/// 计算和为零的三元组的数量。
///</summary>///<param name="a">输入数组。</param>///<returns></returns>publicstaticint Count(int[] a)
{
int n = a.Length;
int count = 0;
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)
{
count++;
}
}
}
}
return count;
}
}
}
1.4.3
题目
修改 DoublingTest，使用 StdDraw 产生类似于正文中的标准图像和对数图像，
根据需要调整比例使图像总能够充满窗口的大部分区域。
解答
见代码，这里贴出绘图函数，窗体只是在得到测试结果之后简单调用以下这两个函数。
代码
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();
}
publicstaticvoid 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.4 为 TwoSum 建立一张类似的表格。
解答
代码分块↑
时间分析↓
1.4.5
题目
给出下面这些量的近似：
a. N + 1
b. 1 + 1/N
c. (1 + 1/N)(1 + 2/N)
d. 2N^3 - 15N^2 + N
e. lg(2N) / lgN
f. lg(N^2 + 1) / lgN
g. N^100 / 2^N
解答
类似于取极限的做法。
a. N
b. 1
c. 1
d. 2N3
e. 1
f. 2
g. N100
1.4.6
题目
给出以下代码段的运行时间的增长数量级（作为 N 的函数）。
a.
int sum = 0;
for (int n = N; n > 0; n /= 2)
for (int i = 0; i < n; i++)
sum++;
b.
int sum = 0;
for (int i = 1; i < N; i *= 2)
for (int j = 0; j < i; j++)
sum++;
c.
int sum = 0;
for (int i = 1; i < N; i *= 2)
for (int j = 0; j < N; j++)
sum++;
解答
a. N + N/2 + N/4 + … = ~2N，线性。
b. 1 + 2 + 4 + … = ~2N，线性。
c. logN * N，线性对数。
1.4.7
题目
以统计涉及输入数字的算数操作（和比较）的成本模型分析 ThreeSum。
解答
最外层循环进行了 N 次比较。
次外层循环进行了 N^2 次比较。
最里层循环进行了 N^3 次比较。
内部 if 语句进行了 N^3 次比较。
if 内部进行了 N(N-1) 次加法。
加起来，~2N^3。
1.4.8
题目
编写一个程序，计算输入文件中相等的整数对的数量。
如果你的第一个程序是平方级别的，
请继续思考并用 Array.sort() 给出一个线性对数级别的解答。
解答
平方级别：直接二层循环遍历一遍。
线性对数：只遍历一遍数组，在遍历过程中用二分查找确认在剩余数组中是否有相等的整数。
代码
///
<summary>
///
暴力查找数组中相等的整数对。
///
</summary>
///
<param name="a">
需要查找的数组。
</param>
///
<returns></returns>
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;
}
暴力算法↑
二分查找算法↓
///
<summary>
///
利用二分查找进行优化的查找相等整数对算法。
///
</summary>
///
<param name="a">
需要查找的数组。
</param>
///
<returns></returns>
static
int CountEqualLog(int[] a)
{
int n = a.Length;
int count = 0;
Array.Sort(a);
for (int i = 0; i < n; ++i)
{
if (BinarySearch.Rank(a[i], a, i + 1, a.Length - 1) != -1)
{
count++;
}
}
return count;
}
1.4.9
题目
已知由倍率实验可得某个程序的时间倍率为 2^b 且问题规模为 N0 时程序运行时间为 T，
给出一个公式预测该程序在处理规模为 N 的问题时所需的运行时间。
解答
1.4.10
题目
修改二分查找算法，使之总是返回和被查找的键匹配的索引最小的元素。
（但仍能够保证对数级别的运行时间）
解答
修改二分查找的结束条件，找到后仍然向左侧寻找，如果还能找到更小的，则返回较小的下标；否则返回当前下标。
代码
namespace
_1._4._10
{
///
<summary>
///
二分查找。
///
</summary>
public
class
BinarySearch
{
///
<summary>
///
用递归方法进行二分查找。
///
</summary>
///
<param name="key">
关键字。
</param>
///
<param name="a">
查找范围。
</param>
///
<param name="lo">
查找的起始下标。
</param>
///
<param name="hi">
查找的结束下标。
</param>
///
<returns>
返回下标，如果没有找到则返回 -1。
</returns>
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;
}
elseif (a[mid] < key)
{
return Rank(key, a, mid + 1, hi);
}
else
{
return Rank(key, a, lo, mid - 1);
}
}
}
}
1.4.11
题目
为 StaticSETofInts （请见表 1.2.15） 添加一个实例方法 howMany()，
找出给定键的出现次数且在最坏情况下所需的运行时间应该和 log(N) 成正比。
解答
这里给出官网上的 Java 实现：StaticSETofInts.java。
howMany() 可以用二分查找实现，在找到一个值后继续向两侧查找，最后返回找到的次数。
代码
using
System;
namespace
Measurement
{
///
<summary>
///
有序数组，能够快速查找并自动维护其中的顺序。
///
</summary>
public
class
StaticSETofInts
{
private
int
[] a;
///
<summary>
///
用一个数组初始化有序数组。
///
</summary>
///
<param name="keys">
源数组。
</param>
public StaticSETofInts(int[] keys)
{
this.a = newint[keys.Length];
for (int i = 0; i < keys.Length; ++i)
{
this.a[i] = keys[i];
}
Array.Sort(this.a);
}
///<summary>/// 检查数组中是否存在指定元素。
///</summary>///<param name="key">要查找的值。</param>///<returns>存在则返回 true，否则返回 false。</returns>publicbool Contains(int key)
{
return Rank(key, 0, this.a.Length - 1) != -1;
}
///<summary>/// 返回某个元素在数组中存在的数量。
///</summary>///<param name="key">关键值。</param>///<returns>返回某个元素在数组中存在的数量。</returns>publicint HowMany(int key)
{
int hi = this.a.Length - 1;
int lo = 0;
return HowMany(key, lo, hi);
}
///<summary>/// 返回某个元素在数组中存在的数量。
///</summary>///<param name="key">关键值。</param>///<param name="lo">查找起始下标。</param>///<param name="hi">查找结束下标。</param>///<returns>返回某个元素在数组中存在的数量。</returns>privateint HowMany(int key, int lo, int hi)
{
int mid = Rank(key, lo, hi);
if (mid == -1)
return0;
else
{
return1 + HowMany(key, lo, mid - 1) + HowMany(key, mid + 1, hi);
}
}
///<summary>/// 二分查找。
///</summary>///<param name="key">关键值。</param>///<param name="lo">查找的起始下标。</param>///<param name="hi">查找的结束下标。</param>///<returns>返回关键值的下标，如果不存在则返回 -1。</returns>publicint Rank(int key, int lo, int hi)
{
while (lo <= hi)
{
int mid = (hi - lo) / 2 + lo;
if (key < this.a[mid])
hi = mid - 1;
elseif (key > this.a[mid])
lo = mid + 1;
elsereturn mid;
}
return -1;
}
}
}
1.4.12
题目
编写一个程序，有序打印给定的两个有序数组（含有 N 个 int 值） 中的所有公共元素，
程序在最坏情况下所需的运行时间应该和 N 成正比。
解答
由于两个数组都是有序的，可以同时进行比较。
设 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 = newint[4] { 2, 3, 4, 10 };
int[] b = newint[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++;
}
elseif (a[i] > b[j])
{
j++;
}
else
{
Console.WriteLine($"Common Element:{a[i]}, First index: (a[{i}], b[{j}])");
i++;
j++;
}
}
}
}
}
1.4.13
题目
根据正文中的假设分别给出表示以下数据类型的一个对象所需的内存量：
a. Accumulator
b. Transaction
c. FixedCapacityStackOfStrings，其容量为 C 且含有 N 个元素。
d. Point2D
e. Interval1D
f. Interval2D
g. Double
解答
对象的固定开销用 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
题目
4-sum。
为 4-sum 设计一个算法。
解答
这里给出暴力方法，将最内侧循环换成二分查找即为优化版本。
代码
using
System;
namespace
Measurement
{
///
<summary>
///
用暴力方法查找数组中和为零的四元组。
///
</summary>
public
static
class
FourSum
{
///
<summary>
///
输出数组中所有和为 0 的四元组。
///
</summary>
///
<param name="a">
包含所有元素的数组。
</param>
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");
}
}
}
}
}
}
///<summary>/// 计算和为零的四元组的数量。
///</summary>///<param name="a">包含所有元素的数组。</param>///<returns></returns>publicstaticint Count(long[] a)
{
int N = a.Length;
int cnt = 0;
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)
{
cnt++;
}
}
}
}
}
return cnt;
}
}
}
1.4.15
题目
快速 3-sum。
作为热身，使用一个线性级别的算法
（而非基于二分查找的线性对数级别的算法）
实现 TwoSumFaster 来计算已排序的数组中和为 0 的整数对的数量。
用相同的思想为 3-sum 问题给出一个平方级别的算法。
解答
由于数组已经排序（从小到大），负数在左侧，正数在右侧。
TwoSumFaster
设最左侧下标为 lo，最右侧下标为 hi。
如果 a[lo] + a[hi] > 0, 说明正数太大，hi--。
如果 a[lo] + a[hi] < 0，说明负数太小，lo++。
否则就找到了一对和为零的整数对，lo++, hi--。
ThreeSumFaster
对于数组中的每一个数 a，ThreeSum 问题就等于求剩余数组中所有和为 -a 的 TwoSum 问题。
只要在 TwoSumFaster 外层再套一个循环即可。
代码
///
<summary>
///
TwoSum 的快速实现。（线性级别）
///
</summary>
///
<param name="a">
需要查找的数组范围。
</param>
///
<returns>
数组中和为零的整数对数量。
</returns>
static
int TwoSumFaster(int[] a)
{
int i = 0;
int j = a.Length - 1;
int count = 0;
while (i != j)
{
if (a[i] + a[j] == 0)
{
count++;
i++;
j--;
}
elseif (a[i] + a[j] < 0)
{
i++;
}
else
{
j--;
}
}
return count;
}
///<summary>/// ThreeSum 的快速实现。（平方级别）
///</summary>///<param name="a">需要查找的数组范围。</param>///<returns>数组中和为零的三元组数量。</returns>staticint 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--;
}
elseif (a[lo] + a[hi] + a[i] < 0)
{
lo++;
}
else
{
hi--;
}
}
}
return count;
}
1.4.16
题目
最接近一对（一维）。
编写一个程序，给定一个含有 N 个 double 值的数组 a[]，
在其中找到一对最接近的值：两者之差（绝对值）最小的两个数。
程序在最坏情况下所需的运行时间应该是线性对数级别的。
解答
先将数组从小到大排序，再遍历一遍即可得到差距最小的两个数。
排序算法需要消耗 NlogN，具体见 MSDN：Array.Sort 方法 (Array)。
代码
using
System;
namespace
_1._4._16
{
/*
* 1.4.16
*
* 最接近一对（一维）。
* 编写一个程序，给定一个含有 N 个 double 值的数组 a[]，
* 在其中找到一对最接近的值：两者之差（绝对值）最小的两个数。
* 程序在最坏情况下所需的运行时间应该是线性对数级别的。
*
*/
class
Program
{
//
总运行时间： NlogN + N = NlogN
static
void Main(string[] args)
{
double[] a = newdouble[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
题目
最遥远的一对（一维）。
编写一个程序，给定一个含有 N 个 double 值的数组 a[]，
在其中找到一对最遥远的值：两者之差（绝对值）最大的两个数。
程序在最坏情况下所需的运行时间应该是线性级别的。
解答
遍历找到最小值和最大值即可。
代码
using
System;
namespace
_1._4._17
{
/*
* 1.4.17
*
* 最遥远的一对（一维）。
* 编写一个程序，给定一个含有 N 个 double 值的数组 a[]，
* 在其中找到一对最遥远的值：两者之差（绝对值）最大的两个数。
* 程序在最坏情况下所需的运行时间应该是线性级别的。
*
*/
class
Program
{
static
void Main(string[] args)
{
double[] a = newdouble[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
题目
数组的局部最小元素。
编写一个程序，给定一个含有 N 个不同整数的数组，找到一个局部最小元素：
满足 a[i] < a[i-1]，且 a[i] < a[i+1] 的索引 i。
程序在最坏情况下所需的比较次数为 ~ 2lgN。
解答
和二分查找的方式类似，先确认中间的值是否是局部最小，如果不是，则向较小的一侧二分查找。
代码
using
System;
namespace
_1._4._18
{
/*
* 1.4.18
*
* 数组的局部最小元素。
* 编写一个程序，给定一个含有 N 个不同整数的数组，找到一个局部最小元素：
* 满足 a[i] < a[i-1]，且 a[i] < a[i+1] 的索引 i。
* 程序在最坏情况下所需的比较次数为 ~ 2lgN。
*
*/
class
Program
{
static
void Main(string[] args)
{
int[] a = newint[5] { 5, 6, 5, 3, 5 };
Console.WriteLine(LocalMinimum(a));
}
///<summary>/// 寻找数组的局部最小元素。
///</summary>///<param name="testcases">寻找范围。</param>///<returns>局部最小元素的值。</returns>staticint LocalMinimum(int[] testcases)
{
int lo = 0;
int hi = testcases.Length - 1;
int mid = (hi - lo) / 2 + lo;
while (lo < hi)
{
mid = (hi - lo) / 2 + lo;
if (testcases[mid] < testcases[mid - 1] && testcases[mid] < testcases[mid + 1])
{
return mid;
}
else
{
if (testcases[mid - 1] < testcases[mid + 1])
{
hi = mid - 1;
}
else
{
lo = mid + 1;
}
}
}
return -1;
}
}
}
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 成正比。
解答
算法过程类似于 “滑雪”，从数值较高的一侧向周围数值较小的一侧移动，直到到达“山谷”（局部最小）。
首先在中间行搜索最小值，再将最小值与其上下两个元素比较，如果不满足题意，则“滑向”较小的一侧，矩阵被分为了两半（上下两侧）。
在较小的一侧，找到中间列的最小值，再将最小值与其左右两个元素比较，如果不满足题意，类似的移动到较小的一侧（左右两侧）。
现在查找范围缩小到了原来矩阵的四分之一，递归的进行上述操作，最后可以得到答案。
每次查找最小值都是对行/列进行遍历，遍历耗时和 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 = newint[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));
}
///<summary>/// 在矩阵中间行查找局部最小。
///</summary>///<param name="matrix">矩阵。</param>///<param name="rowStart">实际查找范围的行起始。</param>///<param name="rowLength">实际查找范围的行结尾。</param>///<param name="colStart">实际查找范围的列起始。</param>///<param name="colLength">实际查找范围的列结尾。</param>///<returns>矩阵中的局部最小元素。</returns>staticint MinimumRow(int[,] matrix, int rowStart, int rowLength, int colStart, int colLength)
{
int min = int.MaxValue;
if (rowLength < 3)
returnint.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);
}
}
///<summary>/// 在矩阵中间列查找局部最小。
///</summary>///<param name="matrix">矩阵。</param>///<param name="rowStart">实际查找范围的行起始。</param>///<param name="rowLength">实际查找范围的行结尾。</param>///<param name="colStart">实际查找范围的列起始。</param>///<param name="colLength">实际查找范围的列结尾。</param>///<returns>矩阵中的局部最小元素。</returns>staticint 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
题目
双调查找。
如果一个数组中的所有元素是先递增后递减的，则称这个数组为双调的。
编写一个程序，给定一个含有 N 个不同 int 值的双调数组，判断它是否含有给定的整数。
程序在最坏情况下所需的比较次数为 ~3lgN。
解答
首先给出 BitMax 类的官方 Java 实现：BitonicMax.java。
我们使用这个类生成双调数组，并使用其中的 Max() 方法找到双调数组的最大值。
找到最大值之后分别对左右两侧进行二分查找，注意对于升序和降序的数组二分查找的实现有所不同。
代码
BitonicMax 类
using
System;
namespace
_1._4._20
{
///
<summary>
///
双调查找类。
///
</summary>
public
class
BitonicMax
{
///
<summary>
///
生成双调数组。
///
</summary>
///
<param name="N">
数组的大小。
</param>
///
<returns></returns>
public
static
int[] Bitonic(int N)
{
Random random = new Random();
int mid = random.Next(N);
int[] a = newint[N];
for (int i = 1; i < mid; ++i)
{
a[i] = a[i - 1] + 1 + random.Next(9);
}
if (mid > 0)
{
a[mid] = a[mid - 1] + random.Next(10) - 5;
}
for (int i = mid + 1; i < N; ++i)
{
a[i] = a[i - 1] - 1 - random.Next(9);
}
return a;
}
///<summary>/// 寻找数组中的最大值。
///</summary>///<param name="a">查找范围。</param>///<param name="lo">查找起始下标。</param>///<param name="hi">查找结束下标。</param>///<returns>返回数组中最大值的下标。</returns>publicstaticint 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);
}
elseif (rightside != -1)
{
Console.WriteLine(rightside);
}
else
{
Console.WriteLine("No Result");
}
}
///<summary>/// 对升序数组的二分查找。
///</summary>///<param name="a">升序数组。</param>///<param name="key">关键值。</param>///<param name="lo">查找的左边界。</param>///<param name="hi">查找的右边界。</param>///<returns>返回找到关键值的下标，如果没有找到则返回 -1。</returns>staticint 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;
}
elseif (a[mid] > key)
{
hi = mid - 1;
}
else
{
return mid;
}
}
return -1;
}
///<summary>/// 对降序数组的二分查找。
///</summary>///<param name="a">升序数组。</param>///<param name="key">关键值。</param>///<param name="lo">查找的左边界。</param>///<param name="hi">查找的右边界。</param>///<returns>返回找到关键值的下标，如果没有找到则返回 -1。</returns>staticint 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;
}
elseif (a[mid] < key)
{
hi = mid - 1;
}
else
{
return mid;
}
}
return -1;
}
}
}
1.4.21
题目
无重复值之中的二分查找。
用二分查找实现 StaticSETofInts （参见表 1.2.15），
保证 contains() 的运行时间为 ~lgR，其中 R 为参数数组中不同整数的数量。
解答
直接将 Contains() 实现为二分查找即可。
代码
///
<summary>
///
检查数组中是否存在指定元素。
///
</summary>
///
<param name="key">
要查找的值。
</param>
///
<returns>
存在则返回 true，否则返回 false。
</returns>
public
bool Contains(int key)
{
return Rank(key, 0, this.a.Length - 1) != -1;
}
///<summary>/// 二分查找。
///</summary>///<param name="key">关键值。</param>///<param name="lo">查找的起始下标。</param>///<param name="hi">查找的结束下标。</param>///<returns>返回关键值的下标，如果不存在则返回 -1。</returns>publicint Rank(int key, int lo, int hi)
{
while (lo <= hi)
{
int mid = (hi - lo) / 2 + lo;
if (key < this.a[mid])
hi = mid - 1;
elseif (key > this.a[mid])
lo = mid + 1;
elsereturn mid;
}
return -1;
}
1.4.22
题目
仅用加减实现的二分查找（Mihai Patrascu）。
编写一个程序，给定一个含有 N 个不同 int 值的按照升序排列的数组，判断它是否含有给定的整数。
只能使用加法和减法以及常数的额外内存空间。
程序的运行时间在最坏情况下应该和 logN 成正比。
解答
普通二分查找是通过除法不断减半缩小搜索范围。
这里我们用斐波那契数列来缩小范围。
举个例子，例如数组大小是 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。
递归上述过程即可完成查找。
代码
///
<summary>
///
使用斐波那契数列进行的查找。
///
</summary>
///
<param name="a">
查找范围。
</param>
///
<param name="key">
关键字。
</param>
///
<returns>
返回查找到的关键值下标，没有结果则返回 -1。
</returns>
static
int rank(int[] a, int key)
{
// 使用斐波那契数列作为缩减范围的依据int Fk = 1;
int Fk_1 = 1;
int Fk_2 = 0;
// 获得 Fk，Fk需要大于等于数组的大小，复杂度 lgNwhile (Fk < a.Length)
{
Fk = Fk + Fk_1;
Fk_1 = Fk_1 + Fk_2;
Fk_2 = Fk - Fk_1;
}
int lo = 0;
// 按照斐波那契数列缩减查找范围，复杂度 lgNwhile (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;
}
elseif (a[i] == key)
{
return i;
}
Fk = Fk_1;
Fk_1 = Fk_2;
Fk_2 = Fk - Fk_1;
}
return -1;
}
1.4.23
题目
分数的二分查找。
设计一个算法，使用对数级别的比较次数找出有理数 p/q，其中 0<p<q<N，
比较形式为给定的数是否小于 x?
解答
根据书中的提示，将二分查找中判断相等的条件改为两个数的差小于等于 1/N2。
代码
//
将二分查找中的相等判定条件修改为差值小于 x，其中 x = 1/N^2。
///
<summary>
///
二分查找。
///
</summary>
///
<param name="a">
查找范围。
</param>
///
<param name="key">
关键字。
</param>
///
<returns>
结果的下标，没有结果时返回 -1。
</returns>
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;
}
elseif (a[mid] < key)
{
lo = mid + 1;
}
else
{
hi = mid - 1;
}
}
return -1;
}
1.4.24
题目
扔鸡蛋。
假设你面前有一栋 N 层的大楼和许多鸡蛋，
假设将鸡蛋从 F 层或者更高的地方扔下鸡蛋才会摔碎，否则则不会。
首先，设计一种策略来确定 F 的值，其中扔 ~ lgN 次鸡蛋后摔碎的鸡蛋数量为 ~ lgN。
然后想办法将成本降低到~ 2lgF。
解答
第一问：二分查找即可。
第二问：
按照第 1, 2, 4, 8,..., 2^k 层顺序查找，一直到 2^k > F，
随后在 [2^(k - 1), 2^k] 范围中二分查找。
代码
这里建立了一个结构体用于返回测试结果：
struct
testResult
{
public
int F;// 找到的 F 值。publicint BrokenEggs;// 打碎的鸡蛋数。
}
用于测试的方法：
///
<summary>
///
扔鸡蛋，没碎返回 true，碎了返回 false。
///
</summary>
///
<param name="floor">
扔鸡蛋的高度。
</param>
///
<returns></returns>
static
bool ThrowEgg(int floor)
{
return floor <= F;
}
///<summary>/// 第一种方案。
///</summary>///<param name="a">大楼。</param>///<returns></returns>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;
}
///<summary>/// 第二种方案。
///</summary>///<param name="a">大楼。</param>///<returns></returns>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
题目
扔两个鸡蛋。
和上一题相同的问题，但现在假设你只有两个鸡蛋，而你的成本模型则是扔鸡蛋的次数。
设计一种策略，最多扔 2√(N) 次鸡蛋即可判断出 F 的值，
然后想办法把这个成本降低到 ~c√(F) 次。
这和查找命中（鸡蛋完好无损）比未命中（鸡蛋被摔碎）的成本小得多的情形类似。
解答
第一问：
第一个蛋按照 √(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 值publicint BrokenEggs;// 碎掉的鸡蛋数。publicint ThrowTimes;// 扔鸡蛋的次数。
}
之后是测试用的方法：
///
<summary>
///
扔鸡蛋，没碎返回 true，碎了返回 false。
///
</summary>
///
<param name="floor">
扔鸡蛋的高度。
</param>
///
<returns></returns>
static
bool ThrowEgg(int floor)
{
return floor <= F;
}
///<summary>/// 第一种方案。
///</summary>///<param name="a">大楼。</param>///<returns></returns>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;
}
///<summary>/// 第二种方案。
///</summary>///<param name="a">大楼。</param>///<returns></returns>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
题目
三点共线。
假设有一个算法，接受平面上的 N 个点并能够返回在同一直线上的三个点的组数。
证明你能够用这个算法解决 3-sum 问题。
解答
1.4.27
题目
两个栈实现的队列。
用两个栈实现一个队列，使得每个队列操作所需要的堆栈操作均摊后为一个常数。
解答
实现比较简单，想象两个栈背靠背接在一起，左侧栈负责出队，右侧栈负责入队。
当左侧栈为空时就把右侧栈中的元素倒到左侧栈，这个过程是 O(n) 的。
但在这个过程之前必然有 n 个元素入栈，均摊后即为 O(1)。
代码
namespace
_1._4._27
{
///
<summary>
///
用两个栈模拟的队列。
///
</summary>
///
<typeparam name="Item">
队列中的元素。
</typeparam>
class StackQueue<Item>
{
Stack<Item> H;//用于保存出队元素
Stack<Item> T;//用于保存入队元素///<summary>/// 构造一个队列。
///</summary>public StackQueue()
{
this.H = new Stack<Item>();
this.T = new Stack<Item>();
}
///<summary>/// 将栈 T 中的元素依次弹出并压入栈 H 中。
///</summary>privatevoid Reverse()
{
while (!this.T.IsEmpty())
{
this.H.Push(this.T.Pop());
}
}
///<summary>/// 将一个元素出队。
///</summary>///<returns></returns>public Item Dequeue()
{
//如果没有足够的出队元素，则将 T 中的元素移动过来if (this.H.IsEmpty())
{
Reverse();
}
returnthis.H.Pop();
}
///<summary>/// 将一个元素入队。
///</summary>///<param name="item">要入队的元素。</param>publicvoid Enqueue(Item item)
{
this.T.Push(item);
}
}
}
1.4.28
题目
一个队列实现的栈。
使用一个队列实现一个栈，使得每个栈操作所需的队列操作数量为线性级别。
解答
每次入队的时候将队列倒转，这样入队的元素就是第一个了。
代码
namespace
_1._4._28
{
///
<summary>
///
用一条队列模拟的栈。
///
</summary>
///
<typeparam name="Item">
栈中保存的元素。
</typeparam>
class QueueStack<Item>
{
Queue<Item> queue;
///<summary>/// 初始化一个栈。
///</summary>public QueueStack()
{
this.queue = new Queue<Item>();
}
///<summary>/// 向栈中添加一个元素。
///</summary>///<param name="item"></param>publicvoid 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());
}
}
///<summary>/// 从栈中弹出一个元素。
///</summary>///<returns></returns>public Item Pop()
{
returnthis.queue.Dequeue();
}
///<summary>/// 确定栈是否为空。
///</summary>///<returns></returns>publicbool IsEmpty()
{
returnthis.queue.IsEmpty();
}
}
}
1.4.29
题目
两个栈实现的 steque。
用两个栈实现一个 steque（请见练习 1.3.32），
使得每个 steque 操作所需的栈操作均摊后为一个常数。
解答
和用两个栈实现队列的方法类似。
push 的时候把右侧栈内容倒到左侧栈，之后再入栈。
pop 的时候也做相同操作，右侧栈内容进左侧栈，之后再出栈。
enqueue 的时候则将左侧栈内容倒到右侧栈，之后再入队。
代码
namespace
_1._4._29
{
///
<summary>
///
用两个栈模拟的 Steque。
///
</summary>
///
<typeparam name="Item">
Steque 中的元素类型。
</typeparam>
class StackSteque<Item>
{
Stack<Item> H;
Stack<Item> T;
///<summary>/// 初始化一个 Steque
///</summary>public StackSteque()
{
this.H = new Stack<Item>();
this.T = new Stack<Item>();
}
///<summary>/// 向栈中添加一个元素。
///</summary>///<param name="item"></param>publicvoid Push(Item item)
{
ReverseT();
this.H.Push(item);
}
///<summary>/// 将 T 中的元素弹出并压入到 H 中。
///</summary>privatevoid ReverseT()
{
while (!this.T.IsEmpty())
{
this.H.Push(this.T.Pop());
}
}
///<summary>/// 将 H 中的元素弹出并压入到 T 中。
///</summary>privatevoid ReverseH()
{
while (!this.H.IsEmpty())
{
this.T.Push(this.H.Pop());
}
}
///<summary>/// 从 Steque 中弹出一个元素。
///</summary>///<returns></returns>public Item Pop()
{
ReverseT();
returnthis.H.Pop();
}
///<summary>/// 在 Steque 尾部添加一个元素。
///</summary>///<param name="item"></param>publicvoid Enqueue(Item item)
{
ReverseH();
this.T.Push(item);
}
///<summary>/// 检查 Steque 是否为空。
///</summary>///<returns></returns>publicbool IsEmpty()
{
returnthis.H.IsEmpty() && this.T.IsEmpty();
}
}
}
1.4.30
题目
一个栈和一个 steque 实现的双向队列。
使用一个栈和一个 steque 实现一个双向队列（请见练习 1.3.32），
使得双向队列的每个操作所需的栈和 steque 操作均摊后为一个常数。
解答
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
{
///
<summary>
///
用一个栈和一个 Steque 模拟的双向队列。
///
</summary>
///
<typeparam name="Item">
双向队列中保存的元素类型。
</typeparam>
class Deque<Item>
{
Stack<Item> stack;//代表队列尾部
Steque<Item> steque;//代表队列头部///<summary>/// 创建一条空的双向队列。
///</summary>public Deque()
{
this.stack = new Stack<Item>();
this.steque = new Steque<Item>();
}
///<summary>/// 在左侧插入一个新元素。
///</summary>///<param name="item">要插入的元素。</param>publicvoid PushLeft(Item item)
{
this.steque.Push(item);
}
///<summary>/// 将栈中的内容移动到 Steque 中。
///</summary>privatevoid StackToSteque()
{
while (!this.stack.IsEmpty())
{
this.steque.Push(this.stack.Pop());
}
}
///<summary>/// 将 Steque 中的内容移动到栈中。
///</summary>privatevoid StequeToStack()
{
while (!this.steque.IsEmpty())
{
this.stack.Push(this.steque.Pop());
}
}
///<summary>/// 从双向队列左侧弹出一个元素。
///</summary>///<returns></returns>public Item PopLeft()
{
if (this.steque.IsEmpty())
{
StackToSteque();
}
returnthis.steque.Pop();
}
///<summary>/// 向双向队列右侧添加一个元素。
///</summary>///<param name="item">要插入的元素。</param>publicvoid PushRight(Item item)
{
if (this.stack.IsEmpty())
{
this.steque.Enqueue(item);
}
else
{
this.stack.Push(item);
}
}
///<summary>/// 从双向队列右侧弹出一个元素。
///</summary>///<returns></returns>public Item PopRight()
{
if (this.stack.IsEmpty())
{
StequeToStack();
}
returnthis.stack.Pop();
}
///<summary>/// 判断队列是否为空。
///</summary>///<returns></returns>publicbool IsEmpty()
{
returnthis.stack.IsEmpty() && this.steque.IsEmpty();
}
///<summary>/// 返回队列中元素的数量。
///</summary>///<returns></returns>publicint Size()
{
returnthis.stack.Size() + this.steque.Size();
}
}
}
1.4.31
题目
三个栈实现的双向队列。
使用三个栈实现一个双向队列，使得双向队列的每个操作所需的栈操作均摊之后为一个常数。
解答
三个栈分别命名为左中右。
左侧栈和右侧栈负责模拟队列，和用两个栈模拟队列的方法类似。
由于是双向队列，左栈和右栈会频繁的倒来倒去，因此每次都只倒一半的元素可以有效减少开销。
有一侧栈为空时，另一侧栈中上半部分先移动到中间栈中，下半部分倒到另一侧栈里，再从中间栈拿回上半部分元素。
这样可以确保接下来的 pop 操作一定是常数级别的。
代码
namespace
_1._4._31
{
///
<summary>
///
用三个栈模拟的双向队列。
///
</summary>
///
<typeparam name="Item">
双向队列中的元素。
</typeparam>
class Deque<Item>
{
Stack<Item> left;
Stack<Item> middle;
Stack<Item> right;
///<summary>/// 构造一条新的双向队列。
///</summary>public Deque()
{
this.left = new Stack<Item>();
this.middle = new Stack<Item>();
this.right = new Stack<Item>();
}
///<summary>/// 向双向队列左侧插入一个元素。
///</summary>///<param name="item">要插入的元素。</param>publicvoid PushLeft(Item item)
{
this.left.Push(item);
}
///<summary>/// 向双向队列右侧插入一个元素。
///</summary>///<param name="item">要插入的元素。</param>publicvoid PushRight(Item item)
{
this.right.Push(item);
}
///<summary>/// 当一侧栈为空时，将另一侧的下半部分元素移动过来。
///</summary>///<param name="source">不为空的栈。</param>///<param name="destination">空栈。</param>privatevoid Move(Stack<Item> source, Stack<Item> destination)
{
int n = source.Size();
// 将上半部分元素移动到临时栈 middlefor (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());
}
}
///<summary>/// 检查双端队列是否为空。
///</summary>///<returns></returns>publicbool IsEmpty()
{
returnthis.right.IsEmpty() && this.middle.IsEmpty() && this.left.IsEmpty();
}
///<summary>/// 从右侧弹出一个元素。
///</summary>///<returns></returns>public Item PopRight()
{
if (this.right.IsEmpty())
{
Move(this.left, this.right);
}
returnthis.right.Pop();
}
///<summary>/// 从左侧弹出一个元素。
///</summary>///<returns></returns>public Item PopLeft()
{
if (this.left.IsEmpty())
{
Move(this.right, this.left);
}
returnthis.left.Pop();
}
///<summary>/// 返回双端队列的大小。
///</summary>///<returns></returns>publicint Size()
{
returnthis.left.Size() + this.middle.Size() + this.right.Size();
}
}
}
1.4.32
题目
均摊分析。
请证明，对一个基于大小可变的数组实现的空栈的 M 次操作访问数组的次数和 M 成正比。
解答
首先，不需要扩容数组的的操作都只需访问数组一次，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
题目
32位计算机中的内存需求。
给出 32 位计算机中 Integer、Date、Counter、int[]、double[]、double[][]、String、Node 和 Stack（链表表示）对象所需的内存，
设引用需要 4 字节，表示对象的开销为 8 字节，所需内存均会被填充为 4 字节的倍数。
解答
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 到 N 之间的一个秘密的整数。
每次猜完一个整数后，你会直到你的猜测距离该秘密整数是否相等（如果是则游戏结束）。
如果不相等，你会知道你的猜测相比上一次猜测距离秘密整数是比较热（接近），还是比较冷（远离）。
设计一个算法在 ~2lgN 之内找到这个秘密整数，然后设计一个算法在 ~1lgN 之内找到这个秘密整数。
解答
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
{
///
<summary>
///
某次猜测的结果。
///
</summary>
enum
GuessResult
{
Hot = 1, // 比上次猜测更接近目标。
Equal = 0, // 猜中目标。
Cold = -1, // 比上次猜测更远离目标。
FirstGuess = -2// 第一次猜测。 }
///<summary>/// 游戏类。
///</summary>class Game
{
publicint N { get; } // 目标值的最大范围。publicint SecretNumber { get; } // 目标值。publicint LastGuess { get; privateset; } // 上次猜测的值///<summary>/// 构造函数，新开一局游戏。
///</summary>///<param name="N">目标值的最大范围。</param>public Game(int N)
{
Random random = new Random();
this.N = N;
this.SecretNumber = random.Next(N - 1) + 1;
this.LastGuess = -1;
}
///<summary>/// 猜测，根据与上次相比更为接近还是远离目标值返回结果。
///</summary>///<param name="guess">本次的猜测值</param>///<returns>接近或不变返回 Hot，远离则返回 Cold，猜中返回 Equal。</returns>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;
}
}
///<summary>/// 重置游戏，清空上次猜测的记录。目标值和最大值都不变。
///</summary>publicvoid Restart()
{
this.LastGuess = -1;
}
}
}
之后是实际测试的方法：
using
System;
namespace
_1._4._34
{
/*
* 1.4.34
*
* 热还是冷。
* 你的目标是猜出 1 到 N 之间的一个秘密的整数。
* 每次猜完一个整数后，你会直到你的猜测距离该秘密整数是否相等（如果是则游戏结束）。
* 如果不相等，你会知道你的猜测相比上一次猜测距离秘密整数是比较热（接近），还是比较冷（远离）。
* 设计一个算法在 ~2lgN 之内找到这个秘密整数，然后设计一个算法在 ~1lgN 之内找到这个秘密整数。
*
*/
class
Program
{
///
<summary>
///
某种方案的测试结果，包含猜测结果和尝试次数。
///
</summary>
struct
TestResult
{
public
int SecretNumber;// 猜测到的数字。publicint TryTimes;// 尝试次数。 }
staticvoid 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}");
}
///<summary>/// 方案一，用二分查找实现，需要猜测 2lgN 次。
///</summary>///<param name="game">用于猜测的游戏对象。</param>///<returns>返回测试结果，包含猜测结果和尝试次数。</returns>static TestResult PlayGameA(Game game)
{
TestResult result;
result.TryTimes = 0;
result.SecretNumber = 0;
GuessResult guessResult;
int hi = game.N;
int lo = 1;
// 利用二分查找猜测，2lgNwhile (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;
}
elseif (guessResult == GuessResult.Hot)
{
lo = mid;
}
else
{
hi = mid;
}
}
return result;
}
///<summary>/// 方案二，根据 (lastGuess + nowGuess)/2 = (lo + hi) / 2 确定每次猜测的值。
///</summary>///<param name="game">用于猜测的游戏对象。</param>///<returns>返回测试结果，包含猜测结果和尝试次数。</returns>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;
}
elseif (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;
}
elseif (game.Guess(hi) == GuessResult.Equal)
{
result.TryTimes++;
result.SecretNumber = hi;
}
return result;
}
}
}
1.4.35
题目
下压栈的时间成本。
解释下表中的数据，它显示了各种下压栈的实现的一般时间成本，
其中成本模型会同时记录数据引用的数量
（指向被压入栈之中的数据的引用，指向的可能是数组，也可能是某个对象的实例变量）
和被创建的变量数量。
| 数据结构 | 元素类型 | 数据的引用 | 创建的对象 |
|---|---|---|---|
| 基于链表 | int | 2N | N |
| 基于链表 | Integer | 3N | 2N |
| 基于大小可变的数组 | int | ~5N | lgN |
| 基于大小可变的数组 | Integer | ~5N | ~N |
解答
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 = ~5N
4. 创建引用和上题一样，创建对象则多出了装箱过程，每次 push 都会新建一个 Integer 对象，N + lgN = ~N。
1.4.36
题目
下压栈的空间成本。
解释下表中的数据，它显示了各种下压栈实现的一般空间成本，
其中链表的结点为一个静态的嵌套类，从而避免非静态嵌套类的开销。
| 数据结构 | 元素类型 | N 个 int 值所需的空间（字节） |
|---|---|---|
| 基于链表 | int | ~32N |
| 基于链表 | Integer | ~56N |
| 基于大小可变的数组 | int | ~4N到~16N之间 |
| 基于大小可变的数组 | Integer | ~32N到~56N之间 |
解答
1. N 个 Node<int> 对象的空间开销
= N * (16(对象开销) + 4(int) + 8(下一个 Node 的引用) + 4(填充字节)) = 32N
2. 比起上一题来说，空间开销变为
= 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，并使用类似 DoublingRatio 的用例比较它和泛型 FixedCapacityStack 在进行大量 push() 和 pop() 时的性能。
解答
数据量比较大时才会有比较明显的差距。
代码
FixedCapacityStackOfInts，根据 FixedCapacityOfString 修改而来：
using
System;
using
System.Collections;
using
System.Collections.Generic;
namespace
_1._4._37
{
///
<summary>
///
固定大小的整型数据栈。
///
</summary>
class FixedCapacityStackOfInts : IEnumerable<int>
{
privateint[] a;
privateint N;
///<summary>/// 默认构造函数。
///</summary>///<param name="capacity">栈的大小。</param>public FixedCapacityStackOfInts(int capacity)
{
this.a = newint[capacity];
this.N = 0;
}
///<summary>/// 检查栈是否为空。
///</summary>///<returns></returns>publicbool IsEmpty()
{
returnthis.N == 0;
}
///<summary>/// 检查栈是否已满。
///</summary>///<returns></returns>publicbool IsFull()
{
returnthis.N == this.a.Length;
}
///<summary>/// 将一个元素压入栈中。
///</summary>///<param name="item">要压入栈中的元素。</param>publicvoid Push(int item)
{
this.a[this.N] = item;
this.N++;
}
///<summary>/// 从栈中弹出一个元素，返回被弹出的元素。
///</summary>///<returns></returns>publicint Pop()
{
this.N--;
returnthis.a[this.N];
}
///<summary>/// 返回栈顶元素（但不弹出它）。
///</summary>///<returns></returns>publicint Peek()
{
returnthis.a[this.N - 1];
}
public IEnumerator<int> GetEnumerator()
{
returnnew ReverseEnmerator(this.a);
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
privateclass ReverseEnmerator : IEnumerator<int>
{
privateint current;
privateint[] a;
public ReverseEnmerator(int[] a)
{
this.current = a.Length;
this.a = a;
}
int IEnumerator<int>.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)
returnfalse;
this.current--;
returntrue;
}
void IEnumerator.Reset()
{
this.current = this.a.Length;
}
}
}
}
FixedCapacityStack<Item>
using
System;
using
System.Collections;
using
System.Collections.Generic;
namespace
_1._4._37
{
///
<summary>
///
固定大小的栈。
///
</summary>
class FixedCapacityStack<Item> : IEnumerable<Item>
{
private Item[] a;
privateint N;
///<summary>/// 默认构造函数。
///</summary>///<param name="capacity">栈的大小。</param>public FixedCapacityStack(int capacity)
{
this.a = new Item[capacity];
this.N = 0;
}
///<summary>/// 检查栈是否为空。
///</summary>///<returns></returns>publicbool IsEmpty()
{
returnthis.N == 0;
}
///<summary>/// 检查栈是否已满。
///</summary>///<returns></returns>publicbool IsFull()
{
returnthis.N == this.a.Length;
}
///<summary>/// 将一个元素压入栈中。
///</summary>///<param name="item">要压入栈中的元素。</param>publicvoid Push(Item item)
{
this.a[this.N] = item;
this.N++;
}
///<summary>/// 从栈中弹出一个元素，返回被弹出的元素。
///</summary>///<returns></returns>public Item Pop()
{
this.N--;
returnthis.a[this.N];
}
///<summary>/// 返回栈顶元素（但不弹出它）。
///</summary>///<returns></returns>public Item Peek()
{
returnthis.a[this.N - 1];
}
public IEnumerator<Item> GetEnumerator()
{
returnnew ReverseEnmerator(this.a);
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
privateclass ReverseEnmerator : IEnumerator<Item>
{
privateint current;
private Item[] a;
public ReverseEnmerator(Item[] a)
{
this.current = a.Length;
this.a = a;
}
Item IEnumerator<Item>.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)
returnfalse;
this.current--;
returntrue;
}
void IEnumerator.Reset()
{
this.current = this.a.Length;
}
}
}
}
测试函数：
using
System;
using
Measurement;
namespace
_1._4._37
{
///
<summary>
///
FixedCapacityStackOfInts 测试类。
///
</summary>
public
static
class
DoubleTest
{
private
static
readonly
int MAXIMUM_INTEGER = 1000000;
///<summary>/// 返回对 n 个随机整数的栈进行 n 次 push 和 n 次 pop 所需的时间。
///</summary>///<param name="n">随机数组的长度。</param>///<returns></returns>publicstaticdouble TimeTrial(int n)
{
int[] a = newint[n];
FixedCapacityStackOfInts stack = new FixedCapacityStackOfInts(n);
Random random = new Random(DateTime.Now.Millisecond);
for (int i = 0; i < n; ++i)
{
a[i] = random.Next(-MAXIMUM_INTEGER, MAXIMUM_INTEGER);
}
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();
}
///<summary>/// 返回对 n 个随机整数的栈进行 n 次 push 和 n 次 pop 所需的时间。
///</summary>///<param name="n">随机数组的长度。</param>///<returns></returns>publicstaticdouble TimeTrialGeneric(int n)
{
int[] a = newint[n];
FixedCapacityStack<int> stack = new FixedCapacityStack<int>(n);
Random random = new Random(DateTime.Now.Millisecond);
for (int i = 0; i < n; ++i)
{
a[i] = random.Next(-MAXIMUM_INTEGER, MAXIMUM_INTEGER);
}
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();
}
}
}
主函数：
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
题目
3-sum 的初级算法的实现。
通过实验评估以下 ThreeSum 内循环的实现性能。
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 (a[i] + a[j] + a[k] == 0)
cnt++;
为此实现另一个版本的 DoublingTest，计算该程序和 ThreeSum 的运行时间的比例。
解答
把 DoublingTest 中调用的函数稍作修改即可。
代码
ThreeSum 测试类
using
System;
namespace
_1._4._38
{
///
<summary>
///
ThreeSum 测试类。
///
</summary>
public
static
class
DoubleTest
{
private
static
readonly
int MAXIMUM_INTEGER = 1000000;
///<summary>/// 返回对 n 个随机整数的数组进行一次 ThreeSum 所需的时间。
///</summary>///<param name="n">随机数组的长度。</param>///<returns></returns>publicstaticdouble TimeTrial(int n)
{
int[] a = newint[n];
Random random = new Random(DateTime.Now.Millisecond);
for (int i = 0; i < n; ++i)
{
a[i] = random.Next(-MAXIMUM_INTEGER, MAXIMUM_INTEGER);
}
Measurement.Stopwatch timer = new Measurement.Stopwatch();
ThreeSum.Count(a);
return timer.ElapsedTime();
}
}
}
ThreeSum
using
System;
namespace
_1._4._38
{
///
<summary>
///
用暴力方法寻找数组中和为零的三元组。
///
</summary>
public
static
class
ThreeSum
{
///
<summary>
///
输出所有和为零的三元组。
///
</summary>
///
<param name="a">
输入数组。
</param>
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]}");
}
}
}
}
}
}
///<summary>/// 计算和为零的三元组的数量。
///</summary>///<param name="a">输入数组。</param>///<returns></returns>publicstaticint Count(int[] a)
{
int n = a.Length;
int count = 0;
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)
{
count++;
}
}
}
}
}
return count;
}
}
}
1.4.39
题目
改进倍率测试的精度。
修改 DoublingRatio，使它接受另一个命令行参数来指定对于每个 N 值调用 timeTrial() 方法的次数。
用程序对每个 N 执行 10、100 和 1000 遍实验并评估结果的准确程度。
解答
执行 N 次后取平均即可。
代码
修改后的 DoublingTest：
using
System;
using
Measurement;
namespace
_1._4._39
{
///
<summary>
///
ThreeSum 测试类。
///
</summary>
public
static
class
DoubleTest
{
private
static
readonly
int MAXIMUM_INTEGER = 1000000;
///<summary>/// 返回对 n 个随机整数的数组进行一次 ThreeSum 所需的时间。
///</summary>///<param name="n">随机数组的长度。</param>///<param name="repeatTimes">重复测试的次数。</param>///<returns></returns>publicstaticdouble TimeTrial(int n, int repeatTimes)
{
int[] a = newint[n];
double sum = 0;
Random random = new Random(DateTime.Now.Millisecond);
for (int i = 0; i < n; ++i)
{
a[i] = random.Next(-MAXIMUM_INTEGER, MAXIMUM_INTEGER);
}
for (int i = 0; i < repeatTimes; ++i)
{
Stopwatch timer = new Stopwatch();
ThreeSum.Count(a);
sum += timer.ElapsedTime();
}
return sum / repeatTimes;
}
}
}
1.4.40
题目
随机输入下的 3-sum 问题。
猜测找出 N 个随机 int 值中和为 0 的整数三元组的数量所需的时间并验证你的猜想。
如果你擅长数学分析，请为此问题给出一个合适的数学模型，
其中所有值均匀的分布在 -M 和 M 之间，且 M 不能是一个小整数。
解答
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 = newint[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 估计在你的计算机上用 TwoSumFast、TwoSum、ThreeSumFast 以及 ThreeSum 处理一个含有 100 万个整数的文件所需的时间。
解答
代码
这里使用了委托来简化代码。
DoublingRatio
using
System;
using
Measurement;
namespace
_1._4._41
{
public
delegate
int Count(int[] a);
staticclass DoublingRatio
{
///<summary>/// 从指定字符串中读入按行分割的整型数据。
///</summary>///<param name="inputString">源字符串。</param>///<returns>读入的整型数组</returns>privatestaticint[] ReadAllInts(string inputString)
{
char[] split = newchar[1] { ‘\n‘ };
string[] input = inputString.Split(split, StringSplitOptions.RemoveEmptyEntries);
int[] a = newint[input.Length];
for (int i = 0; i < a.Length; ++i)
{
a[i] = int.Parse(input[i]);
}
return a;
}
///<summary>/// 使用给定的数组进行一次测试，返回耗时（毫秒）。
///</summary>///<param name="Count">要测试的方法。</param>///<param name="a">测试用的数组。</param>///<returns>耗时（秒）。</returns>publicstaticdouble TimeTrial(Count Count, int[] a)
{
Stopwatch timer = new Stopwatch();
Count(a);
return timer.ElapsedTimeMillionSeconds();
}
///<summary>/// 对 TwoSum、TwoSumFast、ThreeSum 或 ThreeSumFast 的 Count 方法做测试。
///</summary>///<param name="Count">相应类的 Count 方法</param>///<returns>随着数据量倍增，方法耗时增加的比率。</returns>publicstaticdouble Test(Count Count)
{
double ratio = 0;
double times = 3;
// 1Kint[] 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;
}
publicstaticdouble TestTwoSumFast(Count Count)
{
double ratio = 0;
double times = 2;
// 8Kint[] 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 = newint[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 = newint[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
题目
问题规模。
设在你的计算机上用 TwoSumFast、TwoSum、ThreeSumFast 以及 ThreeSum 能够处理的问题规模为 2^P × 10^3 个整数。
使用 DoublingRatio 估计 P 的最大值。
解答
这里我们把时限设置为一小时，使用上一题的数据估计。
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
题目
大小可变的数组与链表。
通过实验验证对于栈来说基于大小可变的数组的实现快于基于链表的实现的猜想（请见练习 1.4.35 和练习 1.4.36）。
为此实现另一个版本的 DoublingRatio，计算两个程序的运行时间的比例。
解答
代码
修改后的 DoublingRatio
using
System;
using
Measurement;
namespace
_1._4._43
{
static
class
DoublingRatio
{
///
<summary>
///
从指定字符串中读入按行分割的整型数据。
///
</summary>
///
<param name="inputString">
源字符串。
</param>
///
<returns>
读入的整型数组
</returns>
private
static
int[] ReadAllInts(string inputString)
{
char[] split = newchar[1] { ‘\n‘ };
string[] input = inputString.Split(split, StringSplitOptions.RemoveEmptyEntries);
int[] a = newint[input.Length];
for (int i = 0; i < a.Length; ++i)
{
a[i] = int.Parse(input[i]);
}
return a;
}
///<summary>/// 使用给定的数组对链栈进行一次测试，返回耗时（毫秒）。
///</summary>///<param name="a">测试用的数组。</param>///<returns>耗时（毫秒）。</returns>publicstaticdouble TimeTrialLinkedStack(int[] a)
{
LinkedStack<int> stack = new LinkedStack<int>();
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();
}
///<summary>/// 使用给定的数组对数组栈进行一次测试，返回耗时（毫秒）。
///</summary>///<param name="a">测试用的数组。</param>///<returns>耗时（毫秒）。</returns>publicstaticdouble TimeTrialDoublingStack(int[] a)
{
DoublingStack<int> stack = new DoublingStack<int>();
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();
}
///<summary>/// 对链栈和基于大小可变的数组栈做测试。
///</summary>publicstaticvoid Test()
{
double linkedTime = 0;
double arrayTime = 0;
Console.WriteLine("数据量\t链栈\t数组\t比值\t单位：毫秒");
// 16Kint[] 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
题目
生日问题。
编写一个程序，从命令行接受一个整数 N 作为参数并使用 StdRandom.uniform() 生成一系列 0 到 N-1 之间的随机整数。
通过实验验证产生第一个重复的随机数之前生成的整数数量为 ~√(πN/2)。
解答
每生成一个随机数都和之前生成过的随机数相比较。
代码
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 = newint[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}个数字后出现重复");
}
///<summary>/// 检查是否有重复的数字出现。
///</summary>///<param name="a">需要检查的数组。</param>///<param name="i">当前加入数组元素的下标。</param>///<returns>有重复则返回 true，否则返回 false。</returns>staticbool IsDuplicated(int[] a, int i)
{
for (int j = 0; j < i; ++j)
{
if (a[j] == a[i])
{
returntrue;
}
}
returnfalse;
}
}
}
1.4.45
题目
优惠券收集问题。
用和上一题相同的方式生成随机整数。
通过实验验证生成所有可能的整数值所需生成的随机数总量为 ~NHN（调和级数）。
解答
建立一个布尔数组，将每次随机出来的数作为下标，将相应位置的布尔值改为 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 = newbool[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}个数字后所有可能都出现");
}
///<summary>/// 计算 N 阶调和级数的和。
///</summary>///<param name="N">调和级数的 N 值</param>///<returns>N 阶调和级数的和。</returns>staticdouble HarmonicSum(int N)
{
double sum = 0;
for (int i = 1; i <= N; ++i)
{
sum += 1.0 / i;
}
return sum;
}
///<summary>/// 检查所有数字是否都生成过了。
///</summary>///<param name="a">布尔数组。</param>///<returns>全都生成则返回 true，否则返回 false。</returns>staticbool IsAllGenerated(bool[] a)
{
foreach (bool i in a)
{
if (!i)
returnfalse;
}
returntrue;
}
}
}
原文：http://www.cnblogs.com/ikesnowy/p/7467994.html
内容总结
以上是互联网集市为您收集整理的算法（第四版）C#题解——1.4全部内容，希望文章能够帮你解决算法（第四版）C#题解——1.4所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。