《算法实例枚举》PPT课件

基本算法,解析算法,枚举算法,排序,查找,c,枚举算法：一一列举问题所有可能的解，并在逐一列举的过程中，检验每个可能解是否是问题的真正解。,2枚举算法,【例5】求1-1000中，能被3整除的数。【例6】找出1-1000中所有能被7和11整除的数。【例7】涂抹单据。5位数的编号缺连续二位。【例8】判断一个正整数是否质数。【例9】输出1000以内的素数。【例10】找水仙花数。【例11】鸡兔同笼问题。【例12】百鸡百钱问题。,c,【例5】求1-1000中，能被3整除的数。,开始,结束,T,F,i=1,i=1000,i=i+1,imod3=0,T,F,输出i,imod3=0,T,F,输出i,检验,检验:,枚举时注意：不遗漏，不重复，且可能的解有限。,c,【例5】求1-1000中，能被3整除的数。,在枚举算法中往往把问题分解成二部分：1）一一列举：这是一个循环结构。要考虑的问题是如何设置循环变量、初值、终值和递增值。循环变量是否参与检验。2）检验：一般是一个分支结构。要考虑的问题是检验的对象是谁？逻辑判断后的二个结果该如何处理？分析出以上二个核心问题后，再合成：要注意循环变量与判断对象是否是同一个变量。该算法的输入和输出处理：大部分情况下是利用循环变量来代替。判断的一个分支中实现的。,c,【例6】找出1-1000中所有能被7和11整除的数。,开始,结束,T,F,i=1,i=1000,i=i+1,imod3=0,T,F,输出i,imod7=0andimod11=0,imod77=0,c,【例7】某单据1xx47,缺千位数和百位数，但知道这个5位数是57或67的倍数，请设计一个算法，输出所有满足条件的5位数，并统计这样的数的个数。,开始,结束,T,F,i=1,i=1000,i=i+1,imod3=0,T,F,输出i,一一列举：初值：终值：递增值：,i0991,检验：,nmod57=0ornmod67=0,n=10047+i*100,如何统计这样的数的个数？,j=0,开始,结束,T,F,i=,i100,i=i+1,T,F,输出n,nmod57=0ornmod67=0,N=10047+i*100,j=j+1,输出个数j,c,【例7-1】某单据1x4x7,缺千位数和十位数，但知道这个5位数是57或67的倍数，请设计一个算法，输出所有满足条件的5位数，并统计这样的数的个数。,一一列举：初值：终值：递增值：,i091,检验：,nmod57=0ornmod67=0,n=10407+i*1000+k*10,如何统计这样的数的个数？,千位十位,k091,开始,T,F,i=,i10,i=i+1,T,F,k10,k=k+1,检验,K=0,c,【例7-1】某单据1x4x7,缺千位数和十位数，但知道这个5位数是57或67的倍数，请设计一个算法，输出所有满足条件的5位数，并统计这样的数的个数。,j=0,开始,结束,T,F,i=,i10,i=i+1,T,F,输出n,nmod57=0ornmod67=0,n=10407+i*1000+k*10,j=j+1,输出个数j,T,F,k10,k=k+1,检验,K=0,c,【例8】判断一个正整数是否质数。,开始,结束,T,F,i=2,in,nmodi=0,T,F,一一列举：初值：终值：递增值：,i2n-11,检验：,nmodi0,输入正整数n,输入n,i=i+1,i=n+1,i=n,T,F,输出“否”,输出“是”,c,【例9】输出1000以内的素数。,开始,结束,T,F,i=2,in,nmodi=0,T,F,一一列举：初值：终值：递增值：,i2n-11,检验：,nmodi0,in-12-1,输入正整数n,输入n,i=i+1,i=n+1,i=n,T,F,输出“否”,输出“是”,n110001,i2n-11,c,【例9】输出1000以内的素数。,T,F,i=2,in,nmodi=0,T,F,i=i+1,i=n+1,i=n,T,F,输出“否”,输出“是”,开始,T,F,n=1,n=1000,n=n+1,结束,c,【例9】输出1000以内的素数。,T,F,i=2,in,nmodi=0,T,F,i=i+1,i=n+1,i=n,T,F,输出n,开始,T,F,n=1,n=1000,n=n+1,结束,c,【例10】找水仙花数。(一个3位数,其各位数字立方和等于该数),一一列举：初值：终值：递增值：,i1009991,检验：,开始,结束,T,F,i=100,i1000,i=i+1,a3+b3+c3=i,a=int(i/100)b=int(i/10)mod10c=imod10,输出i,T,F,c,今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？,一一列举：初值：终值：递增值：,a0351,检验：,鸡兔,35-a,a*2+(35-a)*4=94,【例11】鸡兔同笼问题,开始,结束,T,F,a=0,a=35,a=a+1,T,F,输出a、35-a,a*2+(35-a)*4=94,c,【例12】百鸡百钱问题。,鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几何？,一一列举：初值：终值：递增值：,a0201,检验：,a*5+b*3+c/3=100