【啊哈！算法】之枚举

问题引入

对于这样的奥数题大家一定不会陌生，实现起来也是没有什么难度的：

for(i = 1;i<=9;i++)
{
    if((i*10+3)*6528 == (30+i)*8256)
    {
        printf("%d",i);
    }

}

这就是采用枚举的方法，把所有的可能性都进行了尝试。

对于形如这样的火柴棍，

如何在全部使用给定的火柴（m<=24）后拼出A+B =C的等式呢？

问题分析

1. 等式中存在固定不变的地方， 就是加号与等号，他们一共占4根。

2. A + A = C这种，只能存在一次。

3. A + B = C与B + A = C视为不同的两组。

4. 确定范围。枚举也是需要在一定的范围内进行的。1这个数字需要的火柴最少，是2根，对于任意一个数，最多是（24-4）/ 2

最多拼10个1，所以任意一个数不会超过11111

5. 如果A、B、C一共使用的是m-4根，那么就是一组解。

但是，我们发现，对A，B，C三个数进行枚举，复杂度是11112*11112*11112,大约需要1000多秒。

但如果只需要枚举A和B，直接通过计算得出C，复杂度将会变成11112*11112，可以降低到1秒以内。

解决思路

1. 记录每个数字需要的火柴数

int f[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

2. 获取X数值需要的火柴数

int num = 0;    //所需要的火柴数
while(x/10 != 0)
{
    num += f[x%10];    //通过取余算法获得各个位上的数字
    x = x / 10;    //更新x值
}

num += f[x];

return num;

3. 开始枚举

int main()
{
    int a, b, c, m, i, sum = 0;
    scanf("%d",&m);

    for(a = 0; a<= 11111; a++)
    {
        for(b = 0;b <= 11111; b++)
        {
            c = a + b;
            if(fun(a) + fun(b) + fun(c) == m -4)
            {
                printf("%d+%d=%dn",a,b,c);
                sum++;
            }
        }
    }
    
    printf("一共可以拼出%d个不同的等式",sum);
    return 0;

}

最后

以上就是烂漫嚓茶为你收集整理的【啊哈！算法】之枚举的全部内容，希望文章能够帮你解决【啊哈！算法】之枚举所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。