经典c语言课件第2章算法.ppt

,第二章,程序的灵魂-算法,主要内容,2.1 算法的概念 2.2 简单算法举例 2.3 算法的特性 2.4 怎样表示一个算法 2.5 程序化设计方法,一个程序应包括两个方面的内容:,对数据的描述：数据结构(data structure) 对操作的描述：算法(algorithm),著名计算机科学家沃思提出一个公式: 数据结构 + 算法 = 程序,数据结构算法程序设计方法语言工具,完整的程序设计应该是:,上述四个方面中： 算法是灵魂； 数据结构是加工对象； 语言是工具； 编程需要采取合适的方法。 算法解决“做什么“和“怎么做“的问题。 程序中的按一定顺序列出的操作语句，就是算法的体现。 通过本门课，大家学会使用c语言的语法编写不太复杂的c程序。,算法的概念,用计算机解决问题的步骤，即计算机算法。,例2.1 求12345,改进算法： S1: 使t=1 S2: 使i=2 S3: 使ti,乘积仍然放在变量 t中，可表示为tit S4: 使i的值+1，即i+1i S5: 如果i5, 返回重新执行 步骤S3以及其后的S4和S5； 否则，算法结束。,原始方法： 步骤1：先求12， 得到结果2。 步骤2：将步骤1得到的乘 积2乘以3，得到 结果6。 步骤3：将6再乘以4，得24。 步骤4：将24再乘以5，得 120。,i：第个学生学号 i：第个学生成绩,S1: 1i S2: 如果gi80，则打印ni和gi，否则不打印 S3: i+1i S4: 若i50, 返回S2，否则，结束。,例2.2 有50个学生，要求将他们之中成绩在80分以上者打印出来。,闰年的条件： 能被4整除，但不能被100整除的年份； 能被100整除，又能被400整除的年份；,例2. 判定2000 2500年中的每一年是否闰年，将结果输出。,S1: 2000y S2: 若y不能被4整除，则输出y“不是闰年”， 然 后转到S6 S3: 若y能被4整除，不能被100整除，则输 出y“是闰年”，然后转到S6 S4: 若y能被100整除，又能被400整除，输 出y“是闰年” 否则输出y“不是闰年”， 然后转到S6 S5: 输出y“不是闰年”。 S6: y+1y S7: 当y2500时, 返回S2继续执行，否则， 结束。,C程序设计 第二章 程序的灵魂算法,例2. 求,S1: sigh=1 S2: sum=1 S3: deno=2 S4: sigh=(-1)sigh S5: term= sigh(1/deno ) S6: sum=sum+term S7: deno= deno +1 S8:若deno100，返回S4；否则，结束。,算法的特性,有穷性：一个算法应包含有限的操作步骤而不能是无限的 确定性：算法中每一个步骤应当是确定的，而不能应当是含糊的、模棱两可的 输入:有零个或多个输入 输出:有一个或多个输出 有效性：算法中每一个步骤应当能有效地执行，并得到确定的结果,小结：,流程图是表示算法的较好的工具。一个流程图包括以下几部分 ： (1)表示相应操作的框； (2)带箭头的流程线； (3)框内外必要的文字说明。,算法的表示,用自然语言表示 用流程图表示（传统流程图和N-S图） 用伪代码表示 用计算机语言表示 结构化程序的三种基本结构： 顺序、选择、循环结构,（一）用自然语言表示算法,上节中讨论的例1和例2的算法是用自然语言写的。 自然语言指人们日常使用的语言，如汉语、英语等。 用自然语言表示算法的特点：通俗易懂，但不严谨，容易产生歧义。 除非问题很简单，一般不用自然语言描述算法。,（二） 用流程图表示算法,流程图采用一些图形框表示算法要表述的各种操作。 美国国家标准化协会ANSI规定了一些常用的流程图符号： 起止框 处理框 输入输出框 流程线 或 判断框 连接点 注释,开始,结束,例1的算法用流程图来表示,计算1 x 3x5x.x11的值 步骤1：令p=1 步骤2：令i=1 步骤3：使p x i,并将乘积放入p中。通常表示为 p x i = p 步骤4：使 i 的值加2，表示为 i+ 2 = i 步骤5：如果i 不大于11，返回到步骤3继续向下执行；否则算法结束。p中的值即最后结果。,例2的算法用流程图来表示,有两个数a,b，按大小顺序打印它们。 步骤1： 输入a,b的值； 步骤2： 如果ab,则先打印a，再打印b；否则，先打印b，再 打印a； 算法结束。,（三）三种基本结构,顺序结构：,虚线框内是一个顺序结构。 AB两个框是顺序执行的： 按图中所画的框的顺序，先执行A操作，再执行B操作。,选择结构,也称为分支结构。 虚线框内是一个选择结构。 此结构包括一个选择框，框中写有一个条件，根据给定的条件是否成立，从而选择执行A框还是B框。 例如：条件可以是i101,B操作为空时，画成直线,（三）三种基本结构,循环结构（当型-while型）,虚线框内是一个当型循环结构。 当给定的条件成立时，执行A框中的操作； 执行完A操作后，判条件P是否成立； 如果仍成立，继续执行A操作； 如此反复执行A框中的操作，直到条件P不成立为止。,条件P,A,成立,不成立,（三）三种基本结构,循环结构（直到型-until型）,条件P,A,成立,不成立,虚线框内是一个直到型循环结构。 先执行A框中的操作； 执行完A操作后，判条件P是否成立； 如果不成立，继续执行A操作； 如此反复执行A框中的操作，直到条件P成立为止。,（三）三种基本结构,（四）结构化程序设计方法,三种基本结构的共同点： 只有一个入口； 一个出口； 结构内每一部分都有机会被执行。 结构内不存在“死循环“。 如条件永远成立时，就成了“死循环“ 已经证明，用上述三种基本结构顺序组成的算法结构，可以解决任何复杂的问题。 由基本结构构成的算法属于“结构化“的算法 只要符合上述的四个特点的结构，都称为基本结构。,对例1算法的流程图的结构化分析,计算1 x 3x5x.x101的值 步骤1：令p=1 步骤2：令i=3 步骤3：使p x i,并将乘积放入p中。通常表示为 p x i = p 步骤4：使 i 的值加2，表示为 i+ 2 = i 步骤5：如果i 不大于101，返回到步骤3继续向下执行；否则算法结束。p中的值即最后结果。,这两个操作之间是顺序关系,这是一个循环结构,这是一个顺序结构,上述算法由基本结构组成,对例2算法的流程图的结构化分析,有两个数a,b，按大小顺序打印它们。 步骤1： 输入a,b的值； 步骤2： 如果ab,则先打印a，再打印b；否则，先打印b，再 打印a； 算法结束。,这是一个选择结构,上述算法由基本结构组成,用基本结构的组合表示算法，从而去掉了流程线。避免了随意的跳转。 1973年两名美国学者提出了一种新的流程图形式，并用二人名字的第一个字母组合命名了该流程图。即N-S流程图，也称盒图。 三种基本结构的表示：,（五）用N-S流程图表示算法,不成立,当条件P成立时,直到条件P1成立,前面的算法用N-S流程图来表示,计算1 x 3x5x.x11的值 步骤1：令p=1 步骤2：令i=1 步骤3：使p x i,并将乘积放入p中。通常表示为 p x i = p 步骤4：使 i 的值加2，表示为 i+ 2 = i 步骤5：如果i 不大于11，返回到步骤3继续向下执行；否则算法结束。p中的值即最后结果。,这两个操作之间是顺序关系,这是一个顺序结构,这是一个循环结构,上述算法由基本结构组成,N-S图表示算法的优点,比文字描述直观、形象、 易于理解；比传统流程图紧凑易画。尤其是它废除了流程线，整个算法结构是由各个基本结构按顺序组成的，N-S流程图中的上下顺序就是执行时的顺序。用N-S图表示的算法都是结构化的算法，因为它不可能出现流程无规律的跳转，而只能自上而下地顺序执行。,小结：,一个结构化的算法是由一些基本结构顺序组成的。在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构范围之内(如循环中流程的跳转)；一 个非结构化的算法可以用一个等价的结构化算法代替，其功能不变 。如果一个算法不能分解为若干个基本结构，则它必然不是一个结构化的算法。,（六）用伪码表示算法,伪码 是用一种介于自然语言和计算机语言之间的文字和符号来描述算法。 好处： 书写方便，格式紧凑，易懂，便于向计算机语言过渡。 前面的算法可用伪码表示为：,开始 置p的初值为1 置i的初值为1 当i 小于11时，执行下面的操作： 使 p=p x i 使 i=i+2 打印 p 的值 结束,（七）用计算机语言表示算法,只有用计算机语言描述的算法才能被计算机的编译环境识别，并被处理、执行。 用计算机语言表示算法必须严格遵守所用语言的语法规则。 前面几种描述算法的方法对文字等格式要求不严，一般来说，只要能示意就行。,前面的算法用c语言表示,#include void main() int p,i; p=1; i=1; while(i=11) p=p*i; i=i+2; ,五、程序设计步骤,分析问题 确定解决方案 建立数学模型 设计算法 用计算机语言描述算法（即写出源程序） 上机调试源程序：经过编辑、编译、连接、运行，得到可执行的程序。（参看教科书第7页上的图1.1 上机步骤） 运行程序，得到需要的结果。,应当强调说明：写出了C程序，仍然只是描述了算法，并未实现算法。只有运行程序才是实现算法。应该说，用计算机语言表示的算法是计算机能够执行的算法。,2.5 结构化程序设计方法,一个结构化程序 就是用高级语言表示的结构化算法。用三种基本结构组成的程序必然是结构化的程序，这种程序便于编写、便于阅读、便于修改和维护。 结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。 结构化程序设计方法的基本思路是：把一个复杂问题的求解过程 分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。,用这种方法逐步分解，直到作者认为可以直接将各小段表达为文字语句为止。这种方法就叫 做“自顶向下，逐步细化”。,自顶向下，逐步细化方法的优点： 考虑周全，结构清晰，层次分明，作者容易写，读者容易看。如果发现某一部分中有一段内容不妥，需要修改，只需找出该部分修改有关段落即可，与其它部分无关。我们提倡用这种方法设计程序。这就是用工程的方法设计程序。,模块设计的方法： 模块化设计的思想实际上是一种“分而治之”的思想，把一个大任务分为若干个子任务，每一个子任务就相对简单了。 在拿到一个程序模块以后，根据程序模块的功能将它划分为若干个子模块，如果这些子模块的规模还嫌大，还再可以划分为更小的模块。这个过程采用自顶向下方法来实现。 子模块一般不超过50行。 划分子模块时应注意模块的独立性，即：使一个模块完成一项功能，耦合性愈少愈好。,实验一 C程序设计入门 目的要求： l 了解Turbo C2.0的集成开发环境，学习如何在Turbo C2.0中编辑、编译、连接、运行与调试C程序； 2 通过运行简单C程序，初步了解C源程序的特点。 实验内容： 1. 首先在e盘建立以自已学号命名（注意文件夹名或文件名都不要超过8个字符，也不要用汉字）的目录，以后自已编辑和调试的有关C的源文件可保存在这个目录下。 2. 启动Turbo C 2.0，输入教材第一章例1.1程序，并进行编译和运行。 注意观察：在此过程中，系统是用何命令进行编译和运行的？编译和连接后所得到的目标程序的后缀是什么？同时请注意相应的目标程序存放在何处？ 3. 输入并运行教材第一章例1.2，了解如何在运行时向程序中的变量输入数据。 4. 输入并运行教材第一章例1.3。 5. 输入并运行自已编写的程序(教材第一章P14 三 编程题)。*,实验二 C基本数据类型及运算 目的要求： l 掌握C语言中整型、字符型、实型变量的定义及赋值； 2 学会使用C的有关运算符及相关表达式； 3 进一步熟悉Turbo C 2.0的集成开发环境。 实验内容： 1. 编写一个程序，从键盘接收3个实数（分别为10.0、20.0、5.0），输出这3个数的和s、乘积t和平均值a。 2. 编程。要求用户输入两个整数a、b（分别为20、10）， 读取用户从键盘输入的值，然后： 1) 用整数输出这两个数的和、差； 2) 用长整型输出这两个数的积，用float输出商； 3) 用整数输出这两个数的余数，用float输出平均值。 3. 将第2题中的程序修改