算法 第四版 习题 答案Word文件下载.docx

1、 if（a=b&b=c） return 1; return 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; b） c = 0; b. if （a b） c = 0;1.1.5 编写一段程序，如果double 类型的变量x 和y 都严格位于0 和1 之间则打印true，否则打印false。double x;double y;x=StdIn.readDouble（）;y=StdIn.readDouble（）;StdOut.

2、print（compare（x）& compare（y）;public static boolean compare（double x）If（x0&x1）returen ture;else return false;1.1.6 下面这段程序会打印出什么？int f = 0;int g = 1;for （int i = 0; i .001）t = （9.0/t + t） / 2.0;StdOut.printf（%.5fn, t）;b. int sum = 0;for （int i = 1; 1000;for （int j = 0; j 0; n /= 2）s = （n % 2） + s;1.1.

3、10 下面这段代码有什么问题？int a; 10;ai = i * i;它没有用new 为a 分配内存。这段代码会产生一个variable a might not havebeen initialized 的编译错误。1.1.11 编写一段代码，打印出一个二维布尔数组的内容。其中，使用* 表示真，空格表示假。打印出行号和列号。public class Test public Test（） / TODO Auto-generated constructor stub public static void main（String args） / TODO Auto-generated method

4、 stub boolean a = new boolean1010; a=RandomInitial（a）;/随机初始化 TestPrint（a）;/打印数组 public static void TestPrint（boolean a） for（int i=0;ia.length;i+）/打印行号 StdOut.print（ +i）; for（int i=0;10;i+） StdOut.print（i）; for（int j=0;j=M） N=N/M; a+;1.1.15 编写一个静态方法histogram（），接受一个整型数组a 和一个整数M 为参数并返回一个大小为M的数组，其中第i个元素

5、的值为整数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;M; if（i=aj） n+; bi=n; n=0; m=m+bi;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 找出

6、以下递归函数的问题：public static String exR2（int n）String s = exR2（n-3） + n + exR2（n-2） + n;return s;答：这段代码中的基础情况永远不会被访问。调用exR2（3） 会产生调用exR2（0）、exR2（-3） 和exR2（-6），循环往复直到发生StackOverflowError。可以修改为：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

7、）;return mystery（a+a, b/2） + a;mystery（2, 25） 和mystery（3, 11） 的返回值是多少？给定正整数a 和b，mystery（a,b）计算的结果是什么？将代码中的+ 替换为* 并将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 F（N-1） + F（N-2）;public sta

8、tic void main（String args）for （int N = 0; N return Math.ln（N）+factorialln（N-1）; else return 0;1.1.21 编写一段程序，从标准输入按行读取数据，其中每行都包含一个名字和两个整数。然后用printf（） 打印一张表格，每行的若干列数据包括名字、两个整数和第一个整数除以第二个整数的结果，精确到小数点后三位。可以用这种程序将棒球球手的击球命中率或者学生的考试分数制成表格。public class ScoreTable String s = Lets go for lunch! In in = new In

9、（Se String whitelist = in.readAllStrings（）;/将文件中的字符串读取到数组中 for（int i=0;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）;1.1.22 使用1.1.6.4 节中的rank（） 递归方法重新实现BinarySea

10、rch 并跟踪该方法的调用。每当该方法被调用时，打印出它的参数lo 和hi 并按照递归的深度缩进。提示：为递归方法添加一个参数来保存递归的深度。1.1.23 为BinarySearch 的测试用例添加一个参数：+ 打印出标准输入中不在白名单上的值；-，则打印出标准输入中在白名单上的值。public static int rank（int key, int a,char c） int lo = 0; int hi = a.length - 1; if（c=+） while （lo = hi） / Key is in alo.hi or not present. int mid = lo + （h

11、i - lo） / 2; if （key amid） lo = mid + 1; else return mid; return -1;- return -1; return 0;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） StdO

12、ut.println（x=+x+y=+y）; if（x b） t = a; a = b; b = t; c） t = a; a = c; c = t;if （b c） t = b; b = c;1.1.27 二项分布。估计用以下代码计算binomial（100, 50） 将会产生的递归调用次数：public static double binomial（int N, int k, double p）if （N = 0 & k = 0） return 1.0; and if （N 0 | k 0） return 0.0;return （1.0 - p）*binomial（N-1, k, p） +

13、 p*binomial（N-1, k-1）;将已经计算过的值保存在数组中并给出一个更好的实现。估计递归调用次数： 100！public static double binomial（int N,int k,double p） cnt+;N=+N+k=+k+p=+p）; if （N = 0 & k = 0） N = 0 & k = 0 return 1.0; if （N 0）N 0 return （1.0 - p）*binomial（N-1, k, p） + p*binomial（N-1, k-1,p）;值保存在数组中的实现方法：public static void binomialArrays（int N,int K,double p） double a=new doubleN+1K+1; a00=1; for（int j=1;N+1; aj0=aj-10*（1-p）; for（