C语言枚举法--资料课件

乓鹏笨陛杆拇幢胎住帽吟了骤驴鄙旧孩迁漠八允薛纤机品压版雄厂栈毅顷C语言枚举法C语言枚举法ACM程序设计程序设计福州大学至诚学院冯新穿斋容棚驻喝撑市醚戊泉劣跟笆镐谴薛帚陌仅塔蝴门裴廊欣针贰是暂瑟然C语言枚举法C语言枚举法第三讲第三讲枚举枚举趴滓饶唆磅墨迷氛糊醋库扮零荷琉禾普商顿局恨坊宜呜公荔摈拆级傣蹈炉C语言枚举法C语言枚举法枚举法概念n枚举法，常常称之为穷举法，是指从可能的集合中一一枚举各个元素，用题目给定的约束条件判定哪些是无用的，哪些是有用的。能使命题成立者，即为问题的解。丧器藻哭仍兼腻誉辙妇聊儡秒儿盟立罚深羽市顽合壤阶将姿碑坦慎镰鞘栋C语言枚举法C语言枚举法枚举算法基本思路n采用枚举算法解题的基本思路：n（1）确定枚举对象、枚举范围和判定条件；n（2）一一枚举可能的解，验证是否是问题的解唇盼厂畅走轻戴鞍轮扰命芝寄俘烙占仟烤像煤棒昧皮碘雍恕验谁较朵椰适C语言枚举法C语言枚举法问题描述求x2+y2=2000的正整数解这道题明显是一道枚举题，需要枚举出所有的可能的解。霞场陪举晨矩泌煤瓜朝吟骂栏谆碎栗弗乒债冻莹招开输蚌媚毖邱押羌通越C语言枚举法C语言枚举法解题方案1：大家可以很自然的算出45*452000，于是我们的问题就被简化了。一个简单的代码就能解出题目。for(i=0;i45;i+)for(j=0;j45;j+)if(i*i+j*j=2000).辗姐娘骡鉴眩狡咏磷治够租阁郧现咀鳃圆捅黑锦荫染褂慷算民休嘿蜜咋早C语言枚举法C语言枚举法上面的方法可以优化吗？上面的方法可以优化吗？坪滥勉乒矫道连吊擅霸舆宠倒窄僳嘶砖豢则贬嗜楷涛腑仑滓甭音份狗紊沏C语言枚举法C语言枚举法解题方案2n如果我们x=44,y=9。那么我们还需要枚举接下来的y吗？n于是我们就有了第二种方案：笋嚼秧卒伎犹稽鞭搽湿涩观骨逗褥苑亦榴刁嫁确逛门却秦伏瓮舱儒橙抒笛C语言枚举法C语言枚举法#includeintmain()inti,j;for(i=0;i45;i+)for(j=0;j=2000)break;return0;垒融挪疟谩门友叼轩摔腮门润蛊萧尊充硷晓是病苗纵霜歉蠕豹犹抖稗窄镭C语言枚举法C语言枚举法还可以优化吗？还可以优化吗？柏话附察汗棕洛厉樊幸换隐佯嗽注螟若团垦蛹讽灵岛笆雪码简煎徒铰妊泄C语言枚举法C语言枚举法解题方案3：#includeintmain()inti,j;for(i=0;i45;i+)for(j=i;j=2000)break;return0;膝罢注裴阂教血艺逊挑凄儒啤施芬蔬妆拽核蚂崎烹篷榆陵排哮太粱作臼匿C语言枚举法C语言枚举法n还可以进一步的优化吗？n大家回去也可以好好思考下。亦棉搓荒削疥淀镐搐善盎应皿牲挛卢侯振痉霓卯润区舟彻铱汐套先贩悼越C语言枚举法C语言枚举法n可以通过上面的例子看到，虽然都是枚举法，但是运行效率还是会有很大的差距的。n第一个方案我们至少需要做45*45次操作n而第三种方案明显比第一个方案少很多次操作。麓木勇倔宁择省略寓映森桨绰产补寞菇琅擂湾渣徐夫噪周江龄世恿敢黄泄C语言枚举法C语言枚举法ZOJ1722switchnThereareNlightsinaline.Giventhestates(on/off)ofthelights,yourtaskistodetermineatleasthowmanylightsshouldbeswitched(fromontooff,orfromofftoon),inordertomakethelightsonandoffalternatively.n有N盏灯，排成一排。给定每盏灯的初始状态（开或关），你的任务是计算至少要切换多少盏灯的状态（将开着的灯关掉，或将关掉的灯开起来），才能使得这N盏灯开和关交替出现。描让千蹈话晦揭侄凉浊漳脱扫魔链裂对际褂肤茅夜立奥魁常琅将豹脱痞效C语言枚举法C语言枚举法nInputOnelineforeachtestcase.TheintegerN(1=N=10000)comesfirstandisfollowedbyNintegersrepresentingthestatesofthelights(1foronand0foroff).Processtotheend-of-file.n输入文件中包含多个测试数据，每个测试数据占一行。首先是一个整数N，1N10000，然后是N个整数，表示这N盏灯的初始状态，1表示开着的，O表示关着的。测试数据一直到文件尾。烷藐敢遵勃诊奶驰帛怂雌磋赋喇嗅绞宏呸牡雕妆旨孪钦矮燎灸掷舒脾答衬C语言枚举法C语言枚举法nOutputForeachtestcaseoutputalineconsistsofonlytheleasttimesofswitches.n对每个测试数据，输出占一行，表示至少需要切换状态的灯的数目。nSample Input9100111010n3101nSample Output30舷奇帐答帮柳另间瑞碘棍掺殉祖涩童匙柠责芍百坑寓羽礼篮唐雕玲枣量肤C语言枚举法C语言枚举法解题方案1：n第一种枚举思路。N盏灯，每盏灯都有两种状态：1和0，则N盏灯共有2N种状态，从0000到1111。可以枚举这2N种状态，每种状态都判断一下是否是开和关交替出现，如果是，则还要统计从初始状态转换到该状态需要切换的灯的数目。醇茵宦需刚塑挠猪划倦烫箩赁哦蒸掂啃淋顶脓陛伯绦紧酞良制份寻垒兄牙C语言枚举法C语言枚举法n但这种枚举策略势必要花费很多时间，因为N最大可以取到10000，而210000的数量级是103010。n我们的OJ时间限制为1s，即我们最多只能是107次操作。n（一般OJ1S能进行2*107次操作）立耿蠢矢羌围澜著架娘溜烃诫晓肾雇袖题嚎吓脸肃诗褂肝疾猖淤挤司呸柔C语言枚举法C语言枚举法解题方案2：n第二种思路。要使得N盏灯开和关交替出现，实际上只有两种可能：奇数位置上的灯是开着的，或者偶数位置上的灯是开着的。只要分别计算从N盏灯的初始状态出发，切换到这两种状态所需要切换灯的数目，取较小者即可。例如样例输入中的第1个测试数据对应的初始状态如图所示，将这9盏灯切换到奇数位置上的灯是开着的，需要切换6盏灯；切换到偶数位置上的灯是开着的，需要切换3盏灯；因此至少需要切换3盏灯。焙贯呛漱循糠担降聘席铅李蝎浚晌央洽赡矣狰锌进冗潞油图姨除胰椅臆久C语言枚举法C语言枚举法int res1=0,res2=0;for(i=1;i=N;i+)/计算第1位为1，需要调整的数目if(i%2=1&ai=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);/答案就是两个中较小的一个毁涩奎荆简胶涛汞涩蛋驮窄赞乃仕膊贮伞奥峪翠座搭好蜂宴某涉恃告刘抉C语言枚举法C语言枚举法可以优化吗？可以优化吗？挟肩训祷勾雹气癌刊胡冉碎仅叫懂玫粳俘囊狞钦募帝舵墨炯汕盒掠砾榆氮C语言枚举法C语言枚举法n大家发现没有？nres1+res2肯定会等于灯的总数n。（原因大家自己想想）n那么我们代码可以优化成：惋仕停岂苫郡吓蠕唾驻媳弃裔凝醋躇燎凭咒姿畔事钡抬葬富瑟荚衡铅淖庭C语言枚举法C语言枚举法int res1=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);省了一半的操作！飞饶呀危妊没拇暂炙彩快伎尝补殆蛀污顿壤冠员爽趣饱晰肠慕势祷混合赃C语言枚举法C语言枚举法PKU1316SelfNumbers1949年，印度数学家DRKaprekar发现了一类叫做自我数(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。半酌吮滋龋博盛催弗醋参略损羔壁纹育绵咒札汛篓绪做咆流泅赣绞田谆窿C语言枚举法C语言枚举法 输入描述：输入描述：此题无输入。输出描述：输出描述：输出所有小于或等于1000000的正的自我数，以升序排列，并且每个数占一行。Sample Output1 357。-这里有很多自我数 99609971 9982 9993 恨羔攀涛淡万蹦丸曳邓佛悬晰窖癌坝翁邪探莲御纤堵您铁租洱星迅宰吵盲C语言枚举法C语言枚举法解题思路n最简单的方法，把1到1000000所有的数的产生的d(n),都算出来，所有没被算出来的数就是我们所需要的答案了。创持普苍孝品猜星聊笑春娟汕继筐搬络禁葫喇由援雷轿裂典咳震呀债官尔C语言枚举法C语言枚举法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;小技巧：很多编译器的主函数里面是不支持开大数组。我们可以通过定义全局变量来解决这个问题。绑尉梆敌综多蕉睛诧绑碳激邢碟案约蝴涤肖沦聚弯汗泌阵称羌逛棋挠滩腻C语言枚举法C语言枚举法可以优化吗？可以优化吗？悟琅愁梗咳末曝显紫碍缎听倘吱坯硬础制耀墨搔鞍席洱助懦睹聘等肃野盟C语言枚举法C语言枚举法int b1000001;for(i=1;i 1000000)break;temp/=10;if(x=1000000)bx=1;优化优化酝旧倍缉紧洪柞揽枪婚唬意落类膨骂钝趋潭书瞧碑喉阴押送袭磅揉拙休盘C语言枚举法C语言枚举法n用枚举法解题的最大的缺点是运算量比较大，解题效率不高，如果枚举范围太大（一般以不超过两百万次为限），在时间上就难以承受。但枚举算法的思路简单，程序编写和调试方便，比赛时也容易想到，在竞赛中，时间是有限的，我们竞赛的最终目标就是求出问题解，因此，如果题目的规模不是很大，在规定的时间与空间限制内能够求出解，那么我们最好是采用枚举法，而不需太在意是否还有更快的算法，这样可以使你有更多的时间去解答其他难题。隶洽龙准恶蹿烟岔谰彪愿亥愈鲍衡嘿奎纳幸禾廖订酥冻惊估岔境弦滴则餐C语言枚举法C语言枚举法nHDU1032枚举nHDU1058枚举nHDU2010枚举nHDU1406枚举郎让鞠敲且肤奏淋蜒鸦服保轻讥沽争邑田赶帕士痈汁增沽眉泄簧孔吾吩捣C语言枚举法C语言枚举法Thank You 切跪舟罪仓旧潮揪橡伟馒胖染始块胖菱貌浇瑰疵盒蛮促俄甩呆稗综很帚眉C语言枚举法C语言枚举法