首页 > 代码库 > 算法（第四版）C#题解——1.2

算法（第四版）C#题解——1.2

2024-10-12 23:29:02   214人阅读

写在前面

整个项目都托管在了 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 的用例，从命令行接受一个整数 N。
在单位正方形中生成 N 个随机点，然后计算两点之间的最近距离。

解答

这里自己实现了一个 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 = 2;
        }

        /// <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 < 0)
                return -1;
            if (area2 > 0)
                return 1;
            return 0;
        }

        /// <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 -1;
            if (this.Y > other.Y)
                return 1;
            if (this.X < other.X)
                return -1;
            if (this.X > other.X)
                return 1;

            return 0;
        }

        /// <summary>
        /// 按照 X 顺序比较。
        /// </summary>
        private class XOrder : Comparer<Point2D>
        {
            public override int Compare(Point2D x, Point2D y)
            {
                if (x.X < y.X)
                {
                    return -1;
                }

                if (x.X > y.X)
                {
                    return 1;
                }

                return 0;
            }
        }

        /// <summary>
        /// 按照 Y 顺序比较。
        /// </summary>
        private class YOrder : Comparer<Point2D>
        {
            public override int Compare(Point2D x, Point2D y)
            {
                if (x.Y < y.Y)
                {
                    return -1;
                }
                if (x.Y > y.Y)
                {
                    return 1;
                }

                return 0;
            }
        }

        /// <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 < 0)
                {
                    return -1;
                }

                if (delta > 0)
                {
                    return 1;
                }

                return 0;
            }
        }

        /// <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 -1;
                }
                else if (angle1 > angle2)
                {
                    return 1;
                }
                else
                {
                    return 0;
                }
            }
        }

        /// <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 >= 0 && dy2 < 0)
                {
                    return -1;
                }
                else if (dy2 >= 0 && dy1 < 0)
                {
                    return 1;
                }
                else if (dy1 == 0 && dy2 == 0)
                {
                    if (dx1 >= 0 && dx2 < 0)
                    {
                        return -1;
                    }
                    else if (dx2 >= 0 && dx1 < 0)
                    {
                        return 1;
                    }
                    else
                    {
                        return 0;
                    }
                }
                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 -1;
                }
                else if (dist1 > dist2)
                {
                    return 1;
                }
                else
                {
                    return 0;
                }
            }
        }

        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 31 * 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 <= 2)
            {
                Console.WriteLine("Make sure there are 2 points at least");
                return;
            }

            //random.NextDouble() 返回一个 0~1 之间的 double 值
            for (int i = 0; i < N; ++i)
            {
                double x = random.NextDouble();
                double y = random.NextDouble();
                pointlist.Add(new Point2D(x, y));
            }

            double min = pointlist[0].DistanceTo(pointlist[1]);
            for (int i = 0; i < N; ++i)
            {
                for (int j = i + 1; 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 的用例，从命令行接受一个整数 N。
从标准输入中读取 N 个间隔（每个间隔由一对 double 值定义）并打印出所有相交的间隔对。

解答

同样实现了一个 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 31 * hash1 + hash2;
        }

        private class MinEndpointComparer : Comparer<Interval1D>
        {
            public override int Compare(Interval1D a, Interval1D b)
            {
                if (a.Min < b.Min)
                {
                    return -1;
                }
                else if (a.Min > b.Min)
                {
                    return 1;
                }
                else if (a.Max < b.Max)
                {
                    return -1;
                }
                else if (a.Max > b.Max)
                {
                    return 1;
                }
                else
                {
                    return 0;
                }
            }
        }

        private class MaxEndpointComparer : Comparer<Interval1D>
        {
            public override int Compare(Interval1D a, Interval1D b)
            {
                if (a.Max < b.Max)
                {
                    return -1;
                }
                else if (a.Max > b.Max)
                {
                    return 1;
                }
                else if (a.Min < b.Min)
                {
                    return -1;
                }
                else if (a.Min > b.Min)
                {
                    return 1;
                }
                else
                {
                    return 0;
                }
            }
        }

        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 -1;
                }
                else if (alen > blen)
                {
                    return 1;
                }
                else
                {
                    return 0;
                }
            }
        }
    }
}

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 < 2)
            {
                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 = 0; i < N; ++i)
            {
                string temp = Console.ReadLine();
                double lo = double.Parse(temp.Split(‘ ‘)[0]);
                double hi = double.Parse(temp.Split(‘ ‘)[1]);

                if (lo > hi)
                {
                    double t = lo;
                    lo = hi;
                    hi = t;
                }

                intervalList.Add(new Interval1D(lo, hi));
            }

            //判断是否相交并输出
            for (int i = 0; i < N; ++i)
            {
                for (int j = i + 1; j < N; ++j)
                {
                    if (intervalList[i].Intersect(intervalList[j]))
                    {
                        Console.WriteLine($"{intervalList[i].ToString()} {intervalList[j].ToString()}");
                    }
                }
            }
        }
    }
}

