习题1.1.26
将三个数字排序。假设 a、b、c 和 t 都是同一种原始数字类型的变量。证明以下代码能够将 a、 b、c 按照升序排列:
if (a > b) { t = a; a = b; b = t; }
if (a > c) { t = a; a = c; c = t; }
if (b > c) { t = b; b = c; c = t; }
参考答案
public class Test {
public static void inAnAscendingOrder(int a, int b, int c) {
System.out.println("将" + a + " "+ b + " " + c + " 升序排列的结果为：" );
int t;
if (a > b) {
t = a;
a = b;
b = t;
}
if (a > c) {
t = a;
a = c;
c = t;
}
if (b > c) {
t = b;
b = c;
c = t;
}
//此时a的值最小，c的值最大，b的值处于中间
System.out.println(a + " "+ b + " " + c);
}
public static void main(String[] args) {
inAnAscendingOrder(5,6,2);
}
}
输出：
将5 6 2 升序排列的结果为：
2 5 6
习题1.1.27
二项分布。估计用以下代码计算binomial(100, 50,0.25)将会产生的递归调用次数:
public static double binomial(int N, int k, double p) {
if (N == 0 && k == 0) return 1.0;
if (N < 0 || k < 0) return 0.0;
return (1.0 - p) * binomial(N - 1, k, p) + p * binomial(N - 1, k - 1, p);
}
将已经计算过的值保存在数组中并给出一个更好的实现
要点分析
本题涉及到概率论相关知识，文科生会很陌生，理科生应该高中学过，无奈我是文科生……将相关资料整理如下：
- 二项分布：（英语：Binomial distribution）是n个独立的是/非试验中成功的次数的离散概率分布，其中每次试验的成功概率为p。这样的单次成功/失败试验又称为伯努利试验。实际上，当n = 1时，二项分布就是伯努利分布
-
概率质量函数和累积分布函数相关公式：
——摘自维基百科
参考答案
因原题N和K太大，这里将binomial(100, 50,0.25)修改为binomial(10, 5,0.25)为例：
import edu.princeton.cs.algs4.StdOut;
public class Test {
public static int count = 0;
public static double binomial(int n, int k, double p) {
count++;
if (n == 0 && k == 0) return 1.0;
if (n < 0 || k < 0) return 0.0;
return (1.0 - p) * binomial(n - 1, k, p) + p * binomial(n - 1, k - 1, p);
}
public static void main(String[] args) {
int n = Integer.parseInt(args[0]), k = Integer.parseInt(args[1]);
double p = Double.parseDouble(args[2]);
double b = binomial(n, k, p);
StdOut.println(b);
StdOut.println(count);
}
}
输出：
0.058399200439453125
2467
将已经计算过的值保存在数组中并给出一个更好的实现：
import edu.princeton.cs.algs4.StdOut;
public class One {
public static double binomial(int N, int k, double p) {
double[][] b = new double[N + 1][k + 1];
for (int i = 0; i <= N; i++)
b[i][0] = Math.pow(1.0 - p, i);
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= k; j++) {
b[i][j] = p * b[i - 1][j - 1] + (1.0 - p) * b[i - 1][j];
}
}
return b[N][k];
}
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
int k = Integer.parseInt(args[1]);
double p = Double.parseDouble(args[2]);
StdOut.println(binomial(N, k, p));
}
}
摘自ALGS4官网
我们来分析上面的代码，以binomial(10, 5,0.25)为例
我们为b数组分配N + 1 * K + 1个大小的空间
double[][] b = new double[N + 1][k + 1];
如下图：
那么我们为什么分配该数组空间的时候，N和K都需要加1呢？我们接着往下看：
for (int i = 0; i <= N; i++)
b[i][0] = Math.pow(1.0 - p, i);
该for循环给二维数组的第一列赋值，对照着该for循环下面的双重for循环我们可以看出
双重for循环并没有涉及到下图中灰色区域相关元素的赋值
所以虽说是分配数组空间的时候，n和k都加了1, 但其实多加的这一行一列只是为了计算方便
为了更好的理解，我们打印出所有元素的值
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= k; j++) {
StdOut.printf("%-10f", b[i][j]);
}
StdOut.println();
}
输出：
1.000000 0.000000 0.000000 0.000000 0.000000 0.000000
0.750000 0.250000 0.000000 0.000000 0.000000 0.000000
0.562500 0.375000 0.062500 0.000000 0.000000 0.000000
0.421875 0.421875 0.140625 0.015625 0.000000 0.000000
0.316406 0.421875 0.210938 0.046875 0.003906 0.000000
0.237305 0.395508 0.263672 0.087891 0.014648 0.000977
0.177979 0.355957 0.296631 0.131836 0.032959 0.004395
0.133484 0.311462 0.311462 0.173035 0.057678 0.011536
0.100113 0.266968 0.311462 0.207642 0.086517 0.023071
0.075085 0.225254 0.300339 0.233597 0.116798 0.038933
0.056314 0.187712 0.281568 0.250282 0.145998 0.058399
我们可以看出b[10][5] = 0.25 * b[10 – 1][5 – 1] + 0.75 * b[10 -1 ][5]
而b[9][4] = 0.25 * b[8][3] + 0.75 * b[8 ][4]
b[9][5] = 0.25 * b[8][4] + 0.75 * b[8 ][5]
相当于
return (1.0 - p) * binomial(n - 1, k, p) + p * binomial(n - 1, k - 1, p);
习题1.1.28
删除重复元素。修改BinarySearch类中的测试用例来删去排序之后白名单中的所有重复元素。
要点分析
关于BinarySearch类的测试用例代码请查看《算法第四版》课后练习题1.1.21-1.1.25答案 第1.1.22题
看到网上该题很多答案都是直接遍历整个数组查找重复元素，这里给出只遍历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, int[] b) {
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 {
//如果找到了这个元素，则遍历lo~hi之间的所有数字,查看哪些是重复元素，存入b数组中
for (int i = lo; i <= hi; i++) {
if (a[i] == key && i != mid) {// 如果i == mid 说明a[i]是我们查找到的那个元素，不作为重复元素处理
b[i] = a[i];
}
}
return mid;
}
}
return -1;
}
public static void main(String[] args) {
int[] whitelist = In.readInts(args[0]);
int[] b = new int[whitelist.length];
Arrays.sort(whitelist);
while (!StdIn.isEmpty()) {
int key = StdIn.readInt();
if (rank(key, whitelist, b) == -1) {
StdOut.println(key);
} else {
System.out.println("重复的元素为：");
for (int i = 0; i < b.length; i++) {
if (b[i] != 0) {
System.out.println("a[" + i + "]:" + b[i]);
b[i] = 0;
}
}
}
}
}
}
习题1.1.29
等值键。为 BinarySearch 类添加一个静态方法 rank()，它接受一个键和一个整型有序数组(可能存在重复键)作为参数并返回数组中小于该键的元素数量，以及一个类似的方法 count() 来 返回数组中等于该键的元素的数量。注意:如果 i 和 j 分别是 rank(key,a) 和 count(key,a) 的返回值，那么 a[i..i+j-1] 就是数组中所有和 key 相等的元素。
参考答案
package tv.zhangjia.one.one;
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;
int count = 0;
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 {
for (int i = lo; i <= hi; i++) {
if (a[i] == key) {
return i;
}
}
}
}
return -1;
}
public static int count(int key, int[] a) {
int lo = 0;
int hi = a.length - 1;
int count = 0;
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 {
for (int i = lo; i <= hi; i++) {
// if (a[i] == key && i != mid) {
// 因为a[i...i + j - 1] 等于所有和key相等的元素，所以这里删去i != mid这个条件
if (a[i] == key) {
count++;
}
}
return count;
}
}
return -1;
}
public static void main(String[] args) {
int[] whitelist = In.readInts(args[0]);
Arrays.sort(whitelist);
while (!StdIn.isEmpty()) {
int key = StdIn.readInt();
int i = rank(key, whitelist);
int j = count(key, whitelist);
if (i != -1) {
System.out.println("比" + key + "小的元素个数为" + i);
System.out.println("重复元素个数为" + j);
}
}
}
}
习题1.1.30
数组练习。编写一段程序，创建一个 N×N 的布尔数组 a[][]。其中当 i 和 j 互质时(没有相同因子)，a[i][j] 为 true，否则为 false。
要点分析
- 质数（Prime number），又称素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的数）。大于1的自然数若不是素数，则称之为合数 ——摘自维基百科
- 1虽不是质数，但与任何正整数都是互质数。
此处感谢@吸入一百米的指正
参考答案
public class Test {
public static int gcd(int p, int q) {
if(p == 0) {
return -1;
}
if (q == 0) {
return p;
}
int r = p % q;
return gcd(q, r);
}
public static void main(String[] args) {
boolean[][] b = new boolean[3][3];
for (int i = 0; i < b.length; i++) {
for (int j = 0; j < b[0].length; j++) {
b[i][j] = (gcd(i, j) == 1 ? true : false);
}
}
for (boolean[] s1 : b) {
for (boolean s2 : s1) {
System.out.print(s2 + " ");
}
System.out.println();
}
}
}
输出：
false false false
true true true
false true false
请登录之后再进行评论