Algorithms(第四版)1.1课后练习答案（个人整理）

摘要：最近着手学习的这本书，开始做习题时发现配套网站上对应的习题答案并不完全，后发现以及有些人的博客上有部分答案，不过一般只做了第一章节的题目，大概是题目太多了的原因，在此自己整理自己所做的一份答案，希望有同行的人一起交流，分享。

最近着手学习Robert Sedgewick的Algorithms这本书，开始做习题时发现配套网站上对应的习题答案并不完全，google后发现github以及有些人的博客上有部分答案，不过一般只做了第一章节的题目，大概是题目太多了的原因，在此自己整理自己所做的一份答案，希望有同行的人一起交流，分享。

1.1.1
a.7
b.200.0000002
c.true

1.1.2
a.1.618
b.10.0
c.true
d.33

1.1.3
需要添加对应官方网站上所提供的标准输入库函数StdIn.java

package Chapter1;

import edu.princeton.cs.algs4.*;

public class prac1_1_3 {
    public static void main(String[] args) {
        int a=StdIn.readInt();
        int b=StdIn.readInt();
        int c=StdIn.readInt();
        if(a==b&&a==c)
            System.out.println("equal");
        else
            System.out.println("not equal");
    }
}

1.1.4
a.多余了then(VB有这种语法)
b.a>b缺少()
c.正确
d.c=0缺少;

1.1.5

package Chapter1;

import edu.princeton.cs.algs4.*;

public class parc1_1_5 {
    public static void main(String[] args) {
        double x=StdIn.readDouble();
        double y=StdIn.readDouble();
        
        if(x>=0&&x<=1&&y>=0&&y<=1)
            System.out.println(true);
        else
            System.out.println(false);
    }
}

1.1.6
一段Fibonacci

0
  1
1
2
3
5
8
13
21
34
55
89
144
233
377
610

1.1.7
a.3.00009 应该是计算算数平方根
b.499500 计算 1+2+3+...+999也就是（1+999）*999/2
c.10000 1000*10，就外循环来看一共十个轮回（2^0,2^1,...,2^9=512<1000,2^10=1024>1000,而内循环每次执行1000次）

1.1.8 (考察 ASCII表格 )
a.b
b.197 (默认是会转换为相加后的数字输出)
c.e

1.1.9

package Chapter1;

import edu.princeton.cs.algs4.*;

public class prac1_1_9 {

