写在前面
整个项目都托管在了 Github 上：https://github.com/ikesnowy/Algorithms-4th-Edition-in-Csharp
这一节内容可能会用到的库文件有 Geometry 和 Commercial，同样在 Github 上可以找到。
善用 Ctrl + F 查找题目。
习题 & 题解
练习（1.2.1~1.2.14）
1.2.1
解答
这里自己实现了一个 Point2D 类（包含在了 Geometry 库中）。
JAVA 版本参考：http://algs4.cs.princeton.edu/12oop/Point2D.java.html。
求最近两点只需要反复调用 Point2D 类中的 DistTo() 方法就可以了。
代码
Point2D 类
/// <summary>
/// Point2D 二维点类。
/// </summary>
public sealed class Point2D : IComparable<Point2D>
{
public readonly static Comparer<Point2D> X_Order = new XOrder();
public readonly static Comparer<Point2D> Y_Order = new YOrder();
public readonly static Comparer<Point2D> R_Order = new ROrder(); public double X { get; }
public double Y { get; }
public int Radius { get; set; } public Point2D(double x, double y)
{
if (double.IsInfinity(x) || double.IsInfinity(y))
{
throw new ArgumentException("x, y must be finite");
} if (double.IsNaN(x) || double.IsNaN(y))
{
throw new ArgumentNullException("Coordinate cannot be NaN");
} this.X = x;
this.Y = y;
this.Radius = ;
} /// <summary>
/// 返回极半径。
/// </summary>
/// <returns></returns>
public double R()
{
return Math.Sqrt(X * X + Y * Y);
} /// <summary>
/// 返回极角。
/// </summary>
/// <returns></returns>
public double Theta()
{
return Math.Atan2(Y, X);
} /// <summary>
/// 返回两个点之间的角度。
/// </summary>
/// <param name="that">要计算角度的另一个点。</param>
/// <returns></returns>
private double AngleTo(Point2D that)
{
double dx = that.X - this.X;
double dy = that.Y - this.Y;
return Math.Atan2(dy, dx);
} /// <summary>
/// 判断 a,b,c 三个点的关系，如果 {顺时针, 共线, 逆时针} 则返回 {-1, 0, 1}。
/// </summary>
/// <param name="a">第一个点。</param>
/// <param name="b">第二个点。</param>
/// <param name="c">第三个点。</param>
/// <returns></returns>
public static int CCW(Point2D a, Point2D b, Point2D c)
{
double area2 = (b.X - a.X) * (c.Y - a.Y) - (b.Y - a.Y) * (c.X - a.X);
if (area2 < )
return -;
if (area2 > )
return ;
return ;
} /// <summary>
/// 返回 abc 三个点构成的三角形的面积的平方。
/// </summary>
/// <param name="a">第一个点。</param>
/// <param name="b">第二个点。</param>
/// <param name="c">第三个点。</param>
/// <returns></returns>
public static double Area2(Point2D a, Point2D b, Point2D c)
{
return (b.X - a.X) * (c.Y - a.Y) - (b.Y - a.Y) * (c.X - a.X);
} /// <summary>
/// 返回当前点到另一个点之间的距离。
/// </summary>
/// <param name="that">另一个点。</param>
/// <returns></returns>
public double DistanceTo(Point2D that)
{
double dx = this.X - that.X;
double dy = this.Y - that.Y; return Math.Sqrt(dx * dx + dy * dy);
} /// <summary>
/// 返回当前点到另一个点之间的距离的平方。
/// </summary>
/// <param name="that">另一个点。</param>
/// <returns></returns>
public double DistanceSquareTo(Point2D that)
{
double dx = this.X - that.X;
double dy = this.Y - that.Y; return dx * dx + dy * dy;
} /// <summary>
/// 绘制二维点。
/// </summary>
/// <param name="g">原点在左下方，y轴向上，x轴向右的画布。</param>
public void Draw(Graphics g)
{
g.FillEllipse(Brushes.Black, (int)X, (int)Y, Radius, Radius);
} /// <summary>
/// 实现 IComparable 接口。
/// </summary>
/// <param name="other">需要比较的另一个对象。</param>
/// <returns></returns>
public int CompareTo(Point2D other)
{
if (this.Y < other.Y)
return -;
if (this.Y > other.Y)
return ;
if (this.X < other.X)
return -;
if (this.X > other.X)
return ; return ;
} /// <summary>
/// 按照 X 顺序比较。
/// </summary>
private class XOrder : Comparer<Point2D>
{
public override int Compare(Point2D x, Point2D y)
{
if (x.X < y.X)
{
return -;
} if (x.X > y.X)
{
return ;
} return ;
}
} /// <summary>
/// 按照 Y 顺序比较。
/// </summary>
private class YOrder : Comparer<Point2D>
{
public override int Compare(Point2D x, Point2D y)
{
if (x.Y < y.Y)
{
return -;
}
if (x.Y > y.Y)
{
return ;
} return ;
}
} /// <summary>
/// 按照极径顺序比较。
/// </summary>
private class ROrder : Comparer<Point2D>
{
public override int Compare(Point2D x, Point2D y)
{
double delta = (x.X * x.X + x.Y * x.Y) - (y.X * y.X + y.Y * y.Y);
if (delta < )
{
return -;
} if (delta > )
{
return ;
} return ;
}
} /// <summary>
/// 按照 atan2 值顺序比较。
/// </summary>
private class Atan2Order : Comparer<Point2D>
{
private Point2D parent;
public Atan2Order() { }
public Atan2Order(Point2D parent)
{
this.parent = parent;
}
public override int Compare(Point2D x, Point2D y)
{
double angle1 = parent.AngleTo(x);
double angle2 = parent.AngleTo(y);
if (angle1 < angle2)
{
return -;
}
else if (angle1 > angle2)
{
return ;
}
else
{
return ;
}
}
} /// <summary>
/// 按照极角顺序比较。
/// </summary>
private class PolorOrder : Comparer<Point2D>
{
private Point2D parent;
public PolorOrder() { }
public PolorOrder(Point2D parent)
{
this.parent = parent;
}
public override int Compare(Point2D q1, Point2D q2)
{
double dx1 = q1.X - parent.X;
double dy1 = q1.Y - parent.Y;
double dx2 = q2.X - parent.X;
double dy2 = q2.Y - parent.Y; if (dy2 >= && dy2 < )
{
return -;
}
else if (dy2 >= && dy1 < )
{
return ;
}
else if (dy1 == && dy2 == )
{
if (dx1 >= && dx2 < )
{
return -;
}
else if (dx2 >= && dx1 < )
{
return ;
}
else
{
return ;
}
}
else
{
return -CCW(this.parent, q1, q2);
}
}
} /// <summary>
/// 按照距离顺序比较。
/// </summary>
private class DistanceToOrder : Comparer<Point2D>
{
private Point2D parent;
public DistanceToOrder() { }
public DistanceToOrder(Point2D parent)
{
this.parent = parent;
}
public override int Compare(Point2D p, Point2D q)
{
double dist1 = parent.DistanceSquareTo(p);
double dist2 = parent.DistanceSquareTo(q); if (dist1 < dist2)
{
return -;
}
else if (dist1 > dist2)
{
return ;
}
else
{
return ;
}
}
} public Comparer<Point2D> Polor_Order()
{
return new PolorOrder(this);
} public Comparer<Point2D> Atan2_Order()
{
return new Atan2Order(this);
} public Comparer<Point2D> DistanceTo_Order()
{
return new DistanceToOrder(this);
} public override bool Equals(object obj)
{
if (obj == this)
{
return true;
}
if (obj == null)
{
return false;
}
if (obj.GetType() != this.GetType())
{
return false;
}
Point2D that = (Point2D)obj;
return this.X == that.X && this.Y == that.Y;
} public override string ToString()
{
return "(" + X + ", " + Y + ")";
} public override int GetHashCode()
{
int hashX = X.GetHashCode();
int hashY = Y.GetHashCode();
return * hashX + hashY;
}
Main() 方法：
namespace _1._2._1
{
/*
* 1.2.1
*
* 编写一个 Point2D 的用例，从命令行接受一个整数 N。
* 在单位正方形中生成 N 个随机点，然后计算两点之间的最近距离。
*
*/
class Program
{
static void Main(string[] args)
{ Console.WriteLine("Type the value of N:");
int N = int.Parse(Console.ReadLine());
List<Point2D> pointlist = new List<Point2D>();
Random random = new Random(); if (N <= )
{
Console.WriteLine("Make sure there are 2 points at least");
return;
} //random.NextDouble() 返回一个 0~1 之间的 double 值
for (int i = ; i < N; ++i)
{
double x = random.NextDouble();
double y = random.NextDouble();
pointlist.Add(new Point2D(x, y));
} double min = pointlist[].DistanceTo(pointlist[]);
for (int i = ; i < N; ++i)
{
for (int j = i + ; j < N; ++j)
{
double temp = pointlist[i].DistanceTo(pointlist[j]);
Console.WriteLine($"Checking Distance({i}, {j}): {temp}");
if (temp < min)
{
min = temp;
}
}
} Console.WriteLine($"\nThe minimal distance is {min}");
}
}
}
1.2.2
解答
同样实现了一个 Interval1D 类（位于 Geometry 库）。
JAVA 版本参考：http://algs4.cs.princeton.edu/12oop/Interval1D.java.html。
直接调用其中的 Intersect() 方法即可
代码
Interval1D 类：
namespace Geometry
{
/// <summary>
/// 一维闭区间。
/// </summary>
public class Interval1D
{
public static readonly Comparer<Interval1D> Min_Order = new MinEndpointComparer();
public static readonly Comparer<Interval1D> Max_Order = new MaxEndpointComparer();
public static readonly Comparer<Interval1D> Length_Order = new LengthComparer(); public double Min { get; }
public double Max { get; } /// <summary>
/// 构造函数。
/// </summary>
/// <param name="lo">一维区域的下界。</param>
/// <param name="hi">一维区域的上界。</param>
public Interval1D(double lo, double hi)
{
if (double.IsInfinity(lo) || double.IsInfinity(hi))
{
throw new ArgumentException("Endpoints must be finite");
}
if (double.IsNaN(lo) || double.IsNaN(hi))
{
throw new ArgumentException("Endpoints cannot be NaN");
} if (lo <= hi)
{
this.Min = lo;
this.Max = hi;
}
else
{
throw new ArgumentException("Illegal interval");
}
} /// <summary>
/// 一维区域的长度。
/// </summary>
/// <returns>返回长度。</returns>
public double Length()
{
return this.Max - this.Min;
} /// <summary>
/// 判断目标区间是否被本区间包含。
/// </summary>
/// <param name="that">需要判断是否被包含的区间。</param>
/// <returns></returns>
public bool Contains(Interval1D that)
{
return this.Min < that.Min && this.Max > that.Max;
} /// <summary>
/// 目标值是否处在区域内。如果目标值在区域内则返回 True，否则返回 False。
/// </summary>
/// <param name="x">需要判断的值。</param>
/// <returns></returns>
public bool Contains(double x)
{
return x >= this.Min && x <= this.Max;
} /// <summary>
/// 判断两个区域是否相交。
/// </summary>
/// <param name="that">需要判断相交的另一个区域。</param>
/// <returns>如果相交则返回 True，否则返回 False。</returns>
public bool Intersect(Interval1D that)
{
if (this.Max < that.Min || that.Max < this.Min)
return false; return true;
} /// <summary>
/// 绘制一维区间。
/// </summary>
/// <param name="g">原点在左下方，y轴向上，x轴向右的画布。</param>
/// <param name="y">绘制一维区间的 y轴 坐标。</param>
public void Draw(Graphics g, int y)
{
Point A = new Point((int)Min, y);
Point B = new Point((int)Max, y);
g.DrawLine(Pens.Black, A, B);
} /// <summary>
/// 将区域转换为 string，返回形如 "[lo, hi]" 的字符串。
/// </summary>
/// <returns></returns>
public override string ToString()
{
string s = "[" + this.Min + ", " + this.Max + "]";
return s;
} /// <summary>
/// 判断两个区间是否相等。
/// </summary>
/// <param name="obj">相比较的区间。</param>
/// <returns></returns>
public override bool Equals(object obj)
{
if (obj == this)
{
return true;
}
if (obj == null)
{
return false;
}
if (obj.GetType() != this.GetType())
{
return false;
}
Interval1D that = (Interval1D)obj;
return this.Min == that.Min && this.Max == that.Max;
} /// <summary>
/// 返回区间的哈希代码。
/// </summary>
/// <returns></returns>
public override int GetHashCode()
{
int hash1 = Min.GetHashCode();
int hash2 = Max.GetHashCode();
return * hash1 + hash2;
} private class MinEndpointComparer : Comparer<Interval1D>
{
public override int Compare(Interval1D a, Interval1D b)
{
if (a.Min < b.Min)
{
return -;
}
else if (a.Min > b.Min)
{
return ;
}
else if (a.Max < b.Max)
{
return -;
}
else if (a.Max > b.Max)
{
return ;
}
else
{
return ;
}
}
} private class MaxEndpointComparer : Comparer<Interval1D>
{
public override int Compare(Interval1D a, Interval1D b)
{
if (a.Max < b.Max)
{
return -;
}
else if (a.Max > b.Max)
{
return ;
}
else if (a.Min < b.Min)
{
return -;
}
else if (a.Min > b.Min)
{
return ;
}
else
{
return ;
}
}
} private class LengthComparer : Comparer<Interval1D>
{
public override int Compare(Interval1D a, Interval1D b)
{
double alen = a.Length();
double blen = b.Length(); if (alen < blen)
{
return -;
}
else if (alen > blen)
{
return ;
}
else
{
return ;
}
}
}
}
}
Main() 方法：
namespace _1._2._2
{
/*
* 1.2.2
*
* 编写一个 Interval1D 的用例，从命令行接受一个整数 N。
* 从标准输入中读取 N 个间隔（每个间隔由一对 double 值定义）并打印出所有相交的间隔对。
*
*/
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Type the value of N:");
int N = int.Parse(Console.ReadLine());
List<Interval1D> intervalList = new List<Interval1D>(); if (N < )
{
Console.WriteLine("Make sure there are at least 2 Intervals");
return;
} //读取并建立间隔数组
Console.WriteLine("Type the data, make sure there is a space between two numbers.\nExample: 0.5 1");
for (int i = ; i < N; ++i)
{
string temp = Console.ReadLine();
double lo = double.Parse(temp.Split(' ')[]);
double hi = double.Parse(temp.Split(' ')[]); if (lo > hi)
{
double t = lo;
lo = hi;
hi = t;
} intervalList.Add(new Interval1D(lo, hi));
} //判断是否相交并输出
for (int i = ; i < N; ++i)
{
for (int j = i + ; j < N; ++j)
{
if (intervalList[i].Intersect(intervalList[j]))
{
Console.WriteLine($"{intervalList[i].ToString()} {intervalList[j].ToString()}");
}
}
}
}
}
}
1.2.3
解答
首先先实现一个 Interval2D 类（位于 Geometry 库），再使用窗体应用程序绘图。
JAVA 版本参考：http://algs4.cs.princeton.edu/12oop/Interval2D.java.html。
代码
Interval2D：
using System.Drawing; namespace Geometry
{
/// <summary>
/// 二维闭合区间。
/// </summary>
public class Interval2D
{
private readonly Interval1D X;
private readonly Interval1D Y; /// <summary>
/// 构造函数。
/// </summary>
/// <param name="x">x 轴上的范围。</param>
/// <param name="y">y 轴上的范围。</param>
public Interval2D(Interval1D x, Interval1D y)
{
this.X = x;
this.Y = y;
} /// <summary>
/// 判断两个平面是否相交。
/// </summary>
/// <param name="that">需要判断的另一个平面。</param>
/// <returns></returns>
public bool Intersects(Interval2D that)
{
if (!this.X.Intersect(that.X))
{
return false;
} if (!this.Y.Intersect(that.Y))
{
return false;
} return true;
} /// <summary>
/// 判断目标区间是否被本区间包含。
/// </summary>
/// <param name="that">需要判断是否被包含的区间。</param>
/// <returns></returns>
public bool Contains(Interval2D that)
{
return this.X.Contains(that.X) && this.Y.Contains(that.Y);
} /// <summary>
/// 判断一个二维点是否在该平面范围内。
/// </summary>
/// <param name="p">需要判断的二维点。</param>
/// <returns></returns>
public bool Contains(Point2D p)
{
return (this.X.Contains(p.X) && this.Y.Contains(p.Y));
} /// <summary>
/// 计算平面范围的面积。
/// </summary>
/// <returns></returns>
public double Area()
{
return this.X.Length() * this.Y.Length();
} /// <summary>
/// 在画布上绘制二维区间。
/// </summary>
/// <param name="g">原点在左下方，x轴向右，y轴向上的画布。</param>
public void Draw(Graphics g)
{
Rectangle rect = new Rectangle((int)this.X.Min, (int)this.Y.Min, (int)this.X.Length(), (int)this.Y.Length());
g.DrawRectangle(Pens.White, rect);
g.FillRectangle(Brushes.Black, rect);
} /// <summary>
/// 返回形如“[xmin, xmax] x [ymin, ymax]”的字符串。
/// </summary>
/// <returns></returns>
public override string ToString()
{
return X + "x" + Y;
} /// <summary>
/// 判断两个二维区间是否相等。
/// </summary>
/// <param name="obj">需要比较的另一个区间。</param>
/// <returns></returns>
public override bool Equals(object obj)
{
if (obj == this)
{
return true;
}
if (obj == null)
{
return false;
} if (obj.GetType() != this.GetType())
{
return false;
} Interval2D that = (Interval2D)obj; return this.X.Equals(that.X) && this.Y.Equals(that.Y);
} /// <summary>
/// 获取哈希值
/// </summary>
/// <returns></returns>
public override int GetHashCode()
{
int hash1 = this.X.GetHashCode();
int hash2 = this.Y.GetHashCode(); return * hash1 + hash2;
}
}
}
绘图方法：
/// <summary>
/// 主绘图函数。
/// </summary>
/// <param name="N">2D 间隔的数目。</param>
/// <param name="Min">分布范围的下界。（大于 0 且小于 1）</param>
/// <param name="Max">分布范围的上界。（大于 0 且小于 1）</param>
public static void StartDrawing(int N, double Min, double Max)
{
Interval2D[] list = new Interval2D[N];
Random random = new Random(); //开始绘图
Form2 drawPad = new Form2();
drawPad.Show();
Graphics graphics = drawPad.CreateGraphics(); //生成随机二维间隔
for (int i = ; i < N; ++i)
{
double x = random.NextDouble() * (Max - Min) + Min;
double y = random.NextDouble() * (Max - Min) + Min;
if (x >= y)
{
double temp = x;
x = y;
y = temp;
}
x *= drawPad.ClientRectangle.Width;
y *= drawPad.ClientRectangle.Width;
Interval1D tempx = new Interval1D(x, y); x = random.NextDouble() * (Max - Min) + Min;
y = random.NextDouble() * (Max - Min) + Min;
if (x >= y)
{
double temp = x;
x = y;
y = temp;
}
x *= drawPad.ClientRectangle.Height;
y *= drawPad.ClientRectangle.Height;
Interval1D tempy = new Interval1D(x, y); list[i] = new Interval2D(tempx, tempy);
} //计算相交和包含的数量
int intersectNum = ;
for (int i = ; i < N; ++i)
{
for (int j = i + ; j < N; ++j)
{
if (list[i].Intersects(list[j]))
{
intersectNum++;
}
}
} int containsNum = ;
for (int i = ; i < N; ++i)
{
for (int j = ; j < N; ++j)
{
if (i == j)
continue; if (list[i].Contains(list[j]))
{
containsNum++;
}
}
} //移动原点至左下方，翻转坐标系
graphics.TranslateTransform(, drawPad.ClientRectangle.Height);
graphics.ScaleTransform(, -); //绘制所有区间
foreach (Interval2D n in list)
{
n.Draw(graphics);
} //新建一个窗口，显示计算结果
MessageBox.Show($"相交的区间数：{intersectNum}, 包含的区间数：{containsNum}"); //清理资源
graphics.Dispose();
}
1.2.4
解答
在 C# 中，这段代码能够完成交换的工作，输出为：
world
hello
代码
using System; namespace _1._2._4
{
/*
* 1.2.4
*
* 以下这段代码会打印出什么？
* String string1 = "hello";
* String string2 = string1;
* string1 = "world";
* StdOut.println(string1);
* StdOut.println(string2);
*
*/
class Program
{
static void Main(string[] args)
{
string string1 = "hello";
string string2 = string1;
string1 = "world";
Console.WriteLine(string1);
Console.WriteLine(string2);
}
}
}
1.2.5
解答
string 类型中的 Uppercase() 以及 Substring() 都不会改变原有字符串，而是新建一个字符串。因此输出仍然为 Hello World。
代码
using System; namespace _1._2._5
{
/*
* 1.2.5
*
* 以下这段代码会打印出什么？
* String s = "Hello World";
* s.toUpperCase();
* s.substring(6, 11);
* StdOut.println(s);
*
*/
class Program
{
static void Main(string[] args)
{
string s = "Hello World";
s.ToUpper();
s.Substring(, );//C# 中两个参数分别代表子串起始下标和长度
Console.WriteLine(s);
}
}
}
1.2.6
解答
对于任意字符串 s，将其拆分成 s = s1 + s2（s2长度即为循环移动的位数）
其回环变位则为 s' = s2 + s1
显然 s' + s' = s2 + s1 + s2 + s1
即 s' + s' = s2 + s + s1，其中必定包含 s
例如 ABC 和 BCA， BCABCA 显然包含 ABC
代码
using System; namespace _1._2._6
{
/*
* 1.2.6
*
* 如果字符串 s 中的字符循环移动任意位置之后能够得到另一个字符串 t，
* 那么 s 就被称为 t 的回环变位（circular rotation）。
* 例如，ACTGACG 就是 TGACGAC 的一个回环变位，反之亦然。
* 判定这个条件在基因组序列的研究中是很重要的。
* 编写一个程序检查两个给定的字符串 s 和 t 是否互为回环变位。
* 提示：答案只需要一行用到 indexOf()、length() 和字符串连接的代码。
*
*/
class Program
{
static void Main(string[] args)
{
string s1 = "ACTGACG";
string s2 = "TGACGAC"; Console.WriteLine(Circular(s1, s2));
} //对于任意字符串 s，将其拆分成 s = s1 + s2（s2长度即为循环移动的位数）
//其回环变位则为 s' = s2 + s1
//显然 s' + s' = s2 + s1 + s2 + s1
//即 s' + s' = s2 + s + s1，其中必定包含 s
//例如 ABC 和 BCA， BCABCA 显然包含 ABC
static bool Circular(string s1, string s2)
{
return s1.Length == s2.Length && (s2 + s2).Contains(s1);
}
}
}
1.2.7
解答
递归交换字符顺序，最后返回反序的字符串。
Mystery(ABCD)=
Mystery(CD) + Mystery(AB)=
Mystery(D) + Mystery(C) + Mystery(B) + Mystery(A)=
DCBA
代码
using System; namespace _1._2._7
{
/*
* 1.2.7
*
* 以下递归函数的返回值是什么？
* public static String mystery(String s)
* {
* int N = s.length();
* if (N <= 1) return s;
* String a = s.substring(0, N/2);
* String b = s.substring(N/2, N);
* return mystery(b) + mystery(a);
* }
*
*/
class Program
{
static void Main(string[] args)
{
Console.WriteLine(Mystery("Hello1"));
} /// <summary>
/// 输出反向字符串。
/// </summary>
/// <param name="s">原字符串。</param>
/// <returns></returns>
public static string Mystery(string s)
{
int N = s.Length;
if (N <= )
return s;
string a = s.Substring(, N / );
string b = s.Substring(N / , N - N / ); return Mystery(b) + Mystery(a);
}
}
}
1.2.8
解答
作用就是交换两个数组。
但在 C# 或 JAVA 中，数组变量实际是数组的一个引用（类似于指针），交换两个引用的效率与数组大小无关，都是常数时间的。
代码
using System;
using System.IO; namespace _1._2._8
{
/*
* 1.2.8
*
* 设 a[] 和 b[] 均为长数百万的整型数组。以下代码的作用是什么？有效吗？
* int[] t = a; a = b; b = t;
*
*/
class Program
{
static void Main(string[] args)
{
//读取 largeW.txt
string[] allNums = File.ReadAllLines("largeW.txt");
int N = allNums.Length;
int[] a = new int[N];
int[] b = new int[N]; //数组 a 与数组 b 数字顺序相反
for (int i = ; i < N; ++i)
{
a[i] = int.Parse(allNums[i]);
b[N - i - ] = a[i];
} //输出前5个数字
Console.WriteLine("Before Swap");
Console.Write("a:");
for (int i = ; i < ; ++i)
{
Console.Write($" {a[i]}");
}
Console.WriteLine();
Console.Write("b:");
for (int i = ; i < ; ++i)
{
Console.Write($" {b[i]}");
}
Console.WriteLine(); //交换
int[] t = a;
a = b;
b = t; //再次输出
Console.WriteLine("After Swap");
Console.Write("a:");
for (int i = ; i < ; ++i)
{
Console.Write($" {a[i]}");
}
Console.WriteLine();
Console.Write("b:");
for (int i = ; i < ; ++i)
{
Console.Write($" {b[i]}");
}
Console.WriteLine();
}
}
}
1.2.9
解答
首先实现一个 Counter 类，随后使用非递归版本的 BinarySearch，每进行一次 While 循环就让 Counter 加一。
代码
Counter 类：
namespace _1._2._9
{
/// <summary>
/// 计数器类
/// </summary>
class Counter
{
private readonly string name;
private int count; /// <summary>
/// 构造函数。
/// </summary>
/// <param name="id">计数器的名称。</param>
public Counter(string id)
{
this.name = id;
} /// <summary>
/// 计数器加一。
/// </summary>
public void Increment()
{
count++;
} /// <summary>
/// 获取当前计数值。
/// </summary>
/// <returns></returns>
public int Tally()
{
return count;
} /// <summary>
/// 输出形如 “1 counter” 的字符串。
/// </summary>
/// <returns></returns>
public override string ToString()
{
return count + " " + name;
}
}
}
Main()：
using System;
using System.IO; namespace _1._2._9
{
/*
* 1.2.9
*
* 修改 BinarySearch（请见 1.1.10.1 节中的二分查找代码），
* 使用 Counter 统计在有查找中被检查的键的总数并在查找全部结束后打印该值。
* 提示：在 main() 中创建一个 Counter 对象并将它作为参数传递给 rank()
*
*/
class Program
{
//参考 1.1.10 节的代码
static void Main(string[] args)
{
Counter count = new Counter("BinarySearch"); //读取白名单
string[] whiteListString = File.ReadAllLines("tinyW.txt");
int[] whiteList = new int[whiteListString.Length]; for (int i = ; i < whiteListString.Length; ++i)
{
whiteList[i] = int.Parse(whiteListString[i]);
}
Array.Sort(whiteList); //读取查询值
string[] inputListString = File.ReadAllLines("tinyT.txt");
int[] inputList = new int[inputListString.Length]; for (int i = ; i < inputListString.Length; ++i)
{
inputList[i] = int.Parse(inputListString[i]);
} //对每一个查询值进行二分查找
foreach (int n in inputList)
{
int result = rank(n, whiteList, count);
//将不在白名单上的数据输出
if (result == -)
{
Console.WriteLine(n);
}
}
Console.WriteLine(); //输出查询数目
Console.WriteLine(count.Tally());
} static int rank(int key, int[] a, Counter count)
{
int lo = ;
int hi = a.Length - ;
while (lo <= hi)
{
int mid = lo + (hi - lo) / ;
count.Increment();
if (key < a[mid])
{
hi = mid - ;
}
else if (key > a[mid])
{
lo = mid + ;
}
else
{
return mid;
}
}
return -;
}
}
}
1.2.10
解答
在 Counter 类基础上修改即可。
代码
VisualCounter 类：
using System.Drawing; namespace _1._2._10
{
/// <summary>
/// 可视化计数器
/// </summary>
class VisualCounter
{
private readonly string name;
private int count;
private int max;
private int operatorTimes; /// <summary>
/// 构造函数。
/// </summary>
/// <param name="id">计数器的名称。</param>
/// <param name="max">计数器的最大值。</param>
/// <param name="operatorTimes">计数器的最大操作数。</param>
public VisualCounter(string id, int max, int operatorTimes)
{
this.name = id;
this.max = max;
this.operatorTimes = operatorTimes;
} /// <summary>
/// 计数器加一。
/// </summary>
public bool Increment()
{
if (operatorTimes <= )
return false;
if (count < max)
{
count++;
operatorTimes--;
}
return true;
} /// <summary>
/// 计数器减一。
/// </summary>
public bool Decreasement()
{
if (operatorTimes <= )
return false;
if (count > )
{
count--;
operatorTimes--;
}
return true;
} /// <summary>
/// 获取当前计数值。
/// </summary>
/// <returns></returns>
public int Tally()
{
return count;
} /// <summary>
/// 输出形如 “1 counter” 的字符串。
/// </summary>
/// <returns></returns>
public override string ToString()
{
return count + " " + name;
} /// <summary>
/// 绘制计数器的图形。
/// </summary>
/// <param name="g">画布。</param>
/// <param name="width">绘图区宽度。</param>
/// <param name="height">绘图区高度。</param>
/// <param name="font">显示的字体。</param>
public void Draw(Graphics g, int width, int height, Font font)
{
//清空画布
g.Clear(SystemColors.Control);
//将画布分为上 1/3 和下 2/3
RectangleF headPart = new RectangleF(, , width, height / );
Rectangle bodyPart = new Rectangle(, height / , (height * ) / , (height * ) / ); //绘图
g.DrawString($"计数：{count} 剩余操作数：{operatorTimes} 最大值：{max}", font, Brushes.Black, headPart);
g.FillPie(Brushes.Blue, bodyPart, , * (float)count / max);
}
}
}
Form2（绘图窗口）：
using System;
using System.Drawing;
using System.Windows.Forms; namespace _1._2._10
{
public partial class Form2 : Form
{
VisualCounter counter;
Graphics graphics;
public Form2(int N, int max)
{
InitializeComponent();
counter = new VisualCounter("count", max, N);
graphics = this.PaintArea.CreateGraphics();
} private void button1_Click(object sender, EventArgs e)
{
if (!counter.Increment())
{
this.ErrorLabel.Text = "操作数不足";
}
else
{
this.ErrorLabel.Text = "";
counter.Draw(graphics,this.PaintArea.Width, this.PaintArea.Height, this.Font);
}
} private void button2_Click(object sender, EventArgs e)
{
if (!counter.Decreasement())
{
this.ErrorLabel.Text = "操作数不足";
}
else
{
this.ErrorLabel.Text = "";
counter.Draw(graphics, this.PaintArea.Width, this.PaintArea.Height, this.Font);
}
}
}
}
1.2.11
解答
在构造函数开始时做一次判断，非法时抛出异常。
首先建立一个数组，数组的第 1 项至第 12 项的值就是每个月的天数。
再声明一个布尔类型的变量，用于标记是否是闰年。
代码
using System; namespace _1._2._11
{
class SmartDate
{
public int Month { get; }//月
public int Day { get; }//日
public int Year { get; }//年 //每个月对应的天数，第 0 位空出来
static private int[] dayOfMonth = { , , , , , , , , , , , , }; public SmartDate(int m, int d, int y)
{
if (Vaildation(m, d, y) == false)
throw new FormatException("Invaild Date");
this.Month = m;
this.Day = d;
this.Year = y;
} private bool Vaildation(int m, int d, int y)
{
if (y < )
return false; bool isLeapYear = false; if (m > || m < )
return false;
if (d < )
return false;
if (m == && d > && isLeapYear)
return false;
if (d > dayOfMonth[m])
return false; return true;
} private bool IsLeapYear(int y)
{
if (y % == )
return true;
if (y % != && y % == )
return true; return false;
} public override string ToString()
{
return this.Month + "/" + this.Day + "/" + this.Year;
}
}
}
1.2.12
解答
这里使用蔡勒公式来推算星期。
参考：http://www.cnblogs.com/mq0036/p/3534314.html
代码
/// <summary>
/// 计算当前日期是星期几，返回对应的星期名称。
/// </summary>
/// <returns></returns>
public string DayOfTheWeek()
{
int d = this.Day;
int m = this.Month;
int y = this.Year; if (m < )
{
m += ;
y--;
} //使用蔡勒公式计算，参见 http://www.cnblogs.com/mq0036/p/3534314.html
int w = (d + * m + * (m + ) / + y + y / - y / + y / ) % ; return dayOfWeek[w];
}
1.2.13
解答
直接实现即可。
JAVA 版本可以参考：http://algs4.cs.princeton.edu/12oop/Transaction.java.html。
代码
using System;
using System.Collections.Generic; namespace Commercial
{
public class Transaction : IComparable<Transaction>
{
public string Who { get; }
public Date When { get; }
public double Amount { get; } /// <summary>
/// 构造函数。
/// </summary>
/// <param name="transaction">用空格隔开的形如 “姓名 日期 金额” 的字符串。</param>
public Transaction(string transaction)
{
string[] a = transaction.Split(' ');
Who = a[];
When = new Date(a[]);
Amount = double.Parse(a[]);
} /// <summary>
/// 构造函数。
/// </summary>
/// <param name="who">客户姓名。</param>
/// <param name="when">交易日期。</param>
/// <param name="amount">交易金额。</param>
public Transaction(string who, Date when, double amount)
{
if (double.IsNaN(amount) || double.IsInfinity(amount))
{
throw new ArgumentException("Amount cannot be NaN or Infinity");
}
this.Who = who;
this.When = when;
this.Amount = amount;
} /// <summary>
/// 返回字符串形式的交易信息。
/// </summary>
/// <returns></returns>
public override string ToString()
{
return string.Format("{0, -10} {1, 10} {2, 8:F2}", Who, When, Amount);
} /// <summary>
/// 默认按照交易金额升序比较。
/// </summary>
/// <param name="other">比较的另一个对象。</param>
/// <returns></returns>
public int CompareTo(Transaction other)
{
if (this.Amount < other.Amount)
return -;
if (this.Amount > other.Amount)
return ;
return ;
} /// <summary>
/// 按照客户姓名升序比较。
/// </summary>
public class WhoOrder : IComparer<Transaction>
{
int IComparer<Transaction>.Compare(Transaction x, Transaction y)
{
return x.Who.CompareTo(y.Who);
}
} /// <summary>
/// 按照交易时间升序比较。
/// </summary>
public class WhenOrder : IComparer<Transaction>
{
int IComparer<Transaction>.Compare(Transaction x, Transaction y)
{
return x.When.CompareTo(y.When);
}
} /// <summary>
/// 按照交易金额升序比较。
/// </summary>
public class HowMuchOrder : IComparer<Transaction>
{
int IComparer<Transaction>.Compare(Transaction x, Transaction y)
{
return x.Amount.CompareTo(y.Amount);
}
} /// <summary>
/// 比较两笔交易是否相同。
/// </summary>
/// <param name="obj">另一个对象。</param>
/// <returns></returns>
public override bool Equals(object obj)
{
if (obj == this)
return true;
if (obj == null)
return false;
if (obj.GetType() != this.GetType())
return false;
Transaction that = (Transaction)obj; return
(that.Amount == this.Amount) &&
(that.When.Equals(this.When)) &&
(that.Who == this.Who);
} /// <summary>
/// 返回交易信息的哈希值。
/// </summary>
/// <returns></returns>
public override int GetHashCode()
{
int hash = ;
hash = * hash + Who.GetHashCode();
hash = * hash + When.GetHashCode();
hash = * hash + Amount.GetHashCode();
return hash;
}
}
}
1.2.14
解答
上一题中的代码已经包含了对 Equals() 方法的实现。
代码
/// <summary>
/// 比较两笔交易是否相同。
/// </summary>
/// <param name="obj">另一个对象。</param>
/// <returns></returns>
public override bool Equals(object obj)
{
if (obj == this)
return true;
if (obj == null)
return false;
if (obj.GetType() != this.GetType())
return false;
Transaction that = (Transaction)obj; return
(that.Amount == this.Amount) &&
(that.When.Equals(this.When)) &&
(that.Who == this.Who);
}
提高题（1.2.15~1.2.19）
1.2.15
解答
这里我们基于 File.ReadAllLines() 进行实现。
代码
public static int[] ReadInts(string path)
{
string[] allLines = File.ReadAllLines(path);
int[] result = new int[allLines.Length]; for (int i = ; i < allLines.Length; ++i)
{
result[i] = int.Parse(allLines[i]);
} return result;
}
1.2.16
解答
JAVA 版本参考：http://algs4.cs.princeton.edu/12oop/Rational.java.html
欧几里得算法仅适用于正整数，使用前需要注意。
用欧几里得算法找到公因子之后直接化简即可。
代码
using System; namespace _1._2._16
{
public class Rational
{
public long Numerator { get; }
public long Denominator { get; }
private bool isNagative; /// <summary>
/// 构造一个有理数对象，自动变为最简形式。
/// </summary>
/// <param name="numerator">分子。</param>
/// <param name="denominator">分母。</param>
/// <exception cref="ArgumentException">分母为 0 时抛出</exception>
public Rational(long numerator, long denominator)
{
if (denominator == )
throw new ArgumentException("Denominator cannot be 0"); if (numerator < && denominator < )
{
isNagative = false;
numerator = -numerator;
denominator = -denominator;
}
else if (numerator < || denominator < )
{
isNagative = true;
}
else
{
isNagative = false;
} long gcd = GCD(Math.Abs(numerator), Math.Abs(denominator));
if (gcd != )
{
numerator /= gcd;
denominator /= gcd;
}
this.Numerator = numerator;
this.Denominator = denominator;
} /// <summary>
/// 将两个有理数对象相加，返回一个有理数。
/// </summary>
/// <param name="b">加数。</param>
/// <returns></returns>
public Rational Plus(Rational b)
{
Rational result = new Rational(this.Numerator * b.Denominator + b.Numerator * this.Denominator, this.Denominator * b.Denominator);
return result;
} /// <summary>
/// 以当前对象为被减数，减去一个有理数。
/// </summary>
/// <param name="b">减数。</param>
/// <returns></returns>
public Rational Minus(Rational b)
{
Rational result = new Rational(this.Numerator * b.Denominator - b.Numerator * this.Denominator, this.Denominator * b.Denominator);
return result;
} /// <summary>
/// 将两个有理数对象相乘。
/// </summary>
/// <param name="b">乘数。</param>
/// <returns></returns>
public Rational Multiply(Rational b)
{
Rational result = new Rational(this.Numerator * b.Numerator, this.Denominator * b.Denominator);
return result;
} /// <summary>
/// 以当前有理数为被除数，除以一个有理数。
/// </summary>
/// <param name="b">除数。</param>
/// <returns></returns>
public Rational Divide(Rational b)
{
Rational result = new Rational(this.Numerator * b.Denominator, this.Denominator * b.Numerator);
return result;
} /// <summary>
/// 求两个正整数的最大公约数。
/// </summary>
/// <param name="a">第一个整数。</param>
/// <param name="b">第二个整数。</param>
/// <returns></returns>
private long GCD(long a, long b)
{
if (b == )
return a;
return GCD(b, a % b);
} public override bool Equals(object obj)
{
if (this == obj)
return true;
if (obj == null)
return false;
if (obj.GetType() != this.GetType())
return false; Rational that = (Rational)obj;
return (this.Numerator == that.Numerator) && (this.Denominator == that.Denominator);
} public override int GetHashCode()
{
return * this.Numerator.GetHashCode() + this.Denominator.GetHashCode();
} /// <summary>
/// 返回形如 “分子/分母” 的字符串
/// </summary>
/// <returns></returns>
public override string ToString()
{
string result = "";
if (isNagative)
result += "-";
result += Math.Abs(this.Numerator) + "/" + Math.Abs(this.Denominator);
return result;
}
}
}
1.2.17
解答
在 C# 中使用 checked 关键字包裹整数运算的代码即可自动检查溢出。
在 JAVA 中可以考虑在运算前控制运算数的大小。
例如 a + b 之前保证 long.MaxValue – b >= a 等等。
代码
using System; namespace _1._2._17
{
public class Rational
{
public long Numerator { get; }
public long Denominator { get; }
private bool isNagative; /// <summary>
/// 构造一个有理数对象，自动变为最简形式。
/// </summary>
/// <param name="numerator">分子。</param>
/// <param name="denominator">分母。</param>
/// <exception cref="ArgumentException">分母为 0 时抛出</exception>
public Rational(long numerator, long denominator)
{
if (denominator == )
throw new ArgumentException("Denominator cannot be 0"); if (numerator < && denominator < )
{
isNagative = false;
numerator = -numerator;
denominator = -denominator;
}
else if (numerator < || denominator < )
{
isNagative = true;
}
else
{
isNagative = false;
} long gcd = GCD(Math.Abs(numerator), Math.Abs(denominator));
if (gcd != )
{
numerator /= gcd;
denominator /= gcd;
}
this.Numerator = numerator;
this.Denominator = denominator;
} /// <summary>
/// 将两个有理数对象相加，返回一个有理数。
/// </summary>
/// <param name="b">加数。</param>
/// <returns></returns>
public Rational Plus(Rational b)
{
checked
{
Rational result = new Rational(this.Numerator * b.Denominator + b.Numerator * this.Denominator, this.Denominator * b.Denominator);
return result;
}
} /// <summary>
/// 以当前对象为被减数，减去一个有理数。
/// </summary>
/// <param name="b">减数。</param>
/// <returns></returns>
public Rational Minus(Rational b)
{
checked
{
Rational result = new Rational(this.Numerator * b.Denominator - b.Numerator * this.Denominator, this.Denominator * b.Denominator);
return result;
}
} /// <summary>
/// 将两个有理数对象相乘。
/// </summary>
/// <param name="b">乘数。</param>
/// <returns></returns>
public Rational Multiply(Rational b)
{
checked
{
Rational result = new Rational(this.Numerator * b.Numerator, this.Denominator * b.Denominator);
return result;
}
} /// <summary>
/// 以当前有理数为被除数，除以一个有理数。
/// </summary>
/// <param name="b">除数。</param>
/// <returns></returns>
public Rational Divide(Rational b)
{
checked
{
Rational result = new Rational(this.Numerator * b.Denominator, this.Denominator * b.Numerator);
return result;
}
} /// <summary>
/// 求两个正整数的最大公约数。
/// </summary>
/// <param name="a">第一个整数。</param>
/// <param name="b">第二个整数。</param>
/// <returns></returns>
private long GCD(long a, long b)
{
if (b == )
return a;
return GCD(b, a % b);
} public override bool Equals(object obj)
{
if (this == obj)
return true;
if (obj == null)
return false;
if (obj.GetType() != this.GetType())
return false; Rational that = (Rational)obj;
return (this.Numerator == that.Numerator) && (this.Denominator == that.Denominator);
} public override int GetHashCode()
{
return * this.Numerator.GetHashCode() + this.Denominator.GetHashCode();
} /// <summary>
/// 返回形如 “分子/分母” 的字符串
/// </summary>
/// <returns></returns>
public override string ToString()
{
string result = "";
if (isNagative)
result += "-";
result += Math.Abs(this.Numerator) + "/" + Math.Abs(this.Denominator);
return result;
}
}
}
1.2.18
解答
当数据比较大时—— 例如 10^9 加上随机小数组成的数列，这时 double 的小数精度将受限。
求和之后整数部分更大，小数部分将自动四舍五入，出现误差
这时再计算平均值时将会带来较大的误差。
因此采用另一个递推公式：
k 为下标。
Mk = Mk-1+ (xk – Mk-1)/k
Sk = Sk-1 + (xk – Mk-1)*(xk – Mk).
方差 s^2 = Sk/(k – 1).
这种情况下并没有直接对所有输入值求和，小数精度不会过多受到整数部分长度的影响。
有关这两个公式的证明可以参考这篇论文，或者去查看我的知乎回答。
代码
using System; namespace _1._2._18
{
public class Accumulator
{
private double m;
private double s;
private int N; public void AddDataValue(double x)
{
N++;
s = s + 1.0 * (N - ) / N * (x - m) * (x - m);
m = m + (x - m) / N;
}
public double Mean()
{
return m;
}
public double Var()
{
return s / (N - );
}
public double Stddev()
{
return Math.Sqrt(this.Var());
}
public override string ToString()
{
return "Mean (" + N + " values): " + string.Format("{0, 7:F5}", Mean());
}
}
}
1.2.19
解答
之前的 Date 和 Transaction 已经包含了这些实现。
代码
Date：
/// <summary>
/// 构造函数。
/// </summary>
/// <param name="date">形如 "05/31/2017" 的字符串。</param>
public Date(string date)
{
string[] a = date.Split('/');
if (a.Length != )
throw new ArgumentException("Illgal Date");
Month = int.Parse(a[]);
Day = int.Parse(a[]);
Year = int.Parse(a[]);
}
Transaction：
/// <summary>
/// 构造函数。
/// </summary>
/// <param name="transaction">用空格隔开的形如 “姓名 日期 金额” 的字符串。</param>
public Transaction(string transaction)
{
string[] a = transaction.Split(' ');
Who = a[];
When = new Date(a[]);
Amount = double.Parse(a[]);
}