本题来自2016年蓝桥杯C/C++ A组第6题
寒假作业现在小学的数学题目也不是那么好玩的。
看看这个寒假作业:每个方块代表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就算两种解法。(加法,乘法交换律后算不同的方案)
你一共找到了多少种方案? 请填写表示方案数目的整数。注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。
思路一:用全排列函数next_permutation一个一个去试结果,13个数字的全排列运算时间非常长,等一个小时左右可以出结果。。。
1 #include2 #include 3 #include 4 #include 5 #include 6 7 using namespace std; 8 9 int main()10 {11 vector v;12 for (int i = 1; i <= 13; ++i)13 v.push_back(i);14 15 int cnt = 0;16 do17 {18 if (v[0] + v[1] == v[2] && v[3] - v[4] == v[5] && v[6] * v[7] == v[8] && v[9] == v[10] * v[11])19 cnt++;20 } while (next_permutation(v.begin(), v.end()));21 22 cout << cnt << endl;23 24 return 0;25 }
思路二:直接dfs回溯,每生成一个算式之后就判断如果不满足就return不再继续。例如,a1 + a2 !=a3的话直接返回。当然,每一个算式都要判断,这样大大的减少了枚举量。
1 #include2 3 using namespace std; 4 5 int a[13]; 6 bool visit[14] = { false }; 7 int ans = 0; 8 9 void dfs(int x)10 {11 if (x >= 13)12 return;13 if (x == 3 && a[0] + a[1] != a[2])14 return;15 if (x == 6 && a[3] - a[4] != a[5])16 return;17 if (x == 9 && a[6] * a[7] != a[8])18 return;19 if (x == 12)20 {21 if (a[11] * a[10] == a[9])22 ans++;23 }24 25 26 for (int i = 1; i <= 13; i++)27 {28 if (!visit[i])29 {30 visit[i] = true;31 a[x] = i;32 dfs(x + 1);33 visit[i] = false;34 }35 }36 }37 38 39 int main()40 {41 dfs(0);42 cout << ans << endl;43 44 return 0;45 }
最终答案: 64