当前位置:首页 >> 数学 >>

第5章 (1)算法_图文

第5章 (1)算法

(一)生活中与计算机中的问题求解
生活中的问题求解:
Problem: 烤蛋糕(Baking a Cake) How to solve: 1. Start 2. 将烤箱预热 3. 准备一个盘子 4. 在盘子上抹上一些黄油 5. 将面粉、鸡蛋、糖和香精混合在一起搅拌均匀 6. 将搅拌好的面粉团放在盘子上 7. 将盘子放到烤箱内 8. End

分治策略 ("Divide and Conquer" Strategy)
Problem: 准备早餐( Prepare a Breakfast)

1. Start 2. 准备早餐 3. End

分治策略 ("Divide and Conquer" Strategy)
1. Start 2. 准备早餐 2.1 准备一个金枪鱼三明治 2.2 准备一些薯条 2.3 冲一杯咖啡 3. End

分治策略 ("Divide and Conquer" Strategy)
1. Start 2.准备早餐 2.1 准备一个金枪鱼三明治 2.1.1 拿来两片面包 2.1.2 准备一些金枪鱼酱 2.2 准备一些薯片 2.3 冲一杯咖啡 3. End

分治策略 ("Divide and Conquer" Strategy)
1. Start 2.准备早餐 2.1 准备一个金枪鱼三明治 2.1.1 拿来两片面包 2.1.2 准备一些金枪鱼酱 2.2 准备一些薯片 2.2.1 将土豆切成片 2.2.2 油炸这些土豆片 2.3 冲一杯咖啡 3. End

分治策略 ("Divide and Conquer" Strategy)
1. Start 2.准备早餐 2.1 准备一个金枪鱼三明治 2.1.1 拿来两片面包 2.1.2 准备一些金枪鱼酱 2.2 准备一些薯片 2.2.1 将土豆切成片 2.2.2 油炸这些土豆片 2.3 冲一杯咖啡 2.3.1 烧些开水放入杯中 2.3.2 在水杯中加入一些咖啡和糖 3. End

结构化程序设计方法
? 基本思路: 把一个复杂问题的求解过程分阶段进 行,每个阶段处理的问题都控制在人们容 易理解和处理的范围内。 ? 采取方法如下: (1)自顶向下 (2)逐步细化 (3)模块化设计:子模块一般不超过 50行,模块应具有一定独立性 (4)结构化编码

程序的三种基本结构
? ⑴ 顺序结构

A

B

⑵ 选择结构
又称分支结构。根据是否满足给定条件而从两组操 作中选择执行一种操作。虚线框内是一个选择结构。
入口
成立

P

不成立

A

B

·无论P条件是否成立,只能执行 A操作或B操作中的一个; ·无论执行完哪一个分支后,就结 束了。 ·两个操作可以有一个是空操作, 即不执行任何操作,形如下图:
成立

出口

P

不成立

A

B



循环结构
执行过程:
入口

又称重复结构,即在一定条件下,反复执行某一部分的操作。 有两种类型:

F P T S
出口

当给定条件P成立时,执行S操作, 然后再判断P条件是否成立,如果仍成 立,再执行S操作,然后再判断…,如 此反复,直到某一次P条件不成立为止, 此时不再执行S,结束循环。

当型循环

特点: 先判断,后执行,S有可能一次也 不执行。



循环结构
入口

执行过程: 执行S操作,然后判断条件P是否 成立,如果不成立,再执行S操作,然 后再判断,…...,如此反复,直到某一 次P条件成立不再执行S,结束循环。
F

S

P T
出口

特点: 先执行,后判断,S最少要执行一

次。

直到型循环

三种基本结构共同特点
? ? ? ? (1)只有一个入口 (2)只有一个出口 (3)结构内每部分都有机会被执行。 (4)结构内不存在死循环

(二)算法描述
? 面向对象程序 = 对象 + 消息

? 面向过程的程序 = 数据结构 + 算法(沃思提出)
? 计算机中的算法( Algorithm ) –为解决一个具体问题而采取的确定的、有限的操 作步骤,仅指计算机能执行的算法 计算机算法分两类: 数值运算算法:求数值解,例如求方程的根、 求函数的定积分等。 非数值运算算法:常用于事务管理领域,例如图 书检索、人事管理、行车调度管理等。

? 算法的正确性衡量标准: – 有穷性:算法包含有限步操作,在合理的时间 内完成 确定性,无歧义 :
如果x≥0,则输出Yes;如果x≤0,则输出No

