题目描述

给你 n 根火柴棍，你可以拼出多少个形如 “A+B=C” 的等式？等式中的 A、B、C 是用火柴棍拼出的整数（若该数非零，则最高位不能是 0）。用火柴棍拼数字 0-9 的拼法如图所示：

图片描述

注意：

• 加号与等号各自需要两根火柴棍;
• 如果 A≠B，则 A+B=C 与 B+A=C 视为不同的等式（A、B、C 非负数）;
• n 根火柴棍必须全部用上。

输入描述

输入一行，一个整数 n $（n\le 24）$。

输出描述

输出一行，表示能拼成的不同等式的数目。

输入输出样例

示例 1

输入

14

输出

2

样例解释

2 个等式为：

$$0+1=1$$

$$1+0=1$$

示例 2

输入

18

输出

9

样例解释

9 个等式为：
$$0+4=4$$

$$0+11=11$$

$$1+10=11$$

$$2+2=4$$

$$2+7=9$$

$$4+0=4$$

$$7+2=9$$

$$10+1=11$$

$$11+0=11$$

解题思路

首先把加号与等号需要的4根火柴棍拿出来，然后一个个地遍历所有地可能性。

拿示例1分析，输入14，那么最后只能用10根火柴组成3个数字，这时我们需要知道组成每个数字需要多少根火柴。

根据题目给的图片描述，不难得出数字0-9需要地火柴数分别是6, 2, 5, 5, 4, 5, 6, 3, 7, 6

这只是一位数，如果是二位数或者是三位数，那么就需要更多的火柴

题目给的n，最大为24，减去4，也就是只有20根火柴能用来摆三个数，我们来估算一下这三个数的范围是多少。

摆数字1需要的火柴根数最少，如果是四位数：

$$1111+1111=2222$$

摆出上面的式子，需要$(2+2+5)\ast 4=56$根棍子（不包括加号与等号需要的根数）

假设所有等式里的元素都是3位数，那么我们只需要找出每个3位数需要的火柴棍数目，然后根据：

A的火柴棍数 + B的火柴棍数 + 结果C的火柴棍数 是否等于 火柴棍总数 - 4

如果等于，那么该等式成立

下面看一下代码的实现

代码实现

def MatchstickEquation():
    n = int(input()) - 4 # 减去加号与等号需要的4根火柴棍
    Matchstick = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6] # 0~9需要的火柴根数
    Matchsticks = Matchstick * 200
    for item in range(10, 1500):
        Sum, Num = 0, item
        while Num:
            Sum += Matchsticks[Num % 10]
            Num = int(Num / 10)
        Matchsticks[item] = Sum

    # print(Matchsticks)

    count = 0
    for i in range(1000):
        for j in range(1000):
            if (Matchsticks[i] + Matchsticks[j] + Matchsticks[i+j] == n):
                count += 1
    print(count)

MatchstickEquation()

最后

以上就是整齐小蘑菇为你收集整理的蓝桥云算法题之火柴棒等式——Python满分解答题目描述输入描述输出描述输入输出样例解题思路代码实现的全部内容，希望文章能够帮你解决蓝桥云算法题之火柴棒等式——Python满分解答题目描述输入描述输出描述输入输出样例解题思路代码实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。