第2A章 程序的灵魂——算 法(zym)

1、1第第2-A章章 程序的灵魂程序的灵魂 算法算法2教学目的1、掌握算法的概念和算法的特性。、掌握算法的概念和算法的特性。2、掌握算法的表示方法。、掌握算法的表示方法。3、掌握结构化程序设计。、掌握结构化程序设计。3 主要内容主要内容1、算法的概念、特点。、算法的概念、特点。2、结构化程序的三种基本结构和、结构化程序的三种基本结构和 N-S (结构化流程图)流程图。流程图。重点部分重点部分1、结构化程序的三种基本结构模式。、结构化程序的三种基本结构模式。2、N-S结构流程图的作用。结构流程图的作用。4利用计算机解决问题的过程问题问题连接程序连接程序编辑程序编辑程序编译程序编译程序5一个程序应包括

2、两个方面内容：一个程序应包括两个方面内容：(1)对数据的描述：对数据的描述：即对程序中指定加工（运算）的各种类数据在计算机中的存储与组织形式的描述。高级语言中将这一复杂问题转换为简单、易为人们所接受的形式，即数据类型数据类型描述。(2) 对操作的描述：对操作的描述：即解决问题（加工数据）的方法、步骤的描述，即算法算法描述。6算法是设计程序进行问题求解的关键算法是设计程序进行问题求解的关键 数据数据：加工（运算）的对象； 算法算法（操作）：对数据进行加工处理，以得到期望的结果的方法。 程序设计：程序设计：“数据结构”和“操作步骤（即算法）”转化为程序程序描述设计程序的关键。数据结构数据结构与算法

3、算法相互影响：同一问题所设计的数据结构不同，可能会导致不同的算法，将对程序的执行效率产生深远影响。因此，著名计算机科学家沃思（Nikiklaus Wirth）提出一个公式： 数据结构数据结构+算法算法程序程序算法算法设计程序的关键设计程序的关键7程序包括：n数据描述数据描述数据结构数据结构n操作描述操作描述算法算法(厨师做菜过程中，配料与菜谱的关系厨师做菜过程中，配料与菜谱的关系)程序程序=算法算法+数据结构数据结构+程序设计方法程序设计方法+ 计算机语言计算机语言程序程序=算法算法+数据结构数据结构 沃斯沃斯82.1算法的概念n作任何事情都需要步骤作任何事情都需要步骤n广义地说，算法是广义地

4、说，算法是为解决一个问题而采取的为解决一个问题而采取的方法和步骤方法和步骤。n本书中的算法本书中的算法计算机算法。计算机算法。n“由计算机执行由计算机执行”n分类：分类：n数值算法数值算法求方程的根求函数的定积分n非数值算法非数值算法图书检索人事管理行车调度管理92.2 简单算法举例例例2.1-I 求求1234 5n人工解题人工解题(自然语言自然语言)通俗易懂，但文字冗长。如果求通俗易懂，但文字冗长。如果求1231000，要写，要写999个步骤，怎个步骤，怎么办？么办？步骤步骤1：先求：先求12，得到结果，得到结果2步骤步骤2：将步骤：将步骤1得到的乘积得到的乘积2再乘以再乘以3，得到，得到6

5、步骤步骤3：将：将6再乘以再乘以4，得，得24步骤步骤4：将：将24再乘以再乘以5，得，得12010n用计算机解题用计算机解题(自然语言自然语言) 设两个变量，设两个变量，p代表被乘数，代表被乘数，i代表乘数，将每代表乘数，将每一步的乘积放在被乘数变量中。一步的乘积放在被乘数变量中。S1：1=pS2：2=iS3：pipS4：i1iS5：若：若i=5，返回，返回S3；否则，输出；否则，输出p值，结束。值，结束。 11例2.1-II 求1357911n算法只需要做很少的改动。算法只需要做很少的改动。 (自然语言自然语言) n 思考：当思考：当S5改为：若改为：若i pS2：3= iS3：pipS4

6、：i2iS5：若：若i=11，返回，返回S3；否则，输出；否则，输出p值，结束。值，结束。12例2.2判定20002500 年中的每一年是否为闰年，将结果输出。n闰年的条件(满足如下两个条件之一)n能被4整除,但不能被100整除.如:1996,2004n能被100整除, 又能被400整除.如:1600,2000n自然语言描述算法 13S1：2000 yS2: 若若y不能被不能被4整除，则输出整除，则输出y“不是闰年不是闰年”。然后转到。然后转到S6。S3：若：若y能被能被4整除，不能被整除，不能被100整除，则输出整除，则输出y“是闰年是闰年”。然后转到然后转到S6。S4：若：若y能被能被10

