C语言课件program_2

1、第2章 算法-程序的灵魂主要内容o 2.0 程序程序o 2.1 算法的概念算法的概念o 2.2 简单算法举例简单算法举例o 2.3 算法的特性算法的特性o 2.4 怎样表示一个算法怎样表示一个算法o 2.5 程序化设计方法程序化设计方法 o 练习练习c-22.0 程序程序o 问题分析问题分析n利用计算机处理问题的过程利用计算机处理问题的过程程序设计的难程序设计的难点在哪里？点在哪里？ 算法算法程序设计的程序设计的“灵魂灵魂”o 程序的内容程序的内容n （沃思（沃思 Nikiklaus Wirth）: 数据结构数据结构 + 算法算法 = 程序程序 (data structure) (algori

2、thm)n 程序程序=算法算法+数据结构数据结构+程序设计方法程序设计方法+语言工具和环境语言工具和环境o 数据结构：对数据的描述，即在程序中要指定数据的类数据结构：对数据的描述，即在程序中要指定数据的类型和数据的组织形式型和数据的组织形式o 算法：对操作的描述，即操作步骤算法：对操作的描述，即操作步骤n 对同一个问题，可以有不同的解题方法和步骤对同一个问题，可以有不同的解题方法和步骤n 为了有效地进行解题，需要保证算法正确，并选择合适的算为了有效地进行解题，需要保证算法正确，并选择合适的算法法n 特性：有穷性、确定性、有特性：有穷性、确定性、有0个或多个输入、有个或多个输入、有1个或多个个或

3、多个输出、有效性输出、有效性o 上述四个方面中：上述四个方面中： 算法是灵魂算法是灵魂 数据结构是加工对象数据结构是加工对象 语言是工具语言是工具 编程需要采取合适的方法编程需要采取合适的方法o 算法解决算法解决做什么做什么和和怎么做怎么做的问题的问题o 程序中的按一定顺序列出的操作语句，就是算法的体现程序中的按一定顺序列出的操作语句，就是算法的体现o 通过本门课，大家学会使用通过本门课，大家学会使用c语言的语法编写不太复杂语言的语法编写不太复杂的的c程序程序o 广义的说广义的说,为解决一个问题而采取的方法和步骤为解决一个问题而采取的方法和步骤,就称为算法就称为算法o 计算机算法计算机算法n

4、用计算机解决问题的步骤用计算机解决问题的步骤n 分类分类o 数值运算算法数值运算算法o 非数值运算算法非数值运算算法例例2.1 2.1 求求1 12 23 34 45 5 改进算法：改进算法：设设t t为被乘数，为被乘数，i i为乘数，用循环为乘数，用循环法求解法求解S1: S1: 使使 t=1t=1S2: S2: 使使 i=2i=2S3: S3: 使使 ti,i,乘积仍然放在变量乘积仍然放在变量 t t中，可表示为中，可表示为t ti it tS4: S4: 使使i i的值的值+1+1，即，即i+1i+1i iS5: S5: 如果如果i5, i5, 返回重新执行返回重新执行 步骤步骤S3S3

5、以及其后的以及其后的S4S4和和S5S5； 否则，算法结束。最后得到否则，算法结束。最后得到 t t的值就是的值就是5 5！的值！的值 原始方法：原始方法：步骤步骤1 1：先求：先求1 12 2，得到结果，得到结果2 2。步骤步骤2 2：将步骤：将步骤1 1得到的乘得到的乘 积积2 2乘以乘以3 3，得到结果，得到结果6 6。步骤步骤3 3：将：将6 6再乘以再乘以4 4，得，得2424。步骤步骤4 4：将：将2424再乘以再乘以5 5，得，得120120。若求若求 1 12 21 1000000，怎么做？怎么做？思考：思考： 若求若求 1 13 35510011001，怎么做？怎么做？例例2

