• 中文
    • English
  • 注册
  • 查看作者
  • 《算法第四版》课后练习题1.1.21-1.1.25答案

    习题1.1.21

    编写一段程序,从标准输入按行读取数据,其中每行都包含一个名字和两个整数。然后用printf() 打印一张表格,每行的若干列数据包括名字、两个整数和第一个整数除以第二个整数 的结果,精确到小数点后三位。可以用这种程序将棒球球手的击球命中率或者学生的考试分数 制成表格。

    参考答案

    import java.util.Scanner;
    
    public class Test {
        public static void main(String[] args) {
            Scanner input = new Scanner(System.in);
            System.out.println("您要输入几个同学的信息?");
            int i = input.nextInt();
            input.nextLine();//过滤\n
            System.out.println("请输入所有同学的信息:");
            String[] str = new String[i];
            for (int j = 0; j < i; j++) {
                str[j] = input.nextLine();
            }
            System.out.println("-------------表格-------------");
            for (int j = 0; j < i; j++) {
                String[] s = str[j].split("\\s+");//  \\s表示 空格,回车,换行等空白符
                // split()方法将一个字符串按照空格分割,结果作为字符串数组返回。
                System.out.printf("姓名:%-10s   成绩1:%-10s   成绩二:%-10s   相除:%-13.3f \n", s[0], s[1], s[2],
                        Double.parseDouble(s[1]) / Double.parseDouble(s[2]));
            }
    
        }
    }
    
    您要输入几个同学的信息?
    3
    请输入所有同学的信息:
    张甲 100 100
    张一 200 200
    张丙 300 300
    -------------表格-------------
    姓名:张甲           成绩1:100          成绩二:100          相除:1.000         
    姓名:张一           成绩1:200          成绩二:200          相除:1.000         
    姓名:张丙           成绩1:300          成绩二:300          相除:1.000


     


    习题1.1.22

    使用1.1.6.4 中的 rank() 递归方法重新实现BinarySearch并跟踪该方法的调用。每当该方法被调用时,打印出它的参数 lo 和 hi 并按照递归的深度缩进。提示 :为递归方法加一个参数来保存递归的深度。

    要点分析

    rank() 方法在课本中第15页

    BinarySearch在课本第5页

    同时为没带课本的同学提供方便,我们这里给出15页的1.1.6.4节中的rank()递归方法代码:

    public static int rank(int key, int[] a) {
        return rank(key, a, 0, a.legth - 1);
    }
    public static int rank(int key, int[] a, int lo, int hi) {
        //如果key存在于a[]中,它的索引不会小于lo且不会大于hi
    
        if (lo > hi) return -1;
        int mid = lo + (hi - lo) / 2;
        if (key < a[mid]) return rank(key, a, lo, mid - 1);
        else if (key > a[mid]) return rank(key, a, mid + 1, hi);
        else return mid;
    }

    和BinarySearch类

    import edu.princeton.cs.algs4.In;
    import edu.princeton.cs.algs4.StdIn;
    import edu.princeton.cs.algs4.StdOut;
    
    import java.util.Arrays;
    
    public class BinarySearch {
        public static int rank(int key, int[] a) {
            int lo = 0;
            int hi = a.length - 1;
            while (lo <= hi) {
                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;
        }
    
        public static void main(String[] args) {
            int[] whitelist = In.readInts(args[0]);
            Arrays.sort(whitelist);
            while (!StdIn.isEmpty()) {
                int key = StdIn.readInt();
                if (rank(key, whitelist) == -1) {
                    StdOut.println(key);
                }
            }
        }
    }

    参考答案

    重新实现的BinarySearch并跟踪调用,按照深度缩进打印出lo和hi

    import edu.princeton.cs.algs4.In;
    import edu.princeton.cs.algs4.StdIn;
    import edu.princeton.cs.algs4.StdOut;
    
    import java.util.Arrays;
    
    public class BinarySearch {
        public static int rank(int key, int[] a) {
            return rank(key, a, 0, a.length - 1, 1);
        }
    
        public static int rank(int key, int[] a, int lo, int hi, int depth) {
            //如果key存在于a[]中,它的索引不会小于lo且不会大于hi
    
            for (int i = 0; i < depth; i++) {
                System.out.print(" ");
            }
            System.out.println("hi = " + hi + " lo = " + lo);
            if (lo > hi) {
                return -1;
            }
            int mid = lo + (hi - lo) / 2;
            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;
            }
        }
    
        public static void main(String[] args) {
            int[] whitelist = In.readInts(args[0]);
            //注意这里的In是采用基于文件的输入,详情可以查看《算法》第25页
            //args[0]传入一个txt文本路径,比如F:\Agorithm\Test.txt
            //这里Test.txt里的内容为11 22 33 44 55 66 77 88 99
            Arrays.sort(whitelist); //将数组升序排序
            System.out.println("请输入您要查找的数字:");
            while (!StdIn.isEmpty()) {
                int key = StdIn.readInt();
                int rv = rank(key, whitelist);
                if (rv == -1) {
                    StdOut.println("没有找到" + key + "这个元素");//如果没有找到就打印key的值
                } else {
                    StdOut.println(key + "的下标为" + rv);
                }
                System.out.println("请输入您要查找的数字:");
            }
        }
    }
    
    输出:
            请输入您要查找的数字:
            66
            hi = 8 lo = 0
            hi = 8 lo = 5
            hi = 5 lo = 5
            66的下标为5
            请输入您要查找的数字:
            2
            hi = 8 lo = 0
            hi = 3 lo = 0
            hi = 0 lo = 0
            hi = -1 lo = 0
            没有找到2这个元素


     


    习题1.1.23

    为 BinarySearch 的测试用例添加一个参数:+ 打印出标准输入中不在白名单上的值; -,则打印出标准输入中在名单上的值。

    要点分析

    很多人没有看懂这个问题,在这里给大家解释一下:

    简单说就是为BinarySearch测试用例添加一个参数

    该参数为‘+’时,输入要查找的数字,如果没有找到,则打印这个数字,如果找到了,则不打印

    该参数为‘-’时,输入要查找的数字,如果没有找到,则不打印,如果找到了,则打印这个数字

    参考答案

    import edu.princeton.cs.algs4.In;
    import edu.princeton.cs.algs4.StdIn;
    import edu.princeton.cs.algs4.StdOut;
    
    import java.util.Arrays;
    
    public class BinarySearch {
        public static int rank(int key, int[] a) {
            int lo = 0;
            int hi = a.length - 1;
            while (lo <= hi) {
                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;
        }
    
        public static void main(String[] args) {
            System.out.println("请输入-或者+");
            char arg = StdIn.readChar();
            int[] whitelist = In.readInts(args[0]);
            Arrays.sort(whitelist);
            while (!StdIn.isEmpty()) {
                int key = StdIn.readInt();
    
                if (arg == '+' && (rank(key, whitelist) == -1)) {
                    StdOut.println(key);
                }
                if (arg == '-' && (rank(key, whitelist) != -1)) {
                    StdOut.println(key);
                }
            }
        }
    }


     


    习题1.1.24

    给出使用欧几里得算法计算 105 和 24 的最大公约数的过程中得到的一系列 p 和 q 的值。扩展该算法中的代码得到一个程序Euclid,从命令行接受两个参数,计算它们的最大公约数并打印出每次调用递归方法时的两个参数。使用你的程序计算 1 111 111 和 1 234 567 的最大公约数。

    参考答案

    import edu.princeton.cs.algs4.StdIn;
    
    public class Test {
        public static int gcd(int p,int q) {
            if (q == 0) return p;
            int r = p % q;
            System.out.println("p = " + p + " , q = " + q);
            return gcd(q,r);
        }
    
        public static void main(String[] args) {
            System.out.println(gcd(105,24));
            System.out.println( gcd(1111111,1234567));
        }
    }
    
    输出:
            p = 105, q = 24
            p = 24, q = 9
            p = 9, q = 6
            p = 6, q = 3
            result: 3
            p = 1111111, q = 1234567
            p = 1111111, q = 123456
            p = 123456, q = 7
            p = 7, q = 4
            p = 4, q = 3
            p = 3, q = 1
            result: 1


     


    习题1.1.25

    使用数学归纳法证明欧几里得算法能够计算任意一对非整数p和q的最大公约数。

    参考答案

    《算法第四版》课后练习题1.1.21-1.1.25答案

    摘自维基百科

     

  • 0
  • 0
  • 0
  • 6k
  • 小曹

    请登录之后再进行评论

    登录
    单栏布局 侧栏位置: