算法与程序设计基础.pptVIP

第3章算法与程序设计基础3.1算法3.2算法的常用表示方法3.3结构化程序设计方法3.4C语句概述补充：顺序结构程序设计3.5选择结构程序设计3.6循环程序设计3.7综合程序应用举例3.1算法3.1.1算法的概念3.1.2算法的特性3.1.1算法的概念当我们要编写一个程序的时候，我们总要首先想好程序是干什么的？应该如何实现这些目标？(应该先进行什么处理、后进行什么处理？)所处理的数据的格式是什么？遇到一些复杂的问题，我们可能还需要考虑采用什么数学方法。这一切都涉及一个专业名词——“算法”。算法——为解决一个实际问题而采取的方法和步骤很多时候，程序设计者所面临的问题就是寻找一个合适的算法。例如，一个熟练的程序员，要设计一个下“五子棋”的游戏程序，对他而言，C语言的编程规则已经清楚。他所面对的核心问题是寻找一种可以模拟人下棋的算法。因此，算法在软件设计中具有重要的地位。正如著名的计算机科学家沃思（NikiklausWirth）所指出的如下公式：【例3.1】求1+2+3+4+…+100=?算法1步骤1：1+2=3步骤2：3+3=6步骤3：6+4=10…步骤99：4950+100=5050算法2步骤1：0+100=100步骤2：1+99=100步骤3：2+98=100…步骤50：49+51=100步骤51：100*50=5000步骤52：5000+50=5050算法3步骤1：k=1，s=0步骤2：如果k100，则算法结束，s即为所求的和，输出s；否则转向步骤3步骤3：s=s+k，k=k+1步骤4：转向步骤23.1.2算法的特性一个方法要成为我们可以在程序设计中所使用的算法，需要具备如下特征：1.有穷性一个算法要在有限的步骤内解决问题（这里所说的步骤是指计算机执行步骤）。计算机程序不能无限地运行下去（甚至不能长时间地运行下去），所以一个无限执行的方法不能成为程序设计中的“算法”。例如，求某一自然数N的阶乘：n!=1*2*3*…*n这是一个算法。因为对任何一个自然数而言，无论这个数多大，总是有限的。用这个公式计算n!总是需要有限的步骤。但是，以下计算公式则不能作为算法，因为其计算步骤是无限的：sum=1+1/1+1/2+1/3+…+1/n+…2.确定性算法中操作步骤的顺序和每一个步骤的内容都应当是确定的，不应当是含糊不清的。它也不能有不同的解释存在，即不能具有“二义性”，不应当产生两种或多种以上的含义。3.可行性每一个算法是可行的，即算法中的每一个步骤都可以有效地执行，并得到确定的结果。（例如：b=0，执行a/b）4.有零个或多个输入输入就是从外界取得必要的信息。一个算法可以有零个或多个输入，例如：输入一个年份，判断其是否是闰年。同时一个算法可以没有输入，例如：计算出5!是多少。5.有一个或多个输出算法的目的就求解，“解”就是我们想要得到的最终结果。输出是同输入有着某些特定关系的量。一个算法得到的最终结果就是输出。没有输出的算法是没有意义的。3.2算法的常用表示方法3.2.1自然语言表示法3.2.2流程图3.2.3N-S结构流程图3.2.4伪代码表示法3.2.5用计算机语言表示算法3.2.1自然语言表示法自然语言是指人们在日常生活中使用的语言，如汉语、英语等。

比如对于以下这句话：如果A大于B，就给它加1。在理解时就可能出现歧义，是给A加1？还是给B加1。

对于以上的一段话，如果我们用C语言进行编程则为：

if(AB)A=A+1;

对于某些程序员来说，自然语言通俗易懂。

缺点是：很冗长，不直观，而且容易发生歧义。【例3.2】求m！如果m=6，即求1×2×3×4×5×6。我们先设s代表累乘之积，以t代表乘数，自然语言表示m!的算法为：①使s=1,t=1。②使s×t，得到的积仍放在s中。③使t的值加1。④如果t≤m，返回第②步重新执行。如果tm，则不再返回②，而停止循环，此时s中的值就是m!，输出s。3.2.2流程图流程图表示法就是用各种图框表示各种操作。这种表示法的优点是直观易于理解。流