关于#蓝桥杯#寒假作业的问题，如何解决？(语言-c语言)

Question

1285: [蓝桥杯2016初赛]寒假作业

题目描述
现在小学的数学题目也不是那么好玩的。
看看这个寒假作业：
每个方块代表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<stdio.h>
#define bool char
#define true 1
#define false 0
bool num[13];
int res=0;
int a[13]={1,2,3,4,5,6,7,8,9,10,11,12,13};

bool check()
{
    if
    ( a[0]+a[1] == a[2]  && a[3]-a[4]  == a[5]  && a[6]*a[7]  == a[8]  && a[11]*a[10] == a[9] )
    {
        return true;
    }
    return false;
}
void dfs(int u)
{
    if(u==13)
    {
        if(check())
        {
            res++;
        }
        return;
    }
    int i;
    for(i=0;i<13;i++)
    {
        if(num[i] == false)
        {
            num[i] = true;
            a[u] = i+1;
            dfs(u+1);
            num[i] = false;
        }
    }
    return;
}
int main()
{
    dfs(0);
    
    printf("%d",res);
    
    return 0;
}

不知道哪出问题了，能帮忙找找错吗？

Answer 1

你这个思路本身没有什么问题，就是穷举法，会循环13!次，也就是62亿多次循环，非常耗时。
所以就是尽可能的提升效率。
这里提供个参考：

#include<stdio.h>

int res=0;
int a[13]={1,2,3,4,5,6,7,8,9,10,11,12,13};

// 该方法可以理解为，k位之前的数已经确定，计算k位开始的这满足的数量
void dfs(int k)
{
    // 前3位确定后，如果不满足第一个等式则后面的不需要继续判断
    if(k>=3){
        if(a[0] + a[1] != a[2]) {
            return ;
        }
    }
    // 同理，前6位确定后。经过上面的判断，代表前三位一定满足第一个等式，那么第4-6位如果不满足第二个等式则后面的不需要继续判断，下面同理
    if(k>=6){
        if(a[3] - a[4] != a[5]) {
            return ;
        }
    }
    if(k>=9) {
        if (a[6] * a[7] != a[8]) {
            return;
        }
    }
    // 所有位都确定且四个等式都满足的情况下，res加1代表符合条件
    if(k>=12){
        if(a[11]*a[10]==a[9]) {
            res++;
            return ;
        }
    }

    // 前k位已经确认的情况下
    for(int i=k;i<13;i++) {
        // 通过下面的交换将第k+1位先确定一下（循环多次即尝试其所有可能性），然后递归执行dfs(k+1)
        int t=a[i];a[i]=a[k];a[k]=t;
        dfs(k+1);
        // 进入下次循环前要将数组复原这样才能保证下次循环没有问题
        t=a[i];a[i]=a[k];a[k]=t;
    }
    return;
}
int main()
{
    dfs(0);
    printf("%d",res);
    return 0;
}