蓝桥杯-结果填空之排座位

排座位

要安排：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;
}