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]且火柴数之和为n
        if (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为当前火柴数加上之前的sum
       	dfs(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); // 从第一个数开始，当前火柴数和为0
    cout << 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。