P1149 [NOIP 2008 提高组] 火柴棒等式c/c++

题目描述

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

在这里插入图片描述

注意：

加号与等号各自需要两根火柴棍；
如果 A\=B，则 A+B=C 与 B+A=C 视为不
的等式（A,B,C≥0）；
n 根火柴棍必须全部用上。

输入格式

一个整数 n(1≤n≤24)。

输出格式

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

输入输出样例

输入

输出

输入

输出

说明/提示

【输入输出样例 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。

整体代码

#include <bits/stdc++.h>
using namespace std;const int N = 1000;
int n; // 用来存储输入的目标火柴数
vector<int> arr(3); // 用来存储三个数的值
int nums[1000] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; // 存储数字0-9所需的火柴数// 计算数字i所需的火柴数
int col(int i) {if (nums[i])return nums[i]; // 如果nums[i]已经有值，直接返回else {int sumFire = 0;// 对数字i进行分解，计算其组成的每个数字的火柴数while (i) {sumFire += nums[i % 10]; // i % 10得到i的最后一位数字i /= 10; // 更新i为除以10后的值，直到i为0}return sumFire;}
}int res = 0; // 记录符合条件的数量// 深度优先搜索函数
void dfs(int x, int sum) {// 如果当前火柴数已经超过n，则返回if (sum > n)return;// 当x超过3时，表示已经排好了三个数if (x > 3) {// 判断是否符合条件：arr[1] + arr[2] == arr[3]且火柴数之和为nif (arr[1] + arr[2] == arr[3] && sum == n) {res++; // 如果符合条件，计数加1}return;}// 遍历从0到999的所有数字，尝试填入arr[x]并进行递归for (int i = 0; i < 1000; i++) {arr[x] = i; // 将当前数字i填入arr[x]// 递归调用，更新sum为当前火柴数加上之前的sumdfs(x + 1, nums[i]+ sum);//dfs(x + 1, col(i) + sum);}
}int main() {cin >> n; // 输入目标火柴数n -= 4; // 减去4根火柴，初始条件已经预留了4根//这个是将计算后的数字存起来for(int i=10;i<=1000;i++){nums[i]=nums[i/10]+nums[i%10];}dfs(1, 0); // 从第一个数开始，当前火柴数和为0cout << res; // 输出符合条件的组合数return 0;
}

解题思路

要解决这个问题，我们需要通过火柴棍的数量来形成合适的等式 A + B = C，同时遵循以下几个关键点：

火柴数限制： 每个数字的拼法需要消耗一定数量的火柴棍，而加号和等号也需要消耗火柴棍。
拼数字规则： 数字 0 至 9 的火柴数量是固定的，我们需要将它们转化成火柴棍的数量,大于的可以通过取个位数。
不允许前导零： 如果数字是多位数，不能有前导零（即 01、02 等不合法）这里是i的递增来试数，数字均合理。

基于这些规则，我们可以通过递归（DFS）来生成所有可能的数字组合，并判断它们是否满足条件。

解释：

nums[] 数组存储了0到9这10个数字所需要的火柴数，例如数字0需要6根火柴，1需要2根火柴等。
col(int i) 函数通过递归计算每个数字所需要的火柴数。对于单个数字，直接返回预先存储的火柴数；对于多位数字，将数字分解为各个位数，累加每一位所需的火柴数。
dfs(int x, int sum) 是一个深度优先搜索算法，目的是通过遍历所有可能的数字组合，找出符合条件的数字组合。arr[]数组存储了这三个数的值，sum是当前已经使用的火柴数。
n -= 4 通过减去4根火柴来考虑初始条件，因为每个数字至少需要一个火柴来展示它本身+号和=号。
最终输出符合条件的组合数res。