nbhkdz.com冰点文库

算法的概念课件

时间:2012-03-10


算法的概念
算法是计算机工作的 基础, 基础,算法的发展推 动了计算机的发展

【学习目标】 学习目标】 1.了解算法的含义,体会算法的思想; 了解算法的含义, 了解算法的含义 体会算法的思想; 2.能够用自然语言叙述算法; 能够用自然语言叙述算法; 能够用自然语言叙述算法 3.掌握正确的算法应满足的特征。 掌握正确的算法应满足的特征。 掌握正确的算法应满足的特征 学习重点】 【学习重点】 算法的含义、 算法的含义、解二元一次方程组和判断一 个数为质数的算法设计; 个数为质数的算法设计; 学习难点】 【学习难点】 把自然语言转化为算法语言。 把自然语言转化为算法语言。

创设情境 给出定义
问题1 有一个农夫带一条狼 一只羊 问题1:有一个农夫带一条狼、一只羊 和一筐白菜过河。如果没有农夫看管, 白菜过河 和一筐白菜过河。如果没有农夫看管, 则狼要吃羊,羊要吃白菜。但是船很小, 则狼要吃羊,羊要吃白菜。但是船很小, 只够农夫带一样东西过河。 只够农夫带一样东西过河。问农夫该如 何解此难题? 何解此难题? 解决步骤: 解决步骤: 1、带羊到对岸,返回; 、带羊到对岸,返回; 2、带菜到对岸,并把羊带回; 、带菜到对岸,并把羊带回; 3、带狼到对岸,返回; 、带狼到对岸,返回; 4、带羊到对岸。 、带羊到对岸。

问题2: 一群小兔一群小鸡, 问题 :“一群小兔一群小鸡,两群 合 到一群中,腿一共有 条 到一群中,腿一共有48条,脑 袋共有17个,问一共有多少小 袋共有 个 鸡?多少小兔? 多少小兔?
我有2条腿 一个脑袋 我有4条腿 一个脑袋

解决步骤: 解决步骤: 1.设未知数:设有x只小鸡,y只小兔 设未知数:设有 只小鸡 只小鸡, 只小兔 设未知数 X+Y=17 2.列方程组;2X+4Y=48 列方程组; 列方程组

3.解方程组; 3.解方程组; X=10 解方程组 y=7 4.得到实际问题的答案。小鸡10只,小兔 只 得到实际问题的答案。小鸡 只 小兔7只 得到实际问题的答案

你能写出求解这个方程组的步骤吗 你能写出求解这个方程组的步骤吗? 步骤 2X+4Y=48 (1) X+Y=17
?a1 x + b1 y = c1 (1) ? ?a2 x + b2 y = c2 (2)

(2)
( a1b2 ? a2b1 ≠ 0 )

探究1:写出求解下列方程组的步骤。 探究 :写出求解下列方程组的步骤。 步骤

什么是算法? 什么是算法?

算法的含义
(数学中)算法通常是指按照一定规则解决 某一类问题的明确和有限的步骤. (广义)完成某项工作的方法和步骤 广义)
? 菜谱是做菜的算法; 菜谱是做菜的算法; ? 歌谱是一首歌曲的算法; 歌谱是一首歌曲的算法; ? 空调说明书是空调使用的算法等

(现代)可以用计算机来解决的一类问题的程序和 步骤.

知识探究 归纳特征

是否为质数。 例1:设计一个算法,判断 是否为质数。 :设计一个算法,判断7是否为质数

是否为质数。 例1:设计一个算法,判断 是否为质数。 :设计一个算法,判断7是否为质数 算法:

35?

第一步, 第一步,用2除7,得到余数 。因为余数不为 ,所以 除 ,得到余数1。因为余数不为0,所以2 不能整除7。 不能整除 。 第二步, 第二步,用3除7,得到余数 。因为余数不为 ,所以 除 ,得到余数1。因为余数不为0,所以3 不能整除7。 不能整除 。 第三步,用4除7,得到余数3。因为余数不为0,所以4 第三步, 除 ,得到余数 。因为余数不为 ,所以 不能整除7。 不能整除 。 第四步, 第四步,用5除7,得到余数 。因为余数不为 ,所以 除 ,得到余数2。因为余数不为0,所以5 不能整除7。 不能整除 。 第五步, 第五步,用6除7,得到余数 。因为余数不为 ,所以 除 ,得到余数1。因为余数不为0,所以6 不能整除7。因此, 是质数 是质数。 不能整除 。因此,7是质数。

