藍橋杯全排列題目一個演算法解決
摘要：
我們下面的例題都可以用一個演算法解決---next_permutation(a,a+N)
例題1
湊算式
B DEF
A + --- + ------- = 10
CGHI
（如果顯示有問題，可以參見【圖1.jpg】）
這個算式中A...
我們下面的例題都可以用一個演算法解決---next_permutation(a,a+N)
例題1
湊算式
B DEF
A + --- + ------- = 10
CGHI
（如果顯示有問題，可以參見【圖1.jpg】）
這個算式中A~I代表1~9的數字，不同的字母代表不同的數字。
比如：
6+8/3+952/714 就是一種解法，
5+3/1+972/486 是另一種解法。
這個算式一共有多少種解法？
注意：你提交應該是個整數，不要填寫任何多餘的內容或說明性文字。
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
#define N 9
int main()
{
int ans=0;
int a[N]={1,2,3,4,5,6,7,8,9};
do
{
if(a[0]*a[2]*(a[6]*100+a[7]*10+a[8])+a[1]*(a[6]*100+a[7]*10+a[8])+(a[3]*100+a[4]*10+a[5])*a[2]==10*a[2]*(a[6]*100+a[7]*10+a[8]))
{
ans++;
}
}
while(next_permutation(a,a+N));
cout<<ans;
return 0;
}
例題2
方格填數
填入0~9的數字。要求：連續的兩個數字不能相鄰。
（左右、上下、對角都算相鄰）
一共有多少種可能的填數方案？
請填寫表示方案數目的整數。
注意：你提交的應該是一個整數，不要填寫任何多餘的內容或說明性文字。
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
#define N 10
int main()
{
int ans=0;
int a[N]={0,1,2,3,4,5,6,7,8,9};
do
{
if( abs(a[0]-a[1])!=1 && abs(a[0]-a[3])!=1 && abs(a[0]-a[4])!=1 && abs(a[0]-a[5])!=1 && abs(a[1]-a[2])!=1 && abs(a[1]-a[5])!=1 && abs(a[1]-a[6])!=1 && abs(a[1]-a[4])!=1 && abs(a[2]-a[6])!=1 && abs(a[2]-a[5])!=1 && abs(a[3]-a[4])!=1 && abs(a[3]-a[7])!=1 && abs(a[3]-a[8])!=1 && abs(a[4]-a[5])!=1 && abs(a[4]-a[7])!=1 && abs(a[4]-a[8])!=1 && abs(a[4]-a[9])!=1 && abs(a[5]-a[6])!=1 && abs(a[5]-a[8])!=1 && abs(a[5]-a[9])!=1 && abs(a[6]-a[9])!=1 && abs(a[7]-a[8])!=1 && abs(a[8]-a[9])!=1 )
{
ans++;
}
}
while(next_permutation(a,a+N));
cout<<ans;
return 0;
}
例題3
寒假作業
現在小學的數學題目也不是那麼好玩的。
看看這個寒假作業：
□ + □ = □
□ - □ = □
□ × □ = □
□ ÷ □ = □
(如果顯示不出來，可以參見【圖1.jpg】)
每個方塊代表1~13中的某一個數字，但不能重複。
比如：
6+ 7 = 13
9- 8 = 1
3* 4 = 12
10 / 2 = 5
以及：
7+ 6 = 13
9- 8 = 1
3* 4 = 12
10 / 2 = 5
就算兩種解法。（加法，乘法交換律後算不同的方案）
你一共找到了多少種方案？
請填寫表示方案數目的整數。
注意：你提交的應該是一個整數，不要填寫任何多餘的內容或說明性文字。
#include<iostream>
#include<algorithm>
using namespace std;
#define N 13
int main()
{
int ans=0;
double a[N]={1,2,3,4,5,6,7,8,9,10,11,12,13};
do
{
if((a[0]+a[1])==a[2] && (a[3]-a[4])==a[5] && a[6]*a[7]==a[8] && a[9]/a[10]==a[11])
{
ans++;
cout<<a[0]<<' '<<a[1]<<' '<<a[2]<<' '<<a[3]<<' '<<a[4]<<' '<<a[5]<<' '<<a[6]<<' '<<a[7]<<' '<<a[8]<<' '<<a[9]<<' '<<a[10]<<' '<<a[11]<<' '<<a[12]<<endl;
}
}
while(next_permutation(a,a+N));
cout<<ans;
return 0;
}
這個題目程式碼運算的時間有點長了，但是沒有運用到我還沒有學過的資料結構的知識，我感覺還不錯，這個演算法很適合運用在藍橋杯這個比賽當中。