6、.2 2.2 有有5050个学生，要求将他们之中成绩在个学生，要求将他们之中成绩在8080分以上者打印出来分以上者打印出来设设i：第个学生学号：第个学生学号 i：第个学生成绩：第个学生成绩算法如下：算法如下： S1: 1i S1: 1i S2: S2: 如果如果 g gi8080，则输出，则输出 n ni和和 g gi i，否则不输出，否则不输出 S3: i+1i S3: i+1i S4: S4: 若若i50, i50, 返回返回S2S2，否则，算法结束，否则，算法结束例例2.3 2.3 判定判定2000 25002000 2500年中的每一年是否闰年，将结果输出。年中的每一年是否闰年，将结果

7、输出。闰年的条件：闰年的条件： 能被能被4整除整除: 但不能被但不能被100整除的年份；整除的年份； 能被能被100整除，又能被整除，又能被400整除的年份；整除的年份； o 算法如下：算法如下： 设设y为被检测的年份。为被检测的年份。o S1: 2000yo S2: 若若y不能被不能被4整除，则输出整除，则输出y“不是闰年不是闰年”，o 然然 后转到后转到S6o S3: 若若y能被能被4整除，不能被整除，不能被100整除，则输整除，则输o 出出y“是闰年是闰年”，然后转到，然后转到S6o S4: 若若y能被能被100整除，又能被整除，又能被400整除，输整除，输o 出出y“是闰年是闰年” 否

8、则输出否则输出y“不是闰年不是闰年”，o 然后转到然后转到S6o S5: 输出输出y“不是闰年不是闰年”o S6: y+1yo S7: 当当y2500时时, 返回返回S2继续执行，否则，算法结束继续执行，否则，算法结束2.3 算法的特性o 有穷性：一个算法应包含有限的操作步骤而不能是无限的有穷性：一个算法应包含有限的操作步骤而不能是无限的o 确定性：算法中每一个步骤应当是确定的，而不能应当是含确定性：算法中每一个步骤应当是确定的，而不能应当是含糊的、模棱两可的不应产生歧义性糊的、模棱两可的不应产生歧义性o 输入输入:有零个或多个输入有零个或多个输入n输入是指在执行算法时需要从外界取得必要的信息

9、输入是指在执行算法时需要从外界取得必要的信息o 输出输出:有一个或多个输出有一个或多个输出n算法的目的是为了求解，算法的目的是为了求解，“解解”就是输出就是输出o 有效性：算法中每一个步骤应当能有效地执行，并得到确定有效性：算法中每一个步骤应当能有效地执行，并得到确定的结果的结果 abc3 3个数中最大的数个数中最大的数算法：求3个数中最大的数2.4 怎样表示一个算法o 怎样表示一个算法？怎样表示一个算法？n 用自然语言表示用自然语言表示n 用流程图表示（传统流程图和用流程图表示（传统流程图和N-S图）图）n 用伪代码表示用伪代码表示n 用计算机语言表示用计算机语言表示n 结构化程序的三种基本

10、结构结构化程序的三种基本结构 顺序、选择、循环顺序、选择、循环o 用自然语言表示算法用自然语言表示算法n 自然语言指人们日常使用的语言，如汉语、英语等自然语言指人们日常使用的语言，如汉语、英语等n 用自然语言表示算法的特点：用自然语言表示算法的特点：o 通俗易懂，但不严谨，容易产生歧义通俗易懂，但不严谨，容易产生歧义n 除非问题很简单，一般不用自然语言描述算法除非问题很简单，一般不用自然语言描述算法o 用流程图表示算法用流程图表示算法n 用传统流程图表示用传统流程图表示n 用用N-S流程图表示流程图表示 程序设计的过程，实程序设计的过程，实际上就是确定解决问题际上就是确定解决问题的详细步骤，而

