啊哈！算法—火柴棍等式

小灰灰 2022-08-21 12:47 208阅读 0赞

现手中有m(m<=24)个火柴棍，希望拼出A+B=C等式。等式中的A、B、C均为火柴棍拼出来的整数（若该数非0，则最高位不能为0）。

注意：  
1、加号与等号各自需要2根火柴棍；

2、如果A不等于B，则A+B=C与B+A=C视为不同的等式（三者均大于0）；

3、所有根火柴棍必须全都用上。

思路：

24根除去4根还有20根，而数字1所需火柴棍最少，需2根。则三者中任一数不能超过1111。

只需枚举三者。A中火柴棍数加上B中火柴棍数等于C中火柴棍数，若恰好等于m-4的话，则成功找出一组解。

#include <iostream>
    using namespace std;
    int fun(int x)    //用来计算一个数所需要的火柴棍总数
    {
        int num=0;  //用来计数变量
        int f[10]={6,2,5,5,4,5,6,3,7,6};   //用一个数组记录0~9数字所需的火柴棍数
        while(x/10!=0)     // x除以10不等于0的话，说明该数至少有两位
        {
            num+=f[x%10];   //加上该位火柴棍数
            x=x/10;
        }
        num+=f[x];     //加上最高位的火柴棍数
        return num;
    }
    int main()
    {
         int a,b,c,m,sum=0;   
         cin>>m;        //火柴棍总个数
         for(a=0;a<=1111;a++)  //开始枚举
         {
             for(b=0;b<=1111;b++)
             {
                 c=a+b;
                 if(fun(a)+fun(b)+fun(c)==m-4)
                 {
                     cout<<a<<"+"<<b<<"="<<c<<endl;
                     sum++;
                 }
             }
         }
         cout<<"一共可以拼出"<<sum<<"个不同的样式"<<endl;
        return 0;
    }

运行结果：

![Center][]

[Center]: /images/20220724/637be59138f44075a437e3a5b4f9e23a.png

发表评论取消回复

表情：

评论列表（有 0 条评论，208人围观）

还没有评论，来说两句吧...

相关阅读

相关【啊哈！算法】文章目录

[《啊哈！算法》读书笔记][Link 1] [《啊哈！算法》学习心得][Link 2] -------------------- <table> <thea

系统管理员/ 2022年10月22日 07:54/ 0 赞/ 204 阅读

相关 SVG新年火柴棍动画

正在学习SVG，弄个2014年的火柴棍动画，大家先看[效果][Link 1]。 ![SouthEast][] 这个主要是用到了SVG的内置动画，大家可以参考msdn上

旧城等待，/ 2022年08月24日 14:25/ 0 赞/ 227 阅读

相关啊哈！算法—DFS—放扑克

将n张扑克放在n个盒子中，有哪些全排列。思路：利用深度优先搜索。深度优先搜索关键在于解决“当下该如何做”。至于“下一步该如何做”则和“当下该怎么做”是一样的。 v

小鱼儿/ 2022年08月21日 12:55/ 0 赞/ 195 阅读

相关啊哈！算法—火柴棍等式

现手中有m(m<=24)个火柴棍，希望拼出A+B=C等式。等式中的A、B、C均为火柴棍拼出来的整数（若该数非0，则最高位不能为0）。注意： 1、加号与等号各自需要2根火

小灰灰/ 2022年08月21日 12:47/ 0 赞/ 209 阅读

相关火柴棍

//火柴棍：输入整数n，输出能拼成的不同等式的数目 include<iostream> using namespace std; int ma

「爱情、让人受尽委屈。」/ 2022年06月16日 08:08/ 0 赞/ 180 阅读

相关算法火柴棍问题

题目：现在有n根火柴棍，拼出A+B=C的等式。注意：加号和等号各自需要两根火柴棍，A不等于B,则A+B=C与B+A=C是为不同的等式，所有火柴棍必须都用上。这个题刚看到

太过爱你忘了你带给我的痛/ 2022年05月30日 05:07/ 0 赞/ 229 阅读

相关啊哈算法（6）——最短路径

最短路径问题：对于一个给定的的图求出任意两点之间的最短路径？可以通过DFS或者BFS求出两个点之间的最短的路径，在本节介绍其他的算法来求出两个点之间的最短路径。

柔光的暖阳◎/ 2022年05月15日 05:44/ 0 赞/ 211 阅读

相关啊哈算法（4）—万能的搜索

深度优先搜索DFS 深度优先搜索的关键在于解决“当下该如何做”。至于下一步怎么做与当下该如何做是一样的。深度优先搜索的基本模型： void dfs(int ste

痛定思痛。/ 2022年05月15日 01:27/ 0 赞/ 265 阅读

相关洛谷P1149 火柴棒等式

题目：题目描述给你n根火柴棍，你可以拼出多少个形如“A+B=CA+B=C”的等式？等式中的AA、BB、CC是用火柴棍拼出的整数（若该数非零，则最高位不能是00）。

柔情只为你懂/ 2022年04月14日 06:56/ 0 赞/ 199 阅读

相关编程珠玑 ~~ 啊哈! 算法

2. 啊哈，算法 A.给定一个包含32位整数的顺序文件，它至多包含40亿个这样的整数，并且整数的次序是随机的，请查找一个此文件中不存在的32位整数(至少必有一个遗漏，为什么？

谁践踏了优雅/ 2022年01月10日 01:21/ 0 赞/ 303 阅读