寒假作业
现在小学的数学题目也不是那么好玩的。
看看这个寒假作业：
□ + □ = □
□ - □ = □
□ × □ = □
□ ÷ □ = □
(如果显示不出来，可以参见【图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
就算两种解法。（加法，乘法交换律后算不同的方案）
你一共找到了多少种方案？
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
思路：
该题是一道典型的搜索类题，为了节省时间，我们首先给出一个数组用来存1—13这13个数，然后进行判断，前两个个加起来是否等于第三个数，若不符合这一条件，则返回，符合则继续，以此类推，直到找到满足条件的解。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
#include<iostream>
#include<cstring> //包含memset(数组名，0/-1（只能是将数组中所有元素初始化这两个数），sizeof(数组名))
#include<algorithm> //算法头文件，其中包含许多好用的库函数
using namespace std;
int a[120]={-1},book[20]={0},sum=0; //book数组是用来标记1-13哪个数已经被用过了，用过则记为1，否则记为0；
void dfs(int x)
{
if(x>3&&a[1]+a[2]!=a[3]) //如果前三个数已经被取出来但不符合题设条件，则返回重找
return;
if(x>6&&a[4]-a[5]!=a[6]) //若前三个数满足第一条，看4-6个数是否满足第二个条件
return;
if(x>9&&a[7]*a[8]!=a[9]) //同上
return;
if(x>12&&a[12]*a[11]==a[10]) //如果所有条件均满足，则让sum++
{
sum++;
return;
}
for(int i=1;i<14;i++) //将1-13放入每一个格子中
{
if(book[i]==0) //若该数字没被用过则可以用，进入下一步
{
a[x]=i;
book[i]=1;
dfs(x+1);
book[i]=0;
}
}
return;
}
int main()
{
memset(a,-1,sizeof(a));
dfs(1);
cout<<sum;
return 0;
}
|
最终答案：64