1.2.3
题目

编写一个 Interval2D 的用例，从命令行接受参数 N、min 和 max。
生成 N 个随机的 2D 间隔，其宽和高均匀的分布在单位正方形中的 min 和 max 之间。
用 StdDraw 画出它们并打印出相交的间隔对的数量以及有包含关系的间隔对数量。

解答

首先先实现一个 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 31 * 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 = 0; 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 = 0;
            for (int i = 0; i < N; ++i)
            {
                for (int j = i + 1; j < N; ++j)
                {
                    if (list[i].Intersects(list[j]))
                    {
                        intersectNum++;
                    }
                }
            }

            int containsNum = 0;
            for (int i = 0; i < N; ++i)
            {
                for (int j = 0; j < N; ++j)
                {
                    if (i == j)
                        continue;

                    if (list[i].Contains(list[j]))
                    {
                        containsNum++;
                    }
                }
            }

            //移动原点至左下方，翻转坐标系
            graphics.TranslateTransform(0, drawPad.ClientRectangle.Height);
            graphics.ScaleTransform(1, -1);

            //绘制所有区间
            foreach (Interval2D n in list)
            {
                n.Draw(graphics);
            }

            //新建一个窗口，显示计算结果
            MessageBox.Show($"相交的区间数：{intersectNum}, 包含的区间数：{containsNum}");

            //清理资源
            graphics.Dispose();
        }
1.2.4
题目

以下这段代码会打印出什么？

String string1 = "hello";
String string2 = string1;
string1 = "world";
StdOut.println(string1);
StdOut.println(string2);
解答

在 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 s = "Hello World";
s.toUpperCase();
s.substring(6, 11);
StdOut.println(s);
解答

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(6, 5);//C# 中两个参数分别代表子串起始下标和长度
            Console.WriteLine(s);
        }
    }
}
1.2.6
题目

如果字符串 s 中的字符循环移动任意位置之后能够得到另一个字符串 t，
那么 s 就被称为 t 的回环变位（circular rotation）。
例如，ACTGACG 就是 TGACGAC 的一个回环变位，反之亦然。
判定这个条件在基因组序列的研究中是很重要的。
编写一个程序检查两个给定的字符串 s 和 t 是否互为回环变位。
提示：答案只需要一行用到 indexOf()、length() 和字符串连接的代码。

解答

对于任意字符串 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
题目

以下递归函数的返回值是什么？

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);
}
解答

递归交换字符顺序，最后返回反序的字符串。

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 <= 1)
                return s;
            string a = s.Substring(0, N / 2);
            string b = s.Substring(N / 2, N - N / 2);

            return Mystery(b) + Mystery(a);
        }
    }
}
1.2.8
题目

设 a[] 和 b[] 均为长数百万的整型数组。以下代码的作用是什么？有效吗？

int[] t = a; a = b; b = t;
解答

作用就是交换两个数组。

但在 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 = 0; i < N; ++i)
            {
                a[i] = int.Parse(allNums[i]);
                b[N - i - 1] = a[i];
            }

            //输出前5个数字
            Console.WriteLine("Before Swap");
            Console.Write("a:");
            for (int i = 0; i < 5; ++i)
            {
                Console.Write($" {a[i]}");
            }
            Console.WriteLine();
            Console.Write("b:");
            for (int i = 0; i < 5; ++i)
            {
                Console.Write($" {b[i]}");
            }
            Console.WriteLine();

            //交换
            int[] t = a;
            a = b;
            b = t;

            //再次输出
            Console.WriteLine("After Swap");
            Console.Write("a:");
            for (int i = 0; i < 5; ++i)
            {
                Console.Write($" {a[i]}");
            }
            Console.WriteLine();
            Console.Write("b:");
            for (int i = 0; i < 5; ++i)
            {
                Console.Write($" {b[i]}");
            }
            Console.WriteLine();
        }
    }
}
1.2.9
题目

