• 中文
    • 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
    • 5.6k
    • 小曹

      请登录之后再进行评论

      登录

      赞助本站

      • 支付宝
      • 微信
      • QQ

      感谢一直支持本站的所有人!

      单栏布局 侧栏位置: