2016年蓝桥杯A组 第六题 寒假作业

时间:2022-12-30 20:03:18
今年的题不知为什么,第三道是考的dfs,这第六道同样是考的dfs,看来深度优先遍历是需要好好学学的!

寒假作业

现在小学的数学题目也不是那么好玩的。
看看这个寒假作业:

□ + □ = □
□ - □ = □
□ × □ = □
□ ÷ □ = □

(如果显示不出来,可以参见【图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

就算两种解法。(加法,乘法交换律后算不同的方案)

你一共找到了多少种方案?

请填写表示方案数目的整数。
注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。

这里我们很直观就可以想到用dfs,所以就不多分析了,直接上代码了,感觉通过这两道题,让我对dfs的感觉更到位了!

对,就是这个赶脚!跟着赶脚走,学算法是很快的,哈哈哈!

#include <stdio.h>
#define _MAX 13

int ans = 0;
int num[_MAX] = {0};
int visited[_MAX] = {0};

int test(int n)
{
if (n == 2)
{
if (num[0] + num[1] == num[2])
{
return 1;
}
}
else if (n == 5)
{
if (num[3] - num[4] == num[5])
{
return 1;
}
}
else if (n == 8)
{
if (num[6] * num[7] == num[8])
{
return 1;
}
}
else if (n == 11)
{
if (num[10] * num[11] == num[9])
{
ans++;
return 1;
}
}
else
{
return 1;
}
return 0;
}

void dfs(int n)
{
int i = 0;
if (n >= _MAX)
{
return ;
}
for (; i < _MAX; i++)
{
if (!visited[i])
{
visited[i] = 1;
num[n] = i + 1;
if (!test(n)) //如果不符合规则,则撤销这个分支
{
visited[i] = 0;
continue;
}
dfs(n + 1);
visited[i] = 0;
}
}
return ;
}

int main(int argc, const char * argv[])
{
dfs(0);
printf("%d\n", ans);
return 0;
}
OVER!!!