1.1.21 # 解答 # 实现上没什么难度，打印表格的部分可以参考之前打印二位布尔数组的方法。 注意整型数据之间相除得到的仍然是整型，小数部分会直接舍去，例如 2 / 3 的结果会是 0。 代码 # /* * 输入示例： * * 3 * hi 1 2 * hey 1 3 * hello 1 4 * */ var columns = 2; var rows = int.Parse(Console.ReadLine()); // 行号 var names = new string[rows]; // 姓名 var array = new int[rows, columns]; // 输入的两个整数 var results = new double[rows]; // 计算结果 for (var i = 0; i < rows; i++) { var temp = Console. ...
1.1.22 # 解答 # 按照书中的提示增加一个保存深度的参数。 代码 # var array = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; Rank(9, array); static int Rank(int key, int[] a) { return RankInternal(key, a, 0, a.Length - 1, 1); } static int RankInternal(int key, int[] a, int lo, int hi, int number) { for (var i = 0; i < number; i++) { Console.Write(" "); } Console.WriteLine($"{number}: {lo} {hi}"); if (lo > hi) { return -1; } var mid = lo + (hi - lo) / 2; if (key < a[mid]) { return RankInternal(key, a, lo, mid - 1, number + 1); } else if (key > a[mid]) { return RankInternal(key, a, mid + 1, hi, number + 1); } else { return mid; } }
1.1.23 # 解答 # 在主函数里做一下判断就可以了，加号则输出所有找不到的值，减号则相反。 代码 # // 从largeW.txt中读取数据 var whiteListLines = File.ReadAllLines("largeW.txt"); var whiteList = new int[whiteListLines.Length]; for (var i = 0; i < whiteListLines.Length; i++) { whiteList[i] = int.Parse(whiteListLines[i]); } Array.Sort(whiteList); Console.WriteLine("Type the numbers you want to query: "); // 输入样例：5 824524 478510 387221 var input = Console.ReadLine(); var query = new int[input.Split(' ').Length]; for (var i = 0; i < query.Length; i++) { query[i] = int.Parse(input.Split(' ')[i]); } Console. ...
1.1.24 # 解答 # 在书本中 GCD 的基础上，在函数开始时增加一条输出语句即可。 代码 # Gcd(105, 24); Console.WriteLine(); Gcd(111111, 1234567); static int Gcd(int a, int b) { Console.WriteLine($"{a} {b}"); if (b == 0) { return a; } return Gcd(b, a % b); }
1.1.25 # 解答 # 已知：$a,b$ 皆为正整数，且 $a>b$。$g$ 是 $a,b$ 的最大公约数. 设 $\ r_0=a \bmod b$，$r_1=b \bmod r_0$ ，$r_k = r_{k-2} \bmod\ r_{k-1}$ 。 那么有 $\gcd(a,b)=\gcd(b,r_0)=\gcd(r_0,r_1)…=\gcd(r_{n-1},r_n)=r_{n-1}$ ，且 $r_n=0$ （此时算法终止），且 $n$ 是有限的。 令 $q_n=\lfloor r_{n-2}/r_{n-1} \rfloor$ 有 $r_{n-2}=q_n\times r_{n-1} + r_n=q_n\times r_{n-1}$ （被除数=商✕除数+余数）。 可得 $r_{n-2}$ 能被 $r_{n-1}$ 整除。 则有 $$ \begin{aligned} r_{n-3} &= q_{n-1} \times r_{n-2} + r_{n-1}\newline &=q_{n-1}\times (q_n \times r_{n-1})+r_{n-1}\newline &=q_{n-1}\times q_n \times r_{n-1} + r_{n-1} \newline &=(q_{n-1} \times q_n +1)\times r_{n-1} \end{aligned} $$ ...
1.1.26 # 解答 # 见代码部分。 代码 # var a = 3; var b = 2; var c = 1; var t = 0; if (a > b) { t = a; a = b; b = t; } // 如果 a > b，那么 a, b 交换，保证b >= a if (a > c) { t = a; a = c; c = t; } // 如果 b >= a > c，那么 a, c 交换，保证 c >= a if (b > c) { t = b; b = c; c = t; } // 如果 b > c >= a，那么 b, c 交换，保证 c >= b Console. ...
1.1.27 # 解答 # 与之前的斐波那契数列类似，都是重复计算的问题。 答案是 7751 次。 代码 # var binomialCalled = 0; // 计算递归调用次数 double?[,] binomialCache; // 保存计算结果的数组 binomialCache = new double?[101, 51]; Console.WriteLine(Binomial(100, 50, 0.25)); Console.WriteLine(binomialCalled); double? Binomial(int n, int k, double p) { binomialCalled++; if (n == 0 && k == 0) return 1.0; if (n < 0 || k < 0) return 0.0; if (binomialCache[n, k] != null) { return binomialCache[n, k]; } binomialCache[n, k] = (1. ...
1.1.28 # 解答 # 实现方法有很多，这里是使用一个 HashSet 做中转，删除所有的重复元素。 也可以使用 Linq 里的 Distinct() 方法， 也可以排序后直接遍历一遍，遇到相同的就删除，遇到不同的就保存起来用于之后的比较。 代码 # // 从largeW.txt中读取数据 // 用 HashSet 的不可重复性去除重复 var hashSet = new HashSet<string>(File.ReadAllLines("largeW.txt")); var strings = new string[hashSet.Count]; hashSet.CopyTo(strings); var whiteList = new int[strings.Length]; for (var i = 0; i < strings.Length; i++) { whiteList[i] = int.Parse(strings[i]); } Array.Sort(whiteList); Console.WriteLine("Type the numbers you want to query: "); // 输入样例：5 824524 478510 387221 var input = Console.ReadLine(); var query = new int[input. ...
1.1.29 # 解答 # 查找小于指定值的元素数量可以多次使用二分查找实现。 例如： 序号：0 1 2 3 4 5 6 7 8 元素：1 2 2 2 2 2 2 2 3 二分查找返回 4 再次在 0~3 之间查找 二分查找返回 1 再次在 0~1 之间查找 二分查找返回 -1，没有指定值了 因此小于该值的元素数量就是 1 – 0 = 1 个 用同样的方法可以找到大于指定值的元素个数， 从总数中减去这两个数值就是等于指定值的元素数量。 代码 # var whiteList = new[] { 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6 }; Array.Sort(whiteList); Console.WriteLine("Type the numbers you want to query: "); var input = Console. ...
1.1.30 # 解答 # 互质可以用之前的 GCD 最大公因数算法判断，如果最大公因数是 1 则两数互质。 代码 # // 互质 = 最大公约数为 1 = gcd(i, j) == 1 var n = int.Parse(Console.ReadLine()); var a = new bool[n, n]; for (var i = 0; i < n; i++) { for (var j = 0; j < n; j++) { a[i, j] = (Gcd(i, j) == 1); } } PrintArray2D(a, n, n); static int Gcd(int a, int b) { if (b == 0) return a; return Gcd(b, a % b); } static void PrintArray2D(bool[,] array, int rows, int columns) { for (var i = 0; i < rows; i++) { for (var j = 0; j < columns; j++) { Console. ...