第5章  枚举法
　　
　　
　　
　　
5.1  算法设计思想
　　枚举法（也称穷举法）是一种蛮力策略，是一种简单而直接地解决问题的方法，也是一种应用非常普遍的方法。它根据问题中的给定条件将所有可能的情况一一列举出来，从中找出满足问题条件的解。此方法通常需要用多重循环来实现，测试每个变量的每个值是否满足给定的条件，若满足条件，就找到了问题的一个解。但是，用枚举法设计的算法其时间复杂度通常都是指数阶的。
　　例如，在“数据结构”课程中学习的选择排序、冒泡排序、插入排序、顺序查找和二叉树的遍历等，都是枚举法的具体应用。
　　用枚举法解决问题时，通常可以从两个方面进行算法设计。
　　（1）找出枚举范围：分析问题涉及的各种情况。
　　（2）找出约束条件：分析问题的解需要满足的条件，并用表达式表示出来。
5.2  典 型 例 题
5.2.1  百鸡问题
　　（题目来源：JLOJ2349）
1. 问题描述
　　【Description】
　　公元前5世纪，我国数学家张丘建在《算经》一书中提出了有趣的百鸡问题：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？ 
　　【Input】
　　无。
　　【Output】
　　给出所有的解，每组解占一行。
　　解的顺序：按“字典序”排列，即公鸡数少的在前；公鸡数相同，母鸡数少的在前。
　　格式控制如下：
　　
cock=%d,hen=%d,chicken=%d\n
　　
　　【Sample Input】
　　无。
　　【Sample Output】
　　cock=0, hen=25, chicken=75
　　cock=4, hen=18, chicken=78
　　cock=8, hen=11, chicken=81
　　cock=12, hen=4, chicken=84
2. 问题分析
　　这是一道典型的枚举类数学问题，分析如下：
　　（1）设鸡翁、鸡母、鸡雏分别为x、y、z只，依题意可以列出方程组：
　　                            x+y+z=100
5x+3y+z/3=100
　　这里有3个未知数，只有两个方程，可能有多组解。根据题意，只求解出正整数解即可。
　　（2）应用枚举法设计算法，需要使用三重循环。根据可能性作分析，不难确定可能的取值范围为：
　　鸡翁x：0～19，不可能大于等于20，否则不能买到100只鸡。
　　鸡母y：0～32，不可能大于等于33，否则不能买到100只鸡。
　　鸡雏z：3～98，且应是3的倍数。
　　（3）解的判断条件：如果x、y、z 的值同时满足两个方程，则是问题的一组解。
3. 参考程序
　　
#include <stdio.h>
#include <stdlib.h>
int main()
{
    int i,j,k;
    for(i=0;i<20;i++)
         for(j=0;j<34;j++)
         for(k=0;k<300;k++)
         if((15*i+9*j+k)==300&&(i+j+k)==100)
                 printf("cock=%d,hen=%d,chicken=%d\n",i,j,k);
    return 0;
}
　　
5.2.2  水仙花数
　　（题目来源：JLOJ2350）
1. 问题描述
　　【Description】
　　所谓“水仙花数”，是指一个3位数，其各位数字的立方和等于该数本身。例如，153是一个水仙花数，因为153=13+53+33。求出所有的水仙花数。 
　　【Input】
　　无。
　　【Output】
　　所有的水仙花数，从小数开始，每行一个。
2. 问题分析
　　设s为任意一个3位数，其个位、十位、百位数字分别为a、b、c，可知a、b的取值范围为0～9；c的取值范围为1～9。依照上述题意可列出表达式：s=100*c+10*b+a，如果满足s=a*a*a+b*b*b+c*c*c，那么这个数就是水仙花数。
3. 参考程序
　　
#include"stdio.h"  
#include"math.h"  
main()  
{ 
      int x=100,a,b,c;  
      while(x>=100&&x<1000) 
      {
            a=0.01*x;b=10*(0.01*x-a);c=x-100*a-10*b;  
            if(x==(pow(a,3)+pow(b,3)+pow(c,3))) 
                  printf("%d\n",x);x++;
      }  
}
　　
5.2.3  完数
　　（题目来源：JLOJ2351）
1. 问题描述
　　【Description】
　　一个数如果恰好等于它的因子之和，则这个数就称为“完数”。例如，6的因子为1、2、3，而6=1+2+3，因此6是“完数”。编写程序，找出N之内的所有完数，并打印出它们的所有因子。
　　【Input】
　　输入正整数n（n<1000）。
　　【Output】
　　 its factors are   
　　【Sample Input】
　　100
　　【Sample Output】
　　6 its factors are 1 2 3 
　　28 its factors are 1 2 4 7 14
2. 问题分析
　　（1）设i为n以内的任意一个整数，令j是小于i的整数，如果j是i的因子，就累加j，所有因子之和用sum表示，如果 i=sum，那么i就是完数，否则不是。
　　（2）应用枚举法设计算法，需要双重循环。根据可能性进行分析，不难确定可能的取值范围为：
　　i：2～n，每个数都需要被判断是否为完数。
　　j：1～i/2，i的因子不可能大于 i/2。
3. 参考程序
　　
#include <stdio.h>
int main()
{
    int n;
    int i,j;
    int sum = 0;
    scanf("%d",&n);
    for(i = 2; i <= n; i++)
    {
        sum = 0;
        for(j = 1; j < i; j++)
        {
            if(i%j == 0)
                sum += j;
        }
        if(sum == i)
        {
            printf("%d its factors are ",i);
            for(j = 1; j < i; j++)
                if(i%j == 0)
                    printf("%d ",j);
            printf("\n");
        }
    }
    return 0;
}
　　
5.2.4  可逆素数
　　（题目来源：JLOJ2352）
1. 问题描述
　　【Description】
　　可逆素数是指将一个素数的各位数字顺序倒过来以后构成的数，也是素数。求出m～n范围内所有的可逆素数。
　　【Input】
　　输入两个正整数m和n（100<m<n<1000）。
　　【Output】
　　例如素数107，其可逆素数701也是素数，只能输出两者中最小的，且最后按升序       输出。
2. 问题分析
　　先求出m～n范围内的素数i，然后把这个素数倒转过来，例如107倒转变成701，如果倒转之后的数也是素数，那么就输出这个数和倒转之后的数。
3. 参考程序
　　
#include <stdio.h>
#include <math.h>
int isPrime(int n)
{
    double j;
    int i;
    j=sqrt(n);
    for(i=2; i<=j; i++)
        if(n%i==0)         /* 判断n是否为素数 */
            return 0;
    return 1;
}
int turn(int n)
{
    int a,b,c;
    a=n/100;
    b=n%100/10;
    c=n%10;
    return c*100+b*10+a;
}
int main()
{
    int i,m,n;
    scanf ("%d%d", &m, &n);
    for (i=m; i<=n; i++)
    {
        if ((i/100)%2==0)
        {
            i=i+100;
            continue;             /*只判断百位为奇数的数*/
        }
        if (isPrime(i)==0)      /* 判断是素数后,继续判断是否为可逆素数 */
            continue;             /* 否则进入下一循环 */
        else if(isPrime(turn(i))&&i<turn(i))
            printf("%d\n",i);
    }
    return 0;
}
　　
5.2.5  串匹配问题
　　（题目来源：JLOJ2353）
1. 问题描述
　　【Description】
　　给定一个字符串（主串），在该字符串中查找并定位任意给定字符串（模式串）。查看给定的字符串是否包含在该字符串中。若匹配成功，则返回模式串第一个字符在主串中的位置，否则返回–1。
　　【Input】
　　第一行为字符串a（主串），第二行为字符串b（模式串）。串a、b的长度都小于5000。
　　【Output】
　　返回b串在a串第一次匹配成功的位置，若匹配不成功，则返回–1。
　　【Sample Input】
　　asdfgh
　　dfg
　　【Sample Output】
　　3
2. 问题分析
　　模式串中的每个字符依次和主串中的一个连续的字符序列相等，则称为匹配成功，反之称为匹配不成功。从主串a的第一个字符开始和模式串b的第一个字符进行比较，若相等，则继续比较两者的后续字符；若不相等，则从主串a的第二个字符开始和模式串b的第一个字符进行比较，重复上述过程，若b中的字符全部比较完毕，则说明本趟匹配成功；若主串a中剩下的字符不足够匹配整个模式串b，则匹配失败。
　　在进行字符串匹配过程中，当某个位置匹配不成功的时候，应该从模式串的下一个位置开始新的比较。将这个位置的值存放在next数组中，其中next数组中的元素满足这个条件：next[j]=k，表示的是当模式串中的第j+1个字符发生匹配不成功的情况时，应该从模式串的第k+1个字符开始新的匹配。如果已经得到了模式串的next数组，匹配可如下进行：令指针i指向主串s，指针j指向模式串t中当前正在比较的位置。令指针i和指针j指向的字符比较，如果两字符相等，则顺次比较后面的字符；如果两字符不相等，则指针i不动，回溯指针j，令其指向模式串t的第pos个字符，使t[0～pos–1] = s[i–pos～i–1]。然后指针i和指针j指向的字符按此种方法继续比较，直到j = m–1，即在主串s中找到模式串t为止。next函数的编写为整个算法的核心，设计出快速正确的next函数也是KMP算法的重中之重。
　　利用递推思想来设计next函数：
　　（1）令next[0] = –1（当next[j] = –1时，证明字符串匹配要从模式串的第0个字符开始，且第0个字符并不和主串的第i个字符相等，i指针向前移动）。
　　（2）假设next[j] = k，说明t[0～k–1] = t[j–k～j–1]。
　　（3）现在来求next[j+1]。
　　① 当t[j] = t[k]时，说明t[0～k] = t[j–k～j]，这时分为两种情况讨论：当t[j+1] != t[k+1]时，显然 next[j+1] = k+1；当t[j+1] = t[k+1]时，说明t[k+1]和t[j+1]一样，都不和主串的字符相匹配，因此m = k+1，j=next[m]，直到t[m] != t[j+1]，next[j+1] = m。
　　② 当t[j] != t[k]时，必须在t[0～k–1]中找到next[j+1]，这时k = next[k]，直到t[j] =            t[k]，next[j+1] = next[k]；这样，我们就通过递推思想求得了匹配串t的next函数。
3. 参考程序
　　
#include <stdio.h>
#include <string.h>
void getnext(char *t,int *next,int tlength)
/* 求模式串t的next函数值并存入数组next */
{
   int i=1,j=0;
   next[1]=0;
   while(i<tlength)
   {
      if(j==0||t[i]==t[j])
      {
         ++i;
         ++j;
         next[i]=j;
      }
      else
         j=next[j];
   }
}
int indexkmp(char *s，char *t,int pos,int tlength,int slength,int *next)
    /* 利用模式串t的next函数求t在主串s中第pos个字符之后的位置 */
{
   int i=pos,j=1;
   while(i<=slength&&j<=tlength)
   {
      if(j==0||s[i]==t[j])  	/* 继续比较后继字符 */
      {
         ++i;
         ++j;
      }
      else                    	/* 模式串向后移动 */
         j=next[j];
   }
   if(j>tlength)            	/* 匹配成功，返回匹配起始位置 */
      return i-tlength;
   else
      return -1;
}
int main()
{
   int locate,tlength,slength,next[256];
   char s[256],t[256];
   slength=strlen(gets(s+1));
   tlength=strlen(gets(t+1));
   getnext(t,next,tlength);
   locate=indexkmp(s,t,0,tlength,slength,next);
   printf("%d\n",locate);
   return 0;
}
　　
5.2.6  最小公倍数问题
　　（题目来源：JLOJ2354）
1. 问题描述
　　【Description】
　　输入3个正整数，求这3个数的最小公倍数。
　　【Input】
　　输入数据只有一行，包括3个不大于1000的正整数。
　　【Output】
　　输出数据也只有一行，给出这3个数的最小公倍数。
　　【Sample Input】
　　4 5 6
　　【Sample Output】
　　60
2. 问题分析
　　输入3个数：x1、x2、x3，如果一个数i能同时整除这3个数，则这个数i就是它们的公倍数。找出满足条件的最小的数i，它就是这3个数的最小公倍数。根据最小公倍数的定义，令i从x1、x2、x3中最大的数开始依次递增，则x1、x2、x3的第一个公倍数i就是我们要求的最小公倍数。
　　利用最小公倍数的定义，逐步枚举尝试问题的解。算法虽然简单易懂，但效率太低。下面用短除法的思想进行算法设计。
　　该方法的主要思想是：找到3个数的所有公约数（因子），然后相乘便是它们的最小公倍数。3个数的因子有3种情况：3个数共有的、2个数共有的、1个数独有的。计算时按顺序优先处理前面的情况。无论哪种情况，一个因子都只能累乘一次。
3. 参考程序
　　
#include <stdio.h>
int max(int x,int y,int z)
{
    if(x>y&&x>z) return(x);
    else if(y>x&&y>z) return(y);
    else return(z);
}
int main()
{
    int x1,x2,x3,t=1,i,flag,x0;
    scanf("%d%d%d",&x1,&x2,&x3);
    x0=max(x1,x2,x3);
    for(i=2; i<=x0; i++)
    {
        flag=1;
        while(flag==1)
        {
            flag=0;        	/*默认没有公约数*/
            if(x1%i==0)    	/*判断i是否为x1的因子*/
            {
                x1=x1/i;
                flag=1;
            }
            if(x2%i==0)
            {
                x2=x2/i;
                flag=1;
            }
            if(x3%i==0)
            {
                x3=x3/i;
                flag=1;
            }
            if(flag==1)
                t*=i;     		/*t为所有因子的乘积，最后得到最小公倍数*/
        }
        x0=max(x1,x2,x3);
    }
    printf("%d\n"，t);
    return 0;
}
　　
5.2.7  狱吏问题
　　（题目来源：JLOJ2355）
1. 问题描述
　　【Description】
　　某国王大赦囚犯，让一狱吏n次通过一排锁着的n间牢房，每通过一次，按规则转动n间牢房的某些门锁，每转动一次，原来锁着的门被打开，原来打开的门被锁上，通过n次后，门开着的，牢房中的犯人被放出，否则犯人不得释放。
　　转动门锁的规则：第一次通过牢房，从第1间牢房开始要转动每把门锁，即把全部的锁打开；第2次通过牢房时，从第2间牢房开始转动，每隔一间转动一次……第k次通过牢房时，从第k间牢房开始转动，每隔k–1间转动一次；问：通过n次后，哪些牢房的锁是打开的？
　　【Input】
　　输入一个整数n（n<1000000），表示牢房的间数，牢房编号从1开始。
　　【Output】
　　输出锁是开着的牢房的编号。
　　【Sample Input】
　　15
　　【Sample Output】
　　1 4 9
2. 问题分析
　　转动门锁的规则：
　　第一次转动的是编号为1的倍数的牢房，第二次转动的是编号为2的倍数的牢房，第三次转动的是编号为3的倍数的牢房……则狱吏问题是一个关于因子个数的问题。
　　对于整数n的因子个数s，有的为奇数，有的为偶数。由于牢房的门开始是关着的，这样编号为i的牢房所含1～i之间不重复因子个数为奇数时，牢房最后是打开的；反之，牢房最后是关闭的。
　　因此只需找到因子个数为奇数的牢房号，也就是s除以2余数为1时，牢房的门是开着的。
　　程序运行的时间长短与枚举的次数成正比，为了提高程序运行的速度，需要尽可能降低循环嵌套的层数、减少选择判断的次数。狱吏问题其实就是一个数学问题，当且仅当n为完全平方数时，n的因子个数为奇数，只找出小于n的平方数即可。
3. 参考程序
　　
#include <stdio.h>