Algorithms 4th - 1.1 Basic Programming Model

　　欢迎交流

　　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

 public class MainApp {

     public static void main(String[] args) {

         int a = Integer.parseInt(args[0]);

         int b = Integer.parseInt(args[1]);

         int c = Integer.parseInt(args[2]);

         if(a == b && b == c) {

             System.out.println("equal");

         } else {

             System.out.println("not equal");

         }

     }

 }

　　 1.1.4

　　a. 去掉"then"

　　b. a > b 外围加括号

　　c. 正确

　　d. else 之前加冒号

　　1.1.5

public class MainApp {

    public static void main(String[] args) {

        Double a = Double.parseDouble(args[0]);

        Double b = Double.parseDouble(args[1]);

        if(a >= 0 && a <= 1 && b >=0 && b <= 1) {

            System.out.println("true");

        } else {

            System.out.println("false");

        }

    }

}

　　1.1.6

　　斐波那契数列

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

1.1.7

　　a. 3.00009

　　b. 499500

　　c. 10000

　　1.1.8

　　a. b

　　b. bc

　　c. e

　　1.1.9

 int N = ;

 String s = "";

 for(int i = N; i > ; i /= ) {

     s = i %  + s;

}

　　1.1.10

　　数组没有初始化

　　1.1.11

public class TestApp1 {

    public static void main(String[] args) {

        int N = 10;

        boolean ma[][] = new boolean[N][N];

        for(int i = 0; i < N; i++) {

            for(int j = 0; j < N; j++) {

                double r = Math.random();

                if(r < 0.5)

                    ma[i][j] = true;

                else

                    ma[i][j] = false;

            }

        }

        for(int i = 0; i < N; i++) {

            for(int j = 0; j < N; j++) {

                if(ma[i][j] == true)

                    System.out.print("*");

                else

                    System.out.print(" ");

            }

            System.out.println();

        }

    }

}

　　1.1.12

　　0 1 2 3 4 4 3 2 1 0

　　1.1.13　

public class TestApp1 {

    public static void main(String[] args) {

        int N = 10;

        int M = 15;

        boolean ma[][] = new boolean[N][M];

        for(int i = 0; i < N; i++) {

            for(int j = 0; j < M; j++) {

                double r = Math.random();

                if(r < 0.5)

                    ma[i][j] = true;

                else

                    ma[i][j] = false;

            }

        }

        System.out.println("origin matrix:");

        for(int i = 0; i < N; i++) {

            for(int j = 0; j < M; j++) {

                if(ma[i][j] == true)

                    System.out.print("*");

                else

                    System.out.print(" ");

            }

            System.out.println();

        }

        System.out.println("transposition matrix:");

        for(int i = 0; i < M; i++) {

            for(int j = 0; j < N; j++) {

                if(ma[j][i] == true)

                    System.out.print("*");

                else

                    System.out.print(" ");

            }

            System.out.println();

        }

    }

}

　　1.1.14

public class TestApp1 {

    public static void main(String[] args) {

        System.out.println(lg(15));

        System.out.println(lg(16));

        System.out.println(lg(17));

    }

    private static int lg(int N) {

        int result = 1;

        while(result <= N) {

            result *= 2;

        }

        return result / 2;

    }

}

　　1.1.15

public class TestApp1 {

    public static void main(String[] args) {

        int A[] = {1, 2, 3, 3, 2, 5, 5, 4};

        int N = 8;

        int M[] = histogram(A, N);

        for(int m : M) {

            System.out.println(m);

        }

    }

    private static int[] histogram(int[] A, int N) {

        int[] M = new int[N];

        for(int i = 0; i < N; i++) {

            M[A[i]]++;

        }

        return M;

    }

}

　　1.1.16

　　311461142246

　　1.1.17

　　由于一直会递归调用，所以不会停止，直到栈溢出。

　　1.1.18

　　修改前：

　　mystery(2, 25) = 50

　　mystery(3, 11) = 33

　　修改后：

　　mystery(2, 25) = 33554432

　　mystery(3, 11) = 177147

　　1.1.19

public class TestApp1 {

    private static long[] list = new long[1000];

    public static void main(String[] args) {

        F(1000);

        for(int i = 0; i < list.length; i++) {

            if(i > 0 && list[i] == 0) {

                break;

            }

            StdOut.println(i + " " + list[i]);

        }

    }

    public static void F(int N) {

        list[0] = 0;

        list[1] = 1;

        for(int i = 2; i < N; i++) {

            list[i] = list[i - 1] + list[i - 2];

            if(list[i] < list[i - 1]) {

                list[i] = 0;

                System.out.println("MAX : " + list[i - 1]);

                break;

            }

        }

    }

}

