寫在前面整個項目都托管在了 Github 上:https://github.com/ikesnowy/Algorithms-4th-Edition-in-Csharp善用 Ctrl + F 查找題目。本節你可能會需要的兩個測試數據文件:largeW: http://algs4.cs.princeto... ...
寫在前面
整個項目都托管在了 Github 上:https://github.com/ikesnowy/Algorithms-4th-Edition-in-Csharp
善用 Ctrl + F 查找題目。
本節你可能會需要的兩個測試數據文件:
largeW: http://algs4.cs.princeton.edu/11model/largeW.txt
largeT: http://algs4.cs.princeton.edu/11model/largeT.txt
習題 & 題解
練習(1.1.1~1.1.25)
1.1.1
題目
給出以下表達式的值:
a. (0 + 15) / 2
b. 2.0e-6 * 100000000.1
c. true && false || true && true
解答
a.7
b.1562500.0015625
c.True
代碼
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
題目
給出以下表達式的類型和值:
a. (1 + 2.236) / 2
b. 1 + 2 + 3 + 4.0
c. 4.1 >= 4
d. 1 + 2 + "3"
解答
Name Type Value
a System.Double 1.618
b System.Double 10
c System.Boolean True
d System.String 33
代碼
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
題目
編寫一個程式,從命令行獲取三個整數參數。
如果它們都相等則列印 equal,
否則列印 not equal。
解答
簡單的 if 判斷即可
代碼
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
題目
下列語句各有什麼問題(如果有的話)?
a. if (a > b) then c = 0;
b. if a > b { c = 0; }
c. if (a > b) c = 0;
d. if (a > b) c = 0 else b = 0;
解答
a. if 後跟 then 的語法不能在 C# 中使用。
b. if 後的判斷語句需要在括弧內。
c. 正確,只有一條語句時大括弧可以省略。
d. c = 0 後缺少分號。
代碼
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後缺少分號 }
1.1.5
題目
編寫一段程式,
如果 double 類型的變數 x 和 y 都嚴格位於 0 和 1 之間則列印 true
否則列印 false。
解答
比較簡單,直接判斷即可。
代碼
static void Main(string[] args) { //修改這兩個值進行測試 double x = 0.05; double y = 0.01; if (x > 0 && x < 1 && y > 0 && y < 1) { Console.WriteLine("true"); } else { Console.WriteLine("false"); } }
1.1.6
題目
下麵這段程式會列印出什麼?
解答
輸出斐波那契數列。
將書中的代碼直接實現即可。
代碼
//輸出斐波那契數列 static void Main(string[] args) { int f = 0; int g = 1; for (int i = 0; i <= 15; i++) { //Console.WriteLine與StdOut.println功能相同 //實現向控制台輸出一行 Console.WriteLine(f); f = f + g; g = f - g; } }
1.1.7
題目
分別給出以下代碼段列印出的值。
解答
同上題,直接實現即可。
a
3.00009
double計算存在誤差,並不精確。
b
499500
1000 + 999 + 998……
c
10000
1000 * 10,外層迴圈的結束條件為 2i > 1000。
代碼
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; i++) { for (int j = 0; j < i; j++) { sum++; } } Console.WriteLine(sum); } private static void c() { Console.WriteLine("\nc"); int sum = 0; for (int i = 1; i < 1000; i *= 2) { for (int j = 0; j < 1000; j++) { sum++; } } Console.WriteLine(sum); } static void Main(string[] args) { //a double 計算存在誤差 a(); //b 1000+999+998…… b(); //c 由於2^10 = 1024 > 1000,最終sum = 1000 * 10 = 10000 c(); }
1.1.8
題目
下列語句會列印出什麼結果?給出解釋。
解答
b
197
e
代碼
static void Main(string[] args) { Console.WriteLine('b'); Console.WriteLine('b' + 'c'); //char 被隱式轉為為 int 類型,取 ascii 碼 Console.WriteLine((char)('a' + 4)); //強制轉換後,ascii 碼被轉換為相應的字元 }
1.1.9
題目
編寫一段代碼,將一個正整數N用二進位表示並轉換為一個 String 類型的值 s。
解答
有兩種方法,要麼直接調用庫函數,要麼用書中給出的代碼轉換。
代碼
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); }
1.1.10
題目
下麵這段代碼有什麼問題?
解答
變數使用前需要先賦值。
代碼
static void Main(string[] args) { int[] a; for (int i = 0; i < 10; i++) { a[i] = i * i; //不允許使用未賦值的局部變數 } }
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 < columns; i++) { Console.Write($"\t{i + 1}"); } Console.Write("\n"); for (int i = 0; i < rows; i++) { //輸出行號 Console.Write($"{i + 1}"); for (int j = 0; j < columns; j++) { if (array[i, j]) { Console.Write($"\t*"); } else { Console.Write($"\t "); } } Console.Write("\n"); } }
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 < 10; i++) { a[i] = 9 - i; } //a[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0} for (int i = 0; i < 10; i++) { a[i] = a[a[i]]; } //a[0] = a[9] = 0; a[1] = a[8] = 1; a[2] = a[7] = 2;...... for (int i = 0; i < 10; i++) { Console.WriteLine(a[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 < M; i++) { for (int j = 0; j < N; j++) { array[i, j] = i + j; } } Console.WriteLine("Origin"); PrintArray2D(array, M, N); Console.WriteLine("Transposed"); PrintArrayTranspose2D(array, M, N); } //轉置輸出 private static void PrintArrayTranspose2D(int[,] array, int rows, int columns) { //交換行、列輸出順序 for (int i = 0; i < columns; i++) { for (int j = 0; j < rows; j++) { Console.Write($"\t{array[j, i]}"); } Console.Write("\n"); } } //正常輸出 private static void PrintArray2D(int[,] array, int rows, int columns) { for (int i = 0; i < rows; i++) { for (int j = 0; j < columns; j++) { Console.Write($"\t{array[i, j]}"); } Console.Write("\n"); } }
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 < N; ++pow) { sum *= baseNumber; } return pow - 1; }
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 < 10; ++i) { a[i] = i; } int[] result = Histogram(a, M); Console.WriteLine($"a.length: {a.Length}"); Console.WriteLine($"sum of result array: {result.Sum()}"); } static int[] Histogram(int[] a, int M) { int[] result = new int[M]; for (int i = 0; i < M; ++i) { //初始化 result[i] = 0; //遍曆數組,計算數組中值為 i 的元素個數 for (int j = 0; j < a.Length; ++j) { if (a[j] == i) //值為 i 的元素 { result[i]++; } } } return result; }
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 <= 0) { return ""; } return exR1(n - 3) + n + exR1(n - 2) + n; }
1.1.17
題目
找出以下遞歸函數的問題:
public static String exR2(int n) { String s = exR2(n - 3) + n + exR2(n - 2) + n; if (n <= 0) return ""; return s; }
解答
書中已經給出瞭解釋。
遞歸時結束條件必須放在遞歸語句的前面,否則會不斷展開而無法結束。
代碼
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 <= 0) return ""; return s; }
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 的值)。
同理對於乘冪 28,既可以用 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 做 8 次乘法,也可以只用三次乘法就計算出來:
22 = 2 * 2
24 = 22 * 22
28 = 24 * 24
這樣時間複雜度就從 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 = //50 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; } //mysteryChanged(a, b) = a ^ b //同理(乘方與乘法,乘法與加法之間具有類似的性質) //a ^ b = (a ^ 2) ^ (b / 2) = (a ^ 2) ^ ((b - 1) / 2) * a public 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 < 100; N++) StdOut.println(N + " " + F(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 < 100; ++N) { //書本中的代碼,非常慢,1小時後 N = 50 //Console.WriteLine($"{N} {F(N)}"); //利用已知結果加速 //全部計算完畢耗時 84ms Console.WriteLine($"{N} {BetterF(N)}"); } Console.WriteLine($"{timer.ElapsedMilliseconds} ms"); } //書中提供的代碼 public static UInt64 F(int N) { if (N == 0) return 0; if (N == 1) return 1; return F(N - 1) + F(N - 2); } //更好的實現,將已經計算的結果保存,不必重覆計算 public static UInt64? BetterF(int N) { if (N == 0) return 0; if (N == 1) return 1; if (fibnacciResults[N] != null) //如果已經計算過則直接讀取已知值 { return fibnacciResults[N]; } else { fibnacciResults[N] = BetterF(N - 1) + BetterF(N - 2); return fibnacciResults[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() 列印一張表格,
每行的若幹列數據包含名字、兩個整數和第一個整數除以第二個整數的結果,
精確到小數點後三位。
可以用這種程式將棒球球手的擊球命中率或者學生的