蓝桥杯-结果填空之排座位
最后更新于：2022-04-01 14:53:34
## 排座位
要安排：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;
}
~~~