《C语言枚举法》PPT课件.ppt

ACM程序设计 福州大学至诚学院 冯新 第三讲 枚举 枚举法概念 枚举法，常常称之为穷举法，是指从可能的集合中一一枚举各个元素，用题目给定的约束条件判定哪些是无用的，哪些是有用的。能使命题成立者，即为问题的解。 枚举算法基本思路 采用枚举算法解题的基本思路： （1）???确定枚举对象、枚举范围和判定条件； （2）??? 一一枚举可能的解，验证是否是问题的解 问题描述 求x2+y2=2000的正整数解 这道题明显是一道枚举题， 需要枚举出所有的可能的解。 解题方案1： 大家可以很自然的算出45*452000，于是我们的问题就被简化了。一个简单的代码就能解出题目。 for(i = 0; i 45; i++) for(j = 0; j 45; j++) if(i*i + j*j == 2000) ... 上面的方法可以优化吗？ 解题方案2 如果我们x = 44, y = 9。那么我们还需要枚举接下来的 y 吗？？？ 于是我们就有了第二种方案： #includestdio.h int main() { int i,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; } } return 0; } 还可以优化吗？ 解题方案3： 还可以进一步的优化吗？？？ 大家回去也可以好好思考下。 可以通过上面的例子看到，虽然都是枚举法，但是运行效率还是会有很大的差距的。 第一个方案 我们至少需要做 45*45次操作 而第三种方案明显比第一个方案少很多次操作。 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盏灯，排成一排。给定每盏灯的初始状态（开或关），你的任务是计算至少要切换多少 盏灯的状态（将开着的灯关掉，或将关掉的灯开起来），才能使得这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，1≤N≤10000，然后是N个整数，表示这N盏灯的初始状态，1表示开着的，O表示关着的。测试数据一直到文件尾。 OutputFor each testcase output a line consists of only the least times of switches. 对每个测试数据，输出占一行，表示至少需要切换状态的灯的数目。 Sample Input9 1 0 0 1 1 1 0 1 0 3 1 0 1 Sample Output30 解题方案1： 第一种枚举思路。N盏灯，每盏灯都有两种状态：1和0，则N盏灯共有2N种状态，从00 0…0到1 1 1…1。可以枚举这2^N种状态，每种状态都判断一下是否是开和关交替出现，如果是，则还要统计从初始状态转换到该状态需要切换的灯的数目。 但这种枚举策略势必要花费很多时间，因为N最大可以取到10000，而2^10000的数量级是10^3010。 我们的OJ时间限制为1s，即我们最多只能是10^7次操作。 （一般OJ 1S 能进行2*10^7次操作） 解题方案2： 第二种思路。要使得N盏灯开和关交替出现，实际上只有两种可能：奇数位置上的灯是开着的，或者偶数位置上的灯是开着的。只要分别计算从N盏灯的初始状态出发，切换到这两种状态所需要切换灯的数目，取较小者即可。例如样例输入中的第1个测试数据对应的初始状态如图所示，将这9盏灯切换到奇数位置上的灯是开着的，需要切换6盏灯；切换到偶数