73程序设计基础

程序设计基础E-mail:[e-mail]循环结构程序设计基础一、算法与算法的描述算法的概念算法的特性算法的描述算法的概念：为解决一个问题而采取的方法和步骤。问题1：有8个小球，其中7个重量相同，仅有一个较重，用天平如何称出那个重的小球。算法(1)：把8个小球分成四组，依次将每组放在天平上，直到某一组天平不平衡，就可确定重的小球，最多需称4次。算法(2)：①从8个小球中任取6个小球，将这6个小球每边3个置于天平上；②若天平平衡，则表明重的小球在剩余的2个小球中，只需将那两个小球放在天平上再称一次就可找到重的那个小球；③若天平不平衡，则从较重的一边的3个球中任取2个球称量，若平衡，则剩下的那个即为要找的那个小球，若不平衡，则重的那边就是要找的小球。算法(2)只需2次称量，比算法(1)优越。算法的特性⑴确定性算法的每一步必须是确切定义的，且无二义性；⑵有穷性一个算法必须在执行有穷次运算后结束；⑶可行性算法中的每一步骤必须能用可执行指令精确表达，并在有限步骤内完成；⑷有0个或多个输入；⑸有输出。算法的描述1.自然语言2.流程图3.程序设计语言N－S图4算法的评价算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法：(1)事后统计法。因为很多计算机内部都有计时功能，有的甚至可精确到毫秒级，不同算法的程序可通过一组或若干组相同的统计数据以分辨优劣。但这种方法有两个缺陷：一是必须先运行依据算法编制的程序；二是所得时间的统计依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣。因此人们通常采用另一种事前分析估算的方法。(2)事前分析估算法。一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：a.依据的算法选用何种策略；b.问题的规模。例如求100以内还是1000以内的素数；c.书写程序的语言。对于同一个算法，实现语言的级别越高，执行效率就越低；d.编译程序所产生的机器代码的质量；e.机器执行指令的速度。显然，同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行时，效率均不相同。这表明使用绝对的时间单位衡量算法的效率是不合适的。问题中的n表示了问题的大小，次数n是问题的规模。算法①：y:=a[0]；fork:=1tondobegint:=a[k]；fori:=1tokdot:=t*x；{计算ak·xk}y:=y+t；end；writeln('y='，y)；可见，内循环计算ak·xk用了k次乘法，计算y共用乘法的次数为1＋2＋3＋…＋n，即n(n+1)/2，时间复杂度为n2。算法②：从算法①中可以发现x，x2，…xn不必每次都用乘法实现，xk+1=xk•x，增加数组b[0]至b[n]，用于存放x0，x1，x2，…xn，则该算法的空间复杂度为2n。b[0]:=1；fork:=1tondob[k]:=b[k-1]*x；y:=a[0]；fork:=1tondoy:=y+a[k]*b[k]；writeln('y='，y)；此算法中，时间复杂度和空间复杂度均为2n。算法③：将y的计算公式改写为y=(…((an*x+an-1)*x+an-2)…+a1)*x+a0如y=7x5+4x4-8x3+6x+2，可改写为y=((((7x+4)x-8)x+0)X+6)x+2，其中a5=7,a4=4,a3=-8，a2=0，a1=6,a0=2y:=a[n]；fori:=n-1to0doy:=y*x+a[i]；writeln('y='，y)；算法的时间复杂度为n，空间复杂度也为n，是三个算法中效果最好的。算法常见的量级估计O(1)表示问题规模变化时，复杂性变化不大，这类算法是十分优秀的。O(n)算法复杂性是问题规模的线性函数，这类算法是很好的。O(nlog2n)虽比O(n)差，但仍属不错的算法。O(nk)应尽可能改进，使k值愈小愈好。O(2n)当n较大时，复杂性会变得很大。1971年,瑞士的NiklausWirth教授正式发表了一种名为Pascal的程序设计语言的报告。Pascal首次将人们带进结构化程序设计之中。Pascal问世以来，先后产生了适合不同机型的各种版本，其中TurboPascal6.0是国际奥林匹克信息学(计算机)竞赛指定使用的语言之一。从全国竞赛中可以看出，使用TurboPascal的选手成绩最为理想。Pascal程序设计基础一个完全的Pascal程序结构Program程序名；uses已知单元说明；label标号说明；const常量说明；type类型说明；var变量说明；function函数说明；procedure过程说明；begin语句；……end.(1)顺序结构.它是最简单,最基本的一种结构.在这个结构中的各块是只能顺序执行的.每一块可以包含一条或若干条可执行的指令.AB三种基本结构(2)判断选择结构.见图1-2.(3)循环结构例1已知：faibonacai(费波那契)数列的前几个数分别为0，1，1，2，3，5...，编程求此数列的前几项。分析：先考虑好解题的算法：仔细观察该数列，发现其规律是：f1=0（n=1）f2=1（n=2）fn=fn-1+fn-2（n≥3）也就是从第三项起，每次均为它的前两项之和。假设用f表示上式的fn，p表示f的前一项（fn-1），l表示它的前两项（fn-2），则有等式f=p+l。在打印出当前项f的值后，若使l变成p，f变成l，那么就可依次得到第三项、第四项......的f值plf第一次01f=0+1=1（第三项）第二次11f=1+1=2（第四项）第三次12f=1+2=3（第五项）........依据以上方法，问题得到解决，程序如下：programp1;varn，p，l，t:integer;beginwriteln（'需要求得faibonacci数列的第几项:');read(n);p:=0;l:=1;t:=2;write(0，1);{打印前两项}whiletndobeginf:=p+l;if(tmod4)=0thenwriteln;write(f:6);p:=l;l:=f;t:=t+1;end;end.执行该程序：需要求得faibonacci数列的第几项：2001123581321345589144233377610987159725844181在这个例子中，我们采用的是“递推”算法。所谓递推是指在一个数的序列值中，下一项的值是在前一项值的基础上推算出来的，也就是下一项对前一项有某种依赖关系。思考练习：1、有1×n的一个长方形方格，用1×1和1×2的骨牌铺满方格。例如n=3时，为1×3方格。试对给出的任意一个n(n〉0)，求出铺法总数的递推公式。2、有n个台阶，一次1步、2步或3步的上台阶。试对给出的任意一个n(n〉0)，求出上台阶的总上法的递推公式。3、有2×n的一个长方形方格，用1×1和1×2的骨牌铺满方格。例如n=3时，为2×3方格。试对给出的任意一个n(n〉0)，求出铺法总数的递推公式。例2求100－999中的水仙花数，（若三位数abc，abc＝a3+b3+c3，则称abc为水仙花数。如153，13+53+33=1+125+27=153，则153是水仙花数）。根据题意采用三重循环求解，由于循环次数一定，用for循环最为简单。programp3;vara，b，c:integer;beginfora:=1to9doforb:=0to9doforc:=0to9doifa*a*a+b*b*b+c*c*c=a*100+b*10+cthenwrite(a*100+b*10+c:6);readlnend.运行结果：153370371407同时也可以采用一个for循环来求解，表面上看好象优于三重循环，实际上却比上面的程序效率低，请自己分析。programp3_2;varm，a，b，c:integer;beginform:=100to999dobegina:=mdiv100;b:=(mmod100)div10;c:=m-a*100-b*10;ifa*a*a+b*b*b+c*c*c=mthenwrite(m:6);end;readlnend.[例3]现有两种药片重量分别是10克和11克，外观一样，现有装10克药的药瓶10个，11克药瓶1个，药瓶也一样，排列时，一不小心药瓶混在一起了，请给出方法区分药瓶，并编程实现。【例4】有Ａ、Ｂ、Ｃ、Ｄ四名偷窃嫌疑犯，其中一人是小偷，审问中，Ａ说：“我不是小偷”，Ｂ说：“Ｃ是小偷”，Ｃ说：“小偷肯定是Ｄ”，Ｄ说：“Ｃ在冤枉人”，有三人说真话，一人说假话，问到底谁是小偷？