Ausführliche Erläuterung von Beispielen für Algorithmen in C#

Vorne geschrieben

Das gesamte Projekt wird auf Github gehostet:

Verwenden Sie Strg + F, um das Thema zu finden.

Zwei Testdatendateien, die Sie möglicherweise für diesen Abschnitt benötigen:

largeW: http://algs4.cs.princeton.edu/11model/largeW.txt

largeT: http://algs4.cs.princeton.edu/11model/largeT.txt

Übungen & Lösungen

Übungen (1.1.1~1.1.25)

1.1. 1

Frage

Gibt den Wert des folgenden Ausdrucks an:

a (0 + 15) / 2
2,0e-6 * 100000000,1
c. wahr && falsch ||. wahr && wahr

Antwort

a.7
b.1562500.0015625
c.True

Code

        static void Main(string[] args)
        {int a = (0 + 15) / 2;double b = Math.Pow(2.0, -6) * 100000000.1; //Math.Pow(double x, double y) 求x的y次方bool c = true && false || true && true;//Console.WriteLine 向控制台窗口输出一行Console.WriteLine($"a.{a}");
            Console.WriteLine($"b.{b}");
            Console.WriteLine($"c.{c}");
        }

1.1.2

Frage

Geben Sie den Typ und Wert des folgenden Ausdrucks an:

a (1 + 2.236) / 2
b. 1 + 2 + 3 + 4,0
c. 4,1 >= 4
d. 1 + 2 + „3“

Name Typwert

a System.Double 1.618

b System.Double 10
c System.Boolean True
                        System.String   33

Code

        static void Main(string[] args)
        {//var 变量名 = 初始值  根据初始值自动判断变量类型var a = (1 + 2.236) / 2;var b = 1 + 2 + 3 + 4.0;var c = 4.1 >= 4;var d = 1 + 2 + "3";//Console.WriteLine 向控制台输出一行//变量名.GetType() 返回变量类型//Type.ToString() 将类型名转换为字符串Console.WriteLine("\tName\tType     \tValue");
            Console.WriteLine($"\ta\t{a.GetType().ToString()}\t{a}");
            Console.WriteLine($"\tb\t{b.GetType().ToString()}\t{b}");
            Console.WriteLine($"\tc\t{c.GetType().ToString()}\t{c}");
            Console.WriteLine($"\td\t{d.GetType().ToString()}\t{d}");
        }

1.1.3

Frage

Schreiben Sie ein Programm, um drei ganzzahlige Parameter von der Befehlszeile abzurufen.

Gleich ausgeben, wenn beide gleich sind,

andernfalls nicht gleich drucken.

Antwort

Einfach, wenn Urteil ausreicht

Code

        static void Main(string[] args)
        {//Console.ReadLine() 从控制台读入一整行（返回int）//string.Split(char) 根据提供的分隔符将字符串分割，返回字符串数组//Int32.Parse(string) 将字符串转换为相应的整型数据string input = Console.ReadLine();int a = Int32.Parse(input.Split(' ')[0]);int b = Int32.Parse(input.Split(' ')[1]);int c = Int32.Parse(input.Split(' ')[2]);//Console.WriteLine() 向控制台输出一行if (a == b && b == c)
            {
                Console.WriteLine("equal");
            }else{
                Console.WriteLine("not equal");
            }
        }

1.1.4

Frage

Was sind die Probleme (falls vorhanden) mit jeder der folgenden Aussagen?

a. wenn (a > b) dann c = 0;

b wenn a > b = 0;
d. if (a > b) c = 0 else b = 0;

Antwort

a Die Syntax von if gefolgt von then kann in C# nicht verwendet werden.

b. Die Urteilsaussage nach „if“ muss in Klammern stehen.

c. Richtig, die Klammern können weggelassen werden, wenn nur eine Aussage vorhanden ist.

d. Fehlendes Semikolon nach c = 0.

Code

1.1.5