11、这些步的详细步骤，而这些步骤通常称为骤通常称为流程流程。o 用传统流程图表示用传统流程图表示算法算法n 流程图采用一些图流程图采用一些图形框表示算法要表形框表示算法要表述的各种操作述的各种操作 直观、形象直观、形象n ANSI规定的常用规定的常用流程图符号流程图符号 起止框起止框 输入输出框输入输出框 判断框判断框 处理框处理框 连接点连接点 流程线流程线 注释框注释框例例2.6 2.6 将例将例2.1 2.1 求求1 12 23 34 45 5 的算法用流程图表示的算法用流程图表示 改进算法：改进算法：设设t t为被乘数，为被乘数，i i为乘数，用循环为乘数，用循环法求解法求解S1: S1:

12、 使使 t=1=1S2: S2: 使使 i=2i=2S3: S3: 使使 ti,i,乘积仍然放在变量乘积仍然放在变量 t t中，可表示为中，可表示为t ti it tS4: S4: 使使i i的值的值+1+1，即，即i+1i+1i iS5: S5: 如果如果i5, i5, 返回重新执行返回重新执行 步骤步骤S3S3以及其后的以及其后的S4S4和和S5S5； 否则，算法结束。最后得到否则，算法结束。最后得到 t t的值就是的值就是5 5！的值！的值 开始开始1=t2=it i=t i+1=ii5真真结束结束假假输出输出t的值的值o 传统流程图的特点传统流程图的特点n 传统流程图的构成传统流程图的

13、构成o 表示相应操作的框表示相应操作的框o 带带箭头箭头的流程线的流程线o 框内外必要的文字说明框内外必要的文字说明n 优点优点 o 直观形象直观形象n 弊端弊端o 占用篇幅较多占用篇幅较多o 流程线使用无限制，乱无头绪（流程线使用无限制，乱无头绪（BS型算法）型算法）o 3种基本结构种基本结构: 顺序、选择、循环结构顺序、选择、循环结构用这用这3种基本结构作为表示一个良好算法的基本单元种基本结构作为表示一个良好算法的基本单元n 顺序结构顺序结构虚线框内是一个顺序结构。虚线框内是一个顺序结构。A A、B B两个框是顺序执行的：两个框是顺序执行的：按图中所画的框的顺序，先按图中所画的框的顺序，先

14、执行执行A A操作，再执行操作，再执行B B操作。操作。n 选择结构（选取结构选择结构（选取结构/分支结构）分支结构）虚线框内是一个选择结构。虚线框内是一个选择结构。此结构必须包含一个判断框，框中写有此结构必须包含一个判断框，框中写有一个条件，根据给定的条件是否成立，一个条件，根据给定的条件是否成立，从而选择执行从而选择执行A A框框或是或是B B框。框。例如：条件可以是例如：条件可以是i101i101ab条件条件PA成立成立不成立不成立B B操作操作为空时，为空时，画成直画成直线线ab虚线框内是一个直到型虚线框内是一个直到型循环结构。循环结构。先执行先执行A A框中的操作；框中的操作；执行完

15、执行完A A操作后，判条件操作后，判条件P P是否成立；是否成立；如果不成立，继续执行如果不成立，继续执行A A操作；操作；如此反复执行如此反复执行A A框中的操框中的操作，直到条件作，直到条件P P成立为止，成立为止，从从b b点脱离本循环结构。点脱离本循环结构。条件条件P2A成立成立不成立不成立ab山无棱山无棱, ,天地合天地合, ,乃敢与君绝乃敢与君绝! ! n 循环结构循环结构o 直到型直到型-until型型o 当型当型-while型型虚线框内是一个当型循环虚线框内是一个当型循环结构。结构。当给定的条件成立时，执当给定的条件成立时，执行行A A框中的操作；框中的操作；执行完执行完A A

16、操作后，判条件操作后，判条件P P是否成立；是否成立；如果仍成立，继续执行如果仍成立，继续执行A A操操作；作；如此反复执行如此反复执行A A框中的操作，框中的操作，直到条件直到条件P P不成立为止，从不成立为止，从 b b点脱离本循环结构。点脱离本循环结构。当山峰没有棱角的时候当山峰没有棱角的时候 当河水不在流当河水不在流当时间停住日月不分当时间停住日月不分 当天地万物化为虚当天地万物化为虚有有 我还是不能和你分手我还是不能和你分手 o 结构化程序设计方法结构化程序设计方法n三种基本结构的共同点三种基本结构的共同点o 只有一个入口只有一个入口o 只有一个出口只有一个出口o 结构内每一部分都有

