结构化程序设计、算法评价.ppt

《结构化程序设计、算法评价.ppt》由会员分享，可在线阅读，更多相关《结构化程序设计、算法评价.ppt（64页珍藏版）》请在三一办公上搜索。

1、结构化程序设计、算法评价,江苏省金湖中学张厚林,结构化程序设计,荷兰学者Dijkstra提出了“结构化程序设计”的思想，规定了一套方法，使程序具有合理的结构，以保证和验证程序的正确性。重要目的：是使程序具有良好的结构，使程序易于设计，易于理解，易于调试修改，以提高设计和维护程序工作的效率。,结构化程序设计,结构化程序规定了三种基本结构作为程序的基本单元：顺序、分支、循环结构。（1）顺序结构它是最简单，最基本的一种结构。在这个结构中的各块是只能顺序执行的。每一块可以包含一条或若干条可执行的指令。,结构化程序设计,（2）判断选择结构根据给定的条件是否满足执行A块或B块,结构化程序设计,（3）循环结

2、构“当型”循环：当给定的条件满足是执行A块，否则不执行A块而执行循环后面的部分。“直到型”循环：执行A块直到满足给定的条件为止(满足了条件就不再执行A块)。这两种循环的区别是:当型循环是先判断(条件)再执行,而直到型循环是先执行后判断。,结构化程序设计,三种基本结构都具有以下特点:有一个入口；有一个出口；结构中每一部分都应当有被执行到的机会,也就是说,每一部分都应当有一条从入口到出口的路径通过它(至少通过一次)；没有死循环(无终止的循环)。,结构化程序设计,描述一个问题求解的算法有多种方法，常用的有自然语言，流程图（包括NS图）、程序设计语言、伪代码等。在结构化程序设计中，使用一种“结构化流程

3、图”，所谓流程图是用图形来表示程序设计的方法，它采用一些几何图形来代表各种性质的操作，是程序设计中广泛使用的一种辅助设计手段.。,结构化程序设计,N-S结构化流程图（1）一条简单的指令,用一个矩形框来表示：顺序结构可以表示：,结构化程序设计,交换两个变量的值的过程：,结构化程序设计,（2）判断选择结构,结构化程序设计,判断某一年份(year)是否闰年就是一个选择结构,闰年的判断方法是:如果此年份是400倍数,则它是闰年,或者此年份不是100的倍数却是4的倍数,则它也是闰年。,结构化程序设计,与框图对应if-then语句为:if year mod 100=0 then if year mod 4

4、00=0then writeln(yes)else writeln(no)elseif year mod 4=0then writeln(yes)else writeln(no),结构化程序设计,（3）循环结构,结构化程序设计,判断一个自然数是否为质数的算法可用当型循环结构流程图来表示：,结构化程序设计,例1用筛选法找出n以内的所有素数(就是质数),并按每行10个数的形式打印出来.n=25时,用筛选法选素数的过程如下:(1)2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20(2)2 3 4 5 6 7 8 9 10 11 12 13 14 15 1

5、6 17 18 19 20(3)2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20(4)2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20(5)2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20,结构化程序设计,首先确定2是素数，接着把凡是2的倍数的那些数筛去，过程见步骤(2)，其中带有圆圈的数就是被筛去的数。接着把凡是3的倍数的那些数筛去，过程见步骤(3)。接着把凡是4的倍数的那些数筛去,过程见步骤(4)。接着在把凡是5的倍数的那些数筛去，过程见步骤(5)

6、。这时数列中剩下的未被筛去那些数就都是素数。,结构化程序设计,结构化程序设计,write(Input n:);readln(n);for i:=2 to maxn do primei:=1;i:=2;while i*i=n dobeginj:=i*2;while j=n do begin primej:=0;j:=j+i end;i:=i+1end;for i:=2 to n do if primei=1 then write(i:8);writeln,结构化程序设计,在某些程序中，一些具有相似功能的程序段在程序的不同位置反复出现，通常将这些重复出现的程序段抽出来，单独书写成为子程序，并通过一