修改 BinarySearch（请见 1.1.10.1 节中的二分查找代码），使用 Counter 统计在有查找中被检查的键的总数并在查找全部结束后打印该值。
提示：在 main() 中创建一个 Counter 对象并将它作为参数传递给 rank()

解答

首先实现一个 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 = 0; 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 = 0; i < inputListString.Length; ++i)
            {
                inputList[i] = int.Parse(inputListString[i]);
            }

            //对每一个查询值进行二分查找
            foreach (int n in inputList)
            {
                int result = rank(n, whiteList, count);
                //将不在白名单上的数据输出
                if (result == -1)
                {
                    Console.WriteLine(n);
                }
            }
            Console.WriteLine();

            //输出查询数目
            Console.WriteLine(count.Tally());
        }

        static int rank(int key, int[] a, Counter count)
        {
            int lo = 0;
            int hi = a.Length - 1;
            while (lo <= hi)
            {
                int mid = lo + (hi - lo) / 2;
                count.Increment();
                if (key < a[mid])
                {
                    hi = mid - 1;
                }
                else if (key > a[mid])
                {
                    lo = mid + 1;
                }
                else
                {
                    return mid;
                }
            }
            return -1;
        }
    }
}
1.2.10
题目

编写一个类 VisualCounter，支持加一和减一操作。它的构造函数接受两个参数 N 和 max，其中 N 指定了操作的最大次数， max 指定了计数器的最大绝对值。作为副作用，用图像显示每次计数器变化后的值。

解答

在 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 <= 0)
                return false;
            if (count < max)
            {
                count++;
                operatorTimes--;
            }
            return true;
        }

        /// <summary>
        /// 计数器减一。
        /// </summary>
        public bool Decreasement()
        {
            if (operatorTimes <= 0)
                return false;
            if (count > 0)
            {
                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(0, 0, width, height / 3);
            Rectangle bodyPart = new Rectangle(0, height / 3, (height * 2) / 3, (height * 2) / 3);

            //绘图
            g.DrawString($"计数：{count} 剩余操作数：{operatorTimes} 最大值：{max}", font, Brushes.Black, headPart);
            g.FillPie(Brushes.Blue, bodyPart, 0, 360 * (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
题目

根据 Date 的 API 实现一个 SmartDate 类型，在日期非法时抛出一个异常。

解答

在构造函数开始时做一次判断，非法时抛出异常。

首先建立一个数组，数组的第 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 = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

        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 < 0)
                return false;

            bool isLeapYear = false;

            if (m > 12 || m < 1)
                return false;
            if (d < 0)
                return false;
            if (m == 2 && d > 29 && isLeapYear)
                return false;
            if (d > dayOfMonth[m])
                return false;

            return true;
        }

        private bool IsLeapYear(int y)
        {
            if (y % 400 == 0)
                return true;
            if (y % 100 != 0 && y % 4 == 0)
                return true;

            return false;
        }

        public override string ToString()
        {
            return this.Month + "/" + this.Day + "/" + this.Year;
        }
    }
}
1.2.12
题目

为 SmartDate 添加一个方法 dayOfTheWeek()，为日期中每周的日返回 Monday、Tuesday、Wednesday、Thursday、Friday、Saturday 或 Sunday 中的适当值。你可以假定时间是 21 世纪。

解答

这里使用蔡勒公式来推算星期。

参考：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 < 3)
            {
                m += 12;
                y--;
            }

            //使用蔡勒公式计算，参见 http://www.cnblogs.com/mq0036/p/3534314.html
            int w = (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400) % 7;

            return dayOfWeek[w];
        }
1.2.13
题目

用我们对 Date 的实现（请见表 1.2.12）作为模板实现 Transaction 类型。

解答

直接实现即可。

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[0];
            When = new Date(a[1]);
            Amount = double.Parse(a[2]);
        }

        /// <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 -1;
            if (this.Amount > other.Amount)
                return 1;
            return 0;
        }

        /// <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 = 1;
            hash = 31 * hash + Who.GetHashCode();
            hash = 31 * hash + When.GetHashCode();
            hash = 31 * hash + Amount.GetHashCode();
            return hash;
        }
    }
}
1.2.14
题目

用我们对 Date 中的 equals() 方法的实现（请见 1.2.5.8 节中的 Date 代码框）作为模板，
实现 Transaction 中的 equals() 方法。

解答

上一题中的代码已经包含了对 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
题目

文件输入。
基于 String 的 split() 方法实现 In 中的静态方法 readInts()。

