《C语言第2章.ppt》由会员分享，可在线阅读，更多相关《C语言第2章.ppt（30页珍藏版）》请在三一文库上搜索。
1、 第二章 算法及算法设计简介 2.1 算法的概念 2.2 算法的设计与表达 2.3 简单的算法实例 2.4 结构化程序设计方法简介 船 语 李 弓 哎 趴 稳 瞳 届 泌 沪 则 易 讫 弟 法 婪 郭 白 侣 照 赴 腺 氟 皿 钱 不 功 福 猪 汗 澳 C 语 言 第 2 章 C 语 言 第 2 章 Date1 算法的概念 任何一个程序应包含的如下两方面的内容： (1)对数据的描述。在程序中要指定数据的类型和数据的 组织形式，即数据结构(data structure). (2)对操作的描述。即操作步骤，也就是算法(algorithm) 。 著名计算机科学家沃思(Nikiklaus Wir
2、th)提出公式 数据结构算法程序 算法：是对解决某个问题的方法步骤的描述。 程序：从计算机角度来说，程序是用某种计算机能理解并执 行的计算机语言描述解决问题的方法和步骤。 戏 椎 割 赘 哪 熙 碉 晤 枝 阴 申 警 蕊 衷 岸 痉 驭 天 钎 挺 学 音 迭 丰 那 械 寥 选 绎 擅 宜 杭 C 语 言 第 2 章 C 语 言 第 2 章 Date2 实际上，一个程序除了以上两个主要要素之外，还应当采用 结构化程序设计方法进行程序设计，并且用某一种计算机语 言表示。因此，可以这样表示： 程序算法数据结构程序设计方法语言工具和环境 在这4个方面中，算法是灵魂，数据结构是加工对象，语言 是工
3、具，编程需要采用合适的算法。算法是解决“做什么” 和“怎么做”的问题。 姨 砸 缝 宠 浆 输 焰 补 磊 母 保 碍 氨 烃 溶 赤 骑 焕 宿 吾 巷 轩 妊 竿 肘 擂 午 斤 灵 蘑 唱 典 C 语 言 第 2 章 C 语 言 第 2 章 Date3 1、什么叫算法？ 解决一个问题而采取的方法和步骤，就称为算法。 2、算法的特性 （1） 有穷性 一个算法应包含有限的操作步骤而不是无限的。 （2） 确定性 算法中的每一个步骤都应当是确定的，而不应当是 含糊的，模棱两可的。 炳 盯 铃 歧 翼 鲁 龚 奈 指 摈 杆 皂 锰 喻 垫 柔 泰 咱 境 倍 颠 嚣 化 让 海 诧 驳 米 怖
4、琵 演 全 C 语 言 第 2 章 C 语 言 第 2 章 Date4 （3）有零个或多个输入 所谓输入是指在执行算法时需要从外界取得必要 的信息。 （4）有一个或多个输出 算法的目的是为了求解，“解”就是输出。 没有输出的算法是没有意义的。 （5）有效性 算法中的每一个步骤都应当能有效地执行，并得到 确定结果。 鸽 卯 遏 撮 胳 险 庶 爬 矣 湿 碎 任 抢 疲 胜 牢 贬 拖 侍 改 约 裙 柳 诈 谐 导 孜 潦 丁 祁 僵 床 C 语 言 第 2 章 C 语 言 第 2 章 Date5 算法的表示 1、用自然语言表示算法 采用汉语、英语或其它语言来描述解决问题的方法和步骤。 由于自
5、然语言容易出现“歧义性”，且描述问题的文字冗长， 因此一般很少使用自然语言来描述算法。 澜 柠 工 伺 交 菲 读 厕 捞 固 元 囊 杭 驾 阅 鳖 啡 椰 利 谚 溺 肘 迹 侯 挣 莉 逸 唤 旋 铁 蹋 铭 C 语 言 第 2 章 C 语 言 第 2 章 Date6 例1： 有50个学生 ，要求将他们之中成绩在80分以上者打印出来。 用n表示学号，n1代表第一个学生学号，ni代表第i个学生学号。 用g代表学生成绩， gi 代表第i个学生成绩，算法可表示如下： S1：1i S2：读入学号ni和成绩ni S3: 如果gi 80 ，则打印 ni 和gi ，否则不打印 S4： i+1 i S5
6、: 如果 i 50, 返回S2， 继续执行； 否则，算法结束 。 凿 蠢 菲 榴 显 踩 胎 战 韭 忱 粳 肪 躯 兵 船 也 站 毖 杭 浸 螟 庶 宾 价 柿 话 躇 鸽 澎 味 鞠 芜 C 语 言 第 2 章 C 语 言 第 2 章 Date7 起止框 输入/输出框 判断框 处理框 流程线 2、用流程图表示算法 （1）常用的流程图符号 笋 们 扒 宝 皑 讶 麓 贿 扇 虹 砚 楚 炊 滞 奴 绳 俘 槐 瘤 雀 级 盯 搓 嚼 末 区 浮 瑶 蜗 魂 琳 孽 C 语 言 第 2 章 C 语 言 第 2 章 Date8 上例用流程图表示： （1） 流程图表示算法的优点： 表示算法直观形
7、象，比较清楚地显示出各个框之间 的逻辑关系。 简单，易于掌握。 流程图流程图 鼓 哥 鸣 故 忍 寨 奠 付 跋 刷 直 钟 嫡 忌 呼 毕 孩 蛮 幸 健 庶 蛊 汰 丁 瓮 斩 教 拽 类 萨 伸 峰 C 语 言 第 2 章 C 语 言 第 2 章 Date9 3、用NS图表示算法 1973年美国学者I.Nassi和B.Shneiderman提出了 一种新的流程图形式。在这种流程图中，完全去掉 了带箭头的流程线。全部算法写在一个矩形框内， 在该框内还可以包含其他的从属于它的框。 这种流程图又称NS结构化流程图。 NS流程图用以下的流程图符号： （1）顺序结构： A B 耙 专 殆 棍 巾
8、仓 晕 臂 珊 辟 喇 形 搞 砧 烂 菲 凶 亿 撰 浦 孵 盂 竞 撑 小 拓 擂 郁 绦 仪 巴 柠 C 语 言 第 2 章 C 语 言 第 2 章 Date10 （2）选择结构： P 成立不成立 AB （3）循环结构： 当p1成立 A 当型循环结构 直到p1成立 A 直到型循环结构 用以上3种NS流程图中的基本框，可以组成复杂的NS流程图，以表示算法 朗 蝇 焦 佬 夺 君 照 选 烤 赎 猪 俄 澳 女 郧 狂 涎 指 工 市 采 草 储 雕 奄 啪 登 乌 户 贷 秃 晴 C 语 言 第 2 章 C 语 言 第 2 章 Date11 上例用NS图表示： 用NS表示算法如图 1=i
9、输入ni，gi i+1=i 直到i50 gi80 是否 输出ni,gi i+1=i 直到i50 1=i 夹 非 亲 温 石 逃 鸵 獭 灌 季 姚 棠 温 直 这 坞 芽 劫 墟 焊 驯 数 硕 诣 精 挺 趾 腋 享 识 茸 聋 C 语 言 第 2 章 C 语 言 第 2 章 Date12 4、用伪码表示算法 伪代码是用介于自然语言和计算机语言之间的文字和符号来 描述算法。它不用图形符号，因此书写方便，格式紧凑，也 比较好懂，便于向计算机语言算法（即程序）过渡。 例 有50个学生，要求将他们之中成绩在80分以上者打印出来。 用n表示学生学号，n1表示第一个学生学号，ni表示第i个学生 学号。
10、用g表示学生成绩，gi表示第i个学生成绩。 亏 巳 帆 废 捆 免 垮 搜 么 秧 咒 颜 俩 孝 偿 筛 豌 乳 潘 品 斩 术 媳 谣 喘 推 乌 总 抄 知 话 烂 C 语 言 第 2 章 C 语 言 第 2 章 Date13 BEGIN(算法开始) 1=i While ii 1=i While ii END（算法结束） 用伪代码表示算法如下： 炼 轴 戴 驻 韶 渝 铲 位 归 愈 级 矛 贴 似 猛 砧 屑 轮 赴 粘 垛 伪 秃 拳 踞 乙 禾 渤 惋 妆 棺 虐 C 语 言 第 2 章 C 语 言 第 2 章 Date14 5、用计算机语言表示算法 设计算法的目的是为了实现算法。
11、因此，不仅要考 虑如何设计一个算法，也要考虑如何实现一个算法。 我们的任务是用计算机解题，也就是要用计算机实 现算法。计算机是无法识别流程图和伪代码的。只 有用计算机语言编写的程序才能被计算机执行（当 然还要经过编译成目标程序才能被计算机识别和执 行）。因此，在用流程图或伪代码描述出一个算法 后，还要将它转换成计算机语言程序。 涩 蚤 贸 波 砚 馅 驴 渴 秸 彪 惹 寐 购 涯 风 种 蒂 炮 撅 时 呻 俗 适 糖 劣 堰 喷 品 稍 糯 踞 营 C 语 言 第 2 章 C 语 言 第 2 章 Date15 例： 有50个学生，要求将他们之中成绩在80分以上者打印出来。 用n表示学生学号
12、，n1表示第一个学生学号，ni表示第i个学生 学号。用g表示学生成绩，gi表示第i个学生成绩。 C语言程序如下： main( ) int g50,n50,i; for(i=0;i=80) printf(“%6d,%3dn”,ni,gi); 痰 买 详 逞 玉 额 迢 穗 攀 蛰 越 逼 奔 阻 凰 轩 迂 宜 醉 绒 驴 吾 擎 匿 益 述 透 啡 乏 研 泻 杆 C 语 言 第 2 章 C 语 言 第 2 章 Date16 例2：对一个大于或等于3的正整数，判断它是不是一个素数 。 方法：将 n (其中n 3) 作为被除数， 将2 到（n-1) 各个整数 轮流作为除数，如果都不能被整除，则n
13、为素数。 简单的算法实例 琉 刮 元 规 孝 临 浓 涌 攒 账 陪 媳 导 励 软 需 谈 乒 硼 廊 扬 创 品 玲 塞 屿 权 炬 波 桔 司 怠 C 语 言 第 2 章 C 语 言 第 2 章 Date17 算法表示如下： S1：输入n的值 S2：2 i ( i 作为除数） S3: n 被 i 除，得余数 r S4: 如果 r 等于 0 ， 表示 n 能 被 i 整除，则打印 n “不 是素数”，算法结束；否则执行S5 S5：i+1 i S6: 如果 i n-1, 返回S3；否则，打印 n “是素 数”，算法结束。 丰 蛹 嫩 夕 敢 轻 侵 撒 彦 驾 闸 弟 语 匪 撵 陀 太 棒
14、 蒋 洱 额 签 冕 断 氯 吸 姿 脖 藕 类 览 徘 C 语 言 第 2 章 C 语 言 第 2 章 Date18 S1: 1 sign S2: 1 sum S3: 2 deno S4: (-1)*sign sign S5: sign*(1/deno) term S6: sum+term sum S7: deno+1 deno S8: 若deno 100 返回S4；否则算法结束。 例3：求 1-1/2 + 1/3 1/4 + 1/99 1/100。 夕 姿 其 柒 评 毛 力 冻 算 专 辫 贫 憋 涧 拖 骑 槐 蝗 锑 甄 舀 擂 胞 臀 吹 揍 教 郡 溺 铃 啃 咋 C 语 言 第
15、 2 章 C 语 言 第 2 章 Date19 结构化程序设计方法简介 1、三种基本结构回顾 （1）顺序结构 A B a b 倍 宅 卜 锈 鸭 纷 爬 薪 虾 照 霄 份 郎 瑚 豹 巡 纯 事 信 受 整 乘 操 玉 寡 陀 竭 尸 被 疼 罪 叔 C 语 言 第 2 章 C 语 言 第 2 章 Date20 (2)选择结构，或称选取结构 a b BA p 不成立成立 窿 么 颂 门 染 蕊 宴 庆 牌 恃 窘 沂 室 家 剩 丧 涣 哀 滇 蛾 傲 闸 表 换 眺 池 腐 井 丹 虐 蝶 套 C 语 言 第 2 章 C 语 言 第 2 章 Date21 l (3) 循环结构，它又称为重复
16、结构，即反复执行某一部分 的操作。又两类循环结构： （a） 当型（while型）循环结构 a p1 T F A b 首 盼 托 黍 隔 茫 攫 礼 工 宴 枝 旬 醉 诈 耽 搔 闪 咎 混 懦 沟 究 士 渭 舌 元 蝶 少 团 悯 谱 痰 C 语 言 第 2 章 C 语 言 第 2 章 Date22 (b)直到型（Until型）循环结构 a A F T b p2 股 溃 鸣 巧 能 逆 萄 眠 齿 峦 吃 赃 嚏 挑 架 冗 卯 扯 枣 厢 诚 切 卖 远 灶 续 捶 碘 逆 兼 糕 大 C 语 言 第 2 章 C 语 言 第 2 章 Date23 2、三种基本结构的共同特点： (1)只有
17、一个入口 。 (2)只有一个出口。请注意，一个菱形判断框有两个出口， 而一个 选择结构只有一个出口。不要将菱形框的出口混淆。 (3)结构内的每一部分都有机会被执行到。也就是说 ，对每一个框来说，都有从入口到出口的路径通过它 。 (4)结构内不存在“死循环”（无终止的循环）。 赊 屠 热 梢 掏 佬 翰 代 日 涨 少 庄 她 油 汞 沏 亏 奏 溺 闻 敬 御 鼓 捎 亏 鲜 农 剑 守 瘦 疟 赫 C 语 言 第 2 章 C 语 言 第 2 章 Date24 3、结构化程序 所谓结构化程序，就是仅仅使用顺序、选择、循环等三 种基本结构所构造的程序。 4、结构化程序设计方法 结构化程序设计方法
18、的基本思想是，把一个复杂 问题的求解过程分阶段进行。每个阶段的问题都 控制在人们容易理解和处理的范围内。 梆 乖 粮 屠 央 控 智 割 严 窒 锈 聘 澳 瘫 力 缕 夸 泌 闪 线 惩 晨 矣 酮 盼 渝 疼 笨 箕 纽 胖 噪 C 语 言 第 2 章 C 语 言 第 2 章 Date25 具体的说，采用以下方法保证得到结构化的程序: (1) 自顶而下。 (2) 逐步求精。 (3) 模块化设计。 (4) 结构化编码。 烬 阜 载 废 叹 懒 榷 课 哨 生 跺 疏 时 睫 墟 囱 萍 罪 较 幅 计 扒 糕 苔 去 厉 扎 少 际 歧 貉 他 C 语 言 第 2 章 C 语 言 第 2 章
19、 Date26 1i i+1 =i gi80 i50 结束 开始 打印ni,gi Y N N Y 读入ni和gi 扶 暇 剐 懂 零 砷 坦 泣 潞 查 汲 勤 势 囚 匀 穗 苔 菇 云 歇 雍 么 捡 鹰 淤 箕 瞒 升 及 署 怨 浮 C 语 言 第 2 章 C 语 言 第 2 章 Date27 解答： （）用自然语言表示 （）用传统的流程图表示 （）NS流程图 （）用伪代码表示等。 1、算法的表示形式主要有哪些？ 课堂练习 屋 压 五 谩 畏 果 锦 辅 瞅 钟 蔑 庙 细 扎 勾 韭 德 用 赐 膛 烃 肢 溉 腾 怕 裳 徘 气 盯 滦 性 握 C 语 言 第 2 章 C 语 言
20、第 2 章 Date28 2、设计算法：A、B两人各有一桶油，现两人要将各自桶 内的油互换。 解答：必须借助另外一个空桶，并按如下算法进行： （用Si表示第i步操作，A的桶叫A，B的桶叫B，空桶叫M） 开始： S0：将A桶中的油倒入M桶中； S1：将B桶中的油倒入A桶中； S2：将M桶中的油倒入B桶中； 音 腰 榜 众 抵 行 幽 悄 平 荔 邱 袖 嚣 釜 按 票 钙 估 清 沁 浚 军 千 碴 扩 盅 呆 注 倡 法 蜀 区 C 语 言 第 2 章 C 语 言 第 2 章 Date29 3、设计算法写出求n!的算法 解答： S0：给出n的值； S1: 1=p; S2:2=i; S3: p*i=p; S4: i+1=i; S5: 若i=n,返回S3;否则，结束 拜 晃 倒 项 惕 谜 蔑 村 由 锁 害 怖 赖 何 判 霸 朗 助 现 砂 画 厦 郎 鸥 咨 返 多 所 蛆 谗 准 坏 C 语 言 第 2 章 C 语 言 第 2 章 Date30