## 排座位 要安排：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; } ~~~