2018-5-15
1.1.31 # 解答 # 概率的实现方法：
例如概率是 60 %，就在 [0, 100) 之间随机一个值，小于等于 60 则执行操作，反之不执行。
需要更精确的情况可以增大随机的范围，例如 [0, 1000)。
绘图结果
N = 10,p = 0.2, 0.5, 1
完整项目可以到 Github 上下载。
代码 # /// <summary> /// 主绘图函数 /// </summary> /// <param name="N">点的总数目</param> /// <param name="p">每对点之间连接的概率</param> public static void StartDrawing(int N, double p) { int pointSize = 5;//每个点绘制的大小 int precious = 1000;//概率判断的精度 //新建一个绘图窗口 Form2 DrawPad = new Form2(); //显示绘图窗口 DrawPad.Show(); //新建画布 Graphics graphics = DrawPad.
...
2018-5-15
1.1.32 # 解答 # 绘图结果：
完整的项目代码可以去 Github 上下载。
代码 # public static void StartDrawing(double[] array, int N, double l, double r) { //创建并显示绘图窗口 Form2 DrawPad = new Form2(); DrawPad.Show(); //新建画布 Graphics graphics = DrawPad.CreateGraphics(); //翻转默认坐标系 graphics.TranslateTransform(0, DrawPad.Height); graphics.ScaleTransform(1, -1); //对原始数组排序 Array.Sort(array); //计算各区域的值 int[] counts = new int[N]; int index = 0; for (int i = 0; i < N; ++i) { for (int j = index; j < array.Length; ++j) { if (array[j] <= (r - l) * (i + 1) / N) { counts[i]++; index++; } else { break; } } } //获取最大值 double max = counts.
...
2018-5-15
1.1.33 # 解答 # 这里矩阵使用交错数组实现（方便取行向量），不是普通的二维数组。
矩阵和矩阵、矩阵和向量、向量和矩阵都使用行向量点乘列向量的方式计算。
代码 # public class Matrix { /// <summary> /// 计算两个向量的点积 /// </summary> /// <param name="x">需要点乘的向量</param> /// <param name="y">需要点乘的另一个向量</param> /// <returns>返回点乘的结果</returns> /// <exception cref="FormatException"></exception> public static double Dot(double[] x, double[] y) { //确保两向量等长 if (x.Length != y.Length) { throw new FormatException("the length of two vectors must be equal"); } //点乘 double result = 0; for (int i = 0; i < x.Length; ++i) { result += x[i] * y[i]; } return result; } /// <summary> /// 计算两个矩阵相乘的结果，返回一个矩阵 /// </summary> /// <param name="a">用交错数组表示的 m * p 矩阵</param> /// <param name="b">用交错数组表示的 p * n 矩阵</param> /// <returns>返回 m * n 的矩阵</returns> /// <exception cref="FormatException"></exception> /// <example> /// a = {(1,2,3),(4,5,6)} /// b = {(1,4),(2,5),(3,6)} /// Mult(a, b) = {(14,32),(32,77)} /// </example> public static double[][] Mult(double[][] a, double[][] b) { if (a[0].
...
2018-5-15
1.1.34 # 解答 # 第二个以及最后三个需要，其他都可以设计成过滤器的模式。
这里的 largeW.txt 只需要保留前 100 个数字就可以了，太多的话最后两个测试会刷屏。
代码 # var allNumbers = File.ReadAllLines("largeW.txt"); var n = allNumbers.Length; var input = new int[n]; for (var i = 0; i < n; i++) { input[i] = int.Parse(allNumbers[i]); } MinAndMax(input); Console.WriteLine(); MidNumber(input); Console.WriteLine(); NumberK(4, input); Console.WriteLine(); SquareSum(input); Console.WriteLine(); AboveAverage(input); Console.WriteLine(); Ascending(input); Console.WriteLine(); Shuffle(input); Console.WriteLine(); static void MinAndMax(int[] input) { // 只用到了两个变量 var min = input[0]; var max = input[0]; // 只对输入值正向遍历一遍，不需要保存 for (var i = 1; i < input.
...
2018-5-15
1.1.35 # 解答 # 这里用 Random 类模拟掷骰子并计算概率，最后和程序得出的比较。
代码 # // 书中给出的程序 const int sides = 6; var dist = new double[2 * sides + 1]; for (var i = 1; i <= sides; i++) for (var j = 1; j <= sides; j++) dist[i + j] += 1.0; for (var k = 2; k <= 2 * sides; k++) dist[k] /= 36.0; // 不断进行模拟，直至误差小于 0.001 var n = 36; var isAccepted = false; double[] distTemp = null; const double error = 0.
...
2018-5-15
1.1.36 # 解答 # N 取到 1000 左右数据就比较明显了。
N = 1000， M = 10
代码 # const int m = 10; // 数组大小 const int n = 1000; // 打乱次数 var a = new int[10]; var result = new int[m, m]; for (var i = 0; i < n; i++) { // 初始化 for (var j = 0; j < a.Length; j++) { a[j] = j; } // 打乱 Shuffle(a, i); // 记录 for (var j = 0; j < m; j++) { result[a[j], j]++; } } PrintMatrix(result); static void Shuffle(int[] a, int seed) { var n = a.
...
2018-5-15
1.1.37 # 解答 # 使用 0~N-1 的随机数会导致每次交换的数字可能相同。
例如：
原数组： 1 2 3 4。
第一次： 2 1 3 4
random = 1，第 0 个和第 1 个交换。
第二次： 1 2 3 4
random = 0，第 1 个和第 0 个交换。
代码 # // 使用 0~N-1 的随机数会导致每次交换的数字可能相同 // 例如： // 原数组： 1 2 3 4 // 第一次： 2 1 3 4 random = 1，第 0 个和第 1 个交换 // 第二次： 1 2 3 4 random = 0，第 1 个和第 0 个交换 const int m = 10; // 数组大小 const int n = 100000; // 打乱次数 var a = new int[10]; var result = new int[m, m]; for (var i = 0; i < n; i++) { // 初始化 for (var j = 0; j < a.
...
2018-5-15
1.1.38 # 解答 # 为了使差距比较明显，故意取了比较靠后的数字。
代码 # var largeWString = File.ReadAllLines("largeW.txt"); var largeW = new int[largeWString.Length]; for (var i = 0; i < largeW.Length; i++) { largeW[i] = int.Parse(largeWString[i]); } var timer = Stopwatch.StartNew(); BruteForceSearch(111111, largeW); Console.WriteLine($"BruteForceSearch: {timer.ElapsedMilliseconds} ms"); timer.Restart(); Rank(111111, largeW); Console.WriteLine($"BinarySearch: {timer.ElapsedMilliseconds} ms"); var largeTString = File.ReadAllLines("largeT.txt"); var largeT = new int[largeTString.Length]; for (var i = 0; i < largeW.Length; i++) { largeT[i] = int.Parse(largeTString[i]); } timer.Restart(); BruteForceSearch(111111, largeT); Console.
...
2018-5-15
1.1.39 # 解答 # 按照要求编程就好，视机器不同需要的时间也不同。
代码 # // 需要 6 秒左右的运算时间 var r = new Random(); var baseNum = 10; var powNum = 3; var T = 10; var m = 4; var matrix = new double[m, 2]; for (var i = 0; i < m; i++) { var n = (int)Math.Pow(baseNum, powNum + i); double sum = 0; for (var j = 0; j < T; j++) { sum += Test(n, r.
...
2018-5-15
1.2.1 # 解答 # 这里自己实现了一个 Point2D 类（包含在了 Geometry 库中）。
JAVA 版本参考：http://algs4.cs.princeton.edu/12oop/Point2D.java.html。
求最近两点只需要反复调用 Point2D 类中的 DistTo() 方法就可以了。
代码 # Point2D 类 # /// <summary> /// Point2D 二维点类。 /// </summary> /// <summary> public sealed class Point2D : IComparable<Point2D> { /// 以 X 坐标升序排序。 /// </summary> /// <value>以 X 坐标升序排序的静态比较器。</value> public static readonly Comparer<Point2D> XOrderComparer = new XOrder(); /// <summary> /// 以 Y 坐标升序排序。 /// </summary> /// <value>以 Y 坐标升序排序的静态比较器。</value> public static readonly Comparer<Point2D> YOrderComparer = new YOrder(); /// <summary> /// 以极半径升序排序。 /// </summary> /// <value>以极半径升序排序的静态比较器。</value> public static readonly Comparer<Point2D> ROrderComparer = new ROrder(); /// <summary> /// 二维点的 X 坐标。 /// </summary> /// <value>X 坐标。</value> public double X { get; } /// <summary> /// 二维坐标的 Y 坐标。 /// </summary> /// <value>Y 坐标。</value> public double Y { get; } /// <summary> /// 绘制时点的半径，以像素为单位，默认值为 2。 /// </summary> /// <value>点的半径，以像素为单位。</value> public int Radius { get; set; } /// <summary> /// 构造一个二维点。 /// </summary> /// <param name="x">点的 X 轴坐标。</param> /// <param name="y">点的 Y 轴坐标。</param> /// <exception cref="ArgumentException">当 <paramref name="x"/> 或 <paramref name="y"/> 为±无穷时抛出此异常。</exception> /// <exception cref="ArgumentNullException">当 <paramref name="x"/> 或 <paramref name="y"/> 为 <see cref="double.
...