程序的灵魂-算法课件

02-程序的灵魂——算法02-程序的灵魂——算法02-程序的灵魂——算法程序的灵魂－－算法程序设计概述算法怎样表示一个算法小结参考书目及网络资源讨论时间程序的灵魂－－算法程序设计概述算法怎样表示一个算法小结参考书目及网络资源讨论时间程序的灵魂－－算法程序设计概述算法怎样表示一个算法小结参考书目及网络资源讨论时间程序设计概述NiklausE.Wirth(1934-)Switzerland

Pascal,StructuredProgramming

1984,TuringAward算法、语言、程序的关系算法：描述了数据对象的元素之间的关系（包括数据逻辑关系、存储关系描述）。描述算法的工具：算法可用自然语言、框图或高级程序设计语言进行描述。自然语言简单但易于产生二义，框图直观但不擅长表达数据的组织结构，而高级程序语言则较为准确但又比较严谨。

程序是算法在计算机中的实现(与所用计算机及语言有关)。算法、语言、程序的关系NiklausE.Wirth给出的公式：算法+数据结构=程序，说明数据结构和算法是程序的两大要素，二者相辅相成，缺一不可。算法是程序的灵魂。算法和程序都是用来表达解决问题的逻辑步骤，但算法独立于具体的计算机，与具体的程序设计语言无关，而程序正好相反；程序是算法，但算法不一定是程序。程序的灵魂－－算法程序设计概述算法算法的概念简单算法举例算法的特性怎样表示一个算法小结参考书目及网络资源讨论时间Whatisanalgorithm?—TheArtofComputerProgramming,Addison-Wesley.Vol1-FundamentalAlgorithms

DonaldE.Knuth

(January10,1938-)

TuringAward(1974)“Afinitesetofruleswhichgivesasequenceofoperationsforsolvingaspecifictypeofproblem.”算法是规则的有限集合，是为解决特定问题而规定的一系列操作。算法的概念算法算法是指解决一个具体问题的意义明确的步骤的集合。是有限的。概括地说，算法是指解题方案的准确而完整的描述。从程序来说，也可以说算法是一个有限条指令的集合，这些指令确定了解决某一特定类型问题的运算序列。对于同一个问题可以有不同的解题方法和步骤，也就是有不同的算法。算法有优劣，一般而言，应当选择简单的、运算步骤少的，既运算快、内存开销小的算法（算法的时空效率）。简单算法举例例1求1×2×3×4×5。可先写出这样的算法：先求1×2，得到结果2；将步骤1得到的结果再乘以3，得到结果6；将6再乘以4，得到24；将24再乘以5，得到120。上述算法太繁琐，我们找一种通用的表示方法。s1:设变量p，被乘数，p=1;s2:设变量i,代表乘数，i=2;s3:使p×i,乘积放在被乘数变量p中，可表示为：p×ip;s4:使i的值加1，即i+1i;s5:如果i不大于5，返回重新执行步骤s3以及其后的s4、s5;否则，算法结束。最后得到的p就是5!的值。简单算法举例例2.求1×3×5×7×9×11上述算法稍作改动：s1:1p;s2:3i;s3:p×ip;s4:i+2is5:若i11,返回s3;否则，结束。用这种方法表示的算法具有通用性、灵活性。s3到s5组成一个循环，在实现算法时，要反复多次执行s3、s4、s5等步骤，直到某一时刻，执行s5步骤时经过判断，乘数i已超过规定的数值而不返回s3步骤为止。计算机实现循环是轻而易举。将s5步骤写成：“s5：若i<11，返回s3；否则结束。”会得到什么结果？简单算法举例例3.有50个学生，要求将他们之中成绩在80分以上者打印出来。用n表示学生学号，n1代表第一个学生学号，ni

