5.1枚举算法的程序实现.pptx

向左走向右走,男主角电话号码,女主角电话号码,枚举算法,按问题本身的性质，一一列举出该问题所有可能的解，并在逐一列举的过程中，检验每个可能解是否是问题的真正解，若是，就采纳这个解，否则就抛弃它。,1、一一列举该问题所有可能的解,2、逐个检验每个可能解是否是问题的真正解,一、基本思想：,二、枚举算法关键：,自行车胎坏掉的时候，修车师傅检查坏掉的位置，就是一个枚举算法,他选定某一个位置为起始位置，然后按顺序一块块的检查过来，直到找到坏掉的位置，需要注意的问题是：找到一个坏掉的位置后，还要继续找吗？为了安全起见，建议继续找,由此，在使用枚举算法的时候的注意事项，即要把所有可能的情况都找出来，否则有可能会漏掉答案。,1、警察审查案件时一一审问疑犯2、将一箱苹果中烂的苹果挑出来3、象山公交车上投币坐车,判断是否用枚举算法解决问题,思考?,问题：将电话号码看成是一个8位数的编号，其百位数和十位数处已经变得模糊不清。,男主角电话号码,判断条件：知道这个8位数(电话号码)是13的倍数。,要求：现在要设计一个算法，找出所有满足这些条件的8位数（电话号码），并统计这些8位数的个数。,00,01,02,03,98,99,让变量J依次取0到99这100个不同的值,接着给J的每个确定的值乘以10加上22764005这样就能形成一个可能解。,0,J,10,00,22764005,22764005,1,10,22764015,2,20,22764025,98,980,22764985,99,990,22764995,所有可能的解用变量n表示,j,步骤一：一一列举该问题的所有可能解,男主角电话号码,提示条件：这个8位数是13的倍数,nMod13=0,22764005,22764015,22764995,步骤二：检验每个可能解是否是问题的真正解,男主角电话号码,可能解n,n=22764005+j*10,22764005+j*10,开始,设计算法，找出所有满足这些条件的8位数，统计这些8位数的个数。,计数器置初值：C0,j0,j100?,n22764005+j*10,N是13的倍数,CC+1,输出：真正解N的值,jj+1,Y,Y,N,输出：计数器C的值,结束,N,J：循环变量，其作用如下：1、用它来控制循环是否继续进行，记录已经执行的循环的次数。2、依次产生应填在百位和十位上的数值。,n：存储一个可能解,计数器C,Command1,Text1,List1,程序界面设计,开始,计数器置初值：C0,j0,j100?,n22764005+j*10,n是13的倍数,计数器C计数CC+1,输出：真正解N的值,jj+1,Y,Y,N,输出计数器C的值,结束,N,PrivateSubCommand1_Click(),EndSub,Dimn,n,jAsInteger,c=0,FORj=0TO99,n=22764005+j*10,IfnMod13=0Then,C=C+1,List1.AdditemStr(n),EndIf,Nextj,Text1.Text=Str(C),exe,枚举算法程序实现,1、枚举解,2、筛选解,枚举算法程序实现三要素,3、输出解（或统计解的个数）,循环结构语句，例如For语句,分支结构语句,例如If语句,女主角电话号码,步骤一：一一列举该问题的所有可能解,j,i,FORi=,FORj=,n=,Nextj,Nexti,22760205,22760215,22760295,0TO9,0TO9,22760205+i*1000+j*10,循环语句,FORi=0TO9,FORj=0TO9,n=22760205+i*1000+j*10,IfThen列出符合条件的电话号码n统计号码个数cEndIf,Nextj,Nexti,步骤二：检验每个可能解是否是问题的真正解,nMod13=0,选择语句,女主角电话号码,j,i,exe,C5算法及程序实现,寻找“水仙花数”。水仙花数是满足下面条件的一组三位的正整数，它们满足条件：每一位上数字的立方之和恰好等于它自己。例如：153就是一个水仙花数，13+53+33=153，,请找出所有的水仙花数及个数。完善主要代码。,Text1,List1,sum=0Fori=100Toa=i100求得百位上的数字b=求得十位上的数字c=求得个位上的数字IfThenList1.AddItemStr(i)输出水仙花数个数sum=sum+统计个数EndIfNextiText1.Text=输出统计好的个数,999,i10mod10,imod10,a3+b3+c3=i,Str(sum),1,Sum=0Fori=1To9百位数Forj=0To9十位数Fork=0To9个位数Ifi3+j3+k3=100*i+10*j+kThenList1.AddItemStr(100*i+10*j+k)sum=sum+1统计个数EndIfNextkNextjNextiText1.Text=Str(sum),用变量i，j，k分别表示百位数、十位数、个位数,Str(100*i+10*j+k),i3+j3+k3=100*i+10*j+k,枚举算法的优化,1、减少枚举变量,2、缩小枚举变量的范围,3、减少重复计算,C5算法及程序实现,公元5世纪末，我国古代数学家张邱健在他编写的“算经”里提出一个百钱百鸡问题：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问鸡翁、母、雏各几何？,设x、y、z分别代表公鸡、母鸡和小鸡的只数，根据题意，列出方程为：,List1,Label1,公鸡数x20，母鸡数y33,IfThenList1.AddItem(Str(a)+Str(b)+Str(c)sum=sum+1EndIfNextcNextbNextaLabel1.Caption=Str(sum),Fora=0To100Forb=0To100Forc=0To100,a+b+c=100anda*5+b*3+c/3=100,Fora=0To20Forb=0To33c=100-a-b,a*5+b*3+c/3=100,1、一一列举,2、逐一判断,exe,枚举算法,按问题本身的性质，一一列举出该问题所有可能的解，并在逐一列举的过程中，检验每个可能解是否是问题的真正解，若是，就采纳这个解，否则就抛弃它。,1、一一列举该问题所有可能的解,