蓝桥杯2016年A组：寒假作业

问题描述

现在小学的数学题目也不是那么好玩的。
看看这个寒假作业：
□ + □ = □
□ - □ = □
□ × □ = □
□ ÷ □ = □

每个方块代表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
就算两种解法。（加法，乘法交换律后算不同的方案）
你一共找到了多少种方案？
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

解决方案

思路

全排列

代码

#include <iostream>
#include <algorithm>

using namespace std;

bool check(int arr[]) {
    if (arr[0] % arr[1])
        return false;

    if (arr[0] / arr[1] == arr[2])
        if (arr[3] + arr[4] == arr[5])
            if (arr[6] - arr[7] == arr[8])
                if (arr[9] * arr[10] == arr[11])
                    return true;

    return false;
}

//递归全排列
int fun(int arr[], int k) {
    if (k == 13)
        if (check(arr))
            return 1;
        else
            return 0;


    int sum = 0;
    for (int i = k; i < 13; ++i) {
        {
            int temp = arr[i];
            arr[i] = arr[k];
            arr[k] = temp;
        }

        if ((k < 5 || arr[3] + arr[4] == arr[5]) && (k < 2 || (arr[0] % arr[1] == 0 && arr[0] / arr[1] == arr[2]))) //加速
            sum += fun(arr, k + 1);
        {
            int temp = arr[i];
            arr[i] = arr[k];
            arr[k] = temp;
        }
    }

    return sum;
}


int main() {
//    int ans = 0;
    int arr[13] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};

//    do {
//        if (check(arr))
//            ans++;
//
//    } while (next_permutation(arr, arr + 13));
//    cout << ans;

    cout << fun(arr, 0);
    return 0;
}

输出

64