首页 > 代码库 > 火柴棍等式

火柴棍等式

问题描述:

现在小明有n根火柴棍,希望拼出如 A+B=C 的等式。等式中的A、B、C均是用火柴棍拼出来的整数(若该数非零,则最高位不能是0)。数字0~9的拼法如图所示:

技术分享

注意:

  1. 加号与等号各自需要两根火柴棍。
  2. 如果 A≠B ,则 A+B=C 与 B+A=C 视为不同的等式(A、B、C都大于0)。
  3. 所有的火柴棍必须全部用上。

假如现在小明手上有m根(m ≤ 24)火柴棍,那么小明究竟可以拼出多少个不同的形如 A+B=C 的等式呢?

 

分析:

1,既然要找出形如A+B=C这样的等式,那最简单的办法就是分别枚举。

2,又因为题目中最多只有24根火柴,除去“+”和“=”占用的4根火柴棍,那么最多剩下20根火柴棍。

3,在0~9这10个数字中,我们可以看到数字1需要用到的火柴棍最少,只需要2根火柴棍。所以20根火柴棍最多能组成10个1。

4,因此在 A+B=C 这个等式A、B、C中的任意一个数都不能超过1111。(这个结论很关键!)

5,接下来我们只需要分别来枚举A、B、C,范围都是0~1111。

6,A所使用的火柴棍的根数加上B所使用的火柴棍的根数,再加上C所使用的火柴棍的根数,如果恰好等于m-4的话,则成功地找出了一组等式。

7,或者我们只需要枚举A和B就可以了,C可以通过A+B算出来。(优先采用这个)

 

代码如下:

#include<stdio.h>
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的末尾数字并将此数所需要用到的火柴棍根数累加到num中
        x=x/10;  //去掉x的末尾数字,例如x的值为123则现在x的值为12 
    } 
    num += f[x];  //最后加上此时x所需用到的火柴棍的根数(此时x一定是一位数)
    return num;  //返回需要火柴棍的总根数 
}

int main()
{
    int a,b,c,m,sum=0;  //sum用来计数,因此要初始化
    scanf("%d",&m);  //读入火柴棍的个数
    /*开始枚举a和b*/
    for(a=0;a<=1111;a++)
    {
        for(b=0;b<=1111;b++)
        {
            c=a+b;  //计算出c
            if(fun(a)+fun(b)+fun(c)==m-4)
            {
                printf("%d+%d=%d\n",a,b,c);
                sum++;
            } 
        }
    } 
    printf("一共可以拼出%d个不同的等式",sum);
    return 0;
} 

 技术分享

 

火柴棍等式