– 有效性:每一步都应能有效执行且能得到确定

的结果 ,如:负数不能开平方 – 0或多个输入: 程序允许无输入 – 1或多个输出:任何程序都必须有输出,哪怕 是提示信息

? 常用的算法描述方法有:自然语言、传统 流程图、NS流程图、伪代码、PAD图等

? 1.自然语言 ? 2.流程图:
美国国家标准化协会ANSI(American National Standard Institute)规定了一 些常用的流程图符号:

? 例:求n!的算法思想: ? n!=1*2*3*…*n ? 计算机执行乘法时通常每次求两个数相乘,因 此上面公式在程序中需要通过反复相乘来实现 。 ? 需要设定一个变量n,表明求多少的阶乘; ? 第二个变量,存当前累乘的结果; ? 第三个变量存当前将要与累乘器相乘的因子, 并且该因子的变化是从1到n每次增加1 ? 流程图如下页所示

开始 输入n yes n<0? no

fac=1,i=1
no i<=n? yes fac=fac*i i= i+1

输出fac值

输出错提示

结束 计算n! 的传统流程图

求5!

? 流程图是表示算法的较好的工具。一个流 程图包括以下几部分 : (1)表示相应操作的框; (2)带箭头的流程线; (3)框内外必要的文字说明。

? 传统流程图弊端: BS型算法(a bowl of spaghetti) 太长

(三) N-S流程图表示算法
? 完全去掉了带箭头的流程线。 ? 全部算法写在一个矩形框内,在该框内还 可以包含其它的从属于它的框。

N-S流程图用以下的流程图符号:

(1)顺序结构

(2)选择结构

(3)循环结构

N-S图表示算法的优点 ? 比文字描述直观、形象、 易于理解; ? 比传统流程图紧凑易画。 ? 用N--S图表示的算法都是结构化的算法。

(四)用伪代码表示算法
? 概念:伪代码是用介于自然语言和计算机 语言之间的文字和符号来描述算法。 ? 特点:
– 每一行(或几行)表示一个基本操作 – 不用图形符号, – 便于向计算机语言算法(即程序)过渡。

? 用处:适用于设计过程中需要反复修改时 的流程描述。

例: “输出x的绝对值 ”的算法可以用伪代 也可以用汉字伪代码表示: 码表示为: 若 x为正
打印 x 否则 打印 -x

if x is positive THEN print x else print -x

也可以中英文混用,如:
if x 为正 print x else print -x

– 开始



置t的初值为1

– 置i的初值为2 – 当i<=5,执行下面操作: – 使t=t×i – 使i=i+1 – {循环体到此结束} – 输出t的值 – 结束

(五)用PAD(Problem Analysis Diagram )图表示算法(补充)

在数组K中找出最大和次大数

PAD图描述算法的优点
? 1)能展现算法的层次结构; 2)表示形式直观易懂。 3)即可用于表示程序逻辑,又可用于描述 数据结构; 4)支持自顶向下,逐步求精的过程。 5) PAD图可以较容易地转换为程序代码。

(七)习题
? 1、将50名学生中成绩在80分以上者的学号和 成绩输出 (1) 循环输入 (2) 循环判断

? 2 、判定2000-2500年中的每一年是否闰年 判定闰年的条件是: (1)能被4整除,但不能被100整除的年份 都是闰年 (2)能被100整除,又能被400整除的年 份是闰年 不符合上述两条件的年份不是闰年

用有含义的单词作变量名,使 算法更易于理解: sum 表示累加和 deno是”分母”英文缩写 sign 代表数值符号 term代表某一项

? 4 、对于一个大于或等于3的正整数,判断它 是不是一个素数 判定方法: 将n作为被除数,将2到n-1(或者2到n/2之 间整数,甚至2到n的平方根之间整数)各个整 数先后做为除数,如果都不能被整除,则n为 素数