7、个标识符加以标识，在程序中凡是出现这个程序段的地方只要简单地引用该标识符即可。这样的程序段就称为子程序，在pascal语言中，子程序一般是以函数和过程的形式来呈现的。,结构化程序设计,引入子程序之后，可以方便地把较为复杂的问题分解成若干较小但易于处理的子问题，更重要的是使程序的结构清晰、层次分明，增强了程序的可读性，使程序易于调试和维护。,结构化程序设计,理解“自顶向下，逐步求精”的思想 编写一个程序有两种截然不同的思考问题的方法：“自顶向下”和“自底向上”。“自顶向下，逐步细化”先进行整体设计，然后再进行下一层的设计，把若干个局部构成整体。结构化程序设计提倡这种方法，应采用自顶向下、逐步细化

8、和模块化的方法。,算法评价,算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。常见的算法有：穷举法，分治法，筛选法，构造法，贪心法，动态规划等。,算法评价,例2 H数问题（Hnum）问题描述所谓数，是指该数除以外最多只有2，3，5，7四种因子，如630即为数，而22不是。要求对键盘输入的自然数，求出第个数。如=30，应输出49。规定要求的数不超出长整型数的范围。,算法评价,算法分析从数的定义可以看出，如果一个数是数，那么将它的2，3，5，7四种因子去掉以后必然是剩下1。下面就根据数的这一特性用穷举法来解决这个问题。首先用自然语言描述该算法。,算法评价,算

9、法1_1：穷举法计算第n个H数第一步：从键盘输入一个自然数给N；第二步：将h置为1，order置为1；表示第一个数为1第三步：如果order=n，则转第七步；否则转第四步；第四步：h增加1，并将k的值置为h；第五步：将k中的2，3，5，7四种因子去掉；第六步：如果k=1，则order 增加1；第七步：输出h；,算法评价,以上描述中第五步的描述不够明确，下面对去掉k中因子i作更进一步的说明:第1步：如果k是i的倍数，则转第2步，否则算法结束；第2步：将k置为k/i；第3步：转第1步；,算法评价,const mark:array 1.4 of integer=(2，3，5，7);var i，h，k

10、，n，order:longint;begin write(Input n:);readln(n);h:=1;order:=1;while ordern do begin h:=h+1;k:=h;for i:=1 to 4 do while k mod marki=0 do k:=k div marki;if k=1 then order:=order+1 end;writeln(The no.，n，H number is，h)end.,算法评价,一个算法应该具有下列特性：有穷性：一个算法必须总是(对任何合法的输入值)在执行有穷步之后结束，且每一步都可在有穷时间内完成。确定性：算法的每一步，必须

11、是确切地定义的，读者理解时不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。,算法评价,输入：一个算法有0个或多个输入。它们是在算法开始前对算法给定的量，这些输入取自于特定对象的集合。输出：一个算法有一个或多个输出。它们是同输入有某种特定关系的量。可行性：算法应该是可行的。这意味着算法中所有有待实现的运算都是相当基本的，也就是说，它们原则上都是能够精确地进行的，甚至人们仅用笔和纸做有穷次运算即可完成。,算法评价,一般对算法进行评价主要有四个方面：1、算法的正确性正确性是设计和评价一个算法的首要条件，如果一个算法不正确，其它方面就无从谈起。一个正

12、确的算法是指在合理的输入数据下，能在有限的运行时间内得到正确的结果。通过对数据输入的所有可能情况的分析和上机调试，以证明算法是否正确。,算法评价,2、算法的简单性算法简单有利于阅读，也使得证明算法正确性比较容易，同时有利于程序的编写、修改和调试。但是算法简单往往并不是最有效。因此，对于问题的求解，我们往往更注意有效性。有效性比简单性更重要。,算法评价,3、算法的运行时间：时间复杂性算法的运行时间是指一个算法在计算机上运算所花费的时间。它大致等于计算机执行简单操作（如赋值操作，比较操作等）所需要的时间与算法中进行简单操作次数的乘积。通常把算法中包含简单操作次数的多少叫做“算法的时间复杂性”。,算