    public static void main(String[] args) {
        int N;
        //count the binary form of N
        while((N=StdIn.readInt())>0){
            String s="";
            while(N/2!=0){
                s+=(N%2);
                N/=2;
            }
            s+="1";
            //reverse the string s            
            char[] ch=new char[s.length()];            
            for(int i=0;i
【还是思维形成定势了，基本运算一致，未曾想从右边加，就像链表的头插尾插一样】
附课本源代码
String s="";
for(int n=N;n>0;n/=2)
   s=(n%2)+s;
1.1.10
在新建一个数组时未给该数组用new分配内存，会产生 variable a might not have been initialized的编译错误
1.1.11
package Chapter1;

public class prac1_1_11 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        boolean[][] array={{true,false,false},{false,false,true},{true,false,true}};
        //print the column number
        System.out.print(" ");
        for(int i=0;i
关于这个题不知道我的理解是否正确，因为和网上查到的另一个朋友的答案不一样，他是直接输出每一个位置+元素，而我的理解是仍保持矩阵的形式将对应的boolean值替换为"*"和‘ ’，并输出行号，列号，由于没有标准答案，见仁见智吧
别人的结果以及原链接

我个人的对应的结果

1.1.12

1.1.13
package Chapter1;

public class prac1_1_13 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[][] a={{1,2,3},{7,5,1}};
        //print 2D array
        System.out.println("before transfer");
        printArray(a);
        System.out.println("after transfer");
        //transfer the 2D array
        printArray(transferArray(a));
    }
    
    public static void printArray(int[][] a){
        for(int i=0;i
1.1.14
package Chapter1;

import edu.princeton.cs.algs4.*;

public class prac1_1_14 {

    public static void main(String[] args) {
        int N=StdIn.readInt();
        System.out.println(lg(N));
    }
    
    public static int lg(int N){
        int lg=0;
        for(int i=0;iN){
                lg=i;
                break;
            }
        }
        return lg;
    }
    
    public static int myPow(int m,int n){
        int temp=m;
        while(--n>0){
            m*=temp;
        }
        return m;
    }

}

1.1.15
package Chapter1;

public class prac1_1_15 {

    public static void main(String[] args) {
        int[] testArray={1,1,2,3,1,7,5,3,2,2,2};
        System.out.println("histogram result");
        printArray(histogram(testArray, 8));
    }
    
    public static int[] histogram(int[] a,int M){
        int[] hArray=new int[M];
        for(int i=0;i
1.1.16
311361142246
1.1.17
该代码中的基础情况永远不会被调用，因为调用exR2(3)会产生调用exR2(0),exR2(-3)和exR2(-6),循环往复直至产生StackOverflowError.
1.1.18
乘法的递归实现
mystery(2,25)=50
mystery(3,11)=33
mystery(a,b)=a*b
修改后结果：
乘方的递归实现
mystery(a,b)=a^b
1.1.19
package Chapter1;

public class prac1_1_19 {

    public prac1_1_19() {
        int[] F = new int[100];
        F[0] = 0;
        F[1] = 1;
        for(int i=2;i<100;++i)
            F[i]=F[i-1]+F[i-2];
        System.out.println(F[30]);
    }

    public static void main(String[] args) {
        prac1_1_19 test=new prac1_1_19();

    }

}
1.1.20
package Chapter1;

import java.lang.Math;
import edu.princeton.cs.algs4.*;

public class prac1_1_20 {

    public static void main(String[] args) {
        int N=StdIn.readInt();
        System.out.println(ln(N));
    }

    public static double ln(int N){
        if(N==1)
            return 0;
        return ln(N-1)+Math.log(N);
    }
}

由于此题考察递归，所以对于ln的计算是调用Math里的现成库
1.1.21
package Chapter1;

import edu.princeton.cs.algs4.*;

public class prac1_1_21 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        while(StdIn.hasNextLine()){
            String name=StdIn.readString();
            int m=StdIn.readInt();
            int n=StdIn.readInt();
            StdOut.printf("%8s | %8d | %8d | %8.3f", name,m,n,(m*1.0)/n);
        }    
    }
}

1.1.22
package Chapter1;

public class prac1_1_22 {
    
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] array={1,3,5,7,9};
        int location=rank(3,array,0);
        if(location<0)
            System.out.println("key not found");
        else
            System.out.println("key location="+(location+1));

    }

    public static int rank(int key, int[] a,int depth) {
        return rank(key, a, 0, a.length - 1,depth);
    }

    private static int rank(int key, int[] a, int lo, int hi,int dep) {
        // TODO Auto-generated method stub
        for(int i=0;i hi)
            return -1;
        int mid = (lo + hi) / 2;
        if (key < a[mid])
            return rank(key, a, lo, mid - 1,dep);
        else if (key > a[mid])
            return rank(key, a, mid + 1, hi,dep);
        else
            return mid;
    }
}

1.1.23
折腾了大半天，最后找到别人的一份代码应该是符合条件的
/**
 * 二分查找 ： 非递归描述
 * @param key   关键字
 * @param arr   数组
 * @return  若找到则返回true，否则返回false
 */
public static boolean BinaryLookup(int key, int[] arr) {
    int low = 0;
    int high = arr.length - 1;
    while(low <= high) {
        int mid = low + ((high - low) >> 1);
        if(key < arr[mid])
            high = mid - 1;
        else if(key > arr[mid])
            low = mid + 1;
        else
            return true;
    }
    return false;
}

public static void main(String[] args) {
    // “ + ” --> 打印出标准输入中不在白名单上的值，
    // “ - ” --> 打印出标准输入中在白名单上的值
    char symbol = "-";
    int[] whitelist = new In(args[0]).readAllInts();
    Arrays.sort(whitelist);
    while(!StdIn.isEmpty()) {
        int key = StdIn.readInt();
        boolean found = BinaryLookup(key, whitelist);
        if("+" == symbol && !found)
            StdOut.println(key);
        if("-" == symbol && found)
            StdOut.println(key);
    }
}

不过需要注意的是，在windows的环境下的控制台直接调用书上的命令是行不通的，首先是调用了书上一直在提的 algs4.jar,然后是需要从命令行读取文件进行比对，而windows控制台是没法运行书上所述的
java xxx largeW.txt < largeT.txt
即使将需要用到的作者写好的库放在java文件的同一目录下也会产生如下异常

可能是命令行不支持“<”命令吧，因为最近联系到这段代码的作者，发现他是在Linux系统下编译执行的，据说是没问题。
经过一番查找，最终我发现有一种方法是用本书作者开发的一套控制台程序,然后按照该连接的操作，使用如下指令进行编译和运行才可以成功
javac-algs4 xxx.java  //编译指令

java-algs4 xxx largeW.txt < largeT.txt    //执行指令
当然注意其中的largeW.txt和largeT.txt也来自相应网站的data文件里，需要放到和java文件相同目录
【更新】后来我在stackoverflow上提问，有人解答了，在windows上的命令应该是这样的
Get-Content tinyT.txt | java prac1_1_23 tinyW.txt
不过比较奇怪的是，用原始的largeW.txt和largeT.txt的话PowerShell就直接崩溃了，应该是数据量过大的缘故吧，但是用所提供的CLI倒是可以跑
【更新】此外，cmd是可以直接执行的，另外一种方法是把命令写为".bat"文件然后执行该文件，效果类似，倒是破除了PowerShell一定优于cmd的封建迷信了，stackoverflow上的朋友还是相当热心严谨那~
【更新】若坚持使用powershell,stackoverflow上有人提出可以用如下指令，亲测有效
cmd /c --% java prac1_1_23 largeW.txt < largeT.txt

【若有更好的方法还希望能不吝赐教】
1.1.24
package Chapter1;

import edu.princeton.cs.algs4.*;

public class prac1_1_24 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        while(StdIn.hasNextLine()){
            int x=StdIn.readInt();
            int y=StdIn.readInt();
            StdOut.println("the greatest common divisor of "+x+" and "+y+" is: "+gcd(x,y));
        }
    }
    
    public static int gcd(int a,int b){
        StdOut.println(a+" "+b);
        int m=max(a,b);
        int n=min(a,b);
        if(m%n==0)
            return n;
        else
            return gcd((m%n),n);
    }
    
    public static int max(int a,int b){
        if(a>=b)
            return a;
        else
            return b;
    }
    
    public static int min(int a,int b){
        if(a>=b)
            return b;
        else
            return a;
    }

}

输出结果如下

考虑到让用户输入不一定按先大后小的顺序输入所以加入了一点预处理
1.1.25
网上找的证明1,证明2

提高题
1.1.26
本质上是在说java里的变量的值的交换的算法，需要第三个数来进行临时存储从而完成交换，其实也有另一种方法，通过两次异或运算‘^’完成交换操作
a=a^b;
b=b^a;   //此时b变为a
a=a^b;    //此时a变为b
1.1.27
第一问是向递归函数里添加了一个计数器参数，使用了第二节的现有的计数器类，每次调用递归时即递增一次，代码如下：
package Chapter1;

import Chapter1.Counter;
import edu.princeton.cs.algs4.StdOut;

public class prac1_1_27 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int n=Integer.parseInt(args[0]),
            k=Integer.parseInt(args[1]);
        double p=Double.parseDouble(args[2]);
        
        Counter c=new Counter("calls");
        double b=binomial(n,k,p,c);
        
        StdOut.println(b);
        StdOut.println(c);
        
    }
    
