## 排座位
要安排: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;
}
~~~
- 前言
- 入門訓練四道題
- 基礎練習之閏年判斷——BASIC-1
- 基礎練習之01字串——BASIC-2
- 基礎練習之字母圖形——BASIC-3
- 基礎練習之數列特征——BASIC-4
- 基礎練習之查找整除——BASIC-5
- 基礎練習之楊輝三角形——BASIC-6
- 基礎練習之特殊的數字——BASIC-7
- 基礎練習之回文數——BASIC-8
- 基礎練習之特殊回文數——BASIC-9
- 基礎練習之十進制轉十六進制——BASIC-10
- 基礎練習之十六進制轉十進制——BASIC-11
- 基礎練習之十六進制轉八進制——BASIC-12
- 基礎練習之數列排序——BASIC-13
- 算法訓練之區間K大數查詢——ALGO-1
- 算法訓練之最大最小公倍數——ALGO-2
- 藍橋杯-代碼填空之一
- 藍橋杯-代碼填空之二
- 藍橋杯-代碼填空之三
- 藍橋杯-代碼填空之精品
- 藍橋杯-歷屆試題之翻硬幣
- 藍橋杯-代碼填空之四
- 藍橋杯-結果填空題
- 藍橋杯-結果填空之排座位
- 藍橋杯-歷屆試題之大臣的旅費