首页 > 代码库 > 递归详解(三）
递归详解(三）
先来看一个题目：
今有7对数字：两个1，两个2，两个3，...两个7，把它们排成一行。 要求，两个1间有1个其它数字，两个2间有2个其它数字，以此类推，两个7之间有7个其它数字。如下就是一个符合要求的排列：
17126425374635
当然，如果把它倒过来，也是符合要求的。
请你找出另一种符合要求的排列法，并且这个排列法是以74开头的。
注意：只填写这个14位的整数，不能填写任何多余的内容，比如说明注释等。
17126425374635
当然，如果把它倒过来，也是符合要求的。
请你找出另一种符合要求的排列法，并且这个排列法是以74开头的。
注意：只填写这个14位的整数，不能填写任何多余的内容，比如说明注释等。
先说一下自己的解法:
1 import java.util.LinkedList; 2 import java.util.List; 3 import java.util.Random; 4 5 public class Test { 6 int m; 7 int n; 8 int first; 9 int last;10 int t;11 String s = "74";12 String sTemp = "";13 int a[]={1,2,3,4,5,6,7};14 Random random = new Random();15 List ListA = new LinkedList();16 public static void main(String[] args) {17 Test example = new Test();18 example.test();19 }20 21 public void test() {22 23 while(true)24 { 25 ListA.add(1);26 ListA.add(2);27 ListA.add(3);28 ListA.add(5);29 ListA.add(6);30 ListA.add(1);31 ListA.add(2);32 ListA.add(3);33 ListA.add(5);34 ListA.add(6);35 ////////////////////////////////////////////////// 36 for(int i=10;i>6;i--) {37 m=randomCreate(1,i);38 s=s+((ListA.get(m-1)).toString());39 ListA.remove(m-1); 40 }41 s=s+"4";42 m=randomCreate(1,6);43 s=s+((ListA.get(m-1)).toString());44 ListA.remove(m-1);45 s=s+"7";46 for(int i=5;i>0;i--) {47 m=randomCreate(1,i);48 s=s+((ListA.get(m-1)).toString());49 ListA.remove(m-1); 50 }51 /////////////////////////////////////////////////// 52 // 上面一段代码随机出来一个74****4*7*****的序列53 // System.out.println(s);54 /////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\55 if(s.length() == 14) {56 for(int x=1;x<=7;x++) {57 sTemp = Integer.toString(a[x-1]);58 first = s.indexOf(sTemp);59 last = s.lastIndexOf(sTemp);60 t= last - first;61 if(t == (x+1)) {62 if(x==7) {63 System.out.println(s);64 break;65 }66 else {67 continue;68 }69 70 }71 else {72 break;73 }74 }75 }76 //判读序列是否符合要求77 /////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\78 s = "74";79 ListA.clear();80 System.gc(); 81 }82 } 83 ////产生min到max之间的随机整数，包含min和max84 public int randomCreate(int min,int max) {85 int temp = random.nextInt(max)%(max-min+1) + min;86 // System.out.println(temp);87 return temp;88 }89 }
因为采用随机数的写法，时间不是很固定，一般入门i3处理器就在5，6分钟。结果：74151643752362
另外代码中有一点需要注意，s如果采用StringBuffer类型，拼接字符串采用apend()，会提示heap空间不足。感觉和书上讲的有出入。
如果不限定开头呢，编程找出所有结果。如果还按上面这种思路，14位数啥时候能随机上，想想中头彩的概率吧。如果采用穷举法呢，不好意思，1个小时也出不了结果。全部排列数为14!，大概就是8700亿种可能。经过实验，穷举法时间上能够接受的数量级在10！也就是300多万次。
后来，找到了大牛的代码，瞬间找出所有可能。而且代码很只有短短26行。佩服，还有谁！
1 class C { 2 static void findSo(int[] a, int n) { 3 for (int i = 0; i < 14; i++) { 4 if (i + n + 1 < 14 && a[i] == 0 && a[i + n + 1] == 0) { 5 a[i] = n; 6 a[i + n + 1] = n; 7 8 if (n == 7) { 9 for (int j = 0; j < 14; j++) {10 System.out.print(a[j]);11 }12 System.out.print("\n");13 } else {14 findSo(a, n + 1);15 }16 a[i] = 0;17 a[i + n + 1] = 0;18 }19 }20 }21 22 public static void main(String[] args) {23 int[] a = new int[14];24 findSo(a, 1);25 }26 }
1 17125623475364 2 17126425374635 3 16172452634753 4 15167245236473 5 14156742352637 6 14167345236275 7 16135743625427 8 15173465324726 9 1516374532642710 1514673542362711 5171625423764312 4171642532763513 4161743526327514 7131643572462515 7141635473265216 6151734653247217 4617145263275318 7316134572642519 4617143562372520 5617135463274221 7415164375236222 5714165347236223 3671314562742524 5741615437263225 2672151463754326 4567141536273227 2372635141765428 3457364151276229 2362734516147530 5247265413176331 2632743561417532 2632573461514733 2472364531716534 5273265341716435 5246275431613736 3572362541716437 2742356437151638 2562374536141739 5264275346131740 5723625347161441 5367235246171442 3467324526171543 7263245376415144 7246235473615145 6274235643715146 7245263475316147 5726325437614148 7362532476514149 3746325427615150 3574362542716151 5364735246217152 46357432652171
该如何理解代码里的递归呢？
递归详解(三）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。