算法实例—枚举.ppt

《算法实例—枚举.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、基本算法１．解析算法２．枚举算法３．排序４．查找c枚举算法：一一列举问题所有可能的解，并在逐一列举的过程中，检验每个可能解是否是问题的真正解。2．枚举算法【例5】．求1-1000中，能被3整除的数。【例6】．找出1-1000中所有能被7和11整除的数。【例7】．涂抹单据。5位数的编号缺连续二位。【例8】．判断一个正整数是否质数。【例9】．输出1000以内的素数。【例10】．找水仙花数。【例11】．鸡兔同笼问题。【例12】．百鸡百钱问题。c【例5】．求1-1000中，能被3整除的数。开始结束TFi=1i<=10

2、00i=i+1imod3=0TF输出iimod3=0TF输出i检验检验:枚举时注意：不遗漏，不重复，且可能的解有限。c【例5】．求1-1000中，能被3整除的数。在枚举算法中往往把问题分解成二部分：1）一一列举：这是一个循环结构。要考虑的问题是如何设置循环变量、初值、终值和递增值。循环变量是否参与检验。2）检验：一般是一个分支结构。要考虑的问题是检验的对象是谁？逻辑判断后的二个结果该如何处理？分析出以上二个核心问题后，再合成：要注意循环变量与判断对象是否是同一个变量。该算法的输入和输出处理：大部分情况下是利用

3、循环变量来代替。判断的一个分支中实现的。c【例6】．找出1-1000中所有能被7和11整除的数。开始结束TFi=1i<=1000i=i+1imod3=0TF输出iimod7=0andimod11=0imod77=0c【例7】．某单据1xx47,缺千位数和百位数，但知道这个5位数是57或67的倍数，请设计一个算法，输出所有满足条件的5位数，并统计这样的数的个数。开始结束TFi=1i<=1000i=i+1imod3=0TF输出i一一列举：初值：终值：递增值：i0991检验：nmod57=0ornmod67=0n=

4、10047+i*100如何统计这样的数的个数？j=0开始结束TFi=０i<100i=i+1TF输出nnmod57=0ornmod67=0N=10047+i*100j=j+1输出个数jc【例7-1】．某单据1x4x7,缺千位数和十位数，但知道这个5位数是57或67的倍数，请设计一个算法，输出所有满足条件的5位数，并统计这样的数的个数。一一列举：初值：终值：递增值：i091检验：nmod57=0ornmod67=0n=10407+i*1000+k*10如何统计这样的数的个数？千位十位k091开始TFi=０i<10

5、i=i+1TFk<10k=k+1检验K=0c【例7-1】．某单据1x4x7,缺千位数和十位数，但知道这个5位数是57或67的倍数，请设计一个算法，输出所有满足条件的5位数，并统计这样的数的个数。j=0开始结束TFi=０i<10i=i+1TF输出nnmod57=0ornmod67=0n=10407+i*1000+k*10j=j+1输出个数jTFk<10k=k+1检验K=0c【例8】．判断一个正整数是否质数。开始结束TFi=2i0

6、输入正整数n输入ni=i+1i=n+1i=nTF输出“否”输出“是”c【例9】．输出1000以内的素数。开始结束TFi=2i0in-12-1输入正整数n输入ni=i+1i=n+1i=nTF输出“否”输出“是”n110001i2n-11c【例9】．输出1000以内的素数。TFi=2i

7、。TFi=2i

8、-a)*4=94【例11】．鸡兔同笼问题开始结束TFa=0a<=35a=a+1TF输出a、35-aa*2+(35-a)*4=94c【例12】．百鸡百钱问题。鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几何？一一列举：初值：终值：递增值：a0201检验：a*5+b*3+c/3=100鸡翁鸡母鸡雏b0331c01003a*5+b*3+c/3=100开始TFa=0a<=20结