//第七届蓝桥杯软件类省赛真题-C-C-3_寒假作业
/*
寒假作业
现在小学的数学题目也不是那么好玩的。
看看这个寒假作业：
【】+【】=【】
【】-【】=【】
【】*【】=【】
【】/【】=【】
每个方块代表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
就算两种解法。（加法，乘法交换律后算不同的方案）
你一共找到了多少种方案？
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
*/
/*【解题思路】
解法:深度优先搜索或暴力枚举,其中要遍历搜索13个数，有可能导致系统栈内存溢出，故需逐步判断优化
答案：64
*/
#include<iostream>
using namespace std;
int a[12];
bool visit[13];
int count = 0;
void dfs(int step)
{
if(step == 3)//逐步判断1
{
if((a[0]+a[1]) != a[2])
return;
}
if(step == 6)//逐步判断2
{
if( (a[3]-a[4]) != a[5] )
return;
}
if(step == 9)//逐步判断3
{
if( (a[6]*a[7]) != a[8] )
return;
}
if(step == 12)//逐步判断4
{
if((a[0]+a[1]) == a[2] && (a[3]-a[4]) == a[5] && (a[6]*a[7]) == a[8] && (a[11]*a[10]) == a[9]){
count++;
}
return;
}
for(int i = 0;i < 13;i ++)
{
if(visit[i] == false)
{
a[step] = i+1;
visit[i] = true;
dfs(step+1);
visit[i] = false;
}
}
return;
}
int main()
{
dfs(0);
cout<<"方案总数为："<<count<<endl;
return 0;
}
/*
#include<iostream>
using namespace std;
int main()
{
int a[12];
int count = 0;
for(a[0] = 1;a[0] <= 13;a[0]++)
for(a[1] = 1;a[1] <= 13;a[1]++)
for(a[2] = 1;a[2] <= 13;a[2]++){
if((a[0]+a[1]) != a[2])//逐步判断1
continue;
for(a[3] = 1;a[3] <= 13;a[3]++)
for(a[4] = 1;a[4] <= 13;a[4]++)
for(a[5] = 1;a[5] <= 13;a[5]++){
if((a[3]-a[4]) != a[5])//逐步判断2
continue;
for(a[6] = 1;a[6] <= 13;a[6]++)
for(a[7] = 1;a[7] <= 13;a[7]++)
for(a[8] = 1;a[8] <= 13;a[8]++){
if((a[6]*a[7]) != a[8])//逐步判断3
continue;
for(a[9] = 1;a[9] <= 13;a[9]++)
for(a[10] = 1;a[10] <= 13;a[10]++)
for(a[11] = 1;a[11] <= 13;a[11]++){
if((a[11]*a[10]) != a[9])//逐步判断4
continue;
if(a[0] != a[1] && a[0] != a[2] && a[0] != a[3] && a[0] != a[4] && a[0] != a[5] && a[0] != a[6] && a[0] != a[7] && a[0] != a[8] && a[0] != a[9] && a[0] != a[10] && a[0] != a[11]
&& a[1] != a[2] && a[1] != a[3] && a[1] != a[4] && a[1] != a[5] && a[1] != a[6] && a[1] != a[7] && a[1] != a[8] && a[1] != a[9] && a[1] != a[10] && a[1] != a[11]
&& a[2] != a[3] && a[2] != a[4] && a[2] != a[5] && a[2] != a[6] && a[2] != a[7] && a[2] != a[8] && a[2] != a[9] && a[2] != a[10] && a[2] != a[11]
&& a[3] != a[4] && a[3] != a[5] && a[3] != a[6] && a[3] != a[7] && a[3] != a[8] && a[3] != a[9] && a[3] != a[10] && a[3] != a[11]
&& a[4] != a[5] && a[4] != a[6] && a[4] != a[7] && a[4] != a[8] && a[4] != a[9] && a[4] != a[10] && a[4] != a[11]
&& a[5] != a[6] && a[5] != a[7] && a[5] != a[8] && a[5] != a[9] && a[5] != a[10] && a[5] != a[11]
&& a[6] != a[7] && a[6] != a[8] && a[6] != a[9] && a[6] != a[10] && a[6] != a[11]
&& a[7] != a[8] && a[7] != a[9] && a[7] != a[10] && a[7] != a[11]
&& a[8] != a[9] && a[8] != a[10] && a[8] != a[11]
&& a[9] != a[10] && a[9] != a[11]
&& a[10] != a[11]){
if((a[0]+a[1]) == a[2] && (a[3]-a[4]) == a[5] && (a[6]*a[7]) == a[8] && (a[11]*a[10]) == a[9]){
count++;
}
}
}
}
}
}
cout<<"方案总数为："<<count<<endl;
return 0;
}
*/
