C语言枚举法课件

ACM程序设计福州大学至诚学院冯新第三讲枚举枚举法概念枚举法，常常称之为穷举法，是指从可能的集合中一一枚举各个元素，用题目给定的约束条件判定哪些是无用的，哪些是有用的。能使命题成立者，即为问题的解。枚举算法基本思路采用枚举算法解题的基本思路：（1）

确定枚举对象、枚举范围和判定条件；（2）

一一枚举可能的解，验证是否是问题的解问题描述求x2+y2=2000的正整数解这道题明显是一道枚举题，需要枚举出所有的可能的解。解题方案1：大家可以很自然的算出45*45>2000，于是我们的问题就被简化了。一个简单的代码就能解出题目。for(i=0;i<45;i++)for(j=0;j<45;j++) if(i*i+j*j==2000) ...上面的方法可以优化吗？解题方案2如果我们x=44,y=9。那么我们还需要枚举接下来的y吗？？？于是我们就有了第二种方案：#include<stdio.h>intmain(){inti,j;for(i=0;i<45;i++){for(j=0;j<45;j++){ if(i*i+j*j==2000) printf("2000=%d*%d+%d+%d\n",i,i,j,j); if(i*i+j*j>=2000) break;}}return0;}还可以优化吗？解题方案3：#include<stdio.h>intmain(){inti,j;for(i=0;i<45;i++){for(j=i;j<45;j++){ if(i*i+j*j==2000) printf("2000=%d*%d+%d+%d\n",i,i,j,j); if(i*i+j*j>=2000) break;}}return0;}还可以进一步的优化吗？？？大家回去也可以好好思考下。可以通过上面的例子看到，虽然都是枚举法，但是运行效率还是会有很大的差距的。第一个方案我们至少需要做45*45次操作而第三种方案明显比第一个方案少很多次操作。ZOJ1722switchThereareNlightsinaline.Giventhestates(on/off)ofthelights,yourtaskistodetermineatleasthowmanylightsshouldbeswitched(fromontooff,orfromofftoon),inordertomakethelightsonandoffalternatively.有N盏灯，排成一排。给定每盏灯的初始状态（开或关），你的任务是计算至少要切换多少 盏灯的状态（将开着的灯关掉，或将关掉的灯开起来），才能使得这N盏灯开和关交替出现。Input

Onelineforeachtestcase.

TheintegerN(1<=N<=10000)comesfirstandisfollowedbyNintegersrepresentingthestatesofthelights("1"foronand"0"foroff).

Processtotheend-of-file.输入文件中包含多个测试数据，每个测试数据占一行。首先是一个整数N，1≤N≤10000，然后是N个整数，表示这N盏灯的初始状态，1表示开着的，O表示关着的。测试数据一直到文件尾。Output

Foreachtestcaseoutputalineconsistsofonlytheleasttimesofswitches.对每个测试数据，输出占一行，表示至少需要切换状态的灯的数目。SampleInput

91001110103101SampleOutput

3

0解题方案1：第一种枚举思路。N盏灯，每盏灯都有两种状态：1和0，则N盏灯共有2N种状态，从000…0到111…1。可以枚举这2^N种状态，每种状态都判断一下是否是开和关交替出现，如果是，则还要统计从初始状态转换到该状态需要切换的灯的数目。但这种枚举策略势必要花费很多时间，因为N最大可以取到10000，而2^10000的数量级是10^3010。我们的OJ时间限制为1s，即我们最多只能是10^7次操作。（一般OJ1S能进行2*10^7次操作）解题方案2：第二种思路。要使得N盏灯开和关交替出现，实际上只有两种可能：奇数位置上的灯是开着的，或者偶数位置上的灯是开着的。只要分别计算从N盏灯的初始状态出发，切换到这两种状态所需要切换灯的数目，取较小者即可。例如样例输入中的第1个测试数据对应的初始状态如图所示，将这9盏灯切换到奇数位置上的灯是开着的，需要切换6盏灯；切换到偶数位置上的灯是开着的，需要切换3盏灯；因此至少需要切换3盏灯。intres1=0,res2=0;for(i=1;i<=N;i++)//计算第1位为1，需要调整的数目{ if(i%2==1&&a[i]==0) //奇数位为0，需要调整 res1++; if(i%2==0&&a[i]==1) //偶数位为1，需要调整 res1++;}for(i=1;i<=N;i++)//计算第1位为0，需要调整的数目{ if(i%2==1&&a[i]==1)//奇数位为1，需要调整 res2++; if(i%2==0&&a[i]==0) //偶数位为0，需要调整 res2++;}res=min(res1,res2);//答案就是两个中较小的一个可以优化吗？？？大家发现没有？？res1+res2肯定会等于灯的总数n。（原因大家自己想想）那么我们代码可以优化成：intres1=0; //计算第1位为1，需要调整的数目for(i=1;i<=N;i++)

{ //奇数位为0，需要调整 if(i%2==1&&a[i]==0) res1++; //偶数位为1，需要调整 if(i%2==0&&a[i]==1) res1++;}intresult=min(res1,n-res1);省了一半的操作！！！PKU1316SelfNumbers1949年，印度数学家D．R．Kaprekar发现了一类叫做自我数(selfnumber)的数。对于任一正整数a，定义d(n)为n加上n的每一位数字得到的总和。 例如，d(75)=75+7+5=87。 取任意正整数n作为出发点，你可以建立一个无穷的正整数序列n,d(n),d(d(n))…… 例如，如果你从33开始，下一个数字就是33+3+3=39，再下一个是39+3+9=51，再下一个是51+5+1=57，…。如此便产生一个整数数列：33,39,51,57,69,84,96,111,114,120,123,129,141,…… 数字n被叫做整数d(n)的生成器。在如上的数列中，33是39的生成器，39是51的生成器，51是57的生成器，等等。 有些数字有多于一个生成器，如101有两个生成器，91和100。而一个没有生成器的数字则称作自我数(selfnumber)。100以内的自我数共有13个：1，3，5，7，9，20，31，42,53，64，75，86和97。输入描述：此题无输入。输出描述：输出所有小于或等于1000000的正的自我数，以升序排列，并且每个数占一行。SampleOutput1357。。。<--这里有很多自我数

9960997199829993解题思路最简单的方法，把1到1000000所有的数的产生的d(n),都算出来，所有没被算出来的数就是我们所需要的答案了。intb[1000001];for(i=1;i<=1000000;i++){ x=i,temp=i; while(temp!=0){ x+=temp%10; temp/=10; } if(x<=1000000) b[x]=1; }小技巧：很多编译器的主函数里面是不支持开大数组。我们可以通过定义全局变量来解决这个问题。可以优化吗？？？intb[1000001];for(i=1;i<=1000000;i++){ x=i,temp=i; while(temp!=0){ x+=temp%10;if(x>1000000)break; temp/=10; } if(x<=1000000) b[x]=1; }优化用枚举法解题的最大的缺点是运算量比较大，解题效率不高，如果枚举范围太大（一般以不超过两百万次为限），