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

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