17、机会被执行到结构内每一部分都有机会被执行到o 结构内不存在结构内不存在死循环死循环。 如条件永远成立时，就成了如条件永远成立时，就成了死死循环循环“ 注意：基本结构并不只限于上面注意：基本结构并不只限于上面3种，只要符合上述的四种，只要符合上述的四个特点的结构，都称为基本结构个特点的结构，都称为基本结构n已经证明，用以上三种基本结构顺序组成的算法结构，可以已经证明，用以上三种基本结构顺序组成的算法结构，可以解决任何复杂的问题解决任何复杂的问题n由基本结构构成的算法属于由基本结构构成的算法属于“结构化结构化”的算法的算法,它不存在无规律它不存在无规律的转向，只在本基本机构内才允许存在分支和向前或

18、向后的的转向，只在本基本机构内才允许存在分支和向前或向后的跳转跳转o 用用N-S流程图表示算法流程图表示算法n 用基本结构的顺序组合可以表示任何复杂的算法结用基本结构的顺序组合可以表示任何复杂的算法结构，那么，就可去掉流程线，避免了随意的跳转构，那么，就可去掉流程线，避免了随意的跳转n 1973年两名美国学者提出了一种新的流程图形式年两名美国学者提出了一种新的流程图形式，并用二人名字的第一个字母组合命名了该流程图，并用二人名字的第一个字母组合命名了该流程图。即。即N-S流程图，也称盒图流程图，也称盒图n 三种基本结构的表示三种基本结构的表示AB顺序结构顺序结构选择结构选择结构 P成立成立 AB

19、不成立不成立当型循环结构当型循环结构A P1直到型循环结构直到型循环结构A P2例例2.11 2.11 将例将例2.1 2.1 求求1 12 23 34 45 5 的算法用的算法用N - SN - S图表示图表示 改进算法：改进算法：设设t t为被乘数，为被乘数，i i为乘数，用循环为乘数，用循环法求解法求解S1: S1: 使使 t=1t=1S2: S2: 使使 i=2i=2S3: S3: 使使 ti,i,乘积仍然放在变量乘积仍然放在变量 p p中，可表示为中，可表示为t ti itS4: S4: 使使i i的值的值+1+1，即，即i+1i+1i iS5: S5: 如果如果i5, i5, 返回

20、重新执行返回重新执行 步骤步骤S3S3以及其后的以及其后的S4S4和和S5S5； 否则，算法结束。最后得到否则，算法结束。最后得到 t t的值就是的值就是5 5！的值！的值 这两个操这两个操作之间是作之间是顺序关系顺序关系1= t2=i直到直到 i5 t x i= t i+1=i输出输出t的值的值这是一这是一个顺序个顺序结构结构这是一这是一个循环个循环结构结构上述算法由基上述算法由基本结构组成本结构组成ABn N-S图表示算法的优点图表示算法的优点o 比文字描述直观、形象、比文字描述直观、形象、 易于理解易于理解o 比传统流程图紧凑易画。尤其是它废除了流程线，整个比传统流程图紧凑易画。尤其是它

21、废除了流程线，整个算法结构是由各个基本结构按顺序组成的，算法结构是由各个基本结构按顺序组成的，N-S流程流程图中的上下顺序就是执行时的顺序图中的上下顺序就是执行时的顺序o 用用N-S图表示的算法都是结构化的算法，因为它不可图表示的算法都是结构化的算法，因为它不可能出现流程无规律的跳转，而只能自上而下地顺序执行能出现流程无规律的跳转，而只能自上而下地顺序执行n 小结小结o 一个结构化的算法是由一些基本结构顺序组成的。在基一个结构化的算法是由一些基本结构顺序组成的。在基本结构之间不存在向前或向后的跳转，流程的转移只存本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构范围之内在于一个基

