《程序的灵魂算法》PPT课件

1、1第四章 程序的灵魂算法1、对数据的描述。（配料，指出应使用那些原料）2、对操作的描述。（操作步骤，如何用料做成菜肴）3、程序设计方法。4、语言工具和环境。程序=数据结构+算法+程序设计方法+语言工具和环境2.1 算法的概念为解决一个问题而采取的方法和步骤，为解决一个问题而采取的方法和步骤，就称为算法。就称为算法。从北京到天津开会一首歌曲的谱子太极拳图解计算机算法分两大类：数值运算算法和计算机算法分两大类：数值运算算法和 非数值运算算法。非数值运算算法。3.2 简单算法举例例例1：求：求1*2*3*4*5方法一：步骤1：先求1*2，得到结果2。步骤2：将步骤1得到的乘积2再乘以3，得到结果6。

2、步骤3：将步骤2得到的乘积6再乘以4，得到结果24。步骤4：将步骤3得到的乘积24再乘以5， 得到最后结果120。4方法二：步骤1：设p=1（p为乘数）。步骤2：设i=2（i为被乘数）。步骤3：使p*i，乘积仍放在变量p中，可表示为p=p*i。步骤4：使i的值加1，可表示为i=i+1 。步骤5：如果i不大于5，返回重新执行步骤3、4、5； 否则算法结束。最后求得的p的值就是5！的值。5例例2 2 有两个变量有两个变量a a和和b b，将它们的值交换。，将它们的值交换。 a tb采用间接交换方法。采用间接交换方法。1、at2、 ba3、 t b6例例3 3 有有50个学生，要求将他们之中成绩在个

3、学生，要求将他们之中成绩在80分以分以上者打印出来。用上者打印出来。用n表示学生学号，表示学生学号，n1代表第一代表第一个学生学号，个学生学号，ni代表第代表第i个学生学号。用个学生学号。用g代表学代表学生成绩，生成绩，gi代表第代表第i个学生成绩，算法可表示如下。个学生成绩，算法可表示如下。S1：1=iS2：如果：如果gi80，则打印，则打印ni和和gi，否则不打，否则不打印印S3：i+1=iS4：如果：如果i50，返回，返回S2，继续执行；否则，继续执行；否则，算法结束。算法结束。7例例4 4 给定一个正整数给定一个正整数M M，判断它是否为素数。，判断它是否为素数。所谓素数，是指除了所谓

4、素数，是指除了1和该数本身之外，不能被和该数本身之外，不能被其他任何整数整除的数。例如，其他任何整数整除的数。例如，13是素数，因是素数，因为它不能被为它不能被2，3，4，12整除。整除。判断一个数判断一个数n(n3)是否素数的方法是很简单的：是否素数的方法是很简单的：将将n作为被除数，将作为被除数，将2到到(n-1)各个整数轮流作为各个整数轮流作为除数，如果都不能被整除，则除数，如果都不能被整除，则n为素数。为素数。8S1：输入：输入n的值的值S2：2=i （i作为除数）作为除数）S3：n被被i除，得余数除，得余数rS4：如果：如果r=0，表示，表示n能被能被i整除，则打印整除，则打印n“不

5、是素不是素数数”，算法结束；否则执行，算法结束；否则执行S5S5：i+1=iS6：如果：如果in-1，返回，返回S3；否则打印；否则打印 n “是素数是素数”，然后结束。然后结束。9.3 算法的特点1、有穷性：一个算法应包含有限的操作步骤，而不能是无限的。2、确定性：算法中每一个步骤都应当是确定的，不能含糊、模棱两可。3、有零个或多个输入。4、有一个或多个输出。5、有效性。一、算法的特征 二、算法设计的要求二、算法设计的要求 1 正确性。正确性。算法应当满足具体问题的需求。“正确”一词 的含义在通常的用法中有很大差别，大体 可分为四个层次： a. 程序不含语法错误。 b. 程序对几组输入数据能

6、够得出满足规格说明 要求的结果。 c. 程序对于精心选择的典型、苛刻而带有刁 难性的几组输入数据能够得出满足规格说 明要求的结果。 d. 程序对于一切合法的输入数据都能产生满足 规格说明要求的结果。 112 可读性。可读性。算法主要是为了人的阅读和交流，可读性 好有助于 人对算法的理解。3 健壮性。健壮性。当输入数据非法时，算法也能适当做出 反应或进行处理，而不会产生莫名其妙 的输出结果。4 效率与低存储量需求。效率与低存储量需求。效率指算法执行的时间； 存储量需求算法执行过程中所需要的 最大存储空间。二、算法设计的要求二、算法设计的要求12 .4 算法的描述。算法的描述。 常用的描述工具有：

7、自然语言，流程图，N-S结构化流程图，PAD图，伪代码等。 1. 程序流程图程序流程图 流程图是一种传统的算法表示法，它利用几何图形框来代表各种不同性质的操作，用流程线来指示算法的执行方向。由于它简单直观，所以应用广泛，特别是在早期语言阶段，只有通过流程图才能简明地表述算法，流程图成为程序员们交流的重要手段，直到结构化的程序设计语言出现，对流程图的依赖才有所降低。13处理框判断框起始框流程线输入/输出框常用符号：常用符号：14例1 打印x的绝对值15例例2 求求5!的算法用流程图表示的算法用流程图表示16例例3 将将50名学生中成绩在名学生中成绩在80分以上者的学号和成绩打印出来分以上者的学号

8、和成绩打印出来17例例4 判断素数的算法判断素数的算法18三种基本结构：顺序结构，选择结构，循环结构。AB顺序结构PBA是否选择结构P1A是否当型循环BP2否是直到型循环三种基本结构有以下共同特点： 1 只有一个入口。 2 只有一个出口。 3 结构内的每一部分都有机会被执行到， 且路径是唯一的。 4 结构内没有死循环。192. N-S结构化流程图结构化流程图 N-S图完全去掉了流程图中的控制流程的流线和箭头。AB顺序结构A当P1当型循环ABYNP选择结构B直到P2直到型循环203. 用计算机语言表示算法例1 将（求5!）的算法用C语言表示。main( )int i，t;t=1;i=2;while(i=5)t=t*i;i=i+1;prin