12個高矮不同的人,排成兩排,每排必須是從矮到高排列,而且第二排比對應的第一排的人高,問排列方式有多少種? (Java版)

思路： 從網上看了半天人家的分析，終于看明白了，在這里記錄一下自己的思路

先用一組數來代表這12個人, 1,2,3,4,5,6 7,8,9,10,11,12 ?排成兩排，每排要遞增排列，且對應位置第二排要大于第一排，則可以是

1 2 3 ?4 ?5 ? ?6 ? ? ? => ? 第一排的數用0來表示，第二排的數用1來表示，則這個數組序列就是 000000 111111

7 8 9 10 11 12

也可以是

1 3 5 7 ?9 ?11 ? ?=> ?這個數組序列就是010101 010101

2 4 6 8 10 12

?

所以對于任意排序 只要有對應的0和1的序列就可以， 就是有一個0就必須對應的有一個1,

比如 000111000111就可以 對應的排隊是 123789 ?- 456 10 11 12 , 但是有個條件需要滿足，就是序列是遞增，且第二排要大于第一排

這樣問題其實轉化為了求12個數的所有可能得入棧和出棧順序，0代表入棧，1代表出棧

?

解決方案：首先12個數可以構成所有的0和1的組合是1<<12-1 = 4095, 我們需要依次遍歷這4095個數，對于每個數的二進制表示，我們首先需要知道是否滿足上述的條件，即肯定要出現六個1, 然后對滿足含有六個1的數，對其分成兩組，第一組是左側的六位，第二組是右側的六位，如果第二組的每個位置的數都大于第一組，則這個數就是我們要找的

?

1 void catalan(){ 2 int num; 3 int[] front = new int[6]; 4 int[] back = new int[6]; 5 int counter = 0; 6 int i, j , k; 7 for(num = 0; num < (1<<12); num++){ 8 //是否含有六個1? 9 if(bitCount(num) == 6){ 10 i = j = 0; 11 12 for(k = 11; k >=0; k--){ 13 //填充前后排 14 if((num & (1<<k)) == 0){ 15 //從左到右掃描num，如果碰見的是0，即num&(1<<k)==0,則填充前排對應的位置 16 //因為我們要從右到左掃描num，所以k是從11開始，這樣的話1<<11才能落在num的最高位 17 front[i++] = 11-k; 18 }else{ 19 //如果碰見的不是是0，即num&(1<<k)!=0,則填充后排對應的位置 20 back[j++] = 11-k; 21 } 22 } 23 boolean ok = true; 24 //前后排填充完畢，開始判斷是否符合前排要低于后排的條件 25 for(int m = 0; m < 6; m++){ 26 if(front[m] > back[m]){ 27 ok = false; 28 break; 29 } 30 } 31 32 if(ok){ 33 logBin(num); 34 counter++; 35 } 36 } 37 } 38 39 System.out.println("TOTAL: " + counter); 40 } 41 42 private int bitCount(int n){ 43 int counter = 0; 44 while(n>0){ 45 n &= (n-1); 46 counter++; 47 } 48 return counter; 49 } 50 51 private void logBin(int n){ 52 System.out.println(Integer.toBinaryString(n)); 53 }

參考:?http://blog.csdn.net/hackbuteer1/article/details/7450250

轉載于:https://www.cnblogs.com/aalex/p/5031927.html

總結

以上是生活随笔為你收集整理的高矮不同的人排队问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。