ascal枚举算法讲解

《ascal枚举算法讲解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、枚举算法讲解FOR初一信息技术兴趣小组枚举算法思想什么是枚举？枚者，一个一个也。举者，列举也。枚举就是一个一个地列举。应用到程序中，枚举有许多表现形式，比如把所有的组合都扫描一遍，找出符合要求的组合。举个简单的例子，找素数。1什么都不是，2是素数，3是，4不是，5是……，如此把所有的自然数就能找出所有的素数(天大的乌托邦，呵。)。可以这么说，枚举是最简单，最基础，也是最没效率的算法.一般来说”枚举算法”的执行效率比较低,所以在通常的程序设计中我们要对”枚举算法”进行优化,比如减少枚举的范围,减少循环的个数,以提高程序的执行效率.百钱买百鸡问题(减少循环次数，减少循环变量的范围）Pr

2、ogramck;VarI,j,k:shortint;num:integer;BeginNum:=0;Fori:=0to100doforj:=0to100dofork:=0to100doIf(i+j+k=100)and(i*2+j+k/2=100)thenBeginWriteln(‘no’,num+1,i:4,j:4,k:4);Num:=num+1;end;End;时间复杂度:100*100*100为O(10^6)FORi:=0TO20DOFORJ:=0TO33DOIF5*I+J*3+(100-I-J)/2=100THENBEGIN………..END时间复杂度为<20*33即10^2用

3、优化枚举法求10000以内素数programmeijuconstn=10000;vara:array[1..n]ofinteger;i,j,k:integer;beginwrite(2);fori:=3tondobeginj:=2;k:=int(sqrt(i)){trunc(sqr(j))};while(j<=k)and(imodj<>0)doj:=j+1;ifj<=kthenwrite(i:4);end;writeln;此算法的运算的运算次数为10000*100=10^6另一种枚举的思路(筛选)programmeijuconstn=10000;vara:array[

4、1..n]of0..1;i,j,k:integer;beginFori:=1tondoa[i]:=true;Forj:=2toint(sqrt(n))doFork:=j+1tondoIf(a[k]=true)and(kmodj=0)thena[k]:=false;Fori:=1tondoifa[i]:=truethenwrite(i:4);end;End;此算法的运算的运算次数为10000*100=10^6用枚举法求10000以内素数programmeijuconstn=10000;vara:array[1..n]ofinteger;i,j,k:integer;beginw

5、rite(2);fori:=3tondobeginj:=2;while(j<=Iand(imodj<>0)doj:=j+1;ifj<=kthenwrite(i:4);end;writeln;此算法的运算的运算次数为99998*99998=10^10空间复杂度为：10000即O（10^3)练习题一:翻硬币题目描述：一摞硬币共有m枚，每一枚都是正面朝上。取下最上面的一枚硬币，将它翻面后放回原处。然后取下最上面的2枚硬币，将他们一起翻面后放回原处。在取3枚，取4枚……直至m枚。然后在从这摞硬币最上面的一枚开始，重复刚才的做法。这样一直做下去，直到这摞硬币中每一枚又是正面朝上为

6、止。例如，m为1时，翻两次即可。输入：仅有的一个数字是这摞硬币的枚数m，0k，但n能被k整除，则应打印出k的值，并用n除以k的商,作为新的正整数你n,重复执行第一步。(3)如果n不能被k整除，则用k+1作为k的值,重复执行

7、第一步。训练题三:”完数”一个数如果恰好等于它的因子之和，这个数就称为“完数”。例如6=1＋2＋3.编程找出100000以内的所有完数。使用优化的枚举法+筛选法来完成程序