《算法》练习题1.1.1--1.1.39 答案解析
文章目錄
- 0.0.0
- 1.1.1
- 1.1.2
- 1.1.3
- 1.1.4
- 1.1.5
- 1.1.6
- 1.1.7
- 1.1.8
- 1.1.9
- 1.1.10
- 1.1.11
- 1.1.12
- 1.1.13
- 1.1.14
- 1.1.15
- 1.1.16
- 1.1.17
- 1.1.18
- 1.1.19
- 1.1.20
- 1.1.21
- 1.1.22
- 1.1.23
- 1.1.24
- 1.1.26
- 1.1.27
- 1.1.28
- 1.1.29
- 1.1.30
- 1.1.31
- 1.1.32
- 1.1.33
- 1.1.35
- 1.1.36
- 1.1.37
- 1.1.38
- 1.1.39
0.0.0
答案解析代碼在我的github：BitHachi/Algorithm-Four
本篇文章已同步到：https://www.bithachi.cn/posts/801dfee5.html
1.1.1
1.1.2
1.1.3
1.1.4
1.1.5
1.1.6
1.1.7
1.1.8
1.1.9
1.1.10
1.1.11
1.1.12
1.1.13
1.1.14
1.1.15
1.1.16
給出exR1(6)的返回值
1.1.17
見書，書上有解析
1.1.18
1.1.19
public class Fibonacci{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)，用數組保存已經計算過的值。
1.1.20
編寫一個遞歸的靜態方法計算ln(N!)的值。
1.1.21
編寫一段程序，從標準輸入按行讀取數據，其中每行都包含一個名字和兩個整數。然后用printf()打印一張表格，每行的若干列數據包括名字、兩個整數和第一個整數除以第二個整數的結果，精確到保留小數點后三位。
1.1.22
使用1.1.6.4節中的rank(遞歸方法重新實現BinarySearch并跟蹤該方法的調用。每當該方法被調用時，打印出它的參數1o和hi并按照遞歸的深度縮進。提示:為遞歸方法添加一個參數來保存遞歸的深度。
1.1.23
為BinarySearch的測試用例添加一個參數:
+ 打印出標準輸人中不在白名單上的值;
-則打印出標準輸人中在白名單上的值。
1.1.24
- 給出使用歐幾里德算法計算105和24的最大公約數的過程中得到的一系列p 和q的值。
- 擴展該算法中的代碼得到一個程序Euclid, 從命令行接受兩個參數，計算它們的最大公約數并打印出每次調用遞歸方法時的兩個參數。
- 使用你的程序計算111 111和1 234 567的最大公約數。
1.1.26
將三個數字排序。假設a,b,c和t都是同一種原始數字類型的變量。證明以下代碼能夠將a,b,c按照升序排列。
1.1.27
二項分布。 估計用以下代碼計算binomial(100，50，0.25)將會產生的遞歸調用次數。
將已經計算過的值保存在數組中并給出一個更好的實現。
1.1.28
刪除重復元素。 修改BinarySearch類中的測試用例來刪去排序后白名單中的所有元素。
1.1.29
等值鍵。為BinarySearch類添加一個靜態方法rank(),它接受一個鍵和一個整型有序數組(可能存在重復鍵)作為參數并返回數組中小于該鍵的元素數量，以及一個類似的方法count()來返回數組中等于該鍵的元素的數量。
注意:如果i和j分別是rank(key,a)和count(key ,a)的返回值，那么a[i…i+j-1]就是數組中所有和key相等的元素。
1.1.30
數組練習。編寫一段程序，創建一個NxN的布爾數組a[][]。其中當i和j互質時(沒有相同因子)，a[i][j] 為true,否則為false。
1.1.31
隨機連接。編寫一段程序，從命令行接受一個整數N和double值p (0到1之間)作為參數，在一個圓上畫出大小為0.05且間距相等的N個點，然后將每對點按照概率p用灰線連接。
1.1.32
直方圖。假設標準輸人流中含有一系列double值。編寫-段程序， 從命令行接受一個整數 N和兩個double值l和r。將(I, r)分為N段并使用StdDraw畫出輸人流中的值落人每段的數量的直方圖。
1.1.33
1.1.35
模擬擲骰子。以下代碼能夠計算每種兩個骰子之和的準確概率分布：
int SIDES = 6; double[] dist = new double[2 * SIDES + 1]; for(int i = 1; i <= SIDES; i++)for(int j = 1; j <= SIDES; j++)dist[i+j] += 1.0; for (int k = 2; k <= 2*SIDES; k++)dist[k] /= 36.0;dist[i] 的值就是兩個骰子之和為i 的概率。用實驗模擬N 次擲骰子，并在計算兩個1 到 6 之間的隨機整數之和時記錄每個值的出現頻率以驗證它們的概率。N 要多大才能夠保證你的經驗數據和準確數據的吻合程度達到小數點后三位？
1.1.36
亂序檢查。通過實驗檢查表1.1.10中亂序代碼是否能夠產生預期的效果。編寫一個程序ShuffleTest,接受命令行參數M和N,將大小為M的數組打亂N次且每次打亂之前都將數組重新初始化為a[i]=i.打印一個MXM的表格，對于所有的列j,行i表示的是i在打亂后落到j的位置的次數。數組中的所有元素的值都應該接近于N/M。
package Chapter1.Section11;import edu.princeton.cs.algs4.StdOut; import edu.princeton.cs.algs4.StdRandom;/** * @Program: Algorithm * @ClassName: EX36 * @Author: Mr.BitHachi * @CreateTime: 2020-07-16 19:11 * @Version: V1.0 * @Description: 練習題1.1.36 * * 參考：https://www.cnblogs.com/longjin2018/p/9848742.html **/public class EX36 {public static void main(String[] args){ // int M=Integer.parseInt(args[0]); // int N=Integer.parseInt(args[1]);int M=6,N=10;int[] a=new int[M];int[][] Info=new int[M][M];//N次打亂for(int k=0;k<N;k++){//每次打亂前數組重新初始化為a[i]=ifor(int i=0;i<M;i++)a[i]=i;//打亂shuffle(a);//打亂后i行的值落到j列的次數增1for(int i=0;i<a.length;i++)Info[a[i]][i]++;}//打印M*M數組printArray(Info);}//打亂數組public static void shuffle(int[] a){int N=a.length;for (int i=0;i<N;i++){int r=i+ StdRandom.uniform(N-i);//返回0~N-i之間的整數再加iint temp=a[i];a[i]=a[r];a[r]=temp;}}//結束打亂//打印數組private static void printArray(int[][] array){int rowLen=array.length;int colLen=array[0].length;StdOut.printf(" ");for (int col=0;col<colLen;col++)StdOut.printf("%5d",col);StdOut.printf("\n");//for (int row=0;row<rowLen;row++){StdOut.printf("%d",row);for (int col=0;col<colLen;col++)StdOut.printf("%5d",array[row][col]);StdOut.printf("\n");}} }1.1.37
糟糕的打亂。假設在我們的亂序代碼中你選擇的是一個0 到N-1 而非i 到N-1 之間的隨機整數。證明得到的結果并非均勻地分布在N! 種可能性之間。用上一題中的測試檢驗這個版本。
package Chapter1.Section11;import edu.princeton.cs.algs4.StdRandom;/*** @Program: Algorithm* @ClassName: EX37* @Author: Mr.BitHachi* @CreateTime: 2020-07-16 19:23* @Version: V1.0* @Description: 練習題1.1.37**/public class EX37 {public static void shuffle(int[] a) {int N = a.length;for (int i = 0; i < N; i++) {int r = StdRandom.uniform(N); // [0,N)int temp = a[i];a[i] = a[r];a[r] = temp;}}public static void main(String[] args) { // if (args.length < 2) { // System.out.println("Error"); // return; // } // int M = Integer.parseInt(args[0]), N = Integer.parseInt(args[1]);int M=6,N=10;int[] a = new int[M];int[][] Info=new int[M][M];for(int k=0;k<N;k++){//每次打亂前數組重新初始化為a[i]=ifor(int i=0;i<M;i++)a[i]=i;//打亂shuffle(a);//打亂后i行的值落到j列的次數增1for(int i=0;i<a.length;i++)Info[a[i]][i]++;}for(int []i : Info) {for (int j:i)System.out.print(j + " ");System.out.println();}} }1.1.38
二分查找與暴力查找。根據1.1.10.4 節給出的暴力查找法編寫一個程序bruteForceSearch，在你的計算機上比較它和BinarySearch 處理largeW.txt 和largeT.txt 所需的時間。
1.1.39
隨機匹配。編寫一個使用BinarySearch 的程序，它從命令行接受一個整型參數T，并會分別針對N=103、104、10^5 和10^6 將以下實驗運行 T 遍：生成兩個大小為N 的隨機6 位正整數數組并找出同時存在于兩個數組中的整數的數量。打印一個表格，對于每個N，給出T 次實驗中該數量的平均值。
package Chapter1.Section11;import edu.princeton.cs.algs4.StdRandom;import java.util.Arrays;/*** @Program: Algorithm* @ClassName: EX39* @Author: Mr.BitHachi* @CreateTime: 2020-07-16 19:57* @Version: V1.0* @Description: 練習題1.1.39**/public class EX39 {public static void main(String[] args) { // int T = Integer.parseInt(args[0]);int T=6;int[] num = new int[4];for (int i = 0; i < T; i++) {//對N為10^3 10^4 10^5 10^6運行T遍int N = 100;for (int j = 0; j < 4; j++) {N *= 10; //對N為10^3 10^4 10^5 10^6運行T遍int[] a = new int[N];int[] b = new int[N];for (int k = 0; k < N; k++) {a[k] = StdRandom.uniform(100000, 1000000);//[100000, 1000000)b[k] = StdRandom.uniform(100000, 1000000);}Arrays.sort(a);for (int k = 0; k < N; k++) {//二分循環查找一個數組中的值是否在另一個數組中if (BinarySearch.indexOf(a, b[k]) != -1) {num[j]++; //對于每個N，N為10^3 10^4 10^5 10^6}}}}System.out.println("N\t\tAverage");int N = 100;for (int i = 0; i < 4; i++) {N *= 10;//N為10^3 10^4 10^5 10^6System.out.printf("%d\t%f\n", N, (double) num[i] / T);}} }參考：
- 《百科》
- 《算法：第四版》課后練習 1.1 答案
- github: https://github.com/jimmysuncpt/Algorithms
總結
以上是生活随笔為你收集整理的《算法》练习题1.1.1--1.1.39 答案解析的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 八大基本数据类型对应的八大包装类（含对应
- 下一篇： 计算机网络之数据链路层思维导图总结