算法(4th ed)(63):基础——基础编程模型 3.13

阅读数:12 2019 年 10 月 30 日 07:09

算法(4th ed)(63):基础——基础编程模型 3.13

(练习)

1.1.1 给出以下表达式的值:

a. ( 0 + 15 ) / 2

b. 2.0e-6 * 100000000.1

c. true && false || true && true

1.1.2 给出以下表达式的类型和值:

a. (1 + 2.236)/2

b. 1 + 2 + 3 + 4.0

c. 4.1 >= 4

d. 1 + 2 + "3"

1.1.3 编写一个程序,从命令行得到三个整数参数。如果它们都相等则打印 equal,否则打印 not equal

1.1.4 下列语句各有什么问题(如果有的话)?

a. if (a > b) then c = 0;

b. if a > b { c = 0; }

c. if (a > b) c = 0;

d. if (a > b) c = 0 else b = 0;

1.1.5 编写一段程序,如果 double 类型的变量 xy 都严格位于 01 之间则打印 true,否则打印 false

1.1.6 下面这段程序会打印出什么?

复制代码
int f = 0;
int g = 1;
for (int i = 0; i <= 15; i++)
{
StdOut.println(f);
f = f + g;
g = f - g;
}

1.1.7 分别给出以下代码段打印出的值:

a.

复制代码
double t = 9.0;
while (Math.abs(t - 9.0/t) > .001)
t = (9.0/t + t) / 2.0;
StdOut.printf("%.5f\n", t);

b.

复制代码
int sum = 0;
for (int i = 1; i < 1000; i++)
for (int j = 0; j < i; j++)
sum++;
StdOut.println(sum);

c.

复制代码
int sum = 0;
for (int i = 1; i < 1000; i *= 2)
for (int j = 0; j < 1000; j++)
sum++;
StdOut.println(sum);

1.1.8 下列语句会打印出什么结果?给出解释。

a. System.out.println('b');

b. System.out.println('b' + 'c');

c. System.out.println((char) ('a' + 4));

1.1.9 编写一段代码,将一个正整数 N 用二进制表示并转换为一个 String 类型的值 s。

解答:Java 有一个内置方法 Integer.toBinaryString(N) 专门完成这个任务,但该题的目的就是给出这个方法的其他实现方法。下面就是一个特别简洁的答案:

复制代码
String s = "";
for (int n = N; n > 0; n /= 2)
s = (n % 2) + s;

1.1.10 下面这段代码有什么问题?

复制代码
int[] a;
for (int i = 0; i < 10; i++)
a[i] = i * i;

解答:它没有用 newa[] 分配内存。这段代码会产生一个 variable a might not have been initialized 的编译错误。

1.1.11 编写一段代码,打印出一个二维布尔数组的内容。其中,使用 * 表示真,空格表示假。打印出行号和列号。

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);

1.1.13 编写一段代码,打印出一个 MN 列的二维数组的转置(交换行和列)。

1.1.14 编写一个静态方法lg(),接受一个整型参数 N,返回不大于 log2N 的最大整数。不要使用 Math 库。

1.1.15 编写一个静态方法 histogram(),接受一个整型数组 a[] 和一个整数 M 为参数并返回一个大小为M 的数组,其中第i 个元素的值为整数i 在参数数组中出现的次数。如果a[] 中的值均在0M-1 之间,返回数组中所有元素之和应该和 a.length 相等。

1.1.16 给出 exR1(6) 的返回值:

复制代码
public static String exR1(int n)
{
if (n <= 0) return "";
return exR1(n-3) + n + exR1(n-2) + n;
}

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;
}

:这段代码中的基础情况永远不会被访问。调用 exR2(3) 会产生调用 exR2(0)exR2(-3)exR2(-6),循环往复直到发生 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) 的返回值是多少?给定正整数 abmystery(a,b) 计算的结果是什么?将代码中的 + 替换为 * 并将 return 0 改为 return 1,然后回答相同的问题。

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) 的一个更好的实现,用数组保存已经计算过的值。

1.1.20 编写一个递归的静态方法计算 ln (N!) 的值。

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

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

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

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

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

评论

发布