1、1第 二 章 程序的灵魂- 算法（algorithm ）2主要内容本章主要介绍算法的思想及算法的表示方法。一、 算法在程序中的地位二、 算法的定义三、 简单算法举例四、 算法的表示五、 程序设计步骤3n一个程序应包括的两个方面： （1）对数据的描述 在程序中要指定数据的类型和数据的组织形式，即数据的结构。 （2）对操作的描述 即操作步骤，也就是算法。n著名计算机科学家沃斯提出了一个公式： 数据结构 + 算法 = 程序一、算法在程序中的地位4n程序 = 数据结构 + 算法 +程序设计方法+语言工具和环境n上述四个方面中： 算法是灵魂； 数据结构是加工对象； 语言是工具； 编程需要采取合适的方法。
2、n算法解决做什么和怎么做的问题。n程序中的按一定顺序列出的操作语句，是算法的体现。5二、算法的定义及特性n计算机算法：用计算机解决特定问题的步骤，即计算机算法。n计算机算法分类：q数值运算算法：求解数值；q非数值运算算法：事务管理领域。6n算法的5个特性：q 有穷性:一个算法必须在执行有穷步之后结束q 确定性:算法的每一步必须是确切定义的。对于相同 输入必须得到相同结果 .q 输入:有零个或多个输入q 输出:有一个或多个输出q 有效性:算法的每一步都是能够实现的，即可操作的7三、简单算法举例n例1：求1X2X3X4X5 最原始的方法： S1：先 求12, 得结果2。 S2： 将S1步得到的结果
3、再乘以3, 得结果6。 S3： 将S2步得到的结果再乘以4, 得结果24。 S4： 将第S3步得到的结果再乘以5, 得120。即最后结果。思考:如果按照此方法，求123.100，要写多少步？上述计算方法不可取！99步！8n改进的方法（或通用的方法）： 先设两个变量p和i，p代表被乘数，i代表乘数。并且将每一步乘积直接放入被乘数变量p中。用循环算法求结果。 S1：令p=1 S2：令i=2 S3：使p x i,并将乘积放入p中。通常表示为 p i = p S4：使 i 的值加1，表示为 i+1= i S5：如果i5 ，返回到S3继续向下执行；否则算法结束。 p中的值即最后结果。9n思考: 如何采用
4、此方法求100!10 先设两个变量p和i，p代表被乘数，i代表乘数。并且将每一步乘积直接放入被乘数变量p中。用循环算法求结果。 S1：令p=1 S2：令i=3 S3：使p i,并将乘积放入p中。通常表示为p i = p S4：使 i 的值加2，表示为 i+ 2 = i S5：如果i 13，返回到s3继续向下执行；否则 算法结束。p中的值即最后结果。n如果将题目改为求1 x 3 x 5 x 7 x 9 x 11x 13， 该如何设计算法？11思考:n采用前面的方法如何求579.21.12例2：有两个数a,b，按大小顺序打印它们。 S1： 输入a,b的值； S2： 如果ab,则先打印a，再打印b；
5、 否则，先打 印b，再 打印a；算法结束。13例3：有50个学生，要求将他们之中成绩在80分以上者打印出来。n假设：n表示学生学号，ni表示第i个学生学号；g表示学生成绩，gi表示第i个学生成绩；nS1: 1 = inS2: 如果gi 80，打印ni和gi ，否则不打印nS3: i+1 = inS4:若i50, 返回S2，否则，结束。14四、算法的表示n用自然语言表示n用流程图表示（传统流程图和N-S图）n用伪代码表示n用计算机语言表示 15（一）用自然语言表示算法n前面例1、2和3的算法都是用自然语言写的。n自然语言指人们日常使用的语言，如汉语、英语等。n用自然语言表示算法的特点：通俗易懂，
6、但不严谨，容易产生歧义。n除很简单问题，一般不用自然语言描述算法。16（二） 用流程图表示算法n流程图采用一些图形框表示算法要表述的各种操作。n常用的流程图符号：17n一个流程图包括：表示相应操作的框；带箭头的流程线；框内外必要的文字说明。18用流程图表示如下的算法计算1 x 3x5x.x11x的值 S1：令p=1 S2：令i=1或i= S3：使p x i,并将乘积放入p中。通常表示为p x i = p S4：使 i 的值加2，表示为 i+ 2 = i S5：如果i 1，返回到S3继续向下执行；否则算法结束。开始1=p1=ip i=p i+2=ii1真结束假输出p的值（）（） （）（）19请将
7、例2的算法（如下）用流程图来表示出来。有两个数a,b，按大小顺序打印它们。 1： 输入a,b的值； 2： 如果ab,则先打印a，再打印b；否则，先打印b，再 打印a；算法结束。 20真假开始ab结束输出b,a的值输入a,b的值输出a,b的值（）（）21例3的算法用流程图来表示n假设：n表示学生学号，ni表示第i个学生学号；g表示学生成绩，gi表示第i个学生成绩；S1: 1 = iS2: 如果gi 80，打印ni和 gi ，否则不打印S3: i+1 = iS4: 若i50, 返回S2，否 则，结束。22（三）三种基本结构顺序结构选择结构循环结构23n顺序结构： BA虚线框内是一个顺序结构。A、B
8、两个框是顺序执行的：按图中所画的框的顺序，先执行A操作，再执行B操作。24n选择结构也称为分支结构。虚线框内是一个选择结构。此结构包括一个选择框，框中写有一个条件，根据给定的条件是否成立，从而选择执行A框还是B框。例如：条件P可以是i101条件PAB成立不成立条件PA成立不成立B操作为空时，画成直线25n循环结构（当型-while型）虚线框内是一个当型循环结构。当给定的条件成立时，执行A框中的操作；执行完A操作后，判条件P是否成立；如果仍成立，继续执行A操作；如此反复执行A框中的操作，直到条件P不成立为止。条件PA成立不成立26n循环结构（直到型-until型）条件PA成立不成立虚线框内是一个
9、直到型循环结构。先执行A框中的操作；执行完A操作后，判条件P是否成立；如果不成立，继续执行A操作；如此反复执行A框中的操作，直到条件P成立为止。27请打印小于5的正整数事例1（直到(until)型循环）:开始结束28（四）结构化程序设计方法n三种基本结构的共同点：q只有一个入口；一个出口；q结构内每一部分都有机会被执行。q结构内不存在死循环。(如条件永远成立时，就成了死循环“)n用上述三种基本结构顺序组成的算法结构，可解决任何复杂问题。n只要符合上述的四个特点的结构，都称为基本结构。n由基本结构构成的算法属于结构化的算法29对例1算法的流程图的结构化分析计算1 x 3x5x.x101的值 S1
10、：令p=1 S2：令i=3 S3：使p x i,并将乘积放入p 中。即 p x i = p S4：使 i 的值加2，表示为 i+ 2 = i S5：如果i 不大于101，返回 到s3继续向下执行； 否则算法结束。p中的值 即最后结果。开始1=p3=ip i=p i+2=ii101真 Y结束假N输出p的值循环结构顺序结构30对例2算法的流程图的结构化分析有两个数a,b，按大小顺序打印它们。 s1： 输入a,b的值； s2： 如果ab,则先打印 a，再打印b；否则， 先打印b，再 打印a； 算法结束。 真假开始ab结束输出b,a的值输入a,b的值输出a,b的值选择结构31练习：2。4 （5）32n
11、用基本结构的组合表示算法，从而去掉了流程线。避免了随意的跳转。n1973年两名美国学者提出了一种新的流程图形式即N-S流程图，也称盒图。n三种基本结构的N-S图表示： P成立 AB（五）用N-S流程图表示算法AB不成立A当条件P成立时直到条件P成立A33前面的算法用N-S流程图来表示计算1 x 3x5x.x11的值 s1：令p=1 s2：令i=1 s3：使p x i,并将乘积放入p 中。表示为 p x i = p s4：使 i 的值加2，表示为 i+ 2 = i s5：如果i 不大于11，返回到 s3继续向下执行；否则算 法结束。p中的值即最后结 果。1=P1=i 直到 i11 p x i=p
12、 i+2=i打印P的值顺序结构循环结构34n假设：n表示学生学号，ni表示第i个学生学号；g表示学生成绩，gi表示第i个学生成绩；S1: 1 = iS2: 如果gi 80，打印ni和 gi ，否则不打印S3: i+1 = iS4: 若i50, 返回S2，否 则，结束。1=i 直到 i50gi 80 是 否打印ni，gii+1 = i例3的算法用N-S图表示35练习：2。5 （4）36（六）用伪码表示算法n伪码 是用一种介于自然语言和计算机语言之间的文字和符号来描述算法。n优点：q书写方便，格式紧凑，易懂，便于向计算机语言过渡。37上例：计算1 x 3x5x.x11的值n开始n 置p的初值为1n
13、 置i的初值为1n 当i 小于11时，执行下面的操作：n 使 p=p x in 使 i=i+2n 打印 p 的值n结束38练习2。6（4）39（七）用计算机语言表示算法n只有用计算机语言描述的算法才能被计算机的编译环境识别，并被处理、执行。n用计算机语言表示算法必须严格遵守所用语言的语法规则。n前面几种描述算法的方法对文字等格式要求不严，一般来说，只要能示意就行。40前面的算法用c语言表示/*求小于等于11的正整数的积*/#include void main() int p, i; p=1; i=1; while(i=11) p=p*i; i=i+2; printf(“%d”,p);41五、程序设计步骤1. 自顶向下2. 逐步细化3. 模块化设计4. 结构化编码42作业：nP37 2.4, 2.5, 2.6题中的 (2) 。
