C语言之程序的灵分-算法.ppt

C语言程序设计 主讲 物理与电子信息工程系 第2章程序的灵魂 算法程序通常包含的内容有 1 数据的描述 指定数据的类型和组织形式 数据结构 2 操作的描述 编程的操作步骤 也称算法 algorithm 操作的目的 对数据进行加工处理 以便得到结果 厨师做菜肴 1 配料 制作菜肴所需的原料 2 步骤 制作某项菜肴时将原料按规定的步骤加工成所需的菜肴 程序设计者编程的步骤 1 数据结构 程序设计中用到哪些数据及其类型 2 操作步骤 编程中对数据加工处理的方法和步骤 即算法 计算机科学家沃思指出 数据结构 算法 程序确切的说 除上述要素外 还要采取结构化程序设计的方法和用何种语言来设施 程序 数据结构 算法 程序设计方法 语言工具及环境 数据结构 反映各种类型数据的构造形式 是计算机加工处理的对象 算法 为解决某一特定问题而采取的确定的有限的步骤 它是程序设计的灵魂 解决做什么和怎么做 程序设计方法 根据数据类型和算法用计算机语言加以实现 程序中的操作语句实际上是算法的具体体现 不了解算法就谈不上程序设计 语言工具和环境 用计算机语言编制的程序需相应的编译系统和硬件环境加以实施 2 1算法的概念日常生活中做任何事情都有其方法和步骤 这些方法 步骤就是算法 它要求合理 有序 如某人一天的作习时间就有个算法问题 不同的问题 有不同的方法和步骤 同一问题 不同的人可能有不同的方法和步骤 衡量方法步骤优劣的标准是 1 思路 清晰 正确 2 过程 简单 明了 扼要 3 算法 合适例如 计算1 2 3 4 5 99 100算法1 1 2 3 3 3 6 6 4 10 10 5 15 15 6 21 4851 99 4950 4950 100 5050 算法2 100 1 99 2 98 3 97 48 52 49 51 50 100 49 100 50 5050相对而言 算法2简洁明了 易算 按数据的处理方式 计算机中的算法可分为 1 数值运算 求数值的解 如求解方程的根 求函数的定积分 2 非数值运算 目前使用范围广泛 如办公自动化处理 图书情报检索等 数值运算 算法研究较深入 成熟 如数学程序库中的有关数学问题的求解 已编制成标准的子程序或汇编成册或以文件的形式存储在磁盘 磁带上供人们使用 非数值运算 算法一般没有固定的模式 由编程者自己编制 或参考已有类似的算法重新设计解决特定问题的专门算法 排序是非运算算法中研究较为深入的一种 2 2简单算法举例例2 1 1 2 3 4 5原始算法 S1 求1 2得结果2S2 将2 3得结果6S3 将6 4得结果24S4 将24 5得结果120上述方法虽正确 但较烦琐 如果求1 2 3 4 5 6 99 100 用上述方法求解则要999个步骤 解决此类问题的通用方法是 设两个变量 p存放被乘数和结果I存放乘数S1 p 1S2 i 2S3 p i pS4 i 1 iS5 若i 5返回s3否则算法结束 此算法较上面的算法具有通用性和灵活性 例2 2 有50个学生 要求将他们中成绩在80分以上者打印出来 设ni表示第i个学生的学号 gi表示第i个学生的成绩 算法如下 S1 1 iS2 如果gi 80则打印ni和gi 否则不打印S3 i 1 iS4 如果i 50 返回s2 否则算法结束 其中 i作下标 用来控制序号 例2 3 判2000 2500年中每一年是否闰年闰年的条件 1 能被4整除 但不能被100整除 2 能被100整除又能被400整除算法表示如下 设y 被检查的年份S1 2000 yS2 若y不能被4整除 则输出y 不是闰年 然后转向s6S3 若y能被4整除 不能被100整除 则输出y 是闰年 然后转向s6S4 若y能被100整除 又能被400整除 则输出y 是闰年 然后转向s6S5 输出y 不是闰年 S6 y 1 yS7 当y 2500时 转s2继续执行 如果y 2500 算法停止 算法如下 S1 sign 1S2 sum 1S3 deno 2S4 sign 1 signS5 term sign 1 deno S6 sum sum termS7 deno deno 1S8 若deno 100返回s4 否则算法结束 例2 5 对一个大于或等于3的正整数 判断它是不是一个素数素数 除了1和自身外 不能被其它任何整数整除的数 算法思路 判断数n是不是素数 将n作被除数 用2 n 1各数轮流作除数 如果不能被整除 则n必为素数 算法如下 S1 输入n的值S2 i 2S3 n被i除得余数rS4 如果r 0 表示n能被i整除 打印n 不是素数 算法结束 否则执行s5S5 i 1 iS6 如果i n 1 返回s3 否则打印n 是素数 然后结束 实际上 n不必被2 n 1 的整数除 只需被2 n 2 间的整数除即可 甚至只需2 之间的数整除即可 2 3算法的特性1 有穷性 在合理的范围内操作步骤是有限的 而不能无限2 确定性 算法中的每一步骤都应是唯一的和确定无误的 不能出现含糊 模凌两可而产生岐义性 3 有零个或多个输入 输入 在执行算法时 需从外界得到必要的信息前面讨论的算法中 判断n是否是素数 只有一个输入 计算n 则无输入 而有的问题中可能有多个输入 4 有一个或多个输出 算法的目的是为了求解 解就是输出 一个算法得到的结果就是该算法的输出 没有输出的算法是没有意义的 5 有效性 算法中每一步骤都应有效地执行 并得到确定的结果 例如 b 0 执行a b是不能有效执行的 2 4怎样表示一个算法算法常用的方法 自然语言 传统流程图 结构化流程图 伪代码等2 4 1用自然语言表示算法自然语言 人们日常使用的语言 可以是英 中 中英文结合 特点 通俗易懂 缺点 文字冗长 易出现岐义性 表示算法的含义不太严格 根据上下文才能判断其含义 2 4 2用流程图表示算法ANSI规定的流程图符号 已为世界各国采用 用图框表示操作 用图形表示算法 特点 直观形象 易于理解 起止框 输入输出框 判别框 处理框 流程线 注释框 连接点 将画在不同地点的流程线连接起来 以下用流程图表示算法 对一些问题的描述例2 6 用流程图算法求5 例2 7 用流程图算法将50名学生中成绩在80分以上者的学号 成绩打印出来 例2 8 用流程图算法判断从2000 2500年每一年是否是闰年 例2 9用流程图算法求 例2 10 用流程图算法判断素数 打印n 不是素数 以上例子可以看出流程图所包含的部分 1 图框 表示相应操作 2 流程线 表示操作的先后顺序 3 框内外必要的文字说明 流程图表示算法 优点 形象直观 表示清晰 各框之间逻辑关系清楚 缺点 流程图占篇幅较多 当算法复杂时 画流程图费时且不方便在结构化程序设计方法推广之后 许多教科书用N S结构化流程图代替传统的流程图 作为编程人员 传统流程图和结构化流程图都应掌握的使用 2 4 3三种基本结构和改进的流程图1 传统流程图的弊端特点 用流程线指出各框的执行顺序没有严格的限制 使流程随意的转来转去 变得无规律 有时如同一团乱麻 这种算法难以阅读和修改 可靠性和维护性都差 解决方法 1 限制箭头的滥用 不允许流程无规律随意转向 只能顺序执行 2 若算法上包含一些分支和循环 或向前或向后非顺序执行 解决的方法是 设计几种基本结构 由基本结构按一定规律组成一个算法结构 整个算法结构由上而下地将各个基本结构顺序排序起来 这样的算法在质量就能得到保证 2 三种基本结构 1966年Bohra和Jacopini提出的三种基本结构 可表示一个良好算法的基本单元 1 顺序结构 虚线内是一个顺序结构 其中 A B两框是顺序执行的 2 选择 选取 分支 结构 结构中有一个判断框 根据给定的条件P是否 成立来选择执行A或B 框 P条件可以是 x y a b c d等 a b a b b a 3 循环 重复 结构 当 while 型循环结构 功能 给定条件P1成立时 执行A 执行完后再判断条件是否成立 如 此反复 直到某次P1条件不成立为止 例 用当型循环实现5个数的打印 输出用传统流程图算法实现 直到型 Until 循环 功能 先执行A 然后判断给定的条件P2是 否成立 若成立 再执行A 如此反复 直到 P2成立为止 此时不在执行A 从b点结束 例 用直到型循环实现5个数的打印输出 用传统流程图算法实现 三种结构的共点 1 只有一个入口 2 只有一个出口 选择框上的两个出口不代表结构 3 结构内的每一部分都有机会被执行到 每一框内都应有一条从入口到出口的路径通过它 右图的结构中没有一条入口到出口通过A框 4 结构内不能存在死循环 实践证明 由三种结构组成的算法结构可以解决任何复杂问题 结论 基本结构所构成的算法 属结构化算法 它不存在无规律的转向 只在基本结构内才允许存在分支和向前或向后跳转 以上所述的四个基本特点 人们还可自己定义基本结构 并由这些基本结构组成结构化程序 如多分支选择结构等 但它们都是由三种基本结构派生出来的 2 4 4用N S流程图表示算法1973年美国学者I Nassi和B Shneiderman提出了一种新的流程图形式特点 去掉带箭头的流程线 全部算法在一个矩形框内 在该框内还可包含从属于它的框 这种流程图称为N S结构化流程图 受到人们欢迎 1 顺序结构 A B框组成一个顺序结构 2 选择结构 当P成立时执行A操作 P不成立时执行B操作它们是一个整体 代表一个基本结构 3 循环结构 当型循环 首先判断P1 当P1成立时反复执行A操作 P1不成立 可能一次也不执行 直到型循环 首先执行A操作 然后判断P1 在C中真正的情况是 当P1为真时执行A 直到P1为假 用N S流程图表示算法讨论上述各例 例2 13判定闰年的算法用N S图表示 例2 14求算法用N S流程图表示 2 4 5用伪代码表示算法它是介于自然语言和计算机语言之间的文字和符号来描述算法 特点 自上而下书写 每行表示一个基本操作 可用中 英 中英书写 原则 意思要表达清楚 格式要清晰易懂 例2 16求5 算法用伪代码表示BEGIN 算法开始 1 t2 iWhilei 5 t i ti 1 i printtEND 算法结束 例2 17打印出50个学生中成绩高于80分者的学号和成绩 用伪代码表示算法BEGIN 算法开始 1 iWhilei 80printniandgii 1 i END 算法结束 例2 18打印2000 2500年中的每一年是否闰年 用伪代码表示算法BEGIN 算法开始 2000 yWhiley 2500 ify被4整除ify不被100整除printy 是闰年 elseify被400整除printy 闰年 elseprinty 非闰年 endifendifelseprinty 非闰年 endify 1 y END 算法结束 BEGIN 算法开始 1 sum2 deno1 signWhiledeno 100 1 sign signsign 1 deno termsum term sumdeno 1 deno printsumEND 算法结束 伪代码优点 书写格式自由 容易修改 容易写出结构化算法 缺点 不太直观 容易出现逻辑上的错误 2 4 6用计算机语言表示算法要完成一项工作 1 设计算法 2 实现算法设计算法的目的 是实现算法实现算法的一般方式 1 人工心算 2 笔算 算盘 3 计算器 计算机无法识别流程图和伪代码计算机实现算法的过程 用计算机语言编写的程序才能被计算机识别 解释 执行 编辑 编译 连接 生成可执行程序 用计算机语言表示算法必须严格遵循所用语言的语法规则下面用C语言讨论两个简例 例2 20求5 前面讨论的算法 用C语言表示main inti t t 1 i 2 while i 5 t t i i i 1 printf d t 例2 21求级数的值 将前面讨论的算法用C语言表示main intsign 1 floatdeno 2 0 sum 1 0 term while deno 100 sign sign term sign deno sum sum term deno deno 1 printf f sum 2 5结构化程序设计方法结构化程序 就是用高级语言表示的算法 三种基本结构组成的程序必然是结构化程序 特点 1 便于书写 阅读 修改 维护 2 减少了程序出错机会 提高了程序可靠性 保证了程序的质量 3 强调程序设计的风格 程序结构的规范性 层次结构的清晰性结构化程序设计的思路 把复杂问题的求解过程分阶段进行 每个阶段处理的问题都控制在人们容易理解和处理的范围 结构化程序设计方法一 1 自顶向下 2 逐步细化 3 模块化设计 4 结构化编程此种方法的特点 考虑周全 结构清晰 层次分明 修改容易过程 将问题求解由抽象逐步具体化 从顶层设计 然后一步步细化结构化程序设计方法二 自下而上逐步积累 想到哪写到哪 熟练的程序员编程时常常如此 一般不提倡 例如 采用筛法将1 1000之间的素数打印出来 筛法 指埃拉托色尼 Eratosthenes 筛法 方法是 在一张纸上写上1 1000个全部整数 然后判断它们是否素数 找到一个非素数就把它去掉 最后剩下的就是全部素数 23 5 7 11 13 17 19 方法 先将1去掉 它不是素数 用2去除它后面各数 把2的倍数去掉再用3去除它后面各数 把3的倍数去掉再用5 各数为除数去除这些数以后的各数 直到除数后面的数被去掉为止 上面问题用自然语言表示算法为 1 去掉1 2 用刚去掉的数的下一个数P去除P后面的各数 把P的倍数去掉 3 检查P是否小于的整数部分 如n 1000 则P 31 4 剩下的数就是素数 上述问题采用N S结构化流程图逐步细化来实现 三部分工作由A B C表示A部分可细化为 将上述各框合起来就得到总的流程图 输入n1 i当i ni xii 1 i0 x12 i当i 取整数部分 xi 0是否i 1 j当j nxj 0是否xj能被xi整除是否0 xjj 1 ji 1 i1 i当i nxi 0是否打印xii 1 i A B C