习题1.1.11
编写一段代码，打印出一个二维布尔数组的内容。其中，使用 * 表示真，空格表示假。打印出行号和列号。
参考答案
public class Test {
public static void printBooleanMatrix(boolean[][] b) {
for (int i = 0; i < b.length; i++) {
for (int j = 0; j < b[i].length; j++) {
System.out.print((i + 1) + " 行 " + (j + 1) + " 列 ：");
System.out.println(b[i][j] == true ? "*" : " ");
}
}
}
public static void main(String[] args) {
boolean[][] b = new boolean[][]{{true, false, false}, {true, true, true}};
printBooleanMatrix(b);
}
}
输出：
1 行 1 列 ：*
1 行 2 列 ：
1 行 3 列 ：
2 行 1 列 ：*
2 行 2 列 ：*
2 行 3 列 ：*
习题1.1.12
以下代码段会打印出什么结果?
int[] a = new int[10]; for (int i = 0; i < 10; i++) a[i] = 9 - i; for (int i = 0; i < 10; i++) a[i] = a[a[i]]; for (int i = 0; i < 10; i++) System.out.println(i);
参考答案
0
1
2
3
4
5
6
7
8
9
不过大多数都认为这里应该是印刷错误，作者的本意应该输出的不是i的值，而是a[i]的值。则答案如下：
0
1
2
3
4
4
3
1
习题1.1.13
编写一段代码，打印出一个 M 行 N 列的二维数组的转置(交换行和列)。
参考答案
public class Test {
public static void transposedMatrix(int[][] a) {
for (int i = 0; i < a[0].length; i++) {
for (int j = 0; j < a.length; j++) {
System.out.print(a[j][i] + " ");
}
System.out.println();
}
}
public static void printMatrix(int[][] a) {
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
System.out.print(a[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
int[][] a = {{1, 2, 3}, {4, 5, 6}};
System.out.println("原始数组 :");
transposedMatrix(a);
System.out.println("置换结果：");
printMatrix(a);
}
}
输出：
原始数组 :
1 4
2 5
3 6
置换结果：
1 2 3
4 5 6
习题1.1.14
编写一个静态方法 lg()，接受一个整型参数 N，返回不大于 log2N 的最大整数。不要使用 Math 库。
参考答案
解法一：
public class Test {
public static int lg(int n) {
int i = 2;
int j = 0;
while (true) {
i *= 2;
j++;
if (i >= n) {
return j;
}
}
}
public static void main(String[] args) {
System.out.println(lg(23));
}
}
输出：
4
4
4
解法二：
//Kyson版本
public static int lg(int N) {
int product = 1;
int x = -1;
while (product <= N) //*，把等于的情况也纳入进来，从而避免了在如23>5这种情况的自增导致输出结果为3的情况
{
product *= 2;
x++;
}
return x;
}
摘自Kyson博客
解法三：
//Jimmy Sun版本
public static int lg(int n) {
int shiftRightCount = 0;
do {
n >>= 1;
shiftRightCount++;
} while (n != 0);
return shiftRightCount - 1;
}
摘自Jimmy SunGitHub
习题1.1.15
编写一个静态方法 histogram()，接受一个整型数组 a[] 和一个整数 M 为参数并返回一个大小为 M 的数组，其中第 i 个元素的值为整数 i 在参数数组中出现的次数。如果 a[] 中的值均在 0 到 M-1之间，返回数组中所有元素之和应该和 a.length 相等。
参考答案
public class Test {
public static int[] histogram(int[] a, int M) {
int[] r = new int[M];
for (int i = 0; i < a.length; i++) {
if (a[i] < M) { //防止数组a中元素大于M后，发生越界错误
r[a[i]]++;
}
}
return r;
}
public static void print(int[] b, int a) {
int sum = 0;
for (int i : b) {
sum += i;
System.out.print(i + " ");
}
System.out.println("\n返回数组中所有元素的和a.length是否相等？" + (sum == a ));
}
public static void main(String[] args) {
int[] a = {1, 1, 1, 2, 2, 2, 3, 3, 5, 6, 7, 9, 9, 9, 9};
print(histogram(a, 10), a.length);
}
}
输出：
0 3 3 2 0 1 1 1 0 4
返回数组中所有元素的和a.length是否相等？true
习题1.1.16
给出 exR1(6) 的返回值
public static String exR1(int n)
{
if (n <= 0) return "";
return exR1(n-3) + n + exR1(n-2) + n;
}
参考答案
311361142246
习题1.1.17
找出以下递归函数的问题:
public static String exR2(int n) {
String s = exR2(n - 3) + n + exR2(n - 2) + n;
if (n <= 0) return "";
return s;
}
参考答案
该方法将会一直不停的调用本身，if语句永远不可能执行，直到运行的时候栈的深度超过了虚拟机容许的最大深度，将抛出 StackOverflowError 异常
习题1.1.18
请看以下递归函数:
public static int mystery(int a, int b) {
if (b == 0) return 0;
if (b % 2 == 0) return mystery(a + a, b / 2);
return mystery(a + a, b / 2) + a;
}
mystery(2, 25) 和 mystery(3, 11) 的返回值是多少?
给定正整数 a 和 b，mystery(a,b)计算的结果是什么?
将代码中的 + 替换为 * 并将 return 0 改为 return 1，然后回答相同的问题。
参考答案
测试类：
public class Test {
public static int mystery(int a, int b) {
if (b == 0) return 0;
if (b % 2 == 0) return mystery(a + a, b / 2);
return mystery(a + a, b / 2) + a;
}
public static int mystery2(int a, int b) {
if (b == 0) return 1;
if (b % 2 == 0) return mystery2(a * a, b / 2);
return mystery2(a * a, b / 2) * a;
}
public static void main(String[] args) {
System.out.println(mystery(2,25));
System.out.println(mystery(3,11));
System.out.println(mystery2(2,25));
System.out.println(mystery2(3,11));
}
}
mystery(2,25)：输出50
mystery(3,11)：输出33
mystery2(3,11)：输出177147
习题1.1.19
在计算机上运行以下程序:
public class Fibonacci {
public static long F(int N) {
if (N == 0) return 0;
if (N == 1) return 1;
return F(N - 1) + F(N - 2);
}
public static void main(String[] args) {
for (int N = 0; N < 100; N++)
StdOut.println(N + " " + F(N));
}
}
计算机用这段程序在一个小时之内能够得到 F(N) 结果的最大 N 值是多少?开发 F(N) 的一个更好的实现，用数组保存已经计算过的值。
参考答案
因时间限制，这里以一分钟为例，一分钟程序跑出的结果如下：
（受到电脑配置的影响一分钟内最大结果可能有所不同）
0 0 1 1 2 1 3 2 4 3 5 5 6 8 7 13 8 21 9 34 10 55 11 89 12 144 13 233 14 377 15 610 16 987 17 1597 18 2584 19 4181 20 6765 21 10946 22 17711 23 28657 24 46368 25 75025 26 121393 27 196418 28 317811 29 514229 30 832040 31 1346269 32 2178309 33 3524578 34 5702887 35 9227465 36 14930352 37 24157817 38 39088169 39 63245986 40 102334155 41 165580141 42 267914296 43 433494437 44 701408733 45 1134903170 46 1836311903 47 2971215073
F(N) 更好的实现方法（用数组保存已经计算过的值）：
import edu.princeton.cs.algs4.StdOut;
public class Test {
public static long F(int N, long[] a) {
if (N == 0) {
return a[0] = 0;
}
if (N == 1) {
return a[1] = 1;
}
return a[N] = a[N - 1] + (a[N - 2]);
}
public static void main(String[] args) {
long[] a = new long[100];
for (int N = 0; N < 100; N++)
StdOut.println(N + " " + F(N, a));
}
}
由于long只能表示-9223372036854775808~9223372036854775807之间（2^64 ~ 2^64 – 1）的数
所以该题的答案会超出范围，可以采用BigInteger来解决该问题
public class Test {
public static BigInteger F(int N, BigInteger[] a) {
if (N == 0) {
return a[0] = BigInteger.valueOf(0);
}
if (N == 1) {
return a[1] = BigInteger.valueOf(1);
}
return a[N] = a[N - 1].add(a[N - 2]);
}
public static void main(String[] args) {
BigInteger[] a = new BigInteger[100];
for (int N = 0; N < 100; N++)
StdOut.println(N + " " + F(N, a));
}
}
习题1.1.20
编写一个递归的静态方法计算 ln(N!) 的值。
感谢@onepiece指出本文的错误，一开始没有使用递归
参考答案
public class Test {
public static double ln(int N) {
if (N == 1 || N == 0) return 0;
else return ln(N - 1) + Math.log(N);//Java中Math.log()默认以e为底
}
public static void main(String[] args) {
System.out.println(ln(3)); //ln(6)的阶乘
}
}
输出：
1.791759469228055
int[][] a = {{1, 2, 3}, {4, 5, 6}};
这个应该是两行三列的 [s-11]