Problem Description
给你n根火柴棍,你可以拼出多少个形如“A+B=C”的等式?等式中的A、B、C是用火柴棍拼出的整数(若该数非零,则最高位不能是0)。用火柴棍拼数字0-9的拼法如图所示:
注意:
1. 加号与等号各自需要两根火柴棍
2. 如果A≠B,则A+B=C与B+A=C视为不同的等式(A、B、C≥0)
3. n根火柴棍必须全部用上
Input
输入一个整数n(n≤24)。
Output
输出能拼成的不同等式的数目。
PS:此题转载自博客园 作者87hbteo 我完全是想记录下这个题来
火柴拼的数字
思路:由于题目中已经给出,最多有24根火柴,而等号和加号各用4根的前提下,A\B\C三个数则总共只有20根火柴,数据范围较小,可以用枚举法枚举A、B。这个时候我们发现,0-9这10个数字所用的火柴数为:6,2,5,5,4,5,6,3,7,6,很明显数字1用的火柴棒最少只要2根,不妨让B为1,那么A和C最多可以使用18根火柴,而C>=A,满足条件的A的最大取值为1111。所以枚举A和B的范围是从0~1111。
为了加快速度,可以将0到2222(1111+1111)的所有整数需要的火柴棒数目提前算好保存在数组中。
#include #include int a[2223]= {6,2,5,5,4,5,6,3,7,6};//前10需要的火柴数目const int b[10]= {6,2,5,5,4,5,6,3,7,6};//定义b数组的值,不可改变int need(int n){int t, num;num=0;if(n==0) return 6;while(n>0){t=n%10;num+=b[t];//统计数字并且把这些数字所需要的火柴数目加起来n/=10;//跳过最后一个数字}return num;}int main( ){int n,i,j,A,B,C,D,sum;scanf("%d",&n);sum=0;for(i=10; i