首页 > 代码库 > java代码实现:12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?
java代码实现:12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?
此题参考与其他人思路, 2个解题方式。
1.
1 /** 2 * 用java代码实现:12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种? 3 * 状态树方式解 4 * 用状态生成树的方式来做的,先把12个人按从低到高一次编号, 5 * 从(1 ; 2)出发,加入3和4的时候生成(1,3 ; 2,4)和(1,2 ; 3,4), 6 * 然后加入5和6,分别从前面的两个状态出发,可以生成5种状态,就是说6个人时有5种排列 7 * @author amos-s 8 * @Time:2017年3月10日 下午6:18:37 9 * @version 1.0 10 */ 11 public class LineUpProblem { 12 13 private int count = 0; 14 private int total = 0; 15 private Stack<Integer> place = new Stack<Integer>(); 16 17 public LineUpProblem(int total) { 18 this.total = total; 19 } 20 21 private void lineOrder(int order, int level) { 22 place.push(order); 23 if (level >= total / 2) { 24 count++; 25 for (Integer integer : place) { 26 System.out.print(integer); 27 } 28 System.out.println(); 29 place.pop(); 30 return; 31 } 32 33 for (int i = order + 1; i < 2 * (level + 1); ++i) { 34 lineOrder(i, level); 35 } 36 place.pop(); 37 } 38 39 40 public void lineOrder() { 41 lineOrder(1, 1); 42 System.out.println("第一排一共有" + count + "种排列"); 43 } 44 45 public static void main(String[] args) { 46 LineUpProblem line = new LineUpProblem(12); 47 line.lineOrder(); 48 } 49 }
2.
1 /** 2 * 用java代码实现:12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种? 3 * 1.目前数是{0,1,2,3,4,5}, ++操作后,数变为{0,1,2,3,4,6},因为6小于且等于位置5的最大值2n = 10,所以此组合是个符合要求的组合。 4 5 * 2.又如目前数是{0,1,2,3,4,10}, ++操作后,数变为{0,1,2,3,4,11},因为11大于位置5的最大值2n = 10, 6 因此要进位,这样位置4的数++,再检查位置4的数++后是5,小于且等于位置4的最大值2n = 8,这个位置符合条件, 7 而位置5的数要置"0",这个0不能是再从范围的起始值开始,而是要等于位置4的数+1.因为从起始值开始的数肯定是小于位置4的值的。 8 9 * 3.以此类推,如果目前数是{0,1,4,6,8,10},++操作后,需要进位,一步一步往前进位,最终进位位置1的数,数就变成了{0,2,5,7,9,11}, 10 然后要把位置1之后位置的每个位置的数置"0", 等于前一个位置的数+1,这样最后数就是{0,2,3,4,5,6}. 11 12 * 4.检查此数组合是否符合条件是,检查最后一个数是否小于且等于其位置的最大值。 13 * 14 * @author amos-s 15 * @Time:2017年3月10日 下午6:18:37 16 * @version 1.0 17 */ 18 public class LineUpProblem2 { 19 20 private int count = 0; 21 private int total = 0; 22 23 public LineUpProblem2(int total) { 24 this.total = total; 25 } 26 27 private void lineOrder() { 28 //No.1 29 //开始写代码,求排列方式有多少种 30 if (total % 2 != 0) 31 return; 32 //初始化数组,并完成第一种排列 33 int[] data = http://www.mamicode.com/new int[total / 2]; 34 for (int i = 1; i < data.length; ++i) { 35 data[i] = i; 36 } 37 count++; 38 //保存操作数组的位置 39 int i = data.length - 1; 40 int allCount = 0; 41 while (i >= 0) { 42 43 data[i]++; //要操作的数+1 44 if (data[i] <= i * 2) { 45 //对其数后面的数字初始化 46 for (int j = i + 1; j < data.length; ++j) { 47 data[j] = data[j - 1] + 1; //保证其是前一位+1,最小数组合 48 } 49 } else { 50 //此位置已达最大值,操作其前面一位 51 i--; 52 continue; 53 } 54 //检查最后一位的数是否小于且等于其位置的最大值,如果是的话,此数组合符合要求 55 System.out.println(data[data.length - 1]); 56 if (data[data.length - 1] <= data[data.length - 1] * 2) { 57 count++; //排列方式+1 58 // 把++操作的数的位置置回最后一个位置。 59 i = data.length - 1; 60 } else { 61 // 如果大于其位置的最大值,说明已遍历完毕,超过了此数组合的最大值。 62 break; 63 } 64 65 } 66 67 68 //end_code 69 } 70 71 public void lineOrder() { 72 lineOrder(); 73 System.out.println("第一排一共有" + count + "种排列"); 74 } 75 76 public static void main(String[] args) { 77 LineUpProblem2 line = new LineUpProblem2(12); 78 line.lineOrder(); 79 } 80 }
java代码实现:12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。