算法与程序设计基础.ppt

《算法与程序设计基础.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3章算法与程序设计基础3.1算法3.2算法的常用表示方法3.3结构化程序设计方法3.4C语句概述补充：顺序结构程序设计3.5选择结构程序设计3.6循环程序设计3.7综合程序应用举例[目录]实验三实验四13.1算法3.1.1算法的概念3.1.2算法的特性[本章]23.1.1算法的概念当我们要编写一个程序的时候，我们总要首先想好程序是干什么的？应该如何实现这些目标？(应该先进行什么处理、后进行什么处理？)所处理的数据的格式是什么？遇到一些复杂的问题，我们可能还需要考虑采用什么数学方法。这一切都涉及一个专业名词——“算法”。算法——为解决

2、一个实际问题而采取的方法和步骤很多时候，程序设计者所面临的问题就是寻找一个合适的算法。例如，一个熟练的程序员，要设计一个下“五子棋”的游戏程序，对他而言，C语言的编程规则已经清楚。他所面对的核心问题是寻找一种可以模拟人下棋的算法。因此，算法在软件设计中具有重要的地位。正如著名的计算机科学家沃思（NikiklausWirth）所指出的如下公式：程序=数据结构+算法3【例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=10

3、0步骤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：如果k>100，则算法结束，s即为所求的和，输出s；否则转向步骤3步骤3：s=s+k，k=k+1步骤4：转向步骤2[本节]43.1.2算法的特性一个方法要成为我们可以在程序设计中所使用的算法，需要具备如下特征：1.有穷性一个算法要在有限的步骤内解决问题（这里所说的步骤是指计算机执行步骤）。计算机程序不能无限地运行下去（甚至不能长时间地运行下去），所以一个无

4、限执行的方法不能成为程序设计中的“算法”。例如，求某一自然数N的阶乘：n!=1*2*3*…*n这是一个算法。因为对任何一个自然数而言，无论这个数多大，总是有限的。用这个公式计算n!总是需要有限的步骤。但是，以下计算公式则不能作为算法，因为其计算步骤是无限的：sum=1+1/1+1/2+1/3+…+1/n+…52.确定性算法中操作步骤的顺序和每一个步骤的内容都应当是确定的，不应当是含糊不清的。它也不能有不同的解释存在，即不能具有“二义性”，不应当产生两种或多种以上的含义。3.可行性每一个算法是可行的，即算法中的每一个步骤都可以有效地执行

5、，并得到确定的结果。（例如：b=0，执行a/b）4.有零个或多个输入输入就是从外界取得必要的信息。一个算法可以有零个或多个输入，例如：输入一个年份，判断其是否是闰年。同时一个算法可以没有输入，例如：计算出5!是多少。5.有一个或多个输出算法的目的就求解，“解”就是我们想要得到的最终结果。输出是同输入有着某些特定关系的量。一个算法得到的最终结果就是输出。没有输出的算法是没有意义的。[本节]63.2算法的常用表示方法3.2.1自然语言表示法3.2.2流程图3.2.3N-S结构流程图3.2.4伪代码表示法3.2.5用计算机语言表示算法[本章

6、]73.2.1自然语言表示法自然语言是指人们在日常生活中使用的语言，如汉语、英语等。比如对于以下这句话：如果A大于B，就给它加1。在理解时就可能出现歧义，是给A加1？还是给B加1。对于以上的一段话，如果我们用C语言进行编程则为：if(A>B)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≤

7、m，返回第②步重新执行。如果t>m，则不再返回②，而停止循环，此时s中的值就是m!，输出s。[本节]83.2.2流程图流程图表示法就是用各种图框表示各种操作。这种表示法的优点是直观易于理解。流程图表示法是美国国家标准化协会ANSI（AmreicanNationalStandardInstitute）规定的。一些常用的流程图符号在Word中都可以通过“绘图”命令来绘制。结构化程序设计中采用三种基本结构，即顺序结构、选择结构和循环结构，这三种基本结构有以下共同特点：只有一个入口；只有一个出口；结构内的每一部分都有机会被执行到；结构内不存在

8、“死循环”(无终止的循环)。9⑴顺序结构A和B两个框是顺序执行的。⑵选择结构选择结构或称分支结构，条件结构。此结构中必包含一个判断框，根据给定的条件P是否成立来进行选择。若P成立，则执行A框中的操作，否则，执行B框中的操