代表第i个学生学号。用g代表学生成绩，gi代表第i个学生成绩，算法表示如下：S1:1i;S2:如果gi80,则打印ni和gi,否则不打印。S3:i+1i;S4:如果i50,返回s2,继续执行，否则算法结束。本例中，变量i作为下标，用它来控制序号（第几个学生，第几个成绩）。当i超过50时，表示已对50个学生的成绩处理完毕，算法结束。简单算法举例例4.判断2000年~2500年中的每一年是否闰年，将结果输出。我们知道，地球绕太阳一转，需365天5小时48分46秒。假如需365天6小时，则每4年一个闰年（设每个被4能除尽的年份为闰年）。假如需365天5小时45分36秒（即5小时45.6分），则每100年减去一个闰年。但被减去太多，每400年再增加一个闰年。简单算法举例闰年的条件是：当year是4的整倍数，但不是100的整倍数时为闰年；条件表示为：(year%4==0)&&(year%100!=0)当year是400的整倍数时为闰年；条件表示为：year%400==0满足以上两条件之一即为闰年。因而有以下逻辑表达式：

该逻辑表达式的值为1即闰年；为0则非闰年。((year%4==0)&&(year%100!=0))||(year%400==0)简单算法举例算法如下：设y为被检测的年份，可采取以下步骤：s1:2000y;s2:若y不能被4整除，则输出y“不是闰年”。然后转到s6.s3:若y能被100整除，又能被400整除，输出y“是闰年”，否则输出“不是闰年”。然后转到s6。s4:若y能被100整除，又能被400整除，输出y“是闰年”，然后转到s6。s5:输出y“不是闰年”。s6:y+1y;s7:当y2500时，转s2继续执行，如y>2500,算法停止。简单算法举例例5.求下列级数的值可以写出下面的算法（1）使S=0（S作为累加变量）；（2）使N=1（N代表分母）；（3）S+1/NS（执行迭代，S为迭代变量）；（4）N+1N；（5）若N≤100，转去执行（3）以及其后的各步骤；否则执行（6）；（6）打印S的值（即所求之总和）。算法的特性有穷性一个算法应当包含有限的步骤，而不能是无限的步骤；同时一个算法应当在执行一定数量的步骤后，算法结束，不能死循环。事实上“有穷性”往往指“在合理的范围之内”的有限步骤。如果让计算机执行一个历时1000年才结束的算法，算法尽管有穷，但超过了合理的限度，人们也不认为此算法是有用的。确定性算法中的每一个步骤都应当是确定的，而不是含糊的、摸棱两可的。也就是说不应当产生歧义。特别是算法用自然语言描述时应当注意这点。例如：“将成绩优秀的同学名单打印输出”就是有歧义的。“成绩优秀”是要求每门课程都90分以上，还是平均成绩在90分以上？不明确，有歧义，不适合描述算法步骤。算法的特性有0个或多个输入（即：可以没有输入，也可以有输入）所谓输入是指算法执行时从外界获取必要信息。（外界是相对算法本身的，输入可以是人工键盘输入的数据，也可以是程序其它部分传递给算法的数据）例如：不需要输入任何信息，就可以计算出5！；（0个输入）例如：如果要计算两个整数的最大公约数，则需要输入2个整数m，n。（2个输入）有1个或多个输出（即算法必须得到结果）算法的输出：算法得到的结果。算法必须有结果，没有结果的算法没有意义。（结果可以是显示在屏幕上的，也可以是将结果数据传递给程序的其它部分）有效性算法的每个步骤都应当能有效执行，并能得到确定的结果。例如：b=0，则执行a/b是不能有效执行的。怎样表示一个算法？为了表示一个算法，可以用不同的方法。常用的算法表示方法：自然语言传统流程图结构化流程图（N-S流程图）伪代码计算机语言等。重点：传统流程图，N-S流程图程序的灵魂－－算法程序设计概述算法怎样表示一个算法自然语言传统流程图结构化流程图（N-S流程图）伪代码计算机语言小结参考书目及网络资源讨论时间用自然语言表示算法自然语言就是人们常用的语言，可以是汉语、英语或其他语言。用自然语言表示通俗易懂；但文字冗长，容易出现“歧义”性；而且，用自然语言描述包含分支和循环的算法，不很方便。一般不使用自然语言描述算法自然语言描述举例例如：描述计算并输出z=y/x的流程，可以用自然语言描述如下：（1）输入x，y。（2）判断x是否为0：若X=0,则输出错误信息；否则计算y/xz，且输出z。算法描述语言算法描述语言为了说明程序的流程而专门规定的某种语言。它一般介于自然语言与程序设计语言之间，它具有自然语言灵活的特点，同时又接近于程序设计语言的描述。算法描述语言所描述的流程，一般不能直接作为程序来使用，最后还需转换成用某种程序设计语言所描述的程序。与程序设计语言的区别前者比较自由，不象后者那样受语法的约束，只要描述得人们能理解就行，而不必考虑计算机处理时所要遵循的规定或其它一些细节。用流程图表示算法流程的描述在程序设计过程中，一般不可能在一开始就用某种程序设计语言编制计算机程序，而是先用某种简单、直观、灵活的描述工具来描述处理问题的流程。当方案确定以后，再将这样的流程转换成计算机程序，这种转换往往是机械的，已经不涉及功能的重新设计或控制流程的变化，而只需考虑程序设计语言所规定的语法要求以及一细节问题。流程图用一些约定的几何图形来描述算法。用某种图框表示某种操作，用箭头表示算法流程。用流程图表示算法流程图（的符号及意义）美国标准化协会ANSI规定了一些常用的流程图符号，已为世界各国程序工作者普遍采用：用流程图表示算法起止框表示算法的开始和结束。一般内部只写“开始”或“结束”。处理框表示算法的某个处理步骤，一般内部常常填写赋值操作。输入输出框表示算法请求输入输入需要的数据或算法将某些结果输出。一般内部常常填写“输入…”,“打印/显示…”菱形框（判断框）作用主要是对一个给定条件进行判断，根据给定的条件是否成立来决定如何执行其后的操作。它有一个入口，两个出口。用流程图表示算法连接点用于将画在不同地方的流程线连接起来。同一个编号的点是相互连接在一起的，实际上同一编号的点是同一个点，只是画不下才分开画。使用连接点，还可以避免流程线的交叉或过长，使流程图更加清晰。注释框注释框不是流程图中必须的部分，不反映流程和操作，它只是对流程图中某些框的操作做必要的补充说明，以帮助阅读流程图的人更好地理解流程图的作用。用流程图表示算法例：求5！

