算法实例—枚举.ppt

:一一列举问题所有可能的解,并在逐一列举的过程中,检验每个可能解是否是问题的真正解。【例5】.求1-1000中,能被3整除的数。【例6】.找出1-1000中所有能被7和11整除的数。【例7】.涂抹单据。5位数的编号缺连续二位。【例8】.判断一个正整数是否质数。【例9】.输出1000以内的素数。【例10】.找水仙花数。【例11】.鸡兔同笼问题。【例12】.百鸡百钱问题。c【例5】.求1-1000中,能被3整除的数。开始结束TFi=1i<=1000i=i+1imod3=0TF输出iimod3=0TF输出i检验检验:枚举时注意:不遗漏,不重复,且可能的解有限。c【例5】.求1-1000中,能被3整除的数。在枚举算法中往往把问题分解成二部分:1)一一列举:这是一个循环结构。要考虑的问题是如何设置循环变量、初值、终值和递增值。循环变量是否参与检验。2)检验:一般是一个分支结构。要考虑的问题是检验的对象是谁?逻辑判断后的二个结果该如何处理?分析出以上二个核心问题后,再合成:要注意循环变量与判断对象是否是同一个变量。该算法的输入和输出处理:大部分情况下是利用循环变量来代替。判断的一个分支中实现的。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=10047+i*100如何统计这样的数的个数?j=0开始结束TFi=0i<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=0i<10i=i+1TFk<10k=k+1检验K=0c【例7-1】.某单据1x4x7,缺千位数和十位数,但知道这个5位数是57或67的倍数,请设计一个算法,输出所有满足条件的5位数,并统计这样的数的个数。j=0开始结束TFi=0i<10i=i+1TF输出nnmod57=0ornmod67=0n=10407+i*1000+k*10j=j+1输出个数jTFk<10k=k+1检验K=0c【例8】.判断一个正整数是否质数。开始结束TFi=2i<nnmodi=0TF一一列举: 初值: 终值: 递增值:i2n-11检验:nmodi<>0输入正整数 n输入ni=i+1i=n+1i=nTF输出“否”输出“是”