解答

这里我们基于 File.ReadAllLines() 进行实现。

代码
public static int[] ReadInts(string path)
        {
            string[] allLines = File.ReadAllLines(path);
            int[] result = new int[allLines.Length];
            
            for (int i = 0; i < allLines.Length; ++i)
            {
                result[i] = int.Parse(allLines[i]);
            }

            return result;
        }
1.2.16
题目

有理数。
为有理数实现一个不可变数据类型 Rational，支持加减乘除操作。

public class Rational
{
    Rantional(int numerator, int denominator)
    Rational plus (Rational b);
    Rational minus(Rational b);
    Rational times(Rational b);
    Rational divides(Rational b);
    Boolean equals(Rational that);
    String toString();
}
无需测试溢出（请见练习 1.2.17），只需使用两个 long 型实例变量表示分子和分母来控制溢出的可能性。
使用欧几里得算法来保证分子和分母没有公因子。
编写一个测试用例检测你实现的所有方法。
解答

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 == 0)
                throw new ArgumentException("Denominator cannot be 0");

            if (numerator < 0 && denominator < 0)
            {
                isNagative = false;
                numerator = -numerator;
                denominator = -denominator;
            }
            else if (numerator < 0 || denominator < 0)
            {
                isNagative = true;
            }
            else
            {
                isNagative = false;
            }

            long gcd = GCD(Math.Abs(numerator), Math.Abs(denominator));
            if (gcd != 1)
            {
                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 == 0)
                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 31 * 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
题目

有理数实现的健壮性。
在 Rational （请见练习 1.2.16）的开发中使用断言来防止溢出。

解答

在 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 == 0)
                throw new ArgumentException("Denominator cannot be 0");

            if (numerator < 0 && denominator < 0)
            {
                isNagative = false;
                numerator = -numerator;
                denominator = -denominator;
            }
            else if (numerator < 0 || denominator < 0)
            {
                isNagative = true;
            }
            else
            {
                isNagative = false;
            }

            long gcd = GCD(Math.Abs(numerator), Math.Abs(denominator));
            if (gcd != 1)
            {
                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 == 0)
                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 31 * 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
题目

累加器的方法。
以下代码为 Accumulator 类添加了 var() 和 stddev() 方法，
它们计算了 addDataValue() 方法的参数的方差和标准差，验证这段代码：

public class Accumulator
{
    private double m;
    private double s;
    private int N;
    public void addDataValue(double x)
    {
        N++;
        s = s + 1.0 * (N - 1) / N * (x - m) * (x - m);
        m = m + (x - m) / N;
    }
    public double mean()
    {
        return m;
    }
    public double var()
    {
        return s / (N - 1);
    }
    public double stddev()
    {
        return Math.sqrt(this.var());
    }
}

与直接对所有数据的平方求和的方法相比较，
这种实现能够更好的避免四舍五入产生的误差。

解答

当数据比较大时—— 例如 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 - 1) / N * (x - m) * (x - m);
            m = m + (x - m) / N;
        }
        public double Mean()
        {
            return m;
        }
        public double Var()
        {
            return s / (N - 1);
        }
        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
题目

字符串解析。
为你在练习 1.2.13 中实现的 Date 和 Transaction 类型编写能够解析字符串数据的构造函数。
它接受一个 String 参数指定的初始值，格式如下所示：

类型

格式

举例

Date

由斜杠分隔的整数

5/22/1939

Transaction

客户、日期和金额，由空白字符分隔

Turing 5/22/1939 11.99
解答

之前的 Date 和 Transaction 已经包含了这些实现。

代码

Date：

/// <summary>
        /// 构造函数。
        /// </summary>
        /// <param name="date">形如 "05/31/2017" 的字符串。</param>
        public Date(string date)
        {
            string[] a = date.Split(‘/‘);
            if (a.Length != 3)
                throw new ArgumentException("Illgal Date");
            Month = int.Parse(a[0]);
            Day = int.Parse(a[1]);
            Year = int.Parse(a[2]);
        }

Transaction：

/// <summary>
        /// 构造函数。
        /// </summary>
        /// <param name="transaction">用空格隔开的形如 “姓名 日期 金额” 的字符串。</param>
        public Transaction(string transaction)
        {
            string[] a = transaction.Split(‘ ‘);
            Who = a[0];
            When = new Date(a[1]);
            Amount = double.Parse(a[2]);
        }

算法（第四版）C#题解——1.2


联系
我们