本题来自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 #include 
     
       2 #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 #include 
     
       2  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