22、本结构范围之内(如循环中流程的跳转如循环中流程的跳转)o 一一 个非结构化的算法可以用一个等价的结构化算法代个非结构化的算法可以用一个等价的结构化算法代替，其功能不变替，其功能不变 。如果一个算法不能分解为若干个基。如果一个算法不能分解为若干个基本结构，则它必然不是一个结构化的算法本结构，则它必然不是一个结构化的算法o 用伪代码表示算法用伪代码表示算法n 伪代码伪代码o 是用介于自然语言和计是用介于自然语言和计算机语言之间的文字和算机语言之间的文字和符号来描述算法符号来描述算法o 优点优点 书写方便，格式紧凑，书写方便，格式紧凑，易懂，易改，便于向计易懂，易改，便于向计算机语言过渡算机语言过渡

23、o 缺点缺点 不如流程图直观，可能不如流程图直观，可能会出现逻辑上的错误会出现逻辑上的错误例例2.16 2.16 将例将例2.1 2.1 求求1 12 23 34 45 5 的算法用伪的算法用伪代码表示代码表示 开始开始 置置t t的初值为的初值为1 1 置置i i的初值为的初值为2 2 当当i = 5 i = 5 时，执行下面的时，执行下面的操作：操作： 使使 t=t x it=t x i 使使 i=i+1i=i+1 输出输出 t t 的值的值结束结束o 用计算机语言表示算法用计算机语言表示算法实现算法实现算法n 只有用计算机语言描述的算法才能被计算机的编译只有用计算机语言描述的算法才能被计

24、算机的编译环境识别，并被处理、执行环境识别，并被处理、执行n 用计算机语言表示算法必须严格遵守所用语言的语用计算机语言表示算法必须严格遵守所用语言的语法规则法规则n 前面几种描述算法的方法对文字等格式要求不严，前面几种描述算法的方法对文字等格式要求不严，一般来说，只要能示意就行一般来说，只要能示意就行例例2.18 2.18 将例将例2.1 6 2.1 6 表示的求表示的求5 5！的算法用！的算法用C C语言表示语言表示 #include int main() int t,i; t=1; i=2; while(i=5) t=t*i; i=i+1; printf(“%dn”,t); return

25、0;n 程序设计步骤程序设计步骤o 分析问题分析问题 o 确定解决方案确定解决方案o 建立数学模型建立数学模型o 设计算法设计算法o 用计算机语言描述算法（即写出源程序）用计算机语言描述算法（即写出源程序）o 上机调试源程序：经过编辑、编译、连接、运行，得到上机调试源程序：经过编辑、编译、连接、运行，得到可执行的程序。（参看可执行的程序。（参看P13图图1.2 ）o 运行程序，得到需要的结果运行程序，得到需要的结果n 说明：说明： 写出了写出了C程序，仍然只是描述了算法，并未实现算程序，仍然只是描述了算法，并未实现算法。只有运行程序才是实现算法。应该说，用计算法。只有运行程序才是实现算法。应该

26、说，用计算机语言表示的算法是计算机能够执行的算法机语言表示的算法是计算机能够执行的算法o 一个结构化程序一个结构化程序 就是用高级语言表示的结构化就是用高级语言表示的结构化算法。用三种基本结构组成的程序必然是结构算法。用三种基本结构组成的程序必然是结构化的程序，这种程序便于编写、便于阅读、便化的程序，这种程序便于编写、便于阅读、便于修改和维护于修改和维护o 结构化程序设计强调程序设计风格和程序结构结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构的规范化，提倡清晰的结构o 结构化程序设计方法的基本思路结构化程序设计方法的基本思路 把一个复杂问题的求解过程把一个复杂问题的求解过程 分阶段进行，每个阶段分阶段进行，每个阶段处理的问