13、法评价,x:=x+1 for i:=1 to n do x:=x+1;for j:=1 to n do for k:=1 to n do x:=x+1 for i:=1 to n do for j:=1 to n do begin ci，j:=0;for k:=1 to n do ci，j:=ci，j+ai，k*bk，j end;,算法评价,一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f（n），算法的时间量度记作：T（n）=O（f（n）它表示问题规模n的增大、算法执行时间的增长率和f（n）的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。,算法评价,在n很大时，不同数量

14、级时间复杂度显然有O（1）O（log n）O（n）O（nlog n）O（n2）O（n3）O（2n），可以看出，在算法设计时，我们应该尽可能选用多项式阶O(nk)的算法，而不希望用指数阶的算法。,算法评价,由于算法的时间复杂度考虑的只是对于问题规模n的增长率，则在难以计算基本操作执行次数(或语句频度)的情况下，只需求出它关于n的增长率或阶即可，一般可忽略常数项、底阶项、甚至系数。例如，在下列程序段中:for i:=2 to n do for j:=2 to i-1 do x:=x+1 语句x:=x+1执行次数关于n的增长率为n2，它是语句频度表达式(n-1)(n-2)/2中增长最快的一项。,算法

15、评价,4、算法所占用的存储空间：空间复杂性算法在运行过程中临时占用的存储空间的大小被定义为“算法的空间复杂性”。空间复杂性包括程序中的变量、过程或函数中的局部变量等所占用的存储空间以及系统为了实现递归所使用的堆栈两部分。算法的空间复杂性一般也以数量级的形式给出。,算法评价,类似于算法的时间复杂度，以空间复杂度作为算法所需存储空间的量度，记作:S(n)=O(f(n),算法评价,5、时间和空间复杂性的计算和讨论 例3计算y=anxn+an-1xn-1+an-2xn-2+a1x+a0的值。问题分析该问题计算的规模在于n的大小，n越大计算量也越大，乘积和累加的次数也愈多，这里n就是问题的规模。对于该问

16、题的求解的基本条件是：已知x的值和系数a0an。,算法评价,算法2_1：y=a0;for k:=1 to n do begin s:=ak;for j:=1 to k do s:=s*x y:=y+s;end;writeln(y=，y),算法评价,在该运算中所需存储单元a0，a1，an，以及固定的几个简单变量，所以其空间复杂性与规模n成正比，即为O（n）。而时间复杂性是内循环乘法计算和外循环的累加计算，计算y共用乘法次数是：1+2+3+n=n(n+1)/2，加法仅n次，而在计算机内部实现乘法要比加法花费更多的时间，所以该算法的时间复杂性为:O（n(n+1)/2）O（n*n/2）O（n2）。,算

17、法评价,算法2_2：算法2_1中的乘法运算有重复计算：xk不需要每次从1，x，x2，x3，xk乘法去实现，只要在原先xk-1基础上再做一次乘法就可以得到xk 的结果，多用一个b数组存放1，x，x2，x3，xn，该问题的空间复杂性为O（2n）O(n)。,算法评价,b0:=1;for k:=1 to n do bk:=bk-1*x;y:=a0;for k:=1 to n do y:=y+ak*bk;writeln(y=，y);此算法用了两次单循环命令，共用了2n次乘法和n次加法，时间复杂性为O（2n）O(n)。,算法评价,算法2_3：利用数学中的公式，将y 的计算公式改写为：y=(an*x+an-

18、1)*x+an-2)+a1)*x+a0 y:=an;for k:=n-1 downto 0 do y:=y*x+ak;writeln(y=，y);该算法所用的存储空间为n个单元，即空间复杂性为O（n），而只用了n次乘法和n次加法，所以时间复杂性为O（n）。,算法评价,算法的优化1、以空间换时间 算法中的时间和空间往往是矛盾的，时间复杂性和空间复杂性在一定条件下也是可以相互转化的，有时候为了提高程序运行速度，在算法的空间要求不苛刻的前提下，设计算法时可考虑充分利用有限的剩余空间来存储程序中反复要计算的数据，这就是“用空间换时间”策略，是优化程序的一种常用方法。,算法评价,例4阿姆斯特朗数问题描述

