《C语言枚举法》ppt课件

1、ACM程序设计程序设计福州大学至诚学院 冯新第三讲第三讲枚举枚举枚举法概念n枚举法，经常称之为穷举法，是指从能够的集合中一一枚举各个元素，用标题给定的约束条件断定哪些是无用的，哪些是有用的。能使命题成立者，即为问题的解。枚举算法根本思绪n采用枚举算法解题的根本思绪：n1 确定枚举对象、枚举范围和断定条件；n2 一一枚举能够的解，验证能否是问题的解问题描画求x2+y2=2000的正整数解这道题明显是一道枚举题，需求枚举出一切的能够的解。解题方案1：大家可以很自然的算出45*452000，于是我们的问题就被简化了。一个简单的代码就能解出标题。for(i = 0; i 45; i+) for(j =

2、 0; j 45; j+) if(i*i + j*j = 2000) .上面的方法可以优化吗？上面的方法可以优化吗？解题方案2n假设我们x = 44, y = 9。那么我们还需求枚举接下来的 y 吗？n于是我们就有了第二种方案：#includeint main() int i,j; for(i = 0; i 45; i+) for(j = 0; j = 2000) break; return 0;还可以优化吗？还可以优化吗？解题方案3：#includeint main() int i,j; for(i = 0; i 45; i+) for(j = i; j = 2000) break; ret

3、urn 0;n还可以进一步的优化吗？n大家回去也可以好好思索下。n可以经过上面的例子看到，虽然都是枚举法，但是运转效率还是会有很大的差距的。n第一个方案 我们至少需求做 45*45次操作n而第三种方案明显比第一个方案少很多次操作。ZOJ 1722 switchnThere 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

4、 to on), in order to make the lights on and off alternatively. n 有N盏灯，排成一排。给定每盏灯的初始形状开或关，他的义务是计算至少要切换多少n盏灯的形状将开着的灯关掉，或将关掉的灯开起来，才干使得这N盏灯开和关交替出现。nInputOne 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

5、0 for off).Process to the end-of-file.n 输入文件中包含多个测试数据，每个测试数输入文件中包含多个测试数据，每个测试数据占一行。首先是一个整数据占一行。首先是一个整数N，1N10000，然后是，然后是N个整数，表示这个整数，表示这N盏灯的初始形状，盏灯的初始形状，1表示开着的，表示开着的，O表示关表示关着的。测试数据不断到文件尾。着的。测试数据不断到文件尾。nOutputFor each testcase output a line consists of only the least times of switches.n对每个测试数据，输出占一行，表示

6、至少需求切换形对每个测试数据，输出占一行，表示至少需求切换形状的灯的数目。状的灯的数目。nSample Input9 1 0 0 1 1 1 0 1 0n3 1 0 1nSample Output30解题方案1：n 第一种枚举思绪。N盏灯，每盏灯都有两种形状：1和0，那么N盏灯共有2N种形状，从00 00到1 1 11。可以枚举这2N种形状，每种形状都判别一下能否是开和关交替出现，假设是，那么还要统计从初始形状转换到该形状需求切换的灯的数目。n但这种枚举战略势必要破费很多时间，由于N最大可以取到10000，而210000的数量级是103010。n我们的OJ时间限制为1s，即我们最多只能是107

7、次操作。n普通OJ 1S 能进展2*107次操作解题方案2：n 第二种思绪。要使得N盏灯开和关交替出现，实践上只需两种能够：奇数位置上的灯是开着的，或者偶数位置上的灯是开着的。只需分别计算从N盏灯的初始形状出发，切换到这两种形状所需求切换灯的数目，取较小者即可。例如样例输入中的第1个测试数据对应的初始形状如下图，将这9盏灯切换到奇数位置上的灯是开着的，需求切换6盏灯；切换到偶数位置上的灯是开着的，需求切换3盏灯；因此至少需求切换3盏灯。int res1 = 0, res2 = 0;for(i = 1; i = N; i+) /计算第1位为1，需求调整的数目if(i%2 = 1 & ai

8、 = 0) /奇数位为0，需求调整res1+;if(i%2 = 0 & ai = 1) /偶数位为1，需求调整res1+;for(i = 1; i = N; i+) /计算第1位为0，需求调整的数目if(i%2 = 1 & ai = 1) /奇数位为1，需求调整res2+;if(i%2 = 0 & ai = 0) /偶数位为0，需求调整res2+;res = min(res1, res2); /答案就是两个中较小的一个可以优化吗？可以优化吗？n大家发现没有？nres1 + res2 一定会等于灯的总数 n。缘由大家本人想想n那么我们代码可以优化成： int res1 =

9、 0;/计算第1位为1，需求调整的数目 for(i = 1; i = N; i+) /奇数位为0，需求调整if(i%2 = 1 & ai = 0)res1+;/偶数位为1，需求调整if(i%2 = 0 & ai = 1) res1+; int result = min(res1, n-res1); 省了一半的操作！PKU 1316 Self Numbers 1949年，印度数学家DRKaprekar发现了一类叫做自我数(self number)的数。对于任一正整数a，定义d(n)为 n 加上 n 的每一位数字得到的总和。例如，d(75) =75+7+5=87。取恣意正整数n作为

10、出发点，他可以建立一个无穷的正整数序列 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 number)。100以内的自我数共有13

11、个：1，3，5，7，9，20，31，42, 53，64，75，86和97。 输入描画：输入描画： 此题无输入。此题无输入。 输出描画：输出描画： 输出一切小于或等于输出一切小于或等于1000000的正的自我数，以升序陈的正的自我数，以升序陈列，并且每个数占一行。列，并且每个数占一行。Sample Output1 357。 - 这里有很多自我数这里有很多自我数 99609971 9982 9993 解题思绪n最简单的方法，把1到1000000一切的数的产生的d(n),都算出来，一切没被算出来的数就是我们所需求的答案了。int b1000001;for(i = 1; i = 1000000; i+)x = i, temp = i;while(temp != 0) x += temp%10;temp /= 10;if(x = 1000000)bx =1;小技巧：很多编译器的主函数里面是不支持开大数组。我们可以经过定义全局变量来处理这个问题。可以优化吗？可以优化吗？int b1000001;for(i = 1; i 1000000) break;temp /= 10;if(x = 1000000)bx =1;优化优化n用枚举法解题的最大的缺陷是运算量比较大，解题效率不高，假设枚举范围太大普通以不超越两百万次为限，在时间上就难以接受。但枚举算法的思绪简单，程序编写和调试方便