　　最大值为 7540113804746346429

　　1.1.20

public class TestApp1 {

    public static void main(String[] args) {

        for(int i = 1; i <= 10; i++) {

            System.out.println("log_fact(" + i + "): " + log_fact(i));

        }

    }

    private static double log_fact(int n) {

        if(n == 1)

            return 0;

        else

            return log_fact(n - 1) + Math.log(n);

    }

}

　　1.1.21

import java.util.ArrayList;

import java.util.List;

public class TestApp1 {

    public static void main(String[] args) {

        List<Info> list = new ArrayList<Info>();

        String line;

        while(StdIn.hasNextLine()) {

            line = StdIn.readLine();

            if(line.isEmpty()) {

                break;

            }

            String[] content = line.split(" ");

            Info info = new Info(content[0], Integer.parseInt(content[1]), Integer.parseInt(content[2]));

            list.add(info);

        }

        for(Info info : list) {

            StdOut.println(info);

        }

    }

}

class Info {

    private String name;

    private int x;

    private int y;

    public Info(String name, int x, int y) {

        this.name = name;

        this.x = x;

        this.y = y;

    }

    public String toString(){

        return "1: " + name + "2: " + x + "3: " + y + "4: " + x * 1.0 / y;

    }

}

　　1.1.22

import java.util.ArrayList;

import java.util.List;

public class TestApp1 {

    public static void main(String[] args) {

        rank(3, new int[]{1, 3, 5, 6, 8, 11, 25, 78, 345, 7653});

    }

    private static int rank(int key, int[] a) {

        return rank(key, a, 0, a.length - 1, 0);

    }

    private static int rank(int key, int[] a, int lo, int hi, int depth) {

        if(lo > hi)

            return -1;

        int mid = (lo + hi) / 2;

        int loop = depth;

        while(loop != 0) {

            System.out.print(" ");

            loop--;

        }

        System.out.println("lo:" + lo + " hi:" + hi);

        if(key < a[mid])

            return rank(key, a, lo, mid - 1, ++depth);

        else if(key > a[mid])

            return rank(key, a, mid + 1, hi, ++depth);

        else

            return mid;

    }

}

　　1.1.23

import java.util.ArrayList;

import java.util.Arrays;

public class BinarySearch {

    private BinarySearch(){}

    public static int rank(int key, int[] a) {

        int lo = ;

        int hi = a.length - ;

        while(lo <= hi) {

            int mid = (lo + hi) / ;

            if(key < a[mid])

                hi = mid - ;

            if(key > a[mid])

                lo = mid + ;

            else

                return mid;

        }

        return -;

    }

    public static void main(String[] args) {

        In in = new In(args[]);

        int[] whitelist = in.readAllInts();

        Arrays.sort(whitelist);

        String flag = args[];

        if("+".equals(flag)) {

            while(!StdIn.isEmpty()) {

                int key = StdIn.readInt();

                if(rank(key, whitelist) == -) {

                    StdOut.println(key);

                }

            }

        }else if("-".equals(flag)) {

            while (!StdIn.isEmpty()) {

                int key = StdIn.readInt();

                if(rank(key, whitelist) != -) {

                    StdOut.println(key);

                }

            }

        } else {

            StdOut.println("Error Flag");

        }

    }

}

　　1.1.24

public class GCD {

    public static void main(String[] args) {

        StdOut.println(gcd(105, 24));

    }

    public static int gcd(int a, int b) {

        StdOut.println("a: " + a + " b: " + b);

        if(b == 0)

            return a;

        else

            return gcd(b, a % b);

    }

}

　　 1.1.25

设两数为a、b(b<a），用gcd(a,b）表示a，b的最大公约数，r=a mod b 为a除以b以后的余数，k为a除以b的商，即a÷b=k.......r。辗转相除法即是要证明gcd(a,b)=gcd(b,r）。

第一步：令c=gcd(a,b），则设a=mc，b=nc

第二步：根据前提可知r =a-kb=mc-knc=(m-kn)c

第三步：根据第二步结果可知c也是r的因数

第四步：可以断定m-kn与n互质【否则，可设m-kn=xd，n=yd，（d>1），则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)dc，b=nc=ycd，故a与b最大公约数成为cd，而非c，与前面结论矛盾】

从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r）。

证毕。

巴特西

Algorithms 4th - 1.1 Basic Programming Model - EXERCISES