该流程能获得正确的结果吗？为什么？传统流程图、三种基本结构和改进的流程图传统流程图的缺点传统流程图采用流程线指出各框的执行顺序，对流程线的使用没有严格限制。因此，使用者可以不受限制地使流程转来转去，使流程图变得毫无规律。人们对这种流程图进行改进，规定几种基本的结构，然后由这些基本结构按一定规律组成算法结构，整个算法结构是由上而下地将各个基本结构顺序排列起来。这样可以在一定程度上，提高算法的质量。三种基本结构和改进的流程图三种基本结构的流程图(1)顺序结构程序设计依次顺序执行程序语句执行a块执行b块a块b块AB例如，令a、b的值分别为5、10；

a=5；

b=10；(2)判别选择结构程序设计首先判别条件，若条件满足，程序执行a块，否则，执行b块；举例，求a、b两个数中的最大值；满足条件否满足不满足执行a块执行b块条件成立？执行a块执行b块成立不成立b>max？max=a；max=b；YN(3)循环结构程序设计循环又分“当型循环”和“直到型循环”举例，求1~100的累加和。

直到条件满足为止执行循环中的指令当条件满足时执行循环中指令sum=sum+i;i=i+1;Ysum=0;Ni<=100？三种基本结构和改进的流程图三种基本结构，有以下共同点：只有一个入口：不得从结构外随意转入结构中某点。只有一个出口：不得从结构内某个位置随意转出（跳出）。结构中的每一部分都有机会被执行到。（没有“死语句”）结构内不存在“死循环”（无终止的循环）已经证明：由三种基本结构顺序组成的算法结构，可以解决任何复杂问题。由基本结构组成的算法属于“结构化”算法。Nassi-ShneidermandiagramIsaacNassi(1927-),USABenShneiderman(1947-),USANassi,I.;Shneiderman,B.:Flowcharttechniquesforstructuredprogramming,ACMSIGPLANNoticesXII,8(8),pp12-26,August1973.用N-S流程图表示算法基本结构的顺序组合可以表示任何复杂的算法结构，那么，基本结构之间的流程线就属于多余的了，于是美国学者I.Nasii和B.shneiderman于1973年提出了一种新的流程图形式。全部算法写在一个矩形框内，完全去掉了带箭头的流程线。这种流程图称为N-S结构化流程图(盒图)。N-S流程图适于结构化程序设计顺序结构程序设计依次顺序执行程序语句执行a块执行b块先执行a操作，再执行b操作判别选择结构程序设计当条件成立，执行a操作，当条件不成立，执行b操作。a，b操作允许空操作，即什么都不做。注意选择结构是一个整体，代表一个基本结构。循环结构程序设计循环又分“当型循环”和“直到型循环”用N-S流程图表示算法直到条件p满足为止执行循环中的指令当条件p满足时执行循环中指令满足条件否满足不满足执行a块执行b块用N-S流程图表示算法“当型循环”当条件p成立时，反复执行循环体中指令，直到p条件不成立为止。当型循环先判断，再决定是否执行循环体，所以在条件p一次都不满足时，循环体可能一次都不执行。直到型循环当条件p不成立时，反复执行循环体中的指令，直到p条件成立为止。直到型循环先执行循环体，然后再判断条件p，所以循环体至少执行一次。当条件p满足时执行循环中指令直到条件p满足为止执行循环中的指令用N-S流程图表示算法例：求5!的算法用N-S图表示。用伪代码表示算法用伪代码表示算法（常常用于算法设计）用传统流程图、N-S图表示算法，直观易懂，但绘制比较麻烦，在设计一个算法时，可能要反复修改，而修改流程图是比较麻烦的，因此，流程图适合表示算法，但在设计算法过程中使用不是很理想。为了设计算法方便，常使用伪代码工具。伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。伪代码不用图形符号，书写方便，格式紧凑，便于向计算机语言算法过渡。伪代码伪代码（Pseudocode）是一种算法描述语言。使用伪代码的目的是为了使被描述的算法可以容易地以任何一种编程语言实现。因此，伪代码必须结构清晰，代码简单，可读性好，并且类似自然语言。伪代码的语法规则在伪代码中，每一条指令占一行（elseif，例外），指令后不跟任何符号（Pascal和C中语句要以分号结尾）；书写上的“缩进”表示程序中的分支程序结构。这种缩进风格也适用于if-then-else语句。伪代码用缩进取代传统Pascal中的begin和end语句来表示程序的块结构可以大大提高代码的清晰性；同一模块的语句有相同的缩进量，次一级模块的语句相对与其父级模块的语句缩进。用伪代码表示算法输入三个整数，然后输出其中最大数。BEGININPUTa,b,cIFa>bTHEN a

