《算法 第四版 习题 答案》由会员分享，可在线阅读，更多相关《算法 第四版 习题 答案（25页珍藏版）》请在金锄头文库上搜索。
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 编写一个程序，从命令行得到三个整数参数。如果它们都相等则打印equal，否则打印not equal。public class TestUqual publ
2、ic 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 static int equals(int a ,int b , int c)if(a=b&b=c)return 1;elsereturn 0;1.1.4下
3、列语句各有什么问题（如果有的话）？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 之间则打印true，否则打印false。public class TestUqual public static void main(String args)double x;double y;x=StdIn.readDoub
4、le();y=StdIn.readDouble();StdOut.print(compare(x)public static boolean compare(double x)If(x0&x .001)t = (9.0/t + t) / 2.0;StdOut.printf(%.5fn, t);b. int sum = 0;for (int i = 1; i 0; n /= 2)s = (n % 2) + s;1.1.10 下面这段代码有什么问题？int a;for (int i = 0; i =M)N=N/M;a+;return a;1.1.15 编写一个静态方法histogram()，接受一
5、个整型数组a 和一个整数M 为参数并返回一个大小为M的数组，其中第i个元素的值为整数i在参数数组中出现的次数。如果a中的值均在0到M-1之间，返回数组中所有元素之和应该和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;i1)return Math.ln(N)+factorialln(N-1);elsereturn 0;1.1.21 编写一段程序，从标准输入按行读取数据，其中每行都包含一个名字和两个整数。然后用printf() 打印一张表格，每行的若干
6、列数据包括名字、两个整数和第一个整数除以第二个整数的结果，精确到小数点后三位。可以用这种程序将棒球球手的击球命中率或者学生的考试分数制成表格。public class ScoreTable public static void main(String args) String s = Lets go for lunch!;In in = new In(Se);String whitelist = in.readAllStrings();/将文件中的字符串读取到数组中for(int i=0;i amid) lo = mid + 1;else return mid;return -1;if(c=-
7、)while (lo amid) lo = mid + 1;else return -1;return 0;elsereturn -1;1.1.24 给出使用欧几里德算法计算105 和24 的最大公约数的过程中得到的一系列 p 和 q 的值。扩展该算法中的代码得到一个程序Euclid，从命令行接受两个参数，计算它们的最大公约数并打印出每次调用递归方法时的两个参数。使用你的程序计算1 111 111 和1 234 567 的最大公约数。public static int CommomDivisor(int x,int y)if(x=1|y=1)StdOut.println(x=+x+y=+y);
8、return 1;if(x 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) 将会产生的递归调用次数：public static double binomial(int N, int k, double p)if (N = 0 return (1.0 - p)*binomial(N-1, k, p) + p*binomial(N-1, k-1);将已经计算过的值保存在数组中并给出一个更好的实现。估计递
9、归调用次数： 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) StdOut.println(N = 0 return 1.0; if (N amid) lo = mid + 1;else while(amid=amid-1&mid0)mid-; return mid; return-1;public static int count (int key, int a) int cnt=0;int i=rank(key,a);w
10、hile(ai=ai+1&i=aj&bi0.0001) Ismatch=true; continue;else cnt+;if(cnt=11)Ismatch=false;StdOut.println(n=+n + cnt=+cnt);Print(dist2,SIDES); public static void Print(double a,int SIDES)for (int k = 2; k 0)for(int i=0;iM;i+)ai=i;StdOut.print(ai+ );shuffle(a);for(int i=0;iM;i+)cN-si=ai;s-;StdOut.println(
11、);StdOut.println(c);for(int j=0;jN;j+)for(int i=0;iM;i+)StdOut.print(cji+ );StdOut.println( );StdOut.println(daluan bmm);for(int k=0;kM;k+)for(int i=0;iM;i+)int num=0;for(int j=0;jN;j+)if(cji=k)num+;bki=num;/StdOut.print(i= +i+ );StdOut.print(bki+ );StdOut.println( k= +k);public static void shuffle(
12、int a) int N = a.length;for (int i = 0; i N; i+) int r = i+StdRandom.uniform(N-i); / between i and N-1int temp = ai;ai = ar;ar = temp;1.1.37 糟糕的打乱。假设在我们的乱序代码中你选择的是一个0 到N-1 而非i 到N-1 之间的随机整数。证明得到的结果并非均匀地分布在 N! 种可能性之间。用上一题中的测试检验这个版本。public static void shuffleTerrible(int a) int N = a.length;for (int i
13、= 0; i N; i+) int r = StdRandom.uniform(N); / between i and N-1int temp = ai;ai = ar;ar = temp;1.1.38 二分查找与暴力查找。根据1.1.10.4 节给出的暴力查找法编写一个程序BruteForceSearch，在你的计算机上比较它和BinarySearch 处理largeW.txt 和largeT.txt 所需的时间。import java.util.Arrays;public class BruteForceSearch public BruteForceSearch() / TODO Aut
14、o-generated constructor stubpublic static void main(String args) In in = new In(largeW);int whitelist = in.readAllInts();In in2 = new In(largeH);int key = in2.readAllInts();/ sort the arrayArrays.sort(whitelist);/ read integer key from standard input; print if not in whitelistfor(int i=0;ikey.length
15、;i+) if (rank(keyi, whitelist) = -1)StdOut.println(keyi);StdOut.println(end);public static int rank(int key, int a)for (int i = 0; i a.length; i+)if (ai = key) return i;return -1;1.1.39 随机匹配。编写一个使用BinarySearch 的程序，它从命令行接受一个整型参数T，并会分别针对 N=103、10 4、10 5 和10 6 将以下实验运行 T 遍：生成两个大小为 N 的随机6 位正整数数组并找出同时存在于两个数组中的整数的数量。打印一个表格，对于每个 N，给出 T 次实验中该数量的平均值。import java.util.Arrays;pub