7、0整除，又能被整除，又能被400整除，则输出整除，则输出y“是闰是闰年年”；否则输出；否则输出y“不是闰年不是闰年”。然后转到。然后转到S6。S5：输出：输出y“不是闰年不是闰年”S6： y+1yS7: 当当y=2500时，转时，转S2继续执行，否则算法停止。继续执行，否则算法停止。分析：设y为被检测的年份。14例例2.3 对一个大于或等于对一个大于或等于3的正整数，判断它是不的正整数，判断它是不是一个素数。是一个素数。n素数素数：除了：除了1和本身之外，不能被其他任何整数整除和本身之外，不能被其他任何整数整除的数。的数。n判断规则判断规则：将：将n作为被除数作为被除数,将将2到到(n-1)各

8、个整数轮流各个整数轮流作为除数作为除数,如果都不能被整除如果都不能被整除,则则n是素数。是素数。n算法描述算法描述nS1：输入：输入n的值的值nS2: 2 i nS3：n被被i 除，得余数除，得余数r （n/i）nS4：如果：如果r=0，可以整除，则打印，可以整除，则打印n“不是素数不是素数”，然后结束。，然后结束。nS5：i +1 inS6：如果：如果i y ?开始开始输入输入x和和y结束结束输出输出z例如: 输入x和y的值，然后比较x和y的值，如果x大于y，则输出x的值，否则输出y的值。23开始1=tt*i=ti5结束N2=ii=i+1Y例2.6 用流程图表示例2.1（求5！)图2.624

9、例2.8 将例2.2判定闰年的算法用流程图表示。NNYNy能被能被400整除整除输出输出y“是闰年是闰年”Y开始开始2000 = yy能被能被4整除整除输出输出y“是闰年是闰年”y能被能被100整除整除结束结束y+1 = yy2500输出输出y“不是闰年不是闰年”输出输出y“不是闰年不是闰年”NYY图2.1025n定义n顺序结构：按照书写顺序依次执行语句。n选择结构：按照条件判断选择执行语句。n循环结构：通过条件控制循环执行语句。顺序选择选择2.4.3 三种基本结构26循环27当型循环 直到型循环 图2.18图2.1928n三种基本结构的共同点三种基本结构的共同点n只有一个入口和一个出口只有一

10、个入口和一个出口n结构内的每一个框都有机会被执行结构内的每一个框都有机会被执行n结构内没有死循环结构内没有死循环292.4.4结构化流程图（N-S）表示算法顺序、选择、循环结构顺序顺序 选择选择 当型循环当型循环 直到型循环直到型循环30图2.28每个结构中的框都可以是一个简单操作，也可以是每个结构中的框都可以是一个简单操作，也可以是三个基本结构之一。三个基本结构之一。选择选择当型循环当型循环31l N-S N-S结构化流程图是对传统流程图的改进。结构化流程图是对传统流程图的改进。l 在在N-SN-S结构化流程图中取消了流程线，规结构化流程图中取消了流程线，规定算法只能自上而下执行，算法的全部

11、描述定算法只能自上而下执行，算法的全部描述过程封闭在一个方框内。过程封闭在一个方框内。l N-SN-S结构化流程图规定算法只允许由顺序结构化流程图规定算法只允许由顺序结构、选择结构和循环结构结构、选择结构和循环结构3 3种基本结构构成。种基本结构构成。32图2.29例2.11用N-S图表示例2.1的求5！。33图2.32例例2.13用用N-S图图表示例表示例2.3判定判定2000-2500间的间的闰年。闰年。342.4.6 计算机语言表示算法n严格遵守所用语言的语法规则n例2.20：用C语言表示5！main()int i,t;t=1;i=2;while(i=5)t=t*i;i=i+1;printf(“%d”,t);352.5 结构化程序设计方法n如果一个程序仅包含三种基本结构（由这些基本结构如果一个程序仅包含三种基本结构（由这些基本结构顺序组成），则称为顺序组成），则称为结构化程序结构化程序。n结构化程序设计方法的基本思路：把一个复杂问题的结构化程序设计方法的基本思路：把一个复杂