算法 第四 习题 答案

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.33 编写一个程序，从命令行得到三个整数参数。如果它们都相等则打印equal，否则打印not equa

2、l。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 static int

3、 equals(int a ,int b , int c)if(a=b&&b=c)return 1;elsereturn 0;下列语句各有什么问题（如果有的话）？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; 编写一段程序，如果double 类型的变量x 和y 都严格位于0 和1 之间则打印true，否则打印fal

4、se。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 下面这段程序会打印出什么？int f = 0;int g =

5、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 < 1000; i+)f

6、or (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 下列语句会打印出什么结果？给出解释。a. System.out.println('b');b. System.out.println('b' + 'c');c

7、. System.out.println(char) ('a' + 4);答案：a. b b. 197 c. e1.1.9 编写一段代码，将一个正整数N 用二进制表示并转换为一个String 类型的值s。解答：Java 有一个内置方法Integer.toBinaryString(N) 专门完成这个任务，但该题的目的就是给出这个方法的其他实现方法。下面就是一个特别简洁的答案：String s = ""for (int n = N; n > 0; n /= 2)s = (n % 2) + s;1.1.10 下面这段代码有什么问题？int a;for (in

8、t i = 0; i < 10; i+)ai = i * i;解答：它没有用new 为a 分配内存。这段代码会产生一个variable a might not havebeen initialized 的编译错误。 编写一段代码，打印出一个二维布尔数组的内容。其中，使用* 表示真，空格表示假。打印出行号和列号。public class Test public Test() / TODO Auto-generated constructor stubpublic static void main(String args) / TODO Auto-generated method stubb

9、oolean a = new boolean1010;a=RandomInitial(a);/随机初始化TestPrint(a);/打印数组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.print("*"+&

10、quot; ");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 以下代码段会打印出什么结果？int a = new int10;for (in

11、t 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 列的二维数组的转置（交换行和列）。public class Migrate public Migrate() / TODO Auto-generated construct

12、or 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); /初始化二维数组 b=MigrateArrays(a,b); /转置二维数组 MigratePrint(b);/输出转置二维数组 public static void MigratePrint(int a)StdOut.println("输出转置二维数组:"); for (i

13、nt 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)StdOut.println("初始化

14、二维数组:"); 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 编写一个静态方法lg()，接受一个整型参数N，返回不大于log2N 的最大整数。不要使用Math 库。public static int lga(int N,int M)int a=0;while(N>=M)N=N/M;a+;return a; 编写一个静

15、态方法histogram()，接受一个整型数组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;i<M;i+)for(int j=0;j<a.length;j+)if(i=aj)n+;bi=n;n=0;for(int i=0;i<M;i+)m=m+bi;return b;1.1

16、.16 给出exR1(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;答：这段代码中的基础情况永远不会被访问。调用exR2(3) 会产生调用exR2(

17、0)、exR2(-3) 和exR2(-6)，循环往复直到发生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 请看以下递归函数：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

18、(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 static void main

19、(String args)for (int N = 0; N < 100; N+)StdOut.println(N + " " + F(N);计算机用这段程序在一个小时之内能够得到F(N) 结果的最大N 值是多少？开发F(N) 的一个更好的实现，用数组保存已经计算过的值。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 static void main(String args)int

20、 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 编写一个递归的静态方法计算ln(N!) 的值。public static double factorialln(long N)if(N>1)return Math.ln(N)+factorialln(N-1);elsereturn 0; 编写一段程序，从标准输入按行读取数据，其中每行都包含一个

21、名字和两个整数。然后用printf() 打印一张表格，每行的若干列数据包括名字、两个整数和第一个整数除以第二个整数的结果，精确到小数点后三位。可以用这种程序将棒球球手的击球命中率或者学生的考试分数制成表格。public class ScoreTable public static void main(String args) String s = "Let's go for lunch!"In in = new In("Se"); String whitelist = in.readAllStrings();/将文件中的字符串读取到数组中 for

22、(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); StdOut.println(" "); 使用1.1.6.4 节中的r

23、ank() 递归方法重新实现BinarySearch 并跟踪该方法的调用。每当该方法被调用时，打印出它的参数lo 和hi 并按照递归的深度缩进。提示：为递归方法添加一个参数来保存递归的深度。 为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

24、 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) / 2; if (key < amid) hi = mid - 1; else if (key > ami

25、d) lo = mid + 1; else return -1; return 0; else return -1; 给出使用欧几里德算法计算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=&quo

26、t;+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 使用数学归纳法证明欧几里德算法能够计算任意一对非负整数p 和q 的最大公约数。提高题 将三个数字排序。假设a、b、c 和t 都是同一种原始数字类型的变量。证明以下代码能够将a、b、c 按照升序排列：if (a >

27、; 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 && k = 0) return 1.0; and if (N < 0 | k < 0) return 0.0;return (1.0 - p)*bin

28、omial(N-1, k, p) + p*binomial(N-1, k-1);将已经计算过的值保存在数组中并给出一个更好的实现。估计递归调用次数： 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 && k = 0");return 1.0; if (N &

29、lt; 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);值保存在数组中的实现方法：public static void binomialArrays(int N,int K,double p)double a=new doubleN+1K+1;a00=1;for(int j=1;j<N+1;j+)aj0=aj-10*(1-p);for (int i=0;i<N+1;

30、i+)for(int j=1;j<=i&&j<K+1;j+)aij= (1-p)*ai-1j+p*ai-1j-1;思路： N列K行的数组：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)/排序后，统计重复数量 int cnt=0; for(int i=0;i<a.length-1;i+) if(ai= ai+1) s+; r

31、eturn 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; 等值键。为BinarySearch 类添加一个静态方法rank()，它接受一个键和一个整型有序数组（可能存在重复键）作为参数并返回数组中小于该键的元素数量，以及一个类似的方法count() 来返回数组中等于该键的元素的数量。注意：如果i 和j 分别是ran

32、k(key,a) 和count(key,a)的返回值，那么ai.i+j-1 就是数组中所有和key 相等的元素。import java.util.Arrays;public class BinarySearch2 public BinarySearch2() / TODO Auto-generated constructor stub/*返回小于key的元素数量 * */public static int rank(int key, int a) int lo = 0; int hi = a.length - 1; while (lo <= hi) / Key is in alo.hi

33、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, int a) int cnt=0;int i=rank(key,a);while(ai=ai+1&&i<a.length)cnt+;i+