以下是算法吗? 以下是算法吗? 判断53是否为质数 是否为质数。 判断 是否为质数。
第一步, 第一步,用2除53,得到余数 。因为余数不为 ,所以 除 ,得到余数1。因为余数不为0,所以2 不能整除53。 不能整除 。 第二步, 第二步,用3除53,得到余数 。因为余数不为 ,所以 除 ,得到余数2。因为余数不为0,所以3 不能整除53。 不能整除 。 第三步,用4除53,得到余数1。因为余数不为0,所以4 第三步, 除 ,得到余数 。因为余数不为 ,所以 不能整除53。 不能整除 。

……

不是算法

第五十一步, 第五十一步,用52除53,得到余数 。因为余数不为 , 除 ,得到余数1。因为余数不为0, 所以52不能整除 不能整除53。因此, 是质数 是质数。 所以 不能整除 。因此,53是质数。

合作探究2: 合作探究 : 任意给定一个大于2的整数 , 任意给定一个大于 的整数n,能否设 的整数 计一个算法对n是否为质数做出判断 是否为质数做出判断? 计一个算法对 是否为质数做出判断?

技巧:①初值 技巧: ②赋值 ③计数

算法分析: 算法分析: 第一步:给定大于2的整数n; 第一步:给定大于2的整数n 第二步:令i=2; 第二步: i=2; 第三步: 除 ,得到余数是r; 第三步:用i除n,得到余数是 ; 第四步:判断 是否为 是否为0,若是, 不是质数; 第四步:判断r是否为 ,若是,则n不是质数; 不是质数 否则, 的值增加 的值增加1,仍用i表示 表示; 否则,将i的值增加 ,仍用 表示; 第五步:判断 是否成立。 第五步:判断i>(n-1)是否成立。若是,则n是质 是否成立 若是, 是质 结束算法;否则,返回第三步。 数,结束算法;否则,返回第三步。

例3: : 用二分法设计一个求方程 (x>0)的近似根的算法 )的近似根的算法.

x ?2=0
2

第一步, 给定精确度d. 第一步,令 f ( x ) = x 2 ? 2 ,给定精确度
f ( x ) = x
2

?

2

第二步, 第二步,确定区间 [ a , b ] ,满足 f (a) ? f (b) < 0
a + b 第三步: 第三步:取区间中点 m = 2

.

第四步,若 f (a) ? f (m) < 0 ,则含零点的区间为 [ a , m ]; 第四步, 否则, 否则,含零点的区间为 [ m , b ] .将新得到的含零点的 将新得到的含零点的 区间仍记为 [ a , b ] . 第五步: 的长度是否小于d或 第五步:判断 [ a , b ] 的长度是否小于 或f(m)是 是 否等于0.若是 若是, 是方程的近似解; 否等于 若是,则m是方程的近似解;否则,返回 是方程的近似解 否则, 第三步. 第三步

思考: 思考: 问题1:你能举出更多算法的例子吗? 问题 :你能举出更多算法的例子吗? 问题2:与一般解决问题的过程相比, 问题2:与一般解决问题的过程相比, 你认为算法有哪些特征? 你认为算法有哪些特征?

算法的基本特征
明确性:算法的每一个步骤都是确切的, 明确性:算法的每一个步骤都是确切的,能 有效执行且得到确定的结果,不能模棱两可。 有效执行且得到确定的结果,不能模棱两可。 有限性:算法应在有限步内结束, 有限性:算法应在有限步内结束,并给出 计算结果。 计算结果。 顺序性: 算法从初始步骤开始, 顺序性 : 算法从初始步骤开始 , 分为若干 明确的步骤, 明确的步骤,每一步都只能有一个确定的继 只有执行完前一步才能进入到后一步, 续,只有执行完前一步才能进入到后一步, 并且每一步都确定无误后,才能解决问题。 并且每一步都确定无误后,才能解决问题。

不唯一性: 不唯一性 : 求解某一个问题的算法不一定 是唯一的, 是唯一的,对于同一个问题可以有不同的算 法。 普遍性:很多具体的问题, 普遍性:很多具体的问题,都可以设计 合理的算法去解决某一类问题, 合理的算法去解决某一类问题,如计算器计 算都要经过有限的、 算都要经过有限的、事先设计好的步骤加以 解决。 解决。