19、编一个程序找出所有的三位数到七位数中的阿姆斯特朗数。阿姆斯特朗数也叫水仙花数，它的定义如下:若一个n位自然数的各位数字的n次方之和等于它本身，则称这个自然数为阿姆斯特朗数。例如153(153=1*1*1+3*3*3+5*5*5)是一个三位数的阿姆斯特朗数，8208则是一个四位数的阿姆斯特朗数。,算法评价,算法设计 由于阿姆斯特朗数是没有规律的，所以程序只能采用穷举法，一一验证范围内的数是否阿姆斯特朗数，若是则打印之。但若对任一个数K，都去求它的各位的若干次方，再求和判断是否等于K，效率比较差，因为我们注意到每个位只可能是09，而且只要算37次方。所以，为了使得程序尽快运行出正确结果，我们采用“

20、以空间换时间”的策略，使用一个数组power存放所有数字的各次幂之值，poweri，j等于i的j次方。,算法评价,for i:=0 to 9 do begin poweri，0:=1;for j:=1 to maxlen do poweri，j:=poweri，j-1*i end;for i:=1 to maxlen do digiti:=0;digit3:=1;highest:=3;currentnumber:=100;total:=0;,算法评价,while digitmaxlen+1=0 do begin sum:=0;for i:=1 to highest do sum:=sum+po

21、werdigiti，highest;if sum=currentnumber then begin total:=total+1;write(currentnumber:maxlen+5);if total mod 6=0 then writeln end;,算法评价,digit1:=digit1+1;i:=1;while digiti=10 do begin digiti+1:=digiti+1+1;digiti:=0;i:=i+1 end;if ihighest then highest:=i;currentnumber:=currentnumber+1 end;,算法评价,2、尽可能利用

22、前面已有的结论比如递推法、构造法和动态规划就是这一策略的典型应用。3、寻找问题的本质特征，以减少重复操作比如：例1中求数问题的算法空间复杂度显然为O(1)，而时间复杂度很难估算，下面我们通过对算法的改进来对它作进一步的分析。,算法评价,算法1_2：构造法计算第n个H数分析数问题，发现数因子只有4种，可以考虑从因子出发由小到大地生成数。假如用一个线性表来存放数，称这个表为数表，则数表中每个元素的2倍，3倍，5倍及7倍均是数，不妨将由数表中每个元素的2倍组成的线性表称为数表的2倍表，设想再用4个线性表分别存放数表的2倍表，3倍表，5倍表和7倍表，然后利用这5个表来生成数表。,算法评价,生成方法如下

23、：开始时数表中存有第一个数1，其它四个表为空表。将当前的数的2倍，3倍，5倍及7倍依次添加到四个表中去，这时四个表中各有一个元素，接下去的所有的数将由这四个表来生成，每次将四个表的第一个元素中的最小者取出来，这个数就是下一个要求的数，将它添加到数表中去，并将这个数的2倍，3倍，5倍及7倍依次添加到四个表中去，然后从四个表中删除这个元素，重复这一过程，直到所要求的数找到为止。,算法评价,程序中为了求出第n个数，必须将它前面的所有的数都求出来并加以保存，所以这一算法的空间复杂度为O(n)；在计算每一个数的过程中，对4个数的倍数表要进行删除操作，对线性表的删除操作的时间复杂度为O(n)，所以这一算法

