P1149 火柴棒等式

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

image

注意：

1. 加号与等号各自需要两根火柴棍
2. 如果A≠B，则A+B=C与B+A=C视为不同的等式（A,B,C>=0)
3. n根火柴棍必须全部用上

输入格式

一个整数

输出格式

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

思路：

本来我个人认为应该用递归做的，其实递归反而不太好做，变量也无法控制。去了洛谷找了个大神的解法。

题解代码：

#include<iostream>
using namespace std;int nu[10]={6,2,5,5,4,5,6,3,7,6};//定义个辅助数组记录每个数字所需的火柴数
int matches(int num){    //一个用来计算一个数需多少个火柴棒的函数
         int i,k=0;       //K是火柴棒的数量
         for(i=num;i!=0;i/=10)k+=nu[i%10];    //将这个数字每一位的火柴棒的数量都计算出来
         if(num==0)k+=nu[0];      //有一种特殊情况：数字为0此时不会执行上述程序，所以加一个
         return k;
}
int main(){
    int i,j,all=0,n;    //all是符合条件的算式总数
    cin>>n;     
        for(i=0;i<=1000;i++)for(j=0;j<=1000;j++)if(matches(i)+matches(j)+matches(i+j)+4==n)all++;    //如果这个算式加起来的火柴棒总数刚好用完所有火柴棒就把数量往上加
        cout<<all;
        return 0;
}

逐步分析：

一、我们先来看看这个matches函数

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

大部分其实都懂，有点意思的应该是第3行的那个for循环：

for(i=num;i!=0;i/=10)k+=nu[i%10];    //将这个数字每一位的火柴棒的数量都计算出来

我们来解读一下，这是一个用来判断位每一数的循环。假设：

num = 24;

那么第一次循环

i = 24; 
i!=0;
k = nu[i%10] = nu[24%10] = nu[4];
i/=10 = 24/10 = 2;

那么第二次循环

i = 2; 
i!=0;
k = nu[i%10] = nu[2%10] = nu[2];
i/=10 = 2/10 = 0;

结束循环，此时得到了正确的火柴数。

二、我们先来看看这个main函数

int main(){
    int i,j,all=0,n;    //all是符合条件的算式总数
    cin>>n;     
    for(i=0;i<=1000;i++)for(j=0;j<=1000;j++)if(matches(i)+matches(j)+matches(i+j)+4==n)all++;    //如果这个算式加起来的火柴棒总数刚好用完所有火柴棒就把数量往上加
        cout<<all;
        return 0;
}

有意思的要数那个for循环了：

for(i=0;i<=1000;i++)
  for(j=0;j<=1000;j++)
    if(matches(i)+matches(j)+matches(i+j)+4==n)
        all++; 

很容易懂，第一层循环就是A的数，第二层循环是B的数，若A的火柴数+B的火柴数+4个火柴=C的火柴数的话，则All（答案）++；