《《C语言枚举法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《C语言枚举法》PPT课件.ppt（32页珍藏版）》请在三一办公上搜索。
1、ACM程序设计,福州大学至诚学院 冯新,第三讲,枚举,枚举法概念,枚举法，常常称之为穷举法，是指从可能的集合中一一枚举各个元素，用题目给定的约束条件判定哪些是无用的，哪些是有用的。能使命题成立者，即为问题的解。,枚举算法基本思路,采用枚举算法解题的基本思路：（1）确定枚举对象、枚举范围和判定条件；（2）一一枚举可能的解，验证是否是问题的解,问题描述,求x2+y2=2000的正整数解这道题明显是一道枚举题，需要枚举出所有的可能的解。,解题方案1：,大家可以很自然的算出45*452000，于是我们的问题就被简化了。一个简单的代码就能解出题目。for(i=0;i 45;i+)for(j=0;j 45
2、;j+)if(i*i+j*j=2000).,上面的方法可以优化吗？,解题方案2,如果我们x=44,y=9。那么我们还需要枚举接下来的 y 吗？于是我们就有了第二种方案：,#includeint main()int i,j;for(i=0;i=2000)break;return 0;,还可以优化吗？,解题方案3：,#includeint main()int i,j;for(i=0;i=2000)break;return 0;,还可以进一步的优化吗？大家回去也可以好好思考下。,可以通过上面的例子看到，虽然都是枚举法，但是运行效率还是会有很大的差距的。第一个方案 我们至少需要做 45*45次操作而第
3、三种方案明显比第一个方案少很多次操作。,ZOJ 1722 switch,There are N lights in a line.Given the states(on/off)of the lights,your task is to determine at least how many lights should be switched(from on to off,or from off to on),in order to make the lights on and off alternatively.有N盏灯，排成一排。给定每盏灯的初始状态（开或关），你的任务是计算至少要切换多少
4、盏灯的状态（将开着的灯关掉，或将关掉的灯开起来），才能使得这N盏灯开和关交替出现。,InputOne line for each testcase.The integer N(1=N=10000)comes first and is followed by N integers representing the states of the lights(1 for on and 0 for off).Process to the end-of-file.输入文件中包含多个测试数据，每个测试数据占一行。首先是一个整数N，1N10000，然后是N个整数，表示这N盏灯的初始状态，1表示开着的，O表示
5、关着的。测试数据一直到文件尾。,OutputFor each testcase output a line consists of only the least times of switches.对每个测试数据，输出占一行，表示至少需要切换状态的灯的数目。Sample Input9 1 0 0 1 1 1 0 1 03 1 0 1Sample Output30,解题方案1：,第一种枚举思路。N盏灯，每盏灯都有两种状态：1和0，则N盏灯共有2N种状态，从00 00到1 1 11。可以枚举这2N种状态，每种状态都判断一下是否是开和关交替出现，如果是，则还要统计从初始状态转换到该状态需要切换的灯的
6、数目。,但这种枚举策略势必要花费很多时间，因为N最大可以取到10000，而210000的数量级是103010。我们的OJ时间限制为1s，即我们最多只能是107次操作。（一般OJ 1S 能进行2*107次操作）,解题方案2：,第二种思路。要使得N盏灯开和关交替出现，实际上只有两种可能：奇数位置上的灯是开着的，或者偶数位置上的灯是开着的。只要分别计算从N盏灯的初始状态出发，切换到这两种状态所需要切换灯的数目，取较小者即可。例如样例输入中的第1个测试数据对应的初始状态如图所示，将这9盏灯切换到奇数位置上的灯是开着的，需要切换6盏灯；切换到偶数位置上的灯是开着的，需要切换3盏灯；因此至少需要切换3盏灯
7、。,int res1=0,res2=0;for(i=1;i=N;i+)/计算第1位为1，需要调整的数目if(i%2=1/答案就是两个中较小的一个,可以优化吗？,大家发现没有？res1+res2 肯定会等于灯的总数 n。（原因大家自己想想）那么我们代码可以优化成：,int res1=0;/计算第1位为1，需要调整的数目for(i=1;i=N;i+)/奇数位为0，需要调整if(i%2=1 省了一半的操作！,PKU 1316 Self Numbers,1949年，印度数学家DRKaprekar发现了一类叫做自我数(self number)的数。对于任一正整数a，定义d(n)为 n 加上 n 的每一位
8、数字得到的总和。例如，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。而一个没有生成器的数字则称作自我数(self nu
9、mber)。100以内的自我数共有13个：1，3，5，7，9，20，31，42,53，64，75，86和97。,输入描述：此题无输入。输出描述：输出所有小于或等于1000000的正的自我数，以升序排列，并且每个数占一行。Sample Output1 357。-这里有很多自我数 99609971 9982 9993,解题思路,最简单的方法，把1到1000000所有的数的产生的d(n),都算出来，所有没被算出来的数就是我们所需要的答案了。,int b1000001;for(i=1;i=1000000;i+)x=i,temp=i;while(temp!=0)x+=temp%10;temp/=10;i
10、f(x=1000000)bx=1;,小技巧：很多编译器的主函数里面是不支持开大数组。我们可以通过定义全局变量来解决这个问题。,可以优化吗？,int b1000001;for(i=1;i 1000000)break;temp/=10;if(x=1000000)bx=1;,优化,用枚举法解题的最大的缺点是运算量比较大，解题效率不高，如果枚举范围太大（一般以不超过两百万次为限），在时间上就难以承受。但枚举算法的思路简单，程序编写和调试方便，比赛时也容易想到，在竞赛中，时间是有限的，我们竞赛的最终目标就是求出问题解，因此，如果题目的规模不是很大，在规定的时间与空间限制内能够求出解，那么我们最好是采用枚举法，而不需太在意是否还有更快的算法，这样可以使你有更多的时间去解答其他难题。,HDU 1032 枚举HDU 1058 枚举HDU 2010 枚举HDU 1406 枚举,Thank You,
