枚举-火柴棍等式

时间:2022-05-24 20:26:18

题目:现小哼有n(n<=24)根火柴棍,希望拼出形如A+B=C的等式,等式中A,B,C均是用火柴棍拼出来的整数,数字0-9所需火柴棍依次为 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 ,那么小哼究竟可以拼出多少个不同的等式呢?

注意:

1、加号与等号各自需要2根火柴棍;

2、如果A不等于B,则A+B=C与B+A=C视为不同的等式(三者均大于0);

3、所有根火柴棍必须全都用上。

思路:

除去加号和等号各需的两根火柴,最多还剩20根火柴,对于0-9的数来说,1占用的火柴最少为2根,20根火柴最多10个1,所以A,B,C最大不会超1111,则只需枚举A,B,再通过A+B=C得到C的值,最终通过判断A+B+C是否等于n=4即可得到解;

代码如下:

 
#include<stdio.h>
int fun(int n)
{
	int sum=0;
	int a[10] = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 };
	while (n / 10 != 0)
	{
		sum+=a[n % 10];
		n = n / 10;
		
	}
	sum += a[n];
	return sum;
}
int main()
{
	int n,a,b,c;
	int num = 0;
	scanf("%d",&n);
	for (a = 0; a <= 1111; a++)
		for (b = 0; b <= 1111; b++)
		{
			c = a + b;
			if ( fun(a) + fun(b) + fun(c) ==n - 4)
			{
				printf("%d+%d=%d\n", a, b, c);
				num++;
			}
		}
	printf("一共可以输出%d个不同的等式",num);
	return 0;
}