34、;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,whitelist); StdOut.println("smaller than "+key+" element have "

35、;+cnt ); int cntequal=count(key,whitelist); StdOut.println("equal "+key+" element have "+cntequal ); 数组练习。编写一段程序，创建一个N×N 的布尔数组a。其中当i 和j 互质时（没有相同因子），aij 为true，否则为false。public static boolean TestArrays( boolean a)/int N=a.length;int M=a0.length;StdOut.println(M+"=M"+

36、"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); 随机连接。编写一段程序，从命令行接受一个整数N 和double 值p（0 到1 之间）作为参数，在一个圆上画出大小为0.05 且间距相等的N 个点，然后将每对点按照概率p 用灰线连接。publi

37、c 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, y*2);StdDraw.setPenRadius(0.005);StdDraw.setPenColor(StdDraw.RED);StdDraw.circle(50, 50, 50

38、);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.setPenColor(StdDraw.RED);/StdDraw.text(m,n,i+" m="+m+" n="+n);public s

39、tatic 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+)for(int j=0;j<N;j+)if(StdRandom.bernoulli(0.5) StdDraw.line(ai0, ai1, aj0, aj1);public st

40、atic 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); 直方图。假设标准输入流中含有一系列double 值。编写一段程序，从命令行接受一个整数N 和两个double 值l 和r。将(l，r) 分为N 段并使用StdDraw 画出输入流中的值落入每段的数量的直方图。public class histogram /*将(l，r) 分为N段

41、 * */ 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(double a,double b,double l,double r) int c=new inta.length-1; for(int i=0;i<b.length;i+) for(int j

42、=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; double y = ci/2.0; double rw = (r-l)/(2*N); double rh = ci/2.0; StdDraw.filledRectangle(x, y, r

43、w, rh); StdOut.print(ci+" "); public static void main(String args) / TODO Auto-generated method stub int N=10;/段数 double l=2; double r=20;double a=new doubleN+1;/记录分段的节点double b=new doubleN*N*N;/随机产生一个数组，作为输入数字。a=segmentation(N,l,r,a);for(int i=0;i<b.length;i+)bi=StdRandom.uniform(l, r)

44、;makehistogram(a,b,l,r); 1.1.33 矩阵库。编写一个Matrix 库并实现以下API：public class Matrixstatic double dot(double x, double y) 向量点乘static double mult(double a, double b) 矩阵和矩阵之积static double transpose(double a) 转置矩阵static double mult(double a, double x) 矩阵和向量之积static double mult(double y, double a) 向量和矩阵之积编写一个测试

45、用例，从标准输入读取矩阵并测试所有方法。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=0;i<x.length;i+)a+=xi*yi;return a;public static double transpose(double a)/ 转置矩阵 for (int i=0

46、;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列的矩阵，得到的结果是一个n行p列的矩阵， * 其中的第i行第j列位置上的数等于前一个矩阵第i行上的m个数与后一个矩阵第j列上的m个数对应 * 相乘后所有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, double x)/矩阵和向量之积int N=a.length;double c=new doubleN;int M=a0.length;if(M!=x.leng