小冷漠‰959 2022-12-23 14:00 采纳率: 70%
浏览 35
已结题

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

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;
}

不知道哪出问题了,能帮忙找找错吗?

  • 写回答

2条回答 默认 最新

  • 小秋Kaito 2022-12-23 15:39
    关注

    你这个思路本身没有什么问题,就是穷举法,会循环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;
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 12月31日
  • 已采纳回答 12月23日
  • 创建了问题 12月23日

悬赏问题

  • ¥15 一个主机电脑有两个显示器,当前有两个软件主体是网页html打包的exe程序,如何通过cmd命令bat同时打开软件一个在主屏幕显示,另外一个软件在2副屏幕上显示
  • ¥15 AE SDK插件开发,获取关键帧值得问题
  • ¥15 谁知道这个咋搞的吗,有偿
  • ¥20 基于spring boot、的scorm
  • ¥15 往复密封问题的两个问题
  • ¥15 DAC函数和STM32
  • ¥15 任务是接收数据并把数据写入DAC7311,这些代码能实现此功能吗
  • ¥15 分析FP -Growth代码运行内存太大而无法运行的原因
  • ¥20 qtcreat 使用msvc编译器开发软件运行时字体锯齿感严重
  • ¥15 为何显示keyerror fruit