static void Main(string[] args)
        {int a = 1;int b = 2;int c = 0;//if (a > b) then c = 0; //if 后不能跟 then//if a > b { c = 0; } //if后必须跟括号if (a > b) c = 0;//正确//if (a > b) c = 0 else b = 0; //c = 0后缺少分号}

Frage

Programm schreiben,

Wenn eine Variable vom Typ double Wenn sowohl x als auch y genau zwischen 0 und 1 liegen, dann geben Sie true

aus, andernfalls geben Sie false aus.

Die Antwort

ist relativ einfach, beurteilen Sie es einfach direkt.

Code

1.1.6

static void Main(string[] args)
        {//修改这两个值进行测试double x = 0.05;double y = 0.01;if (x > 0 && x  0 && y 

Frage

Was wird das folgende Programm ausdrucken?

Antwort

Geben Sie die Fibonacci-Folge aus.

Implementieren Sie den Code einfach direkt im Buch.

Code

1.1.7

//输出斐波那契数列static void Main(string[] args)
        {int f = 0;int g = 1;for (int i = 0; i 

Frage

Geben Sie jeweils die von den folgenden Codeausschnitten gedruckten Werte an .

Antwort

Dasselbe wie bei der obigen Frage, nur direkt umsetzen.

a

3.00009

Bei der Doppelberechnung liegt ein Fehler vor und sie ist nicht korrekt.

b

499500

1000 + 999 + 998...

c

10000

1000 * 10, Ende der äußeren Schleife Die Bedingung ist 2
i

>

^Code

1.1.8

private static void a()
        {
            Console.WriteLine("a");double t = 9.0;while (Math.Abs(t - 9.0 / t) > .001)
            {
                t = (9.0 / t + t) / 2.0;
            }
            Console.Write($"{t:N5}\n");//:N5代表保留5位小数，同理可使用N1、N2……        }private static void b()
        {
            Console.WriteLine("\nb");int sum = 0;for (int i = 1; i  1000，最终sum = 1000 * 10 = 10000            c();
        }

Frage

Welches Ergebnis wird durch die folgende Anweisung gedruckt? Geben Sie eine Erklärung.

Antwort

b

197

e

Code

1.1.9

static void Main(string[] args)
        {
            Console.WriteLine('b');
            Console.WriteLine('b' + 'c'); //char 被隐式转为为 int 类型，取 ascii 码Console.WriteLine((char)('a' + 4)); //强制转换后，ascii 码被转换为相应的字符}

Frage

Schreiben Sie einen Code, um eine positive Ganzzahl N in binärer Darstellung in einen String-Wert s umzuwandeln.

Antwort

Es gibt zwei Methoden: entweder den direkten Aufruf der Bibliotheksfunktion oder die Verwendung der im Buch angegebenen Codekonvertierung.

Code

1.1.10

static void Main(string[] args)
        {int N = 4;//1.直接转换 Convert.ToString(int, int) 第一个为要转换的数，第二个为要转换的进制Console.WriteLine($"{Convert.ToString(N, 2)}");//2.转换为二进制数string s = "";for (int n = N; n > 0; n /= 2)
            {
                s = (n % 2) + s;
            }
            Console.WriteLine(s);
        }

Frage

Was stimmt mit dem folgenden Code nicht?

Antwort

Variablen muss vor der Verwendung ein Wert zugewiesen werden.

Code

1.1.11

题目

编写一段代码，打印出一个二维布尔数组的内容。
其中，使用 * 表示真，空格表示假，打印出行号和列号。

解答

注意，二维数组 bool[M, N] 代表 M 行 N 列的布尔数组。

使用二重循环即可实现。

输出使用制表符 ’\t’ 作为分隔。

代码

static void PrintArray2D(bool[,] array)
        {int rows = array.GetLength(0);//获取行数int columns = array.GetLength(1);//获取列数//输出列号for (int i = 0; i 

1.1.12

题目

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

解答

第一个循环初始化数组{9, 8, 7, 6, 5, 4, 3, 2, 1, 0}

第二个循环用相应位置的值作为下标取值，例如：a[0] = a[a[0]] = a[9] = 0

最后结果为：0,1,2,3,4,4,3,2,1,0

代码

static void Main(string[] args)
        {int[] a = new int[10];for (int i = 0; i 

1.1.13

题目

编写一段代码，打印出一个 M 行 N 列的二维数组的转置。

解答

转置输出只需要在二重循环的时候将行、列输出顺序取反即可。

代码

static void Main(string[] args)
        {int M = 2;int N = 3;int[,] array = new int[M, N];//新建一个二维数组for (int i = 0; i 

1.1.14

题目

编写一个静态方法lg()，接受一个整型参数N，返回不大于log2(N)的最大整数。
不要使用 Math 库。

解答

简单使用 log 的定义逼近即可。

代码

static void Main(string[] args)
        {int N = 9;
            Console.WriteLine($"{ lg(N)}");
        }//利用循环逼近 N，得到 log2(N) 的值static int lg(int N)
        {int baseNumber = 2;int pow = 1;int sum = 2;for (pow = 1; sum 

1.1.15

题目

编写一个静态方法 histogram()，
接受一个整型数组 a[] 和一个整数 M 作为参数并返回一个大小为 M 的数组，
其中第 i 个元素的值为整数 i 在参数数组中出现的次数。
如果 a[] 中的值均在 0 到 M-1 之间，
返回数组中所有元素之和应该和 a.length 相等。

解答

利用二重循环，查找每个值在数组中出现的次数。

代码

static void Main(string[] args)
        {int[] a = new int[10];int M = 10;for (int i = 0; i 

1.1.16

题目

给出 exR1(6) 的返回值。

解答

填入代码测试即可。

用字符串拼接的方式展示递归。

类似于这个：

代码

static void Main(string[] args)
        {
            Console.WriteLine($"{exR1(6)}");
        }//exR1(6) = //exR1(3) + 6 + exR1(4) + 6//exR1(0) + 3 + exR1(1) + 3 + 6 + exR1(4) + 6//"" + 3 + exR1(-2) + 1 + exR1(-1) + 1 + 3 + 6 + exR1(4) + 6//"" + 3 + "" + 1 + "" + 1 + 3 + 6 + exR1(4) + 6//"31136" + exR1(4) + 6//......public static string exR1(int n)
        {if (n 

1.1.17

题目

找出以下递归函数的问题：

public static String exR2(int n)  
    {  
        String s = exR2(n - 3) +  n + exR2(n - 2) + n;  if (n 

解答

书中已经给出了解释。

递归时结束条件必须放在递归语句的前面，否则会不断展开而无法结束。

代码

static void Main(string[] args)
        {
            Console.WriteLine($"{exR2(6)}");//抛出 StackOverflow Exception        }public static string exR2(int n)
        {string s = exR2(n - 3) + n + exR2(n - 2) + n;//运行到 exR2 即展开，不会再运行下一句if (n 

1.1.18

题目

请看以下递归函数：

public static int mystery(int a, int b)
{if (b == 0)    return 0;if (b % 2 == 0)    return mystery(a + a, b / 2);return mystery(a + a, b / 2) + a;
}

mystery(2, 25) 和 mystery(3, 11) 的返回值是多少？
给定正整数 a 和 b，mystery(a, b) 计算的结果是什么？
将代码中的 + 替换为 * 并将 return 0 改为 return 1，然后回答相同的问题。

解答

其实就是一种快速乘法的实现，换成乘号之后就变成了快速乘幂。

例如对于乘法 2 * 4，可以用 2 + 2 + 2 + 2 做四次加法计算；也可以变为 (2 + 2) * 2 = (2 + 2) + (2 + 2) 的形式，用两次加法就可以完成（先计算 2 + 2 的值，再计算 4 + 4 的值）。

同理对于乘幂 2⁸，既可以用 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 做 8 次乘法，也可以只用三次乘法就计算出来：

2² = 2 * 2

2⁴ = 2² * 2²

2⁸ = 2⁴ * 2⁴

这样时间复杂度就从 O(n) 变为了 O(log n)。

代码

static void Main(string[] args)
        {
            Console.WriteLine($"mystery(2, 25): {mystery(2, 25)}");
            Console.WriteLine($"mystery(3, 11): {mystery(3, 11)}");

            Console.WriteLine($"mysteryChanged(2, 8): {mysteryChanged(2, 8)}");
            Console.WriteLine($"mysteryChanged(3, 2): {mysteryChanged(3, 2)}");
        }//mystery(a, b) = a * b//利用等式：a * b = 2a * b/2 = (2a * (b-1) / 2) + a//示例：//mystery(2, 25) =//mystery(2 + 2, 12) + 2 =//mystery(4 + 4, 6) + 2 =//mystery(8 + 8, 3) =//mystery(16 + 16, 1) + 16 + 2 =//mystery(32 + 32, 0) + 32 + 16 + 2 =//0 + 32 + 16 + 2 =//50public static int mystery(int a, int b)
        {if (b == 0) return 0;if (b % 2 == 0) return mystery(a + a, b / 2);return mystery(a + a, b / 2) + a;
        }//mysteryChanged(a, b) = a ^ b//同理（乘方与乘法，乘法与加法之间具有类似的性质）//a ^ b = (a ^ 2) ^ (b / 2) = (a ^ 2) ^ ((b - 1) / 2) * apublic static int mysteryChanged(int a, int b)
        {if (b == 0) return 1;if (b % 2 == 0) return mysteryChanged(a * a, b / 2);return mysteryChanged(a * a, b / 2) * a;
        }

1.1.19

题目

在计算机上运行以下程序：

public class Fibnacci
{public static long F(int N)
    {if (N == 0)    return 0;if (N == 1)    return 1;return F(N - 1) + F(N - 2);
    }public static void main(String[] args)
    {for (int N = 0; N 

计算机用这段程序在一个小时之内能够得到 F(N) 结果的最大 N 值是多少？
开发 F(N) 的一个更好的实现，用数组保存已经计算过的值。

解答

普通的递归算法效率很低，原因是越到后面重复运算的数目越多。

比如：

F(2) = F(1) + F(0)

F(3) = F(2) + F(1) = F(1) + F(1) + F(0)

可以看到 F(1) 被重复计算了两次。

改进的方式是将每次运算的结果保存在数组中，之后计算过的数据直接从数组中提取。

代码

class Fibnacci
    {//long 类型不够大，换成 UINT64 类型//用于保存计算结果的数组，UInt64? 代表可以赋值为普通 UInt64 类型的值以及 null 值private static UInt64?[] fibnacciResults = new UInt64?[100];        static void Main(string[] args)
        {/* * 测试环境
             * 
             * Surface Pro3 i7
             * i7 4650U + 8G
             * 
             */Stopwatch timer = Stopwatch.StartNew();for (int N = 0; N 

1.1.20

题目

编写一个递归的静态方法计算 ln(N!) 的值。

解答

根据对数的性质可以得到：

ln(N!) = ln(N) + ln(N – 1) + ln(N – 2)…

代码

static void Main(string[] args)
        {int N = 4;
            Console.WriteLine($"{factorialLn(N)}");
        }//ln(N!) =//ln(N * (N - 1) * ... * 1) =//ln(N) + ln((N - 1)!)public static double factorialLn(int N)
        {if (N == 1)
            {return 0;
            }return Math.Log(N) + factorialLn(N - 1);
        }

1.1.21

题目

编写一段程序，从标准输入按行读取数据，其中每行都包含一个名字和两个整数。
然后用 printf() 打印一张表格，
每行的若干列数据包含名字、两个整数和第一个整数除以第二个整数的结果，
精确到小数点后三位。
可以用这种程序将棒球球手的击球命中率或者学生的考试分数制成表格。

解答

实现上没什么难度，打印表格的部分可以参考之前打印二位布尔数组的方法。

注意整型数据之间相除得到的仍然是整型，小数部分会直接舍去，例如 2 / 3 = 0。

代码

static void Main(string[] args)
        {int columns = 2;int rows = int.Parse(Console.ReadLine());   //行号string[] names = new string[rows];          //姓名int[,] array = new int[rows, columns];      //输入的两个整数double[] results = new double[rows];        //计算结果for (int i = 0; i 

1.1.22

题目

使用 1.1.6.4 节中的 rank() 递归方法重新实现 BinarySearch 并跟踪该方法的调用。
每当该方法被调用时，打印出它的参数 lo 和 hi 并按照递归的深度缩进。
提示：为递归方法添加一个参数来保存递归的深度。

解答

按照书中的提示增加一个保存深度的参数。

代码

class BinarySearch
    {static void Main(string[] args)
        {int[] array = new int[10] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

            rank(9, array);
        }//重载方法，用于启动二分查找public static int rank(int key, int[] a)
        {return rank(key, a, 0, a.Length - 1, 1);
        }//二分查找public  static int rank(int key, int[] a, int lo, int hi, int number)
        {for (int i = 0; i  hi)
            {return -1;
            }int mid = lo + (hi - lo) / 2;if (key  a[mid])
            {return rank(key, a, mid + 1, hi, number + 1);
            }else{return mid;
            }
        }
    }

1.1.23

题目

为 BinarySearch 的测试用例添加一个参数：
+ 打印出标准输入中不在白名单上的值；
- 则打印出标准输入中在白名单上的值。

解答

在主函数里做一下判断就可以了，加号则输出所有找不到的值，减号则相反。

代码

static void Main(string[] args)
        {//从largeW.txt中读取数据string[] whiteList = File.ReadAllLines("largeW.txt");int[] WhiteList = new int[whiteList.Length];            for (int i = 0; i (WhiteList);

            Console.WriteLine("Type the numbers you want to query: ");//输入样例：5 824524 478510 387221string input = Console.ReadLine();int[] Query = new int[input.Split(' ').Length];for (int i = 0; i  hi)
            {return -1;
            }int mid = lo + (hi - lo) / 2;if (key  a[mid])
            {return rank(key, a, mid + 1, hi);
            }else{return mid;
            }
        }

1.1.24

题目

给出使用欧几里得算法计算 105 和 24 的最大公约数的过程中得到的一系列 p 和 q 的值。
扩展该算法中的代码得到一个程序 Euclid，从命令行接受两个参数，
计算它们的最大公约数并打印出每次调用递归方法时的两个参数。
使用你的程序计算 1111111 和 1234567 的最大公约数。

解答

在书本中 GCD 的基础上，在函数开始时增加一条输出语句即可。

代码

static void Main(string[] args)
        {
            GCD(105, 24);
            Console.WriteLine();
            GCD(111111, 1234567);
        }public static int GCD(int a, int b)
        {
            Console.WriteLine($"{a} {b}");if (b == 0)
            {return a;
            }return GCD(b, a % b);
        }

1.1.25

题目

用数学归纳法证明欧几里得算法能够计算出任意一对非负整数 p 和 q 的最大公约数

解答

证明见代码。

也可以访问维基百科：辗转相除法

代码

namespace _1._1._25
{/* * 1.1.25
     * 
     * 用数学归纳法证明欧几里得算法能够计算出任意一对非负整数 p 和 q 的最大公约数
     * 
     */class Program
    {static void Main(string[] args)
        {/* 证明：
             * 
             * 已知： a, b 皆为正整数，且 a > b。g 是 a、b 的最大公约数
             * 设 r0 = a % b, rk = rk-2 % rk-1
             * 那么有 gcd(a, b) = gcd(b, r0) = gcd(r0, r1)... = gcd(rn-1, rn)
             * 且 rn = 0 （此时算法终止）
             * 
             * 由于 rn-2 = qn * rn - 1 + rn = qn * rn-1 （qn = [rn-2 / rn-1] []代表向下取整)
             * 可得 rn-2 能被 rn-1 整除
             * 则 
             * rn-3 = qn-1 * rn-2 + rn-1 
             * = qn-1 * (qn * rn-1) + rn-1 （代入 rn-2 = qn * rn-1）
             * = qn-1 * qn * rn-1 + rn-1
             * = (qn-1 * qn + 1) * rn-1
             * 可得 rn-3 也能被 rn-1 整除
             * 以此类推，rn-1 可以整除 a 和 b，即 rn-1 是 a 和 b 的公约数
             * 则 rn-1 

提高题（1.1.26~1.1.34）

1.1.26

题目

将三个数字排序。
假设 a、b、c 和 t 都是同一种原始数字类型的变量。
证明如下代码能够将 a、b、c 按照升序排列。

if (a > b) { t = a; a = b; b = t; }if (a > c) { t = a; a = c; c = t; }if (b > c) { t = b; b = c; c = t; }

解答

见代码部分。

代码

static void Main(string[] args)
        {int a = 3;int b = 2;int c = 1;int t = 0;if (a > b) { t = a; a = b; b = t; } //如果 a > b，那么 a, b 交换，保证b >= aif (a > c) { t = a; a = c; c = t; } //如果 b >= a > c，那么 a, c 交换，保证 c >= aif (b > c) { t = b; b = c; c = t; } //如果 b > c >= a，那么 b, c 交换，保证 c >= bConsole.WriteLine($"{a} {b} {c}");  //最终结果为 c >= b >= a，保证升序排列}

1.1.27

题目

二项分布。
估计用以下代码计算 binomial(100, 50, 0.25) 将会产生的递归调用次数：

public static double binomial(int N, int k, double p)
{if (N == 0 && k == 0)    return 1.0;if (N 

将已经计算过的值保存在数组中并给出一个更好的实现。

解答

与之前的斐波那契数列类似，都是重复计算的问题。

7751次。

代码

class Program
    {static int BinomialCalled = 0;  //计算递归调用次数static double?[,] BinomialCache;    //保存计算结果的数组static void Main(string[] args)
        {
            BinomialCache = new double?[101, 51];
            Console.WriteLine(Binomial(100, 50, 0.25));
            Console.WriteLine(BinomialCalled);
        }public static double? Binomial(int N, int k, double p)
        {
            BinomialCalled++;if (N == 0 && k == 0)return 1.0;if (N 

1.1.28

题目

删除重复元素。
修改 BinarySearch 类中的测试用例来删去排序之后白名单中的所有重复元素。

解答

实现方法有很多，这里是使用一个 HashSet 做中转，删除所有的重复元素。

也可以使用 Linq 里的 Distinct() 方法，

也可以排序后直接遍历一遍，遇到相同的就删除，遇到不同的就保存起来用于之后的比较。

代码

static void Main(string[] args)
        {//从largeW.txt中读取数据//用 HashSet 的不可重复性去除重复HashSet<string> h = new HashSet<string>(File.ReadAllLines("largeW.txt"));string[] whiteList = new string[h.Count];
            h.CopyTo(whiteList);int[] WhiteList = new int[whiteList.Length];for (int i = 0; i (WhiteList);

            Console.WriteLine("Type the numbers you want to query: ");//输入样例：5 824524 478510 387221string input = Console.ReadLine();int[] Query = new int[input.Split(' ').Length];for (int i = 0; i  hi)
            {return -1;
            }int mid = lo + (hi - lo) / 2;if (key  a[mid])
            {return rank(key, a, mid + 1, hi);
            }else{return mid;
            }
        }</string></string>

1.1.29

题目

等值键。
为 BinarySearch 类添加一个静态方法 rank()，
它接受一个键和一个整型有序数组（可能存在重复值）作为参数
并返回数组中小于该键的元素数量，
以及一个类似的方法 count() 来返回数组中等于该键的元素数量。

注意：
如果 i 和 j 分别是 rank(key, a) 和 count(key, a) 的返回值，
那么 a[i..i + j - 1] 就是数组中所有和 key 相等的元素。

解答

查找小于指定值的元素数量可以多次使用二分查找实现。

例如：

序号：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 个

用同样的方法可以找到大于指定值的元素个数，从总数中减去这两个数值就是等于指定值的元素数量。

代码

static void Main(string[] args)
        {int[] WhiteList = new int[] { 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6 };

            Array.Sort<int>(WhiteList);

            Console.WriteLine("Type the numbers you want to query: ");string input = Console.ReadLine();int[] Query = new int[input.Split(' ').Length];for (int i = 0; i  upperBound)
                {
                    upperBound = result;
                }
            }return upperBound - lowerBound + 1;
        }//返回数组中小于该数的数字个数public static int rank(int key, int[] a)
        {int mid = rank(key, a, 0, a.Length - 1);if (mid == -1)return 0;int result = mid;while (true)
            {
                result = rank(key, a, 0, mid - 1);if (result == -1)break;if (result  hi)
            {return -1;
            }int mid = lo + (hi - lo) / 2;if (key  a[mid])
            {return rank(key, a, mid + 1, hi);
            }else{return mid;
            }
        }
    }</int>

1.1.30

题目

数组练习。
编写一段程序，创建一个 N×N 的布尔数组 a[][]。
其中当 i 和 j 互质时（没有相同的因子），a[i][j] 为 true，否则为 false。

解答

互质可以用之前的 GCD 最大公因数算法判断，如果最大公因数是 1 则两数互质。

代码

//互质 = 最大公约数为 1 = gcd(i, j) == 1static void Main(string[] args)
        {int N = int.Parse(Console.ReadLine());bool[,] a = new bool[N, N];for (int i = 0; i 

1.1.31

题目

随机连接。
编写一段程序，从命令行接受一个整数 N 和 double 值 p （0 到 1 之间）作为参数，
在一个圆上画出大小为 0.05 且间距相等的 N 个点，
然后将每对点按照概率 p 用灰线连接。

解答

概率的实现方法：

例如概率是 60 %，就在 [0, 100) 之间随机一个值，小于等于 60 则执行操作，反之不执行。

需要更精确的情况可以增大随机的范围，例如 [0, 1000)。

绘图结果：

N = 10,p = 0.2, 0.5, 1

完整项目可以到 Github 上下载。

代码（绘图部分）

/// <summary>/// 主绘图函数/// </summary>/// <param>点的总数目/// <param>每对点之间连接的概率public static void StartDrawing(int N, double p)
        {int pointSize = 5;//每个点绘制的大小int precious = 1000;//概率判断的精度//新建一个绘图窗口Form2 DrawPad = new Form2();//显示绘图窗口            DrawPad.Show();//新建画布Graphics graphics = DrawPad.CreateGraphics();//建立绘图区域（矩形）Rectangle rect = new Rectangle(10, 10, 400, 400);            //画圆            graphics.DrawEllipse(Pens.Black, rect);//计算旋转角度double rotateDgree = 360.0 / N;//计算点的坐标Point Center = new Point(rect.Top + rect.Height / 2, rect.Top + rect.Height / 2);
            Point[] points = new Point[N];
            points[0].X = rect.Left + rect.Width / 2;
            points[0].Y = rect.Top;for (int i = 1; i /// 计算一个点绕某点旋转之后的坐标值/// /// <param>旋转的圆心/// <param>需要旋转的点/// <param>旋转的角度（逆时针）/// <returns>返回旋转后的坐标</returns>public static Point Rotate(Point origin, Point point, double dgree)
        {
            Point rotated = new Point();double dgreePi = dgree / 180 * Math.PI;

            rotated.X = (int)((point.X - origin.X) * Math.Cos(dgreePi) -(point.Y - origin.Y) * Math.Sin(dgreePi) + origin.X);
            rotated.Y = (int)((point.X - origin.X) * Math.Sin(dgreePi) +(point.Y - origin.Y) * Math.Cos(dgreePi) + origin.Y);return rotated;
        }

1.1.32

题目

直方图。
假设标准输入流中含有一系列 double 值。
编写一段程序，从命令行接受一个整数 N 和两个 double 值 l 和 r。
将 (l, r) 分为 N 段并使用 StdDraw 画出输入流中的值落入每段的数量的直方图。

解答

绘图结果：

完整的项目代码可以去 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 

1.1.33

Titel

Matrixbibliothek.
Schreiben Sie eine Matrix-Bibliothek und implementieren Sie die folgende API

public class Matrix	功能
static double dot(double[] x, double[] y)	实现向量点乘
static double[][] mult(double[][] a, double[][] b)	矩阵与矩阵相乘
static double[][] transpose(double[][] a)	矩阵转置
static double[] mult(double[][] a, double[] x)	矩阵与向量相乘
static double[] mult(double[] y, double[][] a)	向量与矩阵相乘

öffentliche Klassenmatrix

Funktion

statischer Doppelpunkt (double[] x, double[] y)

Vektorpunktmultiplikation implementieren

statisches double[][] mult(double[][] a , double[][] b)

Matrixmultiplikation mit Matrix

static double[][] transpose(double[][] a)

Matrix transpose

statisches double[] mult(double[][] a, double[] x)

Matrix- und Vektormultiplikation

statisches double[] mult(double[] y, double[][] a )

Multiplikation von Vektoren und Matrizen

编写一个测试用例，从标准输入读取矩阵并测试所有方法。

解答

这里矩阵使用交错数组实现（方便取行向量），不是普通的二维数组。

矩阵和矩阵、矩阵和向量、向量和矩阵都使用行向量点乘列向量的方式计算。

代码

public class Matrix
    {/// <summary>/// 计算两个向量的点积/// </summary>/// <param>需要点乘的向量/// <param>需要点乘的另一个向量/// <returns>返回点乘的结果</returns>/// <exception></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 /// 计算两个矩阵相乘的结果，返回一个矩阵/// /// <param>用交错数组表示的 m * p 矩阵/// <param>用交错数组表示的 p * n 矩阵/// <returns>返回 m * n 的矩阵</returns>/// <exception></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].Length != b.GetLength(0))
            {throw new FormatException("a's column number must be equal to b's row number");
            }int m = a.GetLength(0);int n = b[0].Length;int p = a[0].Length;double[][] result = new double[m][];for (int i = 0; i /// 将一个矩阵转置/// /// <param>待转置的矩阵/// <returns>返回转置后的数组</returns>public static double[][] Transpose(double[][] a)
        {double[][] trans = new double[a[0].Length][];for (int i = 0; i /// 计算矩阵与向量的乘积/// /// <param>左乘的矩阵/// <param>列向量/// <returns>返回一个向量</returns>/// <exception></exception>public static double[] Mult(double[][] a, double[] x)
        {if (a[0].Length != x.Length)
            {throw new FormatException("a's column number must be equal to x's length");
            }double[] result = new double[a.GetLength(0)];for (int i = 0; i /// 计算向量与矩阵的乘积/// /// <param>行向量/// <param>矩阵/// <returns>返回一个向量</returns>/// <exception></exception>public static double[] Mult(double[] x, double[][] a)
        {if (a.GetLength(0) != x.Length)
            {throw new FormatException("a's column number must be equal to x's length");
            }double[] result = new double[a[0].Length];for (int i = 0; i /// 在控制台上输出矩阵/// /// <param>需要输出的矩阵public static void PrintMatrix(double[][] a)
        {for (int i = 0; i /// 在控制台上输出一行向量/// /// <param>需要输出的向量public static void PrintVector(double[] a)
        {for (int i = 0; i 

1.1.34

题目

过滤。
以下那些任务需要（在数组中，比如）保存标准输入中的所有值？
那些可以被实现为一个过滤器且仅使用固定数量的变量和固定大小的数组（和 N 无关）？
每个问题中，输入都是来自于标准输入且含有 N 个 0 到 1 的实数。

• 打印出最大和最小的数

• 打印出所有数的中位数

• 打印出第 k 小的数， k 小于 100

• 打印出所有数的平方和

• 打印出 N 个数的平均值

• 打印出大于平均值的数的百分比

• 将 N 个数按照升序打印

• 将 N 个数按照随机顺序打印

解答

第二个以及最后三个需要，其他都可以设计成过滤器的模式。

这里的 largeW.txt 只需要保留前 100 个数字就可以了，太多的话最后两个测试会刷屏。

代码

static void Main(string[] args)
        {string[] AllNumbers = File.ReadAllLines("largeW.txt");int N = AllNumbers.Length;int[] input = new int[N];for (int i = 0; i /// 获取最大值和最小值/// /// <param>输入流static void MinAndMax(int[] input)
        {//只用到了两个变量int min = input[0];int max = input[0];//只对输入值正向遍历一遍，不需要保存for (int i = 1; i  max)
                {
                    max = input[i];
                }if (input[i] /// 获取中位数/// /// <param>输入流/// <returns>中位数</returns>static int MidNumber(int[] input)
        {//需要对输入值进行去重 & 排序，故需要保存List<int> DistinctNumbers = new List<int>(input.Distinct());
            DistinctNumbers.Sort();
            Console.WriteLine("MidNumber:");
            Console.WriteLine(DistinctNumbers[DistinctNumbers.Count / 2]);return DistinctNumbers[DistinctNumbers.Count / 2];
        }/// <summary>/// 获取第 k 小的数/// </summary>/// <param>需要获取的排名/// <param>输入流/// <returns>第 k 小的数</returns>static int NumberK (int k, int[] input)
        {int[] temp = new int[101];//只正向遍历一遍，不需要保存for (int i = 0; i /// 计算输入流中所有数的平方和/// /// <param>输入流/// <returns>所有数的平方和</returns>static long SquareSum(int[] input)
        {long sum = 0;//只正向遍历一遍，不需要保存for (int i = 0; i /// 计算所有输入数据的平均值/// /// <param>输入流/// <returns>所有输入数据的平均值</returns>static double Average(int[] input)
        {long sum = 0;//只遍历一遍，且不保存整个数组for (int i = 0; i /// 计算大于平均值的元素数量/// /// <param>输入流/// <returns>大于平均值的元素数量</returns>static double AboveAverage(int[] input)
        {double ave = Average(input);
            Console.WriteLine();double count = 0;for (int i = 0; i  ave)
                {
                    count++;
                }
            }


            Console.WriteLine("AboveAverage:");
            Console.WriteLine($"{(count / input.Length) * 100}%");return count;
        }/// <summary>/// 升序打印数组/// </summary>/// <param>输入流static void Ascending(int[] input)
        {
            Array.Sort(input);

            Console.WriteLine("Ascending:");for (int i = 0; i /// 随机打印数组/// /// <param>输入流static void Shuffle(int[] input)
        {
            Random random = new Random();
            List<int> All = new List<int>(input);int N = input.Length;int temp = 0;

            Console.WriteLine("Shuffle:");for (int i = 0; i </int></int></int></int>

实验题（1.1.35~1.1.39）

1.1.35

题目

模拟掷骰子。
以下代码能够计算每种两个骰子之和的准确概率分布：

int SIDE = 6;double[] dist = new double[2 * SIDES + 1];for (int I = 1; i 

dist[i] 的值就是两个骰子之和为 i 的概率。
用实验模拟 N 次掷骰子，
并在计算两个 1 到 6 之间的随机整数之和时记录每个值出现频率以验证它们的概率。
N 要多大才能够保证你的经验数据和准确数据的吻合程度达到小数点后 3 位？

解答

这里用 Random 类模拟掷骰子并计算概率，最后和程序得出的比较。

代码

//程序运行大概需要十几秒时间（也可能更长，看运气）//我的数据：//24098 44448 37776 44401 32541static void Main(string[] args)
        {//书中给出的程序int SIDES = 6;double[] dist = new double[2 * SIDES + 1];for (int i = 1; i = error)
                        isAccepted = false;
                }
                N++;
            }

            Console.WriteLine($"N:{N}\n");for (int i = 0; i 

1.1.36

题目

乱序检查。
通过实验检查表 1.1.10 中的乱序代码是否能够产生预期的效果。
编写一个程序 ShuttleTest，接受命令行参数 M 和 N，
将大小为 M 的数组打乱 N 次且在每次打乱之前都将数组重新初始化为 a[i] = i。
打印一个 M×M 的表格，对于所有的列 j，行 i 表示的是 i 在打乱后落到 j 的位置的次数。
数组中的所有元素的值都应该接近于 N/M。

解答

N 取到 1000 左右数据就比较明显了。

N = 1000， M = 10

代码

static void Main(string[] args)
        {int M = 10;//数组大小int N = 1000;//打乱次数int[] a = new int[10];int[,] result = new int[M, M];for (int i = 0; i /// 打乱数组/// /// <param>需要打乱的数组/// <param>用于生成随机数的种子值static void Shuffle(int[] a, int seed)
        {int N = a.Length;
            Random random = new Random(seed);for (int i = 0; i /// 在控制台上输出矩阵/// /// <param>需要输出的矩阵public static void PrintMatrix(int[,] a)
        {for (int i = 0; i 

1.1.37

题目

糟糕的打乱。
假设在我们的乱序代码中你选择的是一个 0 到 N - 1 而非 i 到 N - 1 之间的随机整数。
证明得到的结果并非均匀地分布在 N! 种可能性之间。
用上一题中的测试检验这个版本。

解答

使用 0~N-1 的随机数会导致每次交换的数字可能相同。
例如：
原数组： 1 2 3 4。
第一次： 2 1 3 4 random = 1，第 0 个和第 1 个交换。
第二次： 1 2 3 4 random = 0，第 1 个和第 0 个交换。

代码

static void Main(string[] args)
        {int M = 10;//数组大小int N = 100000;//打乱次数int[] a = new int[10];int[,] result = new int[M, M];for (int i = 0; i /// 打乱数组（不够好的版本）/// /// <param>需要打乱的数组/// <param>用于生成随机数的种子值static void Shuffle(int[] a, int seed)
        {int N = a.Length;
            Random random = new Random(seed);for (int i = 0; i /// 在控制台上输出矩阵/// /// <param>需要输出的矩阵public static void PrintMatrix(int[,] a)
        {for (int i = 0; i 

1.1.38

题目

二分查找与暴力查找。

根据 1.1.10.4 节给出的暴力查找法编写一个程序 BruteForceSearch，
在你的计算机上比较它和 BinarySearch 处理 largeW.txt 和 largeT.txt 所需的时间。

解答

为了使差距比较明显，故意取了比较靠后的数字。

代码

static void Main(string[] args)
        {string[] largeWString = File.ReadAllLines("largeW.txt");int[] largeW = new int[largeWString.Length];for (int i = 0; i  hi)
            {return -1;
            }int mid = lo + (hi - lo) / 2;if (key  a[mid])
            {return rank(key, a, mid + 1, hi, number + 1);
            }else{return mid;
            }
        }

1.1.39

题目

随机匹配。
编写一个使用 BinarySearch 的程序，
它从命令行接受一个整型参数 T，
并会分别针对 N = 10^3、10^4、10^5 和 10^6 将以下实验运行 T 遍：
生成两个大小为 N 的随机 6 位正整数数组并找出同时存在于两个数组中的整数的数量。
打印一个表格，对于每个 N，给出 T 次实验中该数量的平均值。

解答

按照要求编程就好，视机器不同需要的时间也不同。

代码

//需要 6 秒左右的运算时间static void Main(string[] args)
        {
            Random r = new Random();int baseNum = 10;int powNum = 3;int T = 10;int M = 4;double[,] Matrix = new double[M,2];for (int i = 0; i /// 执行一次“实验”/// /// <param>数组的大小/// <param>随机种子/// <returns>返回相同数字的数目</returns>static int Test(int N, int seed)
        {
            Random random = new Random(seed);int[] a = new int[N];int[] b = new int[N];int count = 0;for (int i = 0; i  hi)
            {return -1;
            }int mid = lo + (hi - lo) / 2;if (key  a[mid])
            {return rank(key, a, mid + 1, hi, number + 1);
            }else{return mid;
            }
        }/// <summary>/// 在控制台上输出矩阵/// </summary>/// <param>需要输出的矩阵public static void PrintMatrix(double[,] a)
        {for (int i = 0; i 

Das obige ist der detaillierte Inhalt vonAusführliche Erläuterung von Beispielen für Algorithmen in C#. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!