算法设计之枚举法
枚举法，常常称之为穷举法，是指从可能的集合中一一枚举各个元素，用题目给定的约束条件判定哪些是无用的，哪些是有用的。能使命题成立者，即为问题的解。
采用枚举算法解题的基本思路：
（1）确定枚举对象、枚举范围和判定条件；
（2）一一枚举可能的解，验证是否是问题的解
下面我们就从枚举算法的的优化、枚举对象的选择以及判定条件的确定，这三个方面来探讨如何用枚举法解题。
例1：百钱买百鸡问题：有一个人有一百块钱，打算买一百只鸡。到市场一看，公鸡一只3元,母鸡一只5元,小鸡3只1元,试求用100元买100只鸡,各为多少才合适?
算法分析：此题很显然是用枚举法，我们以三种鸡的个数为枚举对象（分别设为cock, hen, chick）,以三种鸡的总数（cock + hen + chick）和买鸡用去的钱的总数(COCKPRICE*cock + HENPRICE*hen + chick/CHICKS)为判定条件，枚举各种鸡的个数。
注：我这里用了一个自定义函数Function()来解三种鸡的百钱买百鸡问题。函数提供了两个参数int money, int chooks，分别表示总钱数和总鸡数，除了把她们都赋值100外，还可以赋任意正整数值，解决x钱买y鸡问题。
#include<stdio.h>
const int COCKPRICE = 3; //一只公鸡的价格
const int HENPRICE = 5; //一只母鸡的价格
const int CHICKS = 3; //一元钱能买的小鸡数量
void Function(int money, int chooks);//计算并输出三种鸡的数量各是多少
int main()
{
int money = 100;//钱的总数
int chooks = 100;//鸡的总数
Function(money, chooks);//计算并输出三种鸡的数量各是多少
getchar();
return 0;
}
void Function(int money, int chooks) //计算并输出三种鸡的数量各是多少
{
int maxCock = money / COCKPRICE;
int maxHen = money / HENPRICE;
int maxChick = chooks;
int cock, hen, chick;
for (cock=0; cock<maxCock; ++cock)//枚举公鸡的可能数量
{
for (hen=0; hen<maxHen; hen++)//枚举母鸡的可能数量
{
for (chick=0; chick<maxChick; chick++)//枚举小鸡的可能数量
{
if (0 == chick%CHICKS && cock + hen + chick == chooks
&& COCKPRICE*cock + HENPRICE*hen + chick/CHICKS == money)//约束条件
{
printf("cock = %2d, hen = %2d, chick = %2d\n", cock, hen, chick);
}
}
}
}
}
上面的条件还有优化的空间，三种鸡的和是固定的，我们只要枚举二种鸡（cock, hen），第三种鸡就可以根据约束条件求得（chick = chooks - cock - hen），这样就缩小了枚举范围，请看下面的程序：
void Function(int money, int chooks)//计算并输出三种鸡的数量各是多少
{
int maxCock = money / COCKPRICE;
int maxHen = money / HENPRICE;
int cock, hen, chick;
for (cock=0; cock<maxCock; ++cock)//枚举公鸡的可能数量
{
for (hen=0; hen<maxHen; hen++)//枚举母鸡的可能数量
{
chick = chooks - cock - hen;//小鸡的数量根据约束条件求得
if (0 == chick%CHICKS
&& COCKPRICE*cock + HENPRICE*hen + chick/CHICKS == money)//约束条件
{
printf("cock = %2d, hen = %2d, chick = %2d\n", cock, hen, chick);
}
}
}
}
未经优化的程序时间复杂度为O(n3)；优化后的程序时间复杂度为O(n2)。通过简单的优化，程序的效率大大提高，实际上如果能从数学角度来考虑优化，会得到意想不到的结果。
根据题意我们可以得到方程组：
3X + 5Y + Z/3 = 100；
X + Y + Z = 100；
（X，Y，Z > 0, Z%3 == 0）；
观察方程的特点，消去一个未知数Z：
4X + 7Y = 100；
X + Y + Z = 100；
（X，Y，Z > 0, Z%3 == 0）；
根据整理以后的方程可以得到新的程序：
#include<stdio.h>
int main()
{
int x, y, z;
for (y=0; y<=14; y++)//根据约束条件（方程），枚举公鸡的可能数量
{
x = 100 - 7 * y;
if (x % 4)//由方程知：x = （100 - 7 * y）/ 4;x是4的倍数
continue;
else
x /= 4;
z = 100 - x - y;
if (z % 3)
continue;
else
printf("x = %d, y = %d, z = %d\n", x, y, z);
}
getchar();
return 0;
}
本程序虽然不如前面两个的通用性强，但不管多少钱多少鸡，我们都可以按照上面的方法对方程进行化简，从而得到对应的方程。程序时间复杂度从O(n3)到O(n2)，再到O(n)，从上面的对比可以看出，对于枚举算法，加强约束条件，缩小枚举的范围，是程序优化的主要考虑方向。
在枚举算法中，枚举对象的选择也是非常重要的，它直接影响着算法的时间复杂度，选择适当的枚举对象可以获得更高的效率。如下例：
例2. 五猴分桃：五只猴子一起摘了一堆桃子,因为太累了,它们商量决定,先睡一觉再分.一会其中的一只猴子来了,它见别的猴子没来,便将这堆桃子平均分成5份 ,结果多了一个,就将多的这个吃了,并拿走其中的一份.一会儿,第2只猴子来了,他不知道已经有一个同伴来过,还以为自己是第一个到的呢,于是将地上的桃子堆起来,再一次平均分成5份,发现也多了一个,同样吃了这1个,并拿走其中一份.接着来的第3,第4,第5只猴子都是这样做的.......,
根据上面的条件,问这5只猴子至少摘了多少个桃子?第5只猴子走后还剩下多少个桃子?
算法分析：我们设总的桃子数为S0，五子猴子分得的桃子数分别为S1，S2，S3，S4，S5，则有以下关系式：S0 = 5*S1 + 1； 4*S1 = 5*S2 + 1； 4*S2 = 5*S3 + 1；
4*S3 = 5*S4 + 1； 4*S4 = 5*S5 + 1；
我们可以枚举桃子总数S0，从5开始直到满足条件，此时S0的值就是最少的总桃子数。对应程序如下：
#include <stdio.h>
int main(void)
{
int s[6] = {0};
int i;
for(s[0]=5; ;s[0]++)
{
s[1] = s[0] - 1;
if (s[1]%5) // （s[0] – 1）要能被5整除
continue;
else
s[1] /= 5;
s[2] = 4 * s[1] - 1;
if (s[2]%5) // （4 * s[1] - 1）要能被5整除
continue;
else
s[2] /= 5;
s[3] = 4 * s[2] - 1;
if (s[3]%5)
continue;
else
s[3] /= 5;
s[4] = 4 * s[3] - 1;
if (s[4]%5)
continue;
else
s[4] /= 5;
s[5] = 4 * s[4] - 1;
if (s[5]%5)
continue;
else
s[5] /= 5;
break;
}
printf("摘了%d个桃子, 剩下%d个桃子\n", s[0], s[5]*4);
for (i=0; i<6; i++)
printf("%d ", s[i]);
getchar();
return 0;
}
程序输出：摘了3121个桃子, 剩下765个桃子。
根据程序结果我们知道循环体执行了3116次，同时我们可以知道第5个猴子分得255个桃子，所以如果枚举S5，则循环体只需执行了255次。对应程序如下：
#include <stdio.h>
int main(void)
{
int s[6] = {0};
int i;
for(s[5]=1; ;s[5]++)
{
s[4] = 5 * s[5] + 1;
if (s[4]%4)
continue;
else
s[4] /= 4;
s[3] = 5 * s[4] + 1;
if (s[3]%4)
continue;
else
s[3] /= 4;
s[2] = 5 * s[3] + 1;
if (s[2]%4)
continue;
else
s[2] /= 4;
s[1] = 5 * s[2] + 1;
if (s[1]%4)
continue;
else
s[1] /= 4;
s[0] = 5 * s[1] + 1;
break;
}
printf("摘了%d个桃子, 剩下%d个桃子\n", s[0], s[5]*4);
getchar();
return 0;
}
我们可以发现求S4，S3，S2，S1的表达式完全是一样的，所以我们可以用一个函数或者循环来表示，改进后的程序如下：
#include <stdio.h>
int main(void)
{
int s[6] = {0};
int i;
for(s[5]=1; ;s[5]++)
{
for (i=4; i>0; i--)
{
s[i] = 5 * s[i+1] + 1;
if (s[i]%4)
break;
else
s[i] /= 4;
}
if (i == 0)
{
s[0] = 5 * s[1] + 1;
break;
}
}
printf("摘了%d个桃子, 剩下%d个桃子\n", s[0], s[5]*4);
getchar();
return 0;
}
评论