《Java数据结构跟算法》第二版 Robert lafore 编程作业 第六章
《Java数据结构和算法》第二版 Robert lafore 编程作业 第六章
《Java数据结构和算法》第二版 Robert lafore 编程作业 第六章
/*
6.1 假设买了一个价格便宜的掌上电脑，但是发现它内置的芯片不能做乘法，只能做
加法。摆脱这种窘境需要自己编写程序，写的是一个递归的方法mult()，它的参
数是x和y返回值是x乘它.当这个方法调用自身或者当它返回的时候，加法是否起
作用了?
6.2 在第8章"二叉树"中，我们将看到二叉树，在它的每一个节点中确实有两个子树。
如果使用字符在屏幕上画一棵二叉树，可以在顶层有一个节点，在下一层有两个，
然后是4、8、16个，依此类推。下面是一棵最底层有16个字符的树的样子：
--------X-------
----X-------X---
--X---X---X---X-
-X-X-X-X-X-X-X-X
XXXXXXXXXXXXXXXX
（注意最下面的一行，应当向右移动半个字符宽，但是在字符模式中做不到。）
可以使用递归的makeBranches()方法来画这个树，这个方法的参数为left和
right，它们是水平范围的端点。当第一次进入这个程序的时候，left等于0，而
且right是所有行中字符的数目（包括短线）减一。在这行范围的中间画一个X。
然后这个方法调用自己两次：一次左一半的范围，一次右一半的范围。当这个范
围太小的时候返回。你可能想要把所有的短线和X都放到一个数组中，并且一次性
显示数组，或许可以使用display()方法。编写main()调用makeBranches()和
display()来画这棵树。允许main()决定显示的每一行的宽度（32，64或者其他
的任何值）。确保存放显示字符的数组不会比所需要的空间大。行数(图中为五）
和每一行的宽度有什么关系？
6.3 应用递归的算法来实现求一个数的乘方，如在这一章接近结尾处的"求一个数的乘
方"部分所讲。写递归的power()方法以及一个main()来测试它。
6.4 写一个能解决背包问题的程序，任意给定背包的容量以及一系列物品的重量，设
把这些重量值存在一个数组中。提示：递归方法knapsack()的参数是目标重量和
剩下物品开始位置的数组下标。
6.5 应用一个递归的方法来显示由一群人组队的所有可能方案(由n个人每次挑k个)。
编写递归的showTeams()方法和一个main()方法来提示用户输入人群的人数以及
组队的人数，以此来作为showTeams()的参数，然后显示所有的组合。
*/
package chap06;
//=======================================================================
//编程作业 6.1
public class Multiplication {
// multiplicand 被乘数
// multiplier 乘数
// multiply 乘
public int multiply(int multiplicand, int multiplier) {
if (multiplier == 1) {
return multiplicand;
} else {
return multiplicand + multiply(multiplicand, multiplier - 1);
}
}
public static void main(String[] args) {
Multiplication mutiplication = new Multiplication();
int result = mutiplication.multiply(6, 8);
System.out.println(result);
}
}
// =======================================================================
package chap06;
// =============================================================================
// 编程作业 6.2
public class BinaryTreeShow {
private char[][] lines;
// number 一行最大显示字符数
public BinaryTreeShow(int number) {
int rows = 1;
int numberDivide = number;// 不要直接用number去除，后面还有用到number
while ((numberDivide = numberDivide / 2) != 0) {// 行数 number和row的关系
rows++; // 2^(row-1) = number 2^(5-1)=16
} // 当number=16时，row=5
lines = new char[rows][number];
for (int i = 0; i < rows; i++) { // 初始化数组
for (int j = 0; j < number; j++) {
lines[i][j] = '-';
}
}
}
public void display() {
for (int i = 0; i < lines.length; i++) { // 初始化数组
for (int j = 0; j < lines[i].length; j++) {
System.out.print(lines[i][j]);
}
System.out.println();
}
}
public void makeBranches(int left, int right) {
int number = right - left + 1;
int row = 0;
int muberDivide = number; // 不要直接用number去除，后面还有用到number
while ((muberDivide = muberDivide * 2) <= lines[0].length) {
row++;// 计算当前行号
}
if (number == 1) {// 基值条件
lines[row][left] = 'X';
return;
} else {
int mid = (left + right) / 2 + 1;
lines[row][mid] = 'X';
makeBranches(left, mid - 1);
makeBranches(mid, right);
}
}
public void makeTree() {
makeBranches(0, lines[0].length - 1);
}
public static void main(String[] args) {
BinaryTreeShow binaryTreeShow = new BinaryTreeShow(16);
binaryTreeShow.makeTree();
binaryTreeShow.display();
}
}
// =============================================================================
package chap06;
//编程作业 6.3
//mathematics 数学，数学运算
//int的范围 [-2^32~2^31-1] -2147483648到2147483647
public class Mathematics {
// 求x的y次方 x^y
// 对于 y总是偶数时
// 2^8 = (2*2)^(8/2)= 4^4
// 4^4 = (4*4)^(4/2)=16^2
// 16^2 = (16*16)^(2/2) = 256^1
// 256^1 = 256
// 对于y出现是奇数时
// 3^18 = (3*3)^(18/2) = 9^9
// 9^9 = 9*(9^8)= 9*((9*9)^(8/2)) = 9*(81^4)
// 9*(81^4)=9*((81*81)^(4/2))=9*(6561^2)
// 9*(6561^2)=9*((6561*6561)^(2/2))=9*43046721^1
// 9*43046721^1 = 9*43046721
public int power(int x, int y) {
if (y == 1) {
return x;
} else {
if (y % 2 == 0) {
return power(x * x, y / 2);
} else {
return x * power(x * x, y / 2);
}
}
}
public static void main(String[] args) {
Mathematics mathematics = new Mathematics();
int result = mathematics.power(3, 18);
System.out.println(result);
}
}
package chap06;
// =============================================================================
// 编程作业 6.4
public class Knapsack {
private int[] weights; // 可供选择的重量
private boolean[] selects; // 记录是否被选择
public Knapsack(int[] weights) {
this.weights = weights;
selects = new boolean[weights.length];
}
// 找所有可能的解
// total总重量
// index可供选择的重量
public void knapsack(int total, int index) {
if (total < 0 || total > 0 && index >= weights.length) {// 基值,没找到解
return;
}
if (total == 0) { // 基值，找到解
for (int i = 0; i < index; i++) {
if (selects[i] == true) {
System.out.print(weights[i] + " ");
}
}
System.out.println();
return;
}
selects[index] = true;
knapsack(total - weights[index], index + 1);
selects[index] = false;
knapsack(total, index + 1);
}
public static void main(String[] args) {
Knapsack knapsack = new Knapsack(new int[] { 11, 8, 7, 6, 5, 4, 3 });
knapsack.knapsack(20, 0);
}
}
// =============================================================================
package chap06;
//编程作业 6.5
//方法一
public class Group {
private char[] persons; // 组中所有可供选择的成员
private boolean[] selects; // 标记成员选中与否
public Group(char[] persons) {
this.persons = persons;
selects = new boolean[persons.length];
}
public void showTeams(int teamNumber) {
showTeams(persons.length, teamNumber);
}
// =============================================
// 找所有可能的解
// totalNuber 总共有多少人供选择
// teamNuber 需要选择多少人
// =============================================
// 从个n人中取出k个人的所可能方案，表示为方法参数(n,k)
// 求(n,k)的所有解
// 当k=0时得一个解，n<k时无解
// 否则(n,k)-->(n-1,k-1)+(n-1,k)
// =============================================
// 列如 ：从3个人中选2个人，此时参数为(3,2)
// (3,2)-->(2,1)+(2,2)-->(1,0)+(1,1)+(1,1)+(1,2)
// (1,0)得到一个解,(1,2)无解
// (1,0)+(1,1)+(1,1)+(1,2)-->(1,1)+(1,1)
// (1,1)+(1,1)-->(0,0)+(0,1)+(0,0)+(0,1)
// (0,0)得到一个解,(0,1)无解
// 所以(3,2)一共有 3个解
// 列如 ：从3个人中选3个人，此时参数为(3,3)
// (3,3)-->(2,2)+(2,3)-->(2,2)-->(1,1)+(1,2)-->(1,1)-->(0,0)+(0,1)-->(0,0)
// 即(3,3)有一个解
// =============================================
private void showTeams(int totalNumber, int teamNumber) {
if (teamNumber == 0) { // teamNumber=0时, 找到一个解
for (int i = 0; i < selects.length; i++) {
if (selects[i] == true) {
System.out.print(persons[i] + " ");
}
}
System.out.println();
return;
}
if (totalNumber < teamNumber) { // totalNuber< teamNumber,无解
return;
}
selects[persons.length - totalNumber] = true;
showTeams(totalNumber - 1, teamNumber - 1);
selects[persons.length - totalNumber] = false;
showTeams(totalNumber - 1, teamNumber);
}
public static void main(String[] args) {
Group group = new Group(new char[] { 'A', 'B', 'C', 'D', 'E' });
group.showTeams(3);
}
}
package chap06;
//编程作业 6.5
//方法二
public class Group1 {
private char[] persons; // 组中所有可供选择的成员
private boolean[] selects; // 标记成员选中与否
public Group1(char[] persons) {
this.persons = persons;
selects = new boolean[persons.length];
}
public void showTeams(int teamNumber) {
showTeams(teamNumber, 0);
}
// =============================================
// 找所有可能的解
// teamNumber需要选择的队员数
// index从第几个队员开始选择
// =============================================
// 从n个人中取出k个人的所可能方案
// 此处方法参数有些变化(n,k)应写成(k,i)(i=0,1,2,...)
// 当k=0时得一个解，i>=n时无解
// 否则(k,i)-->(k-1,i+1)+(k,i+1)
// =============================================
// 列如 ：从3个人中选2个人，
// 参数应写成(2,0)
// (2,0)-->(1,1)+(2,1)-->(0,2)+(1,2)+(1,2)+(2,2)
// (0,2)得一解
// (1,2)+(1,2)+(2,2)-->(0,3)+(1,3)+(0,3)+(1,3)+(1,3)+(2,3)
// (0,3)得一解，(1,3)无解，(2,3)无解，有两个(0,3)
// 所以(2,0)有三个解
// =============================================
private void showTeams(int teamNumber, int index) {
if (teamNumber == 0) { // 当teamNuber=0时 找到
for (int i = 0; i < selects.length; i++) {
if (selects[i] == true) {
System.out.print(persons[i] + " ");
}
}
System.out.println();
return;
}
if (index >= persons.length) {// index超过可供选择的人的数,未找到
return;
}
selects[index] = true;
showTeams(teamNumber - 1, index + 1);
selects[index] = false;
showTeams(teamNumber, index + 1);
}
public static void main(String[] args) {
Group1 group = new Group1(new char[] { 'A', 'B', 'C', 'D', 'E' });
group.showTeams(3);
}
}