当堂检测 巩固知识
1.下面对算法描述正确的一项是: 下面对算法描述正确的一项是: 下面对算法描述正确的一项是 A.求解某一类问题的算法是唯一的 . B.一个算法可以无止境地运算下去 . C.同一问题可以有不同的算法 . D.同一问题的算法不同,结果必然不同 .同一问题的算法不同, 2.下列特征中:①无序性;②有穷性;③确定性;④有效性。能表 下列特征中: 无序性; 有穷性; 确定性; 有效性。 下列特征中 示算法特征的有: 示算法特征的有: A.1个 B.2个 C.3个 D.4个 个 个 个 个 3.已知一个学生的语文、数学、英语成绩分别为 ,96,99,求 已知一个学生的语文、 已知一个学生的语文 数学、英语成绩分别为89, , , 他的平均分的一个算法为: 他的平均分的一个算法为: 第一步: 第一步:取A=89,B=96,C=99; , , ; 第二步: 第二步: ; 第三步: 第三步: ; 第四步:输出计算的结果。 第四步:输出计算的结果。

4.一位商人有 枚银元,其中有 枚略轻的是假银 一位商人有9枚银元 其中有1枚略轻的是假银 一位商人有 枚银元, 你能设计用天平(不用砝码) 元。你能设计用天平(不用砝码)将假银元找 出来的算法吗? 出来的算法吗? 5.任意给定一个大于 的正整数 ,设计一个算法 任意给定一个大于1的正整数 任意给定一个大于 的正整数n, 求出n的所有因数 的所有因数. 求出 的所有因数 6.两个大人和两个小孩一起渡河,渡口只有一条 两个大人和两个小孩一起渡河, 两个大人和两个小孩一起渡河 小船,每次只能渡1 个大人或两个小孩, 小船,每次只能渡 个大人或两个小孩,他们 四人都会划船,但都不会游泳。 四人都会划船,但都不会游泳。试问他们怎样 渡过河去?请写出一个渡河方案。 渡过河去?请写出一个渡河方案。

今天你有什么收获? 今天你有什么收获?
1、算法的概念 、 2、算法的特点及表示 、 3、简单算法的设计 、简单算法的设计


赞助商链接

数学课件

数学课件 - 2017—2018 年第一学期研究生基础课、方向课考试安排 2017.12.25 课程名称 数据结构与算法 (025200076) 数据结构与算法(xxjs007) 结构方程模型...

...技术八年级下册《第九章磨刀不误砍柴工——算法基础...

初中信息技术八年级下册《第九章磨刀不误砍柴工——算法基础知识》教学设计 - 第九章 磨刀不误砍柴工---算法基础知识 一、教学目标 1.理解算法的概念; 2....

kmp算法课件演示(推荐)

模式匹配算法模式匹配算法隐藏>> kmp 算法课件演示(推荐) 数据结构/数据库 2007-10-12 22:23:51 阅读 625 评论 1 中小 订阅 (1)以一个例子引入 KMP 算法 ...

算法的基础知识说课稿(新)

同时学生总结出算法的概念和解决问题的一般方法。 2、指导学生自学教材 P3 页...2、这节课并没有使用多媒体课件,而用得是传统的教学方法,避免了学生被过于...

《算法与程序设计》选修教案_图文

算法就是解决问题的程序或步骤。 (二) 【课件展示】算法的概念: 1、广义的算法是指完成某项工作的方法和步骤,在我们日常生活中也经常使用算法,只是没意识到罢 ...

上海交通大学计算方法课件(宋宝瑞)CH.1

上海交通大学计算方法课件(宋宝瑞)CH.1 - 第一章 绪论 数值分析-研究各种数学问题求解的数值计算方法及其理论也称计算方法。 数值计算——对已知数据进行有限次四则...

第1课 算法的基础知识 说课稿

2、教学目标 (1)知识与技能:1、了解算法的概念和发展历史。2、学会分析问题,...自然语言的表示它也可以用流程图表示,然后课件展示流程图。 4、巩固理解 提问...

LMS算法

搜试试 3 帮助 全部 DOC PPT TXT PDF XLS ...基于误差通道在线建模的自适应内模控制算法研究 学密...W T E{X (n) X T (n)}W 下面定义互相关...

计算机网络课件

计算机网络课件 隐藏>> 基本概念题: 6-1 什么叫递归? 6-2 适宜于用递归算法求解的问题的充分必要条件是什么?什么叫递归出口? 6-3 阶乘问题的循环结构算法和递...

计算机算法总结

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS 百度文库 专业资料 IT/计算机 ...写一算法求斐波 那契数列第 10 项的值。 分析:从斐波那契数列的定义可知,数列...