24、的总的时间复杂度为O(n)*O(n)，即O(n*n)。,算法评价,h1:=1;h21:=2;h31:=3;h51:=5;h71:=7;t2:=1;t3:=1;t5:=1;t7:=1;for i:=2 to n do begin min:=h21;if h31min then min:=h31;if h51min then min:=h51;if h71min then min:=h71;hi:=min;t2:=t2+1;h2t2:=hi*2;t3:=t3+1;h3t3:=hi*3;t5:=t5+1;h5t5:=hi*5;t7:=t7+1;h7t7:=hi*7;,算法评价,if h21=mint

25、hen begin for j:=1 to t2-1 do h2j:=h2j+1;t2:=t2-1 end;if h31=min then begin for j:=1 to t3-1 do h3j:=h3j+1;t3:=t3-1 end;end;,算法评价,仔细分析上述算法，可以发现数的四个倍数表中的所有元素与数表中的所有元素相比，只相差一个倍数而已，可不可以不用这四个倍数表，而借用数表来表示它们呢?答案是肯定的，为了说明问题，首先引进线性表的指针的概念，在用数组描述线性表时，线性表中的元素的位置完全取决于数组下标的值，我们不妨将这个下标值即一个整数看作指向线性表中某一元素的指针。,算法评价

26、,这样就可以用四个指针分别指向数表中的四个数，这四个数的2倍，3倍，5倍及7倍的值分别是四个倍数表中的首元素，以此表示数的四个倍数表。一开始，它们均指向1，即当前的四个倍数表的首元素分别为2*1，3*1，5*1，7*1，取四数中最小者作为第二个数2，记入数表中，并将代表数的2倍表的指针下移一，指向2，再比较2*2，3*1，5*1，7*1，取3，将代表数的3倍表的指针下移一位即指向表中下一个数2，表示数的3倍表中的首元素变成了*=6，以此类推。直到插入表中的数的总数满足要求为止。,算法评价,这个算法在改进空间复杂度的同时，也将时间复杂度降到了O(n)，因为用指针模拟数的倍数表后，线性表的删除操作

27、变成了指针的移动操作，而指针的移动操作只要用一个赋值语句即可。,算法评价,程序中4个指针由数组p实现，p1表示指针指向的数表中元素的2倍为数的2倍表的首元素，数组mark记录4个因子2，3，5，7。数表由数组h来表示。四数中若有多个相等者，取一个即可，并将相应的多个指针均下移一格。,算法评价,const maxn=5910;mark:array1.4 of integer=(2，3，5，7);var i，j，n，min:longint;p:array1.4 of longint;h:array1.maxn of longint;begin write(Input n(n=，maxn，):);r

28、eadln(n);h1:=1;for i:=1 to 4 do pi:=1;,算法评价,for i:=2 to n dobegin min:=hp1*mark1;for j:=2 to 4 do if hpj*markjmin then min:=hpj*markj;hi:=min;for j:=1 to 4 do if hpj*markj=min then pj:=pj+1;end;,算法评价,规模 结果 算法1 算法2 算法3n=100 H100=450 0.00 0.00 0.00 n=500H500=32928 0.01 0.00 0.00 n=1000H1000=385875 0.1

29、 0.00 0.00 n=2000H2000=7077888 2.85 0.01 0.01 n=3000H3000=50176000 14.55 0.01 0.01 n=4000H4000=228614400 54.38 空间不够 0.01n=5000 H5000=797343750 225.23 空间不够 0.01,算法评价,算法的复杂度分析不仅可以对算法的好坏作出客观的评估，同时对算法设计本身也有着指导性作用，因为在解决实际问题时，算法设计者在判断所想出的算法是否可行时，通过对算法作事先评估能够大致得知这个算法的优劣，进而作出决定是否采纳该算法。这样就能避免把大量的精力投入到低效算法的实现中去，特别是现在举行的各级信息学奥林匹克竞赛对程序的运行时间都有着相当严格的限制，掌握好算法复杂度的大致评估方法就显得犹为重要。,