相关文章:
第5章 (1)算法_图文.ppt
第5章 (1)算法 - 第5章(1)算法 (一)生活中与计算机中的问题求解 生活
Java第5章 (1)_图文.ppt
Java第5章 (1) - Java程序设计大学教程 第五章 算法与数据结构 程序是建立在数据结构基础上使用计算机 语言描述的算法,因此简单地讲,程序也 可以表示成:算法+...
算法第5章_图文.ppt
算法第5章 - 第5章 回溯法 1 ? ? ? ? ? ? ? 学习要点 理解回溯法的深度优先搜索策略。 掌握用回溯法解题的算法框架 (1)递归回溯 (2)迭代回溯 (3)子...
第5章 算法及程序设计_图文.ppt
第5章 算法及程序设计 - 第5章 算法及程序设计 ? ? ? ? ? 要点 算法+数据结构=程序设计 算术逻辑运算 非数值计算 面向过程和面向对象的程序设计。 5.1 ...
第5章算法与复杂性_图文.ppt
第5章算法与复杂性 - 文档均来自网络,如有侵权请联系我删除文档... 第5章 算法与复杂性 第5章学习目标 算法与...? 1.算法的时间复杂度 ? 时间复杂度是度量...
第5章算法与数据结构._图文.ppt
Java程序设计大学教程 第五章 算法与数据结构程序是建立在数据结构基础上使用...y ← y / 2 y = y / 2; 1、伪代码描述 : 伪代码(Pseudo-code)是...
第五章 影像匹配基础理论与算法(1)._图文.ppt
第五章 影像匹配基础理论与算法(1). - 华北水利水电学院资源与环境学院测量教
第5章(2) 填充算法_图文.ppt
第5章(2) 填充算法 - 第五章 基本图形生成算法(2) 本课教学目的: 掌握扫描转换与区域填充的常规方法,包括x-扫描线算法、种子填充算法、边缘填充算 法等。 ...
第5章 数字PID控制算法1_图文.ppt
第5章 数字PID控制算法1 - 第五章 数字PID控制算法 刘明芹 机械电子工程系 内容提要 ? ? 概述 准连续PID控制算法 ? ? ? 对标准PID算法的改进 PID...
第5章_数据分类(1)_图文.ppt
第5章_数据分类(1)_数学_自然科学_专业资料。数据仓库与数据挖掘 第5章 数据...算法过程如下: 24 假设给定的数据样本集为: X={(xi,yi)|i=1,2,…,...
优化方案2011考高总复习一轮用书(文)-第五章算法5章1节....ppt
优化方案2011考高总复习轮用书(文)-第五章算法5章1节. - 第五章 算法初步 2011高考导 航 考纲解读 1.了解算法的含义,能用自然语言 描述算法. 2.了解...
第1章 算法及基础知识_图文.ppt
1算法及基础知识 - 教师简介 ?张阳 ?信息工程学院109 ?zhangyang@nwsuaf.edu.cn ?教学资源:作业管理系统-张阳 课程简介 ? 课时:理论课36+实验课1...
第5章LL(1)文法及其程序素材_图文.ppt
第5章LL(1)文法及其程序素材 - 第5章 LL(1)文法及其分析程序 5.1 预测分析程序 5.2 LL(1)文法 ? FIRST和FOLLOW集定义和计算LL(1) ? 文法定义LL(1)....
第5章-回溯算法v1.0_图文.ppt
第5章-回溯算法v1.0_计算机软件及应用_IT/计算机_专业资料。第五章 回溯算法 郑州大学 ? ZZU ? ZZU 第五章 回溯算法 学习要点 ? 理解回溯法的深度优先搜索...
第5章 算法与程序设计初步_图文.ppt
第5章 算法与程序设计初步 - 大学计算机基础 第5章 算法与程序设计基础 5.1 算法基础 算法的概念 1. 用计算机解决问题时,计算机执行的任何操作或计算都 ...
算法初步1_图文.ppt
算法初步1 - 第5章 算法初步 第1课时 5.1算法的含义 情景设计 有种商
第5章 数字PID控制算法1_图文.ppt
第5章 数字PID控制算法1 - 学习资料\2009离散时间控制系统\上海交通大
...梁红兵 哲凤屏_第5章(2016-2017-1)分析_图文.ppt
计算机操作系统 第四版 汤小丹 梁红兵 哲凤屏_第5章(2016-2017-1)分析 - 第五章 虚拟存储器 第五章 虚拟存储器 5.1 虚拟存储器概述 5.2 请求分页存储管理...
第5章存储管理(1)剖析_图文.ppt
第5章存储管理(1)剖析 - 第五章 存储管理 第五章 存储管理 ? ? ? ?
第5章 数字PID控制算法1_图文.ppt
第5章 数字PID控制算法1_工学_高等教育_教育专区。微机原理 数字PID控制算法 PPT 第五章 数字PID控制算法 数字PID控制算法 内容提要 ? 概述 ? 准连续PID...
更多相关标签: