《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-XXXXXXXXXXXXXXXXX（注意最下面的一行，应当向右移动半个字符宽，但是在字符模式中做不到。）可以使用递归的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.1public 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.2public class BinaryTreeShow {private char[][] lines;// number 一行最大显示字符数public BinaryTreeShow(int number) {int rows = 1;int numberDivide = number;// 不要直接用number去除，后面还有用到numberwhile ((numberDivide = numberDivide / 2) != 0) {// 行数 number和row的关系rows++;// 2^(row-1) = number 2^(5-1)=16}// 当number=16时，row=5lines = 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去除，后面还有用到numberwhile ((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到2147483647public 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*43046721public 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.4public 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);}}