ascal枚举算法讲解.ppt

《ascal枚举算法讲解.ppt》由会员分享，可在线阅读，更多相关《ascal枚举算法讲解.ppt（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、环变量的范围）Programck;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(106)FOR i:=0 TO 20 DO FOR J:=0 TO 33 DOIF 5*I+J*3+(100-I-J)/2=100 THENBEGIN.END时间复杂度为时间复杂度

3、为20*33即即102用优化枚举法求10000以内素数programmeijuconstn=10000;vara:array1.nofinteger;i,j,k:integer;beginwrite(2);fori:=3tondobeginj:=2;k:=int(sqrt(i)trunc(sqr(j);while(j=k)and(imodj0)doj:=j+1;ifj=kthenwrite(i:4);end;writeln;此算法的运算的运算次数为10000*100=106另一种枚举的思路(筛选)programmeijuconstn=10000;vara:array1.nof0.1;i,j,k

4、:integer;beginFori:=1tondoai:=true;Forj:=2toint(sqrt(n)doFork:=j+1tondoIf(ak=true)and(kmodj=0)thenak:=false;Fori:=1tondoifai:=truethenwrite(i:4);end;End;此算法的运算的运算次数为10000*100=106用枚举法求10000以内素数programmeijuconstn=10000;vara:array1.nofinteger;i,j,k:integer;beginwrite(2);fori:=3tondobeginj:=2;while(j=Ia

5、nd(imodj0)doj:=j+1;ifj=kthenwrite(i:4);end;writeln;此算法的运算的运算次数为99998*99998=1010空间复杂度为：10000即O（103)练习题一:翻硬币题目描述：题目描述：一摞硬币共有一摞硬币共有m m枚，每一枚都是正面朝上。取下最上枚，每一枚都是正面朝上。取下最上面的一枚硬币，将它翻面后放回原处。然后取下最上面的面的一枚硬币，将它翻面后放回原处。然后取下最上面的2 2枚硬枚硬币，将他们一起翻面后放回原处。在取币，将他们一起翻面后放回原处。在取3 3枚，取枚，取4 4枚枚直至直至m m枚。枚。然后在从这摞硬币最上面的一枚开始，重复刚才

6、的做法。这样然后在从这摞硬币最上面的一枚开始，重复刚才的做法。这样一直做下去，直到这摞硬币中每一枚又是正面朝上为止。例如，一直做下去，直到这摞硬币中每一枚又是正面朝上为止。例如，m m为为1 1时，翻两次即可。时，翻两次即可。输入：仅有的一个数字是这摞硬币的枚数输入：仅有的一个数字是这摞硬币的枚数m m，0 m 10000 m 1000。输出：为了使这摞硬币中的每一枚都是朝正面朝上所必须翻的输出：为了使这摞硬币中的每一枚都是朝正面朝上所必须翻的次数。次数。输入样例：30输出样例：899难度:练习题二：将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。分析过程程序分析：对程序分

7、析：对n n进行分解质因数，应先找到一个最进行分解质因数，应先找到一个最小的质数小的质数k k，然后按下述步骤完成：，然后按下述步骤完成：(1)(1)如果这个质数恰等于如果这个质数恰等于n n，则说明分解质因数的，则说明分解质因数的过程已经结束，打印出即可。过程已经结束，打印出即可。(2)(2)如果如果nknk，但，但n n能被能被k k整除，则应打印出整除，则应打印出k k的值，的值，并用并用n n除以除以k k的商的商,作为新的正整数你作为新的正整数你n,n,重复执行第一步。重复执行第一步。(3)(3)如果如果n n不能被不能被k k整除，则用整除，则用k+1k+1作为作为k k的值的值,重复重复执行第一步。执行第一步。训练题三:”完数”一个数如果恰好等于它的因子之和，这个数就称为“完数”。例如6=123.编程找出100000以内的所有完数。使用优化的枚举法+筛选法来完成程序