首页 » C语言 » 寒假作业

寒假作业

原文 http://blog.csdn.net/Soul_97/article/details/79169644

2018-01-27 02:00:45阅读(267)

现在小学的数学题目也不是那么好玩的。

看看这个寒假作业

   □ + □= □

   □ - □ = □

   □ × □ = □

   □ ÷ □ = □

每个方块代表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回溯,每生成一个算式之后就判断如果不满足就return不再继续

例如a1 + a2 !=a3的话直接返回

当然,每一个算式都要判断,这样大大的减少了枚举量。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[13];
bool visit[14] = {false};
int ans = 0;
void dfs(int x)
{
	if(x >= 13)
	return ;
	if(x == 3 && a[0] + a[1] != a[2])
	return ;
	if(x == 6 && a[3] - a[4] != a[5])
	return ;
	if(x == 9 && a[6] * a[7] != a[8])
	return ;
	if(x == 12)
	{
		if(a[11]*a[10] == a[9])
		ans ++;
	}
	
	
	for(int i = 1;i <= 13;i ++)
	{
		if(!visit[i])
		{
			visit[i] = true;
			a[x] = i;
			dfs(x + 1);
			visit[i] = false;
		}
	}
}
int main()
{
	dfs(0);
	cout<<ans<<endl;
}


最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