算法 第四版 習題 答案

1、1.1.1 給出以下表達式的值：a. ( 0 + 15 ) / 2b. 2.0e-6 * 100000000.1c. true && false | true && true答案：a.7,b.200.0000002 c.ture1.1.2 給出以下表達式的類型和值：a. (1 + 2.236)/2b. 1 + 2 + 3 + 4.0c. 4.1 >= 4d. 1 + 2 + "3"答案：a.1.618 b. 10.0 c.true d.331.1.3 編寫一個程序，從命令行得到三個整數(shù)參數(shù)。如果它們都相等則打印equal，否則打印not

2、 equal。public class TestUqual public static void main(String args)int a,b,c;a=b=c=0;StdOut.println("Please enter three numbers"); a =StdIn.readInt(); b=StdIn.readInt(); c=StdIn.readInt();if(equals(a,b,c)=1)StdOut.print("equal");elseStdOut.print("not equal");public stati

3、c int equals(int a ,int b , int c)if(a=b&&b=c)return 1;elsereturn 0;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 (a > b) c = 0; b. if (a > b) c = 0; 1.1.5 編寫一段程序，如果double 類型的變量x 和y 都嚴格位于0 和1 之

4、間則打印true，否則打印false。public class TestUqual public static void main(String args)double x;double y;x=StdIn.readDouble();y=StdIn.readDouble();StdOut.print(compare(x)&& compare(y);public static boolean compare(double x)If(x>0&&x<1)returen ture;else return false;1.1.6 下面這段程序會打印出什么？in

5、t f = 0;int g = 1;for (int i = 0; i <= 15; i+)StdOut.println(f);f = f + g;g = f - g;答案：0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 6101.1.7 分別給出以下代碼段打印出的值：a. double t = 9.0;while (Math.abs(t - 9.0/t) > .001)t = (9.0/t + t) / 2.0;StdOut.printf("%.5fn", t);b. int sum = 0;for (int i = 1; i

6、 < 1000; i+)for (int j = 0; j < i; j+)sum+;StdOut.println(sum);c. int sum = 0;for (int i = 1; i < 1000; i *= 2)for (int j = 0; j < 1000; j+)sum+;StdOut.println(sum);答案：a.3.00009 b.499500 c. 100001.1.8 下列語句會打印出什么結(jié)果？給出解釋。a. System.out.println('b');b. System.out.println('b'

7、+ 'c');c. System.out.println(char) ('a' + 4);答案：a. b b. 197 c. e1.1.9 編寫一段代碼，將一個正整數(shù)N 用二進制表示并轉(zhuǎn)換為一個String 類型的值s。解答：Java 有一個內(nèi)置方法Integer.toBinaryString(N) 專門完成這個任務，但該題的目的就是給出這個方法的其他實現(xiàn)方法。下面就是一個特別簡潔的答案：String s = ""for (int n = N; n > 0; n /= 2)s = (n % 2) + s;1.1.10 下面這段代碼有什么

8、問題？int a;for (int i = 0; i < 10; i+)ai = i * i;解答：它沒有用new 為a 分配內(nèi)存。這段代碼會產(chǎn)生一個variable a might not havebeen initialized 的編譯錯誤。1.1.11 編寫一段代碼，打印出一個二維布爾數(shù)組的內(nèi)容。其中，使用* 表示真，空格表示假。打印出行號和列號。public class Test public Test() / TODO Auto-generated constructor stubpublic static void main(String args) / TODO Auto-

9、generated method stubboolean a = new boolean1010;a=RandomInitial(a);/隨機初始化TestPrint(a);/打印數(shù)組public static void TestPrint(boolean a)for(int i=0;i<a.length;i+)/打印行號StdOut.print(" "+i);StdOut.println(" ");for(int i=0;i<10;i+)StdOut.print(i);for(int j=0;j<10;j+)if(aij)StdOut

10、.print("*"+" ");elseStdOut.print(" "+" ");StdOut.println(" ");public static boolean RandomInitial( boolean a)for(int i=0;i<a.length;i+)for(int j=0;j<a.length;j+)if(StdRandom.bernoulli(0.1)aij=true;elseaij=false;return a;1.1.12 以下代碼段會打印出什么結(jié)果？int

11、 a = new int10;for (int i = 0; i < 10; i+)ai = 9 - i;for (int i = 0; i < 10; i+)ai = aai;for (int i = 0; i < 10; i+)System.out.println(i);答案：0 1 2 3 4 5 6 7 8 9如System.out.println(ai);0 1 2 3 4 4 3 2 1 01.1.13 編寫一段代碼，打印出一個M 行N 列的二維數(shù)組的轉(zhuǎn)置（交換行和列）。public class Migrate public Migrate() / TODO Au

12、to-generated constructor stubpublic static void main(String args) / TODO Auto-generated method stubint m=5;int n=5; int a=new int mn; int b=new int nm; a=RandomInitial(a,n); /初始化二維數(shù)組 b=MigrateArrays(a,b); /轉(zhuǎn)置二維數(shù)組 MigratePrint(b);/輸出轉(zhuǎn)置二維數(shù)組 public static void MigratePrint(int a)StdOut.println("輸出

13、轉(zhuǎn)置二維數(shù)組:"); for (int i=0;i<a.length;i+) for(int j=0;j<a0.length;j+) StdOut.print(aij+" "); StdOut.println(); public static int MigrateArrays(int a,int b) for (int i=0;i<a.length;i+) for(int j=0;j<a0.length;j+) bji=aij; return b;public static int RandomInitial(int a,int N)St

14、dOut.println("初始化二維數(shù)組:"); for (int i=0;i<a.length;i+) for(int j=0;j<a0.length;j+) aij=StdRandom.uniform(N); StdOut.print(aij+" "); StdOut.println(); return a;1.1.14 編寫一個靜態(tài)方法lg()，接受一個整型參數(shù)N，返回不大于log2N 的最大整數(shù)。不要使用Math 庫。public static int lga(int N,int M)int a=0;while(N>=M)N=

15、N/M;a+;return a;1.1.15 編寫一個靜態(tài)方法histogram()，接受一個整型數(shù)組a 和一個整數(shù)M 為參數(shù)并返回一個大小為M的數(shù)組，其中第i個元素的值為整數(shù)i在參數(shù)數(shù)組中出現(xiàn)的次數(shù)。如果a中的值均在0到M-1之間，返回數(shù)組中所有元素之和應該和a.length 相等。public static int histogram(int a,int M)int b= new int M;int n=0;int m=0;for(int i=0;i<M;i+)for(int j=0;j<a.length;j+)if(i=aj)n+;bi=n;n=0;for(int i=0;i

16、<M;i+)m=m+bi;return b;1.1.16 給出exR1(6) 的返回值：public static String exR1(int n)if (n <= 0) return ""return exR1(n-3) + n + exR1(n-2) + n;答案：3113611422461.1.17 找出以下遞歸函數(shù)的問題：public static String exR2(int n)String s = exR2(n-3) + n + exR2(n-2) + n;if (n <= 0) return ""return s;

17、答：這段代碼中的基礎情況永遠不會被訪問。調(diào)用exR2(3) 會產(chǎn)生調(diào)用exR2(0)、exR2(-3) 和exR2(-6)，循環(huán)往復直到發(fā)生StackOverflowError。可以修改為：public static String exR2(int n)if (n <= 0) return ""String s = exR2(n-3) + n + exR2(n-2) + n;return s;1.1.18 請看以下遞歸函數(shù)：public static int mystery(int a, int b)if (b = 0) return 0;if (b % 2 = 0)

18、 return mystery(a+a, b/2);return mystery(a+a, b/2) + a;mystery(2, 25) 和mystery(3, 11) 的返回值是多少？給定正整數(shù)a 和b，mystery(a,b)計算的結(jié)果是什么？將代碼中的+ 替換為* 并將return 0 改為return 1，然后回答相同的問題。答案：50，33. 225 3111.1.19 在計算機上運行以下程序：public class Fibonaccipublic static long F(int N)if (N = 0) return 0;if (N = 1) return 1;return

19、 F(N-1) + F(N-2);public static void main(String args)for (int N = 0; N < 100; N+)StdOut.println(N + " " + F(N);計算機用這段程序在一個小時之內(nèi)能夠得到F(N) 結(jié)果的最大N 值是多少？開發(fā)F(N) 的一個更好的實現(xiàn)，用數(shù)組保存已經(jīng)計算過的值。public class Fibonaccipublic static long F(int N)if (N = 0) return 0;if (N = 1) return 1;return F(N-1) + F(N-2)

20、;public static void main(String args)int a=new int 100;a=A(a);public static long A(int a)a0=0; a1=1;for (int N = 2; N < 100; N+)aN=aN-1+aN-2; StdOut.println(N + " " +aN);1.1.20 編寫一個遞歸的靜態(tài)方法計算ln(N!) 的值。public static double factorialln(long N)if(N>1)return Math.ln(N)+factorialln(N-1);el

21、sereturn 0;1.1.21 編寫一段程序，從標準輸入按行讀取數(shù)據(jù)，其中每行都包含一個名字和兩個整數(shù)。然后用printf() 打印一張表格，每行的若干列數(shù)據(jù)包括名字、兩個整數(shù)和第一個整數(shù)除以第二個整數(shù)的結(jié)果，精確到小數(shù)點后三位。可以用這種程序?qū)羟蚯蚴值膿羟蛎新驶蛘邔W生的考試分數(shù)制成表格。public class ScoreTable public static void main(String args) String s = "Let's go for lunch!"In in = new In("Se"); String white

22、list = in.readAllStrings();/將文件中的字符串讀取到數(shù)組中 for(int i=0;i<whitelist.length;i=i+3) StdOut.print(whitelisti+" "+whitelisti+1+" "+whitelisti+2+" "); double m=Double.parseDouble(whitelisti+1); double n=Double.parseDouble(whitelisti+2); StdOut.printf("0.3%",m/n);

23、 StdOut.println(" "); 1.1.22 使用1.1.6.4 節(jié)中的rank() 遞歸方法重新實現(xiàn)BinarySearch 并跟蹤該方法的調(diào)用。每當該方法被調(diào)用時，打印出它的參數(shù)lo 和hi 并按照遞歸的深度縮進。提示：為遞歸方法添加一個參數(shù)來保存遞歸的深度。1.1.23 為BinarySearch 的測試用例添加一個參數(shù)：+ 打印出標準輸入中不在白名單上的值；-，則打印出標準輸入中在白名單上的值。public static int rank(int key, int a,char c) int lo = 0; int hi = a.length - 1;

24、if(c='+') while (lo <= hi) / Key is in alo.hi or not present. int mid = lo + (hi - lo) / 2; if (key < amid) hi = mid - 1; else if (key > amid) lo = mid + 1; else return mid; return -1; if(c='-') while (lo <= hi) / Key is in alo.hi or not present. int mid = lo + (hi - lo)

25、/ 2; if (key < amid) hi = mid - 1; else if (key > amid) lo = mid + 1; else return -1; return 0; else return -1; 1.1.24 給出使用歐幾里德算法計算105 和24 的最大公約數(shù)的過程中得到的一系列p 和q 的值。擴展該算法中的代碼得到一個程序Euclid，從命令行接受兩個參數(shù)，計算它們的最大公約數(shù)并打印出每次調(diào)用遞歸方法時的兩個參數(shù)。使用你的程序計算1 111 111 和1 234 567 的最大公約數(shù)。public static int CommomDivisor(i

26、nt x,int y)if(x=1|y=1)StdOut.println("x="+x+"y="+y);return 1;if(x<y)int temp=x;x=y;y=temp;StdOut.println("x="+x+"y="+y);if(x%y=0)return y;elsex=x%y;StdOut.println("x="+x);return CommomDivisor( x,y);1.1.25 使用數(shù)學歸納法證明歐幾里德算法能夠計算任意一對非負整數(shù)p 和q 的最大公約數(shù)。提高題

27、1.1.26 將三個數(shù)字排序。假設a、b、c 和t 都是同一種原始數(shù)字類型的變量。證明以下代碼能夠?qū)、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; 1.1.27 二項分布。估計用以下代碼計算binomial(100, 50) 將會產(chǎn)生的遞歸調(diào)用次數(shù)：public static double binomial(int N, int k, double p)if (N = 0 && k = 0)

28、return 1.0; and if (N < 0 | k < 0) return 0.0;return (1.0 - p)*binomial(N-1, k, p) + p*binomial(N-1, k-1);將已經(jīng)計算過的值保存在數(shù)組中并給出一個更好的實現(xiàn)。估計遞歸調(diào)用次數(shù)： 100！public static double binomial(int N,int k,double p)cnt+;StdOut.println("N="+N+"k="+k+"p="+p);if (N = 0 && k = 0

29、) StdOut.println("N = 0 && k = 0");return 1.0; if (N < 0 | k < 0) StdOut.println("N < 0 | k <0"); return 0; return (1.0 - p)*binomial(N-1, k, p) + p*binomial(N-1, k-1,p);值保存在數(shù)組中的實現(xiàn)方法：public static void binomialArrays(int N,int K,double p)double a=new doubleN+1

30、K+1;a00=1;for(int j=1;j<N+1;j+)aj0=aj-10*(1-p);for (int i=0;i<N+1;i+)for(int j=1;j<=i&&j<K+1;j+)aij= (1-p)*ai-1j+p*ai-1j-1;思路： N列K行的數(shù)組：P(N,K)=（1-p）f(N-1,k)+p* f(N-1,K-1)f(N-1,K-1)f(N-1,k)f(N,K)1.1.28 刪除重復元素。修改BinarySearch 類中的測試用例來刪去排序之后白名單中的所有重復元素。public static int countC(int a)/

31、排序后，統(tǒng)計重復數(shù)量 int cnt=0; for(int i=0;i<a.length-1;i+) if(ai= ai+1) s+; return cnt; public static int remove(int a,int cnt ) int s=0; int b=new inta.length-cnt; b0=a0; for(int i=0;i<a.length-1;i+) if(ai= ai+1) s+; else bi-s+1=ai+1; return b; 1.1.29 等值鍵。為BinarySearch 類添加一個靜態(tài)方法rank()，它接受一個鍵和一個整型有序數(shù)組

32、（可能存在重復鍵）作為參數(shù)并返回數(shù)組中小于該鍵的元素數(shù)量，以及一個類似的方法count() 來返回數(shù)組中等于該鍵的元素的數(shù)量。注意：如果i 和j 分別是rank(key,a) 和count(key,a)的返回值，那么ai.i+j-1 就是數(shù)組中所有和key 相等的元素。import java.util.Arrays;public class BinarySearch2 public BinarySearch2() / TODO Auto-generated constructor stub/*返回小于key的元素數(shù)量 * */public static int rank(int key, in

33、t a) int lo = 0; int hi = a.length - 1; while (lo <= hi) / Key is in alo.hi or not present. int mid = lo + (hi - lo) / 2; if (key < amid) hi = mid - 1; else if (key > amid) lo = mid + 1; else while(amid=amid-1&&mid>0) mid-; return mid; return-1; public static int count (int key,

34、int a) int cnt=0;int i=rank(key,a);while(ai=ai+1&&i<a.length)cnt+;i+;return cnt;public static void main(String args) / TODO Auto-generated method stub In in = new In("tinyW"); int whitelist = in.readAllInts(); Arrays.sort(whitelist); int key=StdIn.readInt(); int cnt=rank(key,whi

35、telist); StdOut.println("smaller than "+key+" element have "+cnt ); int cntequal=count(key,whitelist); StdOut.println("equal "+key+" element have "+cntequal );1.1.30 數(shù)組練習。編寫一段程序，創(chuàng)建一個N×N 的布爾數(shù)組a。其中當i 和j 互質(zhì)時（沒有相同因子），aij 為true，否則為false。public static boolean T

36、estArrays( boolean a)/int N=a.length;int M=a0.length;StdOut.println(M+"=M"+"N="+N);for(int i=0;i<N;i+)for(int j=0;j<M;j+)if(gcd(i,j)=1)aij=true;elseaij=false;return a;public static int gcd(int m,int n)if(m=0|n=0)return 1;if(m%n=0)return n;elsereturn gcd(n,m%n);1.1.31 隨機連接。編

37、寫一段程序，從命令行接受一個整數(shù)N 和double 值p（0 到1 之間）作為參數(shù)，在一個圓上畫出大小為0.05 且間距相等的N 個點，然后將每對點按照概率p 用灰線連接。public class RandomAccess public RandomAccess() / TODO Auto-generated constructor stubpublic static void drawcricle(double x,double y,double r,int N,double p,double a)StdDraw.setXscale(0, x*2);StdDraw.setYscale(0,

38、y*2);StdDraw.setPenRadius(0.005);StdDraw.setPenColor(StdDraw.RED);StdDraw.circle(50, 50, 50);for(int i=0;i<N;i+) StdDraw.setPenRadius(0.05); StdDraw.setPenColor(StdDraw.BLACK); double m=50-50*Math.cos(2*Math.PI*i/N); double n=50+50*Math.sin(2*Math.PI*i/N); StdDraw.point(m, n);ai0=m;ai1=n; StdDraw

39、.setPenColor(StdDraw.RED);/StdDraw.text(m,n,i+" m="+m+" n="+n);public static void Randomline(double x,double y,double a)StdDraw.setXscale(0, x*2);StdDraw.setYscale(0, y*2); StdDraw.setPenRadius(0.01); StdDraw.setPenColor(StdDraw.LIGHT_GRAY); int N=a.length;for(int i=0;i<N;i+)f

40、or(int j=0;j<N;j+)if(StdRandom.bernoulli(0.5) StdDraw.line(ai0, ai1, aj0, aj1);public static void main(String args) double x=50;double y=50;double r=50;int N=10;double p=0.2;double a=new doubleN2;/畫圓/描點drawcricle(x,y,r,N,p,a);/畫線Randomline(x,y,a);1.1.32 直方圖。假設標準輸入流中含有一系列double 值。編寫一段程序，從命令行接受一個整數(shù)

41、N 和兩個double 值l 和r。將(l，r) 分為N 段并使用StdDraw 畫出輸入流中的值落入每段的數(shù)量的直方圖。public class histogram /*將(l，r) 分為N段 * */ public static double segmentation(int N,double l,double r,double a) if(N=0) returna; double s=(r-l)/N; a0=l; for(int i=1;i<a.length;i+) ai=ai-1+s; return a; public static void makehistogram(doub

42、le a,double b,double l,double r) int c=new inta.length-1; for(int i=0;i<b.length;i+) for(int j=0;j<a.length-1;j+) if(bi>=aj&&bi<aj+1) cj+; continue; int N=c.length; StdDraw.setXscale(0,(r-l)*1.2 );StdDraw.setYscale(0, b.length/N*1.5); for(int i=0;i<N;i+) double x = l+(r-l)/N*i

43、; double y = ci/2.0; double rw = (r-l)/(2*N); double rh = ci/2.0; StdDraw.filledRectangle(x, y, rw, rh); StdOut.print(ci+" "); public static void main(String args) / TODO Auto-generated method stub int N=10;/段數(shù) double l=2; double r=20;double a=new doubleN+1;/記錄分段的節(jié)點double b=new doubleN*N*N

44、;/隨機產(chǎn)生一個數(shù)組，作為輸入數(shù)字。a=segmentation(N,l,r,a);for(int i=0;i<b.length;i+)bi=StdRandom.uniform(l, r);makehistogram(a,b,l,r); 1.1.33 矩陣庫。編寫一個Matrix 庫并實現(xiàn)以下API：public class Matrixstatic double dot(double x, double y) 向量點乘static double mult(double a, double b) 矩陣和矩陣之積static double transpose(double a) 轉(zhuǎn)置矩陣s

45、tatic double mult(double a, double x) 矩陣和向量之積static double mult(double y, double a) 向量和矩陣之積編寫一個測試用例，從標準輸入讀取矩陣并測試所有方法。public class Matrix public Matrix() / TODO Auto-generated constructor stubpublic static double dot(double x, double y)/向量點乘double a=0;if(x.length!=y.length) return a; /此處拋出異常for(int i

46、=0;i<x.length;i+)a+=xi*yi;return a;public static double transpose(double a)/ 轉(zhuǎn)置矩陣 for (int i=0;i<a.length;i+) for(int j=i;j<a0.length;j+) double temp=aij; aij=aji; aji=temp; return a;/* * 矩陣的乘積定義：一個n行m列的矩陣乘以一個m行p列的矩陣，得到的結(jié)果是一個n行p列的矩陣， * 其中的第i行第j列位置上的數(shù)等于前一個矩陣第i行上的m個數(shù)與后一個矩陣第j列上的m個數(shù)對應 * 相乘后所有m個乘積的和。 * */static double mult(double a, double b)/ 矩陣和矩陣之積int M=a0.length;int N=a.length;int P=b0.length;double c=new doubleMP;if(M!=b.length)/此處拋出異常for(int i=0;i<N;i+)for(int j=0;j<P;j+)for(int m=0;m<M;m+)cij+=aim*bmj;return c;public static double mult(double a, do