## 排座位 要安排：3個A國人，3個B國人，3個C國人坐成一排。 要求不能使連續的3個人是同一個國籍。 求所有不同方案的總數？ 這道題，一看就排列組合的題目。。。據說給學校講概率論老師做，老師純手算， 費了好大勁。。。好吧，學計算機的當然不能浪費電腦的速度啦。。。 純暴力破解吧！ 我想法就是把三個國家A,B,C用數字1，2,3來表示， 剛開始我想就是用1,2,3來循環做，如果碰到相連的三個國家，就可以continue，選下一個數字代表的國家。 結果發現，計算出來的只有5000多種和答案28萬多種，差好多。。。 后來，經過小帥點播提醒，發現，國家要用九個的情況，并不能直接就讓后面的不能選。 我原來的想法代碼（錯的）： ~~~ #include <iostream> using namespace std; // A,B,C用數字1,2,3代替 // arr 記錄9個人狀態，sum記錄種類數 int arr[10],sum; // num下標記錄每個數字總數是否到3 int num[4]={0,0,0,0}; void find(int n) { if(n==10) { int j; for(j=1;j<=9;++j) cout<<arr[j]<<" "; cout<<endl; ++sum; return; } int i,k; for(i=1;i<=3;++i) { if(n<3) { if(num[i]==3) continue; arr[n]=i; ++num[i]; find(n+1); --num[i]; } if(arr[n-1]==arr[n-2] && arr[n-1]==i) continue; if(num[i]==3) continue; arr[n]=i; ++num[i]; find(n+1); --num[i]; } } int main() { sum=0; find(1); cout<<sum<<endl; return 0; } ~~~ 正確的代碼： ~~~ #include <iostream> using namespace std; // arr為排列方式數組 int arr[11],sum; // num為九個國家，前三個為A國設置為1，中間三個B國，設置為2，后面三個C國，設置為3 int num[11]; // a數組來表示，相應下標國家是否被選 int a[11]; void find(int n) { // 人數大于4是，查找是否有連著三個相同的 if(n>=4) { for(int i=1;i<=n-3;i++) if(arr[i]==arr[i+1]&&arr[i+1]==arr[i+2]) return ; } // n大于9，表示有一種排列可行 if(n>=10) { sum++; return ; } // 九次循環 for(int i=1;i<=9;i++) { if(num[i]==0) continue; num[i]=0; arr[n]=a[i]; find(n+1); num[i]=1; } } int main() { sum=0; // 賦初值1，表示都沒有被選過 for(int i=1;i<=9;i++) num[i]=1; a[1]=a[2]=a[3]=1;a[4]=a[5]=a[6]=2;a[7]=a[8]=a[9]=3; find(1); cout<<sum<<endl; return 0; } ~~~