《C语言枚举法》PPT课件

《《C语言枚举法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ACM程序设计福州大学至诚学院冯新第三讲枚举枚举法概念枚举法，常常称之为穷举法，是指从可能的集合中一一枚举各个元素，用题目给定的约束条件判定哪些是无用的，哪些是有用的。能使命题成立者，即为问题的解。枚举算法基本思路采用枚举算法解题的基本思路：（1）   确定枚举对象、枚举范围和判定条件；（2）   一一枚举可能的解，验证是否是问题的解问题描述求x2+y2=2000的正整数解这道题明显是一道枚举题，需要枚举出所有的可能的解。解题方案1：大家可以很自然的算出45*45>2000，于是我们的问题就被简化了。一个简单的

2、代码就能解出题目。for(i=0;i<45;i++)for(j=0;j<45;j++)if(i*i+j*j==2000)...上面的方法可以优化吗？解题方案2如果我们x=44,y=9。那么我们还需要枚举接下来的y吗？？？于是我们就有了第二种方案：#includeintmain(){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",i,i,j,j);if(i*i+j*j>

3、=2000)break;}}return0;}还可以优化吗？解题方案3：#includeintmain(){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",i,i,j,j);if(i*i+j*j>=2000)break;}}return0;}还可以进一步的优化吗？？？大家回去也可以好好思考下。可以通过上面的例子看到，虽然都是枚举法，但是运行效率还是会有很大的差距的。第

4、一个方案我们至少需要做45*45次操作而第三种方案明显比第一个方案少很多次操作。ZOJ1722switchThereareNlightsinaline.Giventhestates(on/off)ofthelights,yourtaskistodetermineatleasthowmanylightsshouldbeswitched(fromontooff,orfromofftoon),inordertomakethelightsonandoffalternatively.有N盏灯，排成一排。给定每盏灯的初始状

5、态（开或关），你的任务是计算至少要切换多少盏灯的状态（将开着的灯关掉，或将关掉的灯开起来），才能使得这N盏灯开和关交替出现。InputOnelineforeachtestcase.TheintegerN(1<=N<=10000)comesfirstandisfollowedbyNintegersrepresentingthestatesofthelights("1"foronand"0"foroff).Processtotheend-of-file.输入文件中包含多个测试数据，每个测试数据占一行。首先是一个

6、整数N，1≤N≤10000，然后是N个整数，表示这N盏灯的初始状态，1表示开着的，O表示关着的。测试数据一直到文件尾。OutputForeachtestcaseoutputalineconsistsofonlytheleasttimesofswitches.对每个测试数据，输出占一行，表示至少需要切换状态的灯的数目。SampleInput91001110103101SampleOutput30解题方案1：第一种枚举思路。N盏灯，每盏灯都有两种状态：1和0，则N盏灯共有2N种状态，从000…0到111…1。可以

7、枚举这2^N种状态，每种状态都判断一下是否是开和关交替出现，如果是，则还要统计从初始状态转换到该状态需要切换的灯的数目。但这种枚举策略势必要花费很多时间，因为N最大可以取到10000，而2^10000的数量级是10^3010。我们的OJ时间限制为1s，即我们最多只能是10^7次操作。（一般OJ1S能进行2*10^7次操作）解题方案2：第二种思路。要使得N盏灯开和关交替出现，实际上只有两种可能：奇数位置上的灯是开着的，或者偶数位置上的灯是开着的。只要分别计算从N盏灯的初始状态出发，切换到这两种状态所需要切换灯的数

8、目，取较小者即可。例如样例输入中的第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%