    public static double binomial(int N, int k, double p,Counter c){
        double[][] a=new double[N+1][k+1];
        for(int i=0;i<=N;++i){
            for(int j=0;j<=k;++j){
                a[i][j]=-1;
            }
        }
        return binomial(a,N,k,p,c);
    }

    private static double binomial(double[][] a, int N, int k, double p, Counter c) {
        if(N==0&&k==0)
            return 1.0;
        if(N<0||k<0)
            return 0.0;
        if(a[N][k]==-1){
            c.increment();
            a[N][k]=(1.0-p)*binomial(a,N-1,k,p,c)+p*binomial(a,N-1,k-1,p,c);
        }
        return a[N][k];
    }

}
第二道题是用空间换时间的应用，用二维数组来存取所计算的概率值，这样以后计算某一概率的值时可直接从数组中读，而不必重复计算前面已经计算过的值；
package Chapter1;

import Chapter1.Counter;
import edu.princeton.cs.algs4.StdOut;

public class prac1_1_27 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int n=Integer.parseInt(args[0]),
            k=Integer.parseInt(args[1]);
        double p=Double.parseDouble(args[2]);
        
        Counter c=new Counter("calls");
        double b=binomial(n,k,p,c);
        
        StdOut.println(b);
        StdOut.println(c);
        
    }
    
    public static double binomial(int N, int k, double p,Counter c){
        double[][] a=new double[N+1][k+1];
        for(int i=0;i<=N;++i){
            for(int j=0;j<=k;++j){
                a[i][j]=-1;
            }
        }
        return binomial(a,N,k,p,c);
    }

    private static double binomial(double[][] a, int N, int k, double p, Counter c) {
        if(N==0&&k==0)
            return 1.0;
        if(N<0||k<0)
            return 0.0;
        if(a[N][k]==-1){
            c.increment();
            a[N][k]=(1.0-p)*binomial(a,N-1,k,p,c)+p*binomial(a,N-1,k-1,p,c);
        }
        return a[N][k];
    }

}
参考1参考2
1.1.28
这道题我的想法是遍历已排序后的数组逐一判断元素是否和前一元素相同，若不相同则用一个list来收集，最后利用list的内置方法直接将list转换为数组即可
public static Integer[] distinctArray(int[] whitelist) {
        List list=new ArrayList<>();
        list.add(whitelist[0]);
        for(int i=1;i
对应的主函数如下
public static void main(String[] args) {
        // TODO Auto-generated method stub
//        int[] whitelist=In.readInts(args[0]);
        int[] whitelist={1,3,3,3,5,6,6,7,};
        Arrays.sort(whitelist);
        for(int i=0;i
1.1.29
这道题我一开始想简单了就直接遍历了，殊不知既然是写在二分查找这一类中的方法自然应该利用二分查找的方式去提高效率，正确的做法是对之前寻找到middle的部分进行修改
package Chapter1;

public class prac1_1_29 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a={1,2,3,3,3,4,5,5,6,8};
        int i=rank(3,a);
        int j=count(3,a);
        System.out.println(i+" "+j);
//        for(int k=i;k<=i+j-1;++k){
//            System.out.print(a[k]+" ");
//        }
    }
    
    public static int rank(int key,int[] array){
        int low=0; 
        int high=array.length-1;
        while(low<=high){
            int    middle=(low+high)>>1;
            if(keyarray[middle])
                low=middle+1;
            else if(key==array[middle]){
                while(middle>0&&array[middle]==key)
                    middle--;
                return middle+1;
            }                
        }
        return -1;
    }
    
    public static int count(int key,int[] array){
        int count=0;
        int lower=rank(key,array);
        for(int i=lower;i
1.1.30
判断是否互质，个人是事先判断了下两个数的大小以便进行遍历
package Chapter1;

public class prac1_1_30 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        boolean[][] a=new boolean[3][19];
        for(int i=0;ij){
            i=i^j;
            j=j^i;
            i=i^j;
        }
        for(int k=2;k<=i;k++)
            if(j%k==0&&i%k==0)
                return false;
        return true;
    }
}
测试结果


实验题