C/C++语言100题练习计划 87——火柴棒等式（枚举实现）

名人说：故立志者，为学之心也；为学者，立志之事也。—— 王阳明
进度：C/C++语言100题练习计划专栏，目前87/100

🥇C/C++语言100题练习专栏计划：目的：巩固练习C/C++语言，增强上机、动手实践能力，交流学习！

一、问题呈现

1.问题描述

Problem Description

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

注意：

1. 加号与等号各自需要两根火柴棍；

2. 如果 $A\ne B$，则 $A+B=C$ 与 $B+A=C$ 视为不同的等式（$A,B,C\ge 0$）；

3. $n$ 根火柴棍必须全部用上。

2.输入输出

Input

一个整数 $n(1\le n\le 24)$。

Output

一个整数，能拼成的不同等式的数目。

3.测试样例

样例1

Sample Input

14

Sample Output

2

样例2

Sample Input

18

Sample Output

9

★提示

【输入输出样例 1 解释】

$2$ 个等式为 $0+1=1$ 和 $1+0=1$。

【输入输出样例 2 解释】

$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$。

【题目来源】

[NOIP2008 提高组] 火柴棒等式

二、源码实现

#include
using namespace std;
//定义一个辅助数组来记录每个数字所需的火柴数（0 ~ 9）
int f[10]={6,2,5,5,4,5,6,3,7,6};

//一个用来计算一个数需多少个火柴棒的函数
int amount(int num)
{   
	//ans 火柴棒的数量
    int i,ans=0; 
	//将这个数字每一位的火柴棒的数量都计算出来      
    for(i=num;i!=0;i/=10)
		ans+=f[i%10];    
	//有一种特殊情况：数字为0此时不会执行上述程序，但是要考虑到，所以加上一个
    if(num==0)
		ans+=f[0];      
    return ans;
}

int main()
{
    int i,j,sum=0,n,flag=0;    //sum是符合条件的等式总数目
    cin>>n;     
    for(i=0;i<=1000;i++)
		for(j=0;j<=1000;j++)
			if(amount(i)+amount(j)+amount(i+j)+4==n)//如果这个等式加起来的火柴棒总数目，刚好需要用完所有火柴棒，就把数量往上加
				flag++;    
	sum=flag;
    cout<<sum<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

★关于本题思路及枚举：

1、本题思路简述

题意其实可以简单理解为：根据所有的火柴根数，将这些火柴使用完，可以有多少符合要求的拼法
根据题意：
0要用6根火柴
1要用2根火柴
2要用5根火柴
3要用5根火柴
4要用4根火柴
5要用5根火柴
6要用6根火柴
7要用3根火柴
8要用7根火柴
9要用6根火柴
★注意: ‘+’ 和 ‘=’ 也分别需要2根火柴
例如：1+1=2 一共用了2(第一个1)+2(加号)+2(第二个1)+2(等号)+5(结果2)=13根火柴
根据这些，之后进行打表处理即可。

2、枚举

1️⃣枚举相关概念
枚举算法是我们在日常中使用最多的一种算法思想，它的核心思想是：枚举所有的可能，确定枚举对象、范围和判定条件；然后注意枚举可能的解并验证每个解是否是问题的解。

2️⃣常见的枚举结构
循环+判断

3️⃣枚举的优缺点
①优点
枚举算法一般是现实生活问题的“直译”，所以比较直观，易于理解
枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上，所有算法的真确性容易证明
②缺点
枚举算法的效率取决于枚举状态的数量和单个状态枚举的代价，所以枚举效率相对来说比较低

三、测试结果

18
9

--------------------------------
Process exited after 1.408 seconds with return value 0
请按任意键继续. . .

1
2
3
4
5
6
7

Code_流苏(CSDN)（一个喜欢古诗词和编程的Coder）
如果对大家有帮助的话，希望大家能多多点赞+关注！这样我动力会更足哦！ ღ( ´･ᴗ･` )比心