• 問題描述
• Patchouli Knowledge(パチュリー·ノーレッジ) is the owner of the Embodiment of Scarlet Devil library. She often shelves books time by time.
  For she is careless, Patchouli treats all the books in the same size in the same way.
  Give you several books and their sizes (you only need to consider the height of the books), you should output all the books formations Patchouli may shelf.
  
  
• 輸入
• This problem may contains several cases.
  The first line is a single integer N (0 < N <= 8), indicates the number of books.
  The next line has N integers, the ith integer Hi (0 < Hi <= 15) indecate the height of the ith book.
  
• 輸出
• For each case, you have to output the all the possible formations (According to the height difference). Order by lexicographic order. The height will be outputed in hexadecimal.
  上離散課的時候，老師講了關于排列組合的2個算法，一個是字典序法，一個是鄰位交換法，今天試著把前者寫了出來，并A了這題，至于后者，由于字典序輸出的問題，暫時還沒寫 介紹下字典序法 字典序法中，對于數(shù)字1、2、3......n的排列，不同排列的先后關系是從左到右逐個比較對應的數(shù)字的先后來決定的。例如對于5個數(shù)字的排列12354和12345，排列12345在前，排列12354在后。按照這樣的規(guī)定，5個數(shù)字的所有的排列中最前面的是12345，最后面的是54321。
  　　字典序算法如下：
  　　設P是1～n的一個全排列:p=p1p2......pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn
  　　1）從排列的右端開始，找出第一個比右邊數(shù)字小的數(shù)字的序號j（j從左端開始計算），即 j=max{i|pi<pi+1}
  　　2）在pj的右邊的數(shù)字中，找出所有比pj大的數(shù)中最小的數(shù)字pk，即 k=min{i|pi>pj}（右邊的數(shù)從右至左是遞增的，因此k是所有大于pj的數(shù)字中序號最大者）
  　　3）對換pi，pk
  　　4）再將pj+1......pk-1pkpk+1......pn倒轉得到排列p’=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1，這就是排列p的下一個下一個排列。
  　　例如839647521是數(shù)字1～9的一個排列。從它生成下一個排列的步驟如下：
  　　自右至左找出排列中第一個比右邊數(shù)字小的數(shù)字4 839647521
  　　在該數(shù)字后的數(shù)字中找出比4大的數(shù)中最小的一個5 839647521
  　　將5與4交換 839657421
  　　將7421倒轉 839651247
  　　所以839647521的下一個排列是839651247。 //字典序法 #include<stdio.h> #include<string.h> #include<algorithm> using namespace std;char hex[6]={'A','B','C','D','E','F'}; int main() {int str[20];int len;while(~scanf("%d",&len)){int i,j,k,a,b,Max_min;for(i=0;i<len;i++){scanf("%d",&str[i]); }sort(str,str+len);while(1) {Max_min=0x3f3f3f;for(i=0;i<len-1;i++)if(str[i]<=9)printf("%d ",str[i]);elseprintf("%c ",hex[str[i]-10]);if(str[len-1]<=9)printf("%d\n",str[len-1]);elseprintf("%c\n",hex[str[len-1]-10]);for(i=len-1;i>=1;i--)if(str[i]>str[i-1]) //從右往左找第一對正序數(shù){a=str[i-1];k=i-1;break;} if(i<=0) break;for(i=len-1;i>k;i--)if(str[i]>a && str[i]<Max_min){j=i;Max_min=str[i];//從右向左找出一個最小的數(shù)，它比a要大 ，最靠右 }//交換str[k]=str[k]^str[j];str[j]=str[j]^str[k];str[k]=str[k]^str[j];for(i=k+1,j=len-1;i<j;i++,j--){str[i]=str[i]^str[j];str[j]=str[j]^str[i];str[i]=str[i]^str[j];}} }return 0; }
  
  

總結

以上是生活随笔為你收集整理的[1119] Patchouli's Books的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。