枚举

印度阿三17 2020-02-19

展开全文

什么是枚举，百科上的解释：在数学和计算机科学理论中，一个集的枚举是列出某些有穷序列集的所有成员的程序，或者是一种特定类型对象的计数。这两种类型经常（但不总是）重叠。是一个被命名的整型常数的集合，枚举在日常生活中很常见，例如表示星期的SUNDAY、MONDAY、TUESDAY、WEDNESDAY、THURSDAY、FRIDAY、SATURDAY就是一个枚举。

简单的理解，枚举就是逐个尝试答案的一种问题求解策略。

平时我们解决问题有很好的方法，比如数学方法，用数学方法解决问题我们往往是找规律，推出公式。如果用公式直接能得到答案，那就基本上没有什么时间复杂度，所以数学方法是很高明的。

但是现实生活中有很多是没有规律可循的，我们只好用笨办法，就一个一个的试，去看看哪个是真实的答案。

例如：求小于N的最大素数。这种问题就找不到一个数学公式，使根据N就可以计算出这个素数。所以我们得判断N-1是不是素数？N-2是不是素数？……这样依次下去，判断N-i是不是素数。这就是所谓的枚举的思想。

下面例出几个问题。题目皆来自网络。

例一

公鸡每只五元，母鸡每只三元，小鸡三只一元，用一百元买一百只鸡，问公鸡，母鸡，小鸡各多少只？

利用枚举法解决该问题，以三种鸡的个数为枚举对象,分别设x,y,z，用三种鸡的总数和买鸡钱的总数作为判定条件，穷举各种鸡的个数。

x   y   z = 100
5*x   3*y   z/3 = 100

分析1

如果用解方程的方式解这道题需要进行多次猜解，计算机的一个优势就是计算速度特别暴力。因此我们用穷举法的方式来解题，需要 101^3 次猜解，但对于计算机来说，完全没问题。

程序1：

#include <stdio.h>

int main()
{
    int x, y, z;
    
    for( x=0; x <= 100; x   )
        for( y=0; y <= 100; y   )
            for( z=0; z <= 100; z   )
            {
                if( 5*x 3*y z/3==100 && z%3==0 && x y z==100 )
                {
                    printf("公鸡 - 只，母鸡 - 只，小鸡 - 只\n", x, y, z);
                }
            }

    return 0;
}

运行结果：

公鸡  0 只，母鸡 25 只，小鸡 75 只
公鸡  4 只，母鸡 18 只，小鸡 78 只
公鸡  8 只，母鸡 11 只，小鸡 81 只
公鸡 12 只，母鸡  4 只，小鸡 84 只

回看上面这个算法，我们使用了3层循环，时间复杂度为：o(n^3)，在实际生活中，这种复杂度的算法我们根本不会用。那么我们有没有可能继续优化这个算法呢？

分析2

我试着分析了初始式子，两个式子，三个未知数，我们应该可以确定每个未知数的定义域。于是我得到：

x <= 20;
y <= 33;
z <=99;

程序2：

#include <stdio.h>

int main()
{
    int x, y, z;
    
    for( x=0; x <= 20; x   )
        for( y=0; y <= 33; y   )
            for( z=0; z <= 99; z   )
            {
                if( 5*x 3*y z/3==100 && z%3==0 && x y z==100 )
                {
                    printf("公鸡 - 只，母鸡 - 只，小鸡 - 只\n", x, y, z);
                }
            }

    return 0;
}

这样虽然还是没有改变时间复杂度为：o(n^3)的情况，但是我们的运算次数从101^3缩小到了20*33*99次，大概减少了十五六倍的运算。

分析3

然后我再试着是否能用x,y来表示z以减少循环次数。

z = 100 - x - y;

程序3：

#include <stdio.h>

int main()
{
    int x, y, z;
    
    for( x=0; x <= 20; x   )
        for( y=0; y <= 33; y   )
        {
            z = 100 - x - y;
            if( 5*x 3*y z/3==100 && z%3==0)
            {
                printf("公鸡 - 只，母鸡 - 只，小鸡 - 只\n", x, y, z);
            }
        }
    return 0;
}

这次只用了两次循环，时间复杂度为：o(n^2)，直接少了个能级。而且该题中直接从上次的21*34*100变成了21*34，次数直接减少100倍。

分析4

初高中做题时，一般三元一次方程组，我们会选择消元来解题，那么这题我们能不能直接消去z呢。

x   y   z = 100   ①
5x   3y   z/3 = 100   ②

3 * ①，得： 
15x   9y   z = 300   ③
联立②③，得：
（15x   9y   z = 300） - （x   y   z = 100）推出 14x   8y = 200
解得：y = 25 - (7/4)x  ④

然后我们将④带入原式

y = 25 - (7/4)x
为了消除分母，我们设:x = 4k，则：
x = 4k;
y = 25 - 7k;
z= 100 - x - y = 75   3k;
根据分析②：x <= 20 ,y <= 33,z <=99,且三者皆>=0
得：k=1,2,3

程序4：

#include <stdio.h>

int main()
{
    int x, y, z,k;
    
    for( k=0; k <= 3; k   )
    {
        x = 4 * k;
        y = 25 - 7 * k;
        z = 75   3 * k;
        printf("公鸡 - 只，母鸡 - 只，小鸡 - 只\n", x, y, z);
    }
    return 0;
}

这样，我们一个循环就解决了这个问题。时间复杂度为：o(n)，该问题只需四次运算，同之前的101^2,21*34*100以及21*34，简单了无数倍。

所以我们在不得已使用枚举法时，也要尽量的减少程序的运行次数以提高效率。