规则：
现有n根火柴棍，希望拼出形如A+B=C的等式，等式中的A、B、C均是由火柴棍拼出来的整数(若该数非零，则最高位不能是0)，数字0~9的拼法如下所示：
题目：
14根火柴棍，可以拼出两个不同的等式0+1=1和1+0=1.
18根火柴棍，则可以拼出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注意：
- 加号与等号各自需要两根火柴
- 如果A ≠B,则A+B=C与B+A=C视为不等式(A,B,C都大于0)
- 所有火柴棍必须全部用上
假如现在有m(m<=24)根火柴棍，那么可以拼出多少个不同的形如A+B=C的等式？
算法规定时间是小于1s
分析：
1.分别枚举A、B、C，需要求得A、B、C的枚举范围
2.因为题目中最多只有24根火柴棍，除去'+','='占用的4根，那么最多剩下20根火柴棍，而0~9中用到火柴棍最少的是1，只需要两根火柴棍，20根火柴棍最多能组成10个1，因此A、B、C中任意一个数都不能超过11111
11111问题的解析：https://blog.csdn.net/jkl46607/article/details/82752071
- 求解： A + B + C = n-4
- 如果按照上诉求解算法时间复杂度是O(N³),不满足条件4小于1s
- 可以通过A+B来算出以此来降低时间复杂度到1s
代码：
#include <stdio.h>
int f[10]={6,2,5,5,4,5,6,3,7,6} ; //用来存储每一个数所需的火柴数
int fun(int x)
{
int num = 0;
//如果x/10的商不等于0，说明这个数至少有两位
while(x / 10 != 0)
{
//获得x的个位数字并将此数所需要的火柴树根数；累加到num中
num += f[x%10];
//去掉个位数
x = x / 10;
}
//最后加上（个位）此时x所需要用到的火柴跟数
num += f[x];
return num;
}
//计算火柴n所能摆出的数的最大上界,3000是粗略设置的范围，可改变
int CountN(int n)
{
int max = 0,c;
for(int i = 0; i < 3000; i++)
{
for(int j = 0; j < 3000; j++)
{
c = i + j;
if(fun(i) + fun(j) + fun(c) == n - 4)
{
if(j > max)
{
max = j;
}
}
}
}
return max;
}
int main(void)
{
int a,b,c,sum = 0;
int m = 18;//火柴棍的个数
int cnt = CountN(m);
printf("A B C to Upper limit of %d \n",cnt);
for(a = 0; a <= cnt; a++)
{
for(b = 0; b <= cnt; b++)
{
c = a + b;
if(fun(a) + fun(b) + fun(c) == m - 4)
{
printf("%d + %d = %d\n",a,b,c);
sum++;
}
}
}
printf("spell it %d Different inequalities\n",sum);
getchar();
return 0;
}
结果：
A B C to Upper limit of 11
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
spell it 9 Different inequalities
