程序的灵魂算法课件.ppt

《程序的灵魂算法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、上机安排7-10周，周一3，4节10-14周，周四晚7:20---10:00地点：6409第2章程序的灵魂——算法§2.1算法的概念§2.2简单算法举例§2.3算法的特性§2.4怎样表示一个算法§2.5结构化程序设计方法§2.1算法的概念⒈算法的概念一个程序应包括两方面内容：⑴对数据的描述。在程序中要指定数据的类型和数据的组织形式，即：数据结构。⑵对操作的描述。即：操作步骤，也就是算法。程序=算法+数据结构+程序设计方法+语言工具⒉算法的分类⑴数值运算算法。数值运算的目的是求数值解，例如求方程的根，求一个函

2、数的定积分等，都属于数值运算范围。⑵非数值运算算法。非数值运算包括的面十分广泛，最常见的是用于事务管理领域，例如图书检索、人事管理等。返回§2.2简单算法举例例2.1求1×2×3×4×5。方法一：S1：先求1×2，得到结果2。S2：将步骤1得到的乘积再乘以3，得到结果6。S3：将6再乘以4，得24。S4：将24再乘以5，得到120。即最后的结果。方法2：1×2=22×3=66×4=2424×5=120p×i方法二：设两个变量，一个变量代表被乘数，一个变量代表乘数。将每一步骤的乘积直接放在被乘数变量中。今设p

3、为被乘数，i为乘数。用循环算法求结果。S1：使p=1S2：使i=2S3：使p×i,乘积仍放在变量p中,表示为p×iS4：使i的值加1，即i+1piS5：如果i的值不大于5，返回重新执行步骤S3以及其后的步骤S4和S5；否则，算法结束。最后得到的p的值就是5！的值。例2.2求1×3×5×7×9×11。S1：p=1S2：i=3S3：p=p×iS4：i=i+2S5：若i≤11,返回S3；否则，结束。问题：将S5步骤写成S5：若Ii＜11,返回S3；否则，结束。结果？返回§2.3算法的特性⒈有穷性一个算法应包含有限

4、的操作步骤，而不能是无限的。⒉确定性算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的。即：算法的含义应当是唯一的，而不应当产生“歧义性”。⒊有零个或多个输入输入是指在执行算法时需要从外界取得必要的信息。一个算法也可以没有输入。⒋有一个或多个输出算法的目的是为了求解，“解”就是输出。一个算法得到的结果就是算法的输出。没有输出的算法是没有意义的。⒌有效性算法中的每一个步骤都应当能有效地执行，并得到确定的结果。例如，若b=0,则a/b是不能被有效执行的。返回§2.4怎样表示一个算法表示一个算法可以用

5、不同的方法，常用的有：用自然语言表示算法用传统流程图表示算法用N-S流程图表示算法用伪代码表示算法用计算机语言表示算法例：求1×2×3×4×5，即5！=？⒈用自然语言表示算法自然语言就是人们日常使用的语言，可以是汉语、英语或其它语言。用自然语言表示通俗易懂，但文字冗长，容易出现“歧义性”。此外，用自然语言描述包含分支和循环的算法，不很方便。因此，除了很简单的问题外，一般不用自然语言描述算法。S1：使t=1S2：使i=2S3：使t×i,乘积仍放在变量t中,表示为t=t×iS4：使i的值加1，即i=i+1S5：

6、如果i的值不大于5，返回重新执行步骤S3以及其后的步骤S4和S5；否则，算法结束。最后得到t的值就是5！的值。⒉用传统流程图表示算法流程图是用一些图框表示各种操作。用图形表示算法，直观形象，易于理解。美国国家标准化协会ANSI规定了一些常用的流程图符号（课本P20图2-3）。如图1即为传统流程图表示的算法。从中看出，一个传统流程图包括以下几部分：表示相应操作的框；带箭头的流程线；框内外必要的文字说明；开始t=1i=2t=t×ii=i+1i>5?结束YN图1⒊三种基本结构和改进的流程图⑴传统流程图的弊端⑵三种

7、基本结构☆顺序结构ABab☆选择结构又称选取结构，或称分支结构。APB不成立成立ab图aaAP不成立成立b图b☆循环结构又称重复结构，即反复执行某一部分的操作。有两类循环结构：当型（While型）循环结构直到型（Until型）循环结构P1A成立ab图a当型循环结构P2A不成立ab图b直到型循环结构⑶三种基本结构的共同特点：a.只有一个入口。b.只有一个出口。c.结构内的每一部分都有机会被执行到。d.结构内不存在“死循环”（无终止的循环）。AB⒊用N-S流程图表示算法1973年，两位美国学者提出了一种新的流程

8、图形式。在这种流程图中，完全去掉了带箭头的流程线。全部算法写在一个矩形框内，在该框内还可以包含其它的从属它的框。这种流程图又称N-S结构化流程图。N-S流程图用以下的流程图符号：AB图a顺序结构P成立不成立AB图b选择结构当p1成立A图c当型循环结构直到p1成立A图d直到型循环结构t=1i=i+1直到i>5打印ti=2t=t×i归纳：△一个结构化算法是由一些基本结构顺序组成的；△在基本结构之间不存在向前或向后的跳