C语言枚举法

ACM程序设计福州大学至诚学院冯新第三讲枚举枚举法概念枚举法，常常称之为穷举法，是指从可能的集合中一一枚举各个元素，用题目给定的约束条件判定哪些是无用的，哪些是有用的。能使命题成立者，即为问题的解。枚举算法基本思路采用枚举算法解题的基本思路：（1）确定枚举对象、枚举范围和判定条件；（2）一一枚举可能的解，验证是否是问题的解问题描述求x2+y2=2000的正整数解这道题明显是一道枚举题，需要枚举出所有的可能的解。解题方案1：大家可以很自然的算出45*452000，于是我们的问题就被简化了。一个简单的代码就能解出题目。for(i=0;i45;i++)for(j=0;j45;j++)if(i*i+j*j==2000)...上面的方法可以优化吗？解题方案2如果我们x=44,y=9。那么我们还需要枚举接下来的y吗？？？于是我们就有了第二种方案：#includestdio.hintmain(){inti,j;for(i=0;i45;i++){for(j=0;j45;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：#includestdio.hintmain(){inti,j;for(i=0;i45;i++){for(j=i;j45;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次操作而第三种方案明显比第一个方案少很多次操作。ZOJ1722switchThereareNlightsinaline.Giventhestates(on/off)ofthelights,yourtaskistodetermineatleasthowmanylightsshouldbeswitched(fromontooff,orfromofftoon),inordertomakethelightsonandoffalternatively.有N盏灯，排成一排。给定每盏灯的初始状态（开或关），你的任务是计算至少要切换多少盏灯的状态（将开着的灯关掉，或将关掉的灯开起来），才能使得这N盏灯开和关交替出现。InputOnelineforeachtestcase.TheintegerN(1=N=10000)comesfirstandisfollowedbyNintegersrepresentingthestatesofthelights(1foronand0foroff).Processtotheend-of-file.输入文件中包含多个测试数据，每个测试数据占一行。首先是一个整数N，1≤N≤10000，然后是N个整数，表示这N盏灯的初始状态，1表示开着的，O表示关着的。测试数据一直到文件尾。OutputForeachtestcaseoutputalineconsistsofonlytheleasttimesofswitches.对每个测试数据，输出占一行，表示至少需要切换状态的灯的数目。SampleInput91001110103101SampleOutput30解题方案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的正的自我数，以升序排列，并且每个数占一行。•SampleOutput•1•3•5•7•。。。--这里有很多自我数••9960•9971•9982•9993解题思路最简单的方法，把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(x1000000)break;temp/=10;}if(x=1000000)b[x]=1;}优化用枚举法解题的最大的缺点是运算量比较大，解题效率不高，如果枚举范围太大（一般以不超过两百万次为限），在时间上就难以承受。但枚举算法的思路简单，程序编写和调试方便，比赛时也容易想到，在竞赛中，时间是有限的，我们竞赛的最终目标就是求出问题解，因此，如果题目的规模不是很大，在规定的时间与空间限制内能够求出解，那么我们最好是采用枚举法，而不需太在意是否还有更快的算法，这样可以使你有更多的时间去解答其他难题。HDU1032枚举HDU1058枚举HDU2010枚举HDU1406枚举ThankYou~