}
{ N=N/M; a++; }
return a;
1.1.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
1.1.16 给出exR1(6) 的返回值： public static String exR1(int n) {
if (n <= 0) return \
return exR1(n-3) + n + exR1(n-2) + n; }
答案：311361142246
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(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(a+a, b/2) + a; }
mystery(2, 25) 和mystery(3, 11) 的返回值是多少？给定正整数a 和b，mystery(a,b) 计算的结果是什么？将代码中的+ 替换为* 并将return 0 改为return 1，然后回答相同 的问题。 答案：50，33. 2{
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) 结果的最大N 值是多少？开发F(N) 的一 个更好的实现，用数组保存已经计算过的值。
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); }
25 11
3
1.1.19 在计算机上运行以下程序：public class Fibonacci
public static void main(String[] args) {
int[] a=new int [100]; a=A(a); }
public static long[] A(int[] a) { a[0]=0; a[1]=1; for (int N = 2; N < 100; N++) {a[N]=a[N-1]+a[N-2];
StdOut.println(N + \ +a[N]); } }
1.1.20 编写一个递归的静态方法计算ln(N!) 的值。
public static double factorialln(long N) { if(N>1) return Math.ln(N)+factorialln(N-1); else return 0; }
1.1.21 编写一段程序，从标准输入按行读取数据，其中每行都包含一个名字和两个整数。然后用printf() 打印一张表格，每行的若干列数据包括名字、两个整数和第一个整数除以第二个整数的结果，精确到小数点后三位。可以用这种程序将棒球球手的击球命中率或者学生的考试分数制成表格。
public class ScoreTable { public static void main(String[] args) { String s = \; In in = new In(\);
String[] whitelist = in.readAllStrings();//将文件中的字符串读取到数组中 for(int i=0;i StdOut.print(whitelist[i]+\+whitelist[i+1]+\+whitelist[i+2]+\\); double m=Double.parseDouble(whitelist[i+1]); double n=Double.parseDouble(whitelist[i+2]); StdOut.printf(\,m/n); StdOut.println(\); } } } 1.1.22 使用1.1.6.4 节中的rank() 递归方法重新实现BinarySearch 并跟踪该方法的调用。每当该方法被调用时，打印出它的参数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 a[lo..hi] or not present. int mid = lo + (hi - lo) / 2; if (key < a[mid]) hi = mid - 1; else if (key > a[mid]) lo = mid + 1; else return mid; } return -1; } if(c=='-') { while (lo <= hi) { // Key is in a[lo..hi] or not present. int mid = lo + (hi - lo) / 2; if (key < a[mid]) hi = mid - 1; else if (key > a[mid]) lo = mid + 1; else return -1; } return 0; } else return -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+\+y); return 1;} if(x 1.1.25 使用数学归纳法证明欧几里德算法能够计算任意一对非负整数p 和q 的最大公约数。 提高题 1.1.26 将三个数字排序。假设a、b、c 和t 都是同一种原始数字类型的变量。证明以下代码能够将a、 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) 将会产生的递归调用次数： 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) + p*binomial(N-1, k-1); } 将已经计算过的值保存在数组中并给出一个更好的实现。 估计递归调用次数： 100！ public static double binomial(int N,int k,double p) { cnt++; StdOut.println(\+N+\+k+\+p); if (N == 0 && k == 0) { StdOut.println(\); return 1.0; } if (N < 0 || k < 0) { StdOut.println(\); 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 double[N+1][K+1]; a[0][0]=1; for(int j=1;j