习题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的最大公约数。
参考答案
摘自维基百科
请登录之后再进行评论