maxELSE b

maxIFc>maxTHENc

maxPRINTmaxENDBEGININPUTa,b,ca

maxIFmax<bTHENb

maxIFmax<cTHENc

maxPRINTmaxEND用计算机语言表示算法用某种程序设计语言编写的程序本质上也是问题处理方案的描述，并且是最终的描述。在一般的程序设计过程中，不提倡一开始就编写程序，特别是对于大型的程序。程序是程序设计的最终产品，需要经过每一步的细致加工才能得到，如果企图一开始就编写出程序，往往会适得其反，达不到预想的结果。结构化程序设计方法结构化程序设计方法强调程序设计风格和程序结构的规范化，提倡清晰的结构。结构化程序设计方法的基本思路是：把一个复杂的问题的求解过程分阶段进行,每个阶段处理的问题都控制在人们容易理解和处理的范围内。为保证程序满足结构化程序设计，可以采取如下方法自顶向下逐步细化模块化设计结构化编码结构化程序设计方法对于一个具体问题一般有两种方法自顶向下、逐步细化自下而上、逐步积累例如：写文章、建造房屋提倡采用自顶向下、逐步细化的程序设计方法，其过程是将问题求解由抽象逐步具体化的过程。注意：用这种方法便于验证算法的正确性，在向下一层展开之前应仔细检查本层设计是否正确，只有上一层是正确的才能向下细化。用计算机语言表示算法例:求5！(用C