nbhkdz.com冰点文库

1.1.1算法的概念(共32张ppt)

时间:2017-10-25


第 一 章 算 法 初 步

趣味益智游戏
一人带着一只狼、一只羊和一箱蔬菜要过河 ,但只有一条小船 .乘船 时,每次只能带狼、羊和蔬菜中的一种.当有人在场时,狼、羊、蔬菜都 相安无事.一旦人不在,狼会吃羊,羊会吃菜.请设计一个方案,安全地将狼、 羊和蔬菜带过河.

1、带羊到对岸,返回; 2、带菜到对岸,并把羊带回; 3、带狼

狗到对岸,返回; 4、带羊到对岸。

如何发电子邮件?
假如你的朋友不会发电子邮件,你能教会他吗?发邮件的方法很多, 下面就是一种操作步骤. 第一步 第二步 第三步 第四步 第五步 第六步 登录电子信箱; 点击“写信”; 输入收件人地址; 输入主题; 输入信件内容; 点击“发送”.

我们做任何一件事,都是在一定条件下按某种顺序

的一系列.解决数学问题也常常如此,例如用加减消元法
解二元一次方程组时,就可以按照某一程序进行损伤用 配方法解一元二次方程,也是按一定程序操作的.

一般地,对于一类问题的机械式地、统一地、按部就班地求解过程 称为算法(algorithm)它是解决某一问题的程序或步骤. 所谓 “算法”就是解题方法的精确描述 .从更广义的角度来看,并 不是只有“计算”的问题才有算法,日常生活中处处都有.如乐谱是乐队 演奏的算法,菜谱是做菜肴的算法,珠算口诀是使用算盘的算法. 按照这样的理解,我们可以设计出很多具体数学问题的算法.下面 看几个例子:

做 一 做

请你写出解下面二元一次方程组的详细过程.


解:第一步, ① +②×2得 第二步, 解③得 第三步, ② -① ×2得

② 5x=1; ③

5y=3;



第四步, 解④得
第五步, 得到方程组的解为

思考:你能写出解一般的二元一次方程组的步骤吗?

第一步,



第二步,解(3)得

.

第四步,解(4)得

第五步,得到方程组的解为

思考
这 两个解方程组的算法的适用范围有何不同?

?

x ? 2 y ??1, 2 x ? y ?1

① ② ③

?

a1 x ? b1 y ? c1 a2 x ? b2 y ? c2

----------------------------------------

(a1b2 ? a2b1 ? 0)


第一步: ①+②×2,得
第二步:解③ 得 第三步:将 代入①,得

第一步:

(a2b 1 ?a 1b2 ) y ? a2c 1 ? a1c2 ③ a2 c1 ? a1c2 ④ 第二步: 解③,得 y ? a2b1 ? a1b2
b1c2 ? b2 c1 第三步: 将④带入①得 x ? a b ? a b 2 1 1 2

事实上,我们可以将一般的二元一次方程组的解法转化

成计算机语言,做成一个求解二元一次方程组的程序.

练习1. 给出求1+2+3+4+5+6的一个算法.
解法1.按照逐一相加的程序进行. 第一步:计算1+2,得3;

第二步:将第一步中的运算结果3与3相加得6;
第三步:将第二步中的运算结果6与4相加得10; 第四步:将第三步中的运算结果10与5相加得15; 第五步:将第四步中的运算结果15与6相加得21.

解法2.可以运用下面公式直接计算.

n ( n ? 1) 1? 2 ? 3 ? 4 ?? ? n ? 2
第一步,取 n =6; 第二步,计算

第三步,输出计算结果.
点评 : 解法 1 繁琐 , 步骤较多 ; 解法 2 简单,步骤较少 . 找出好的算法 是我们的追求目标.

现在你对算法有了新 的认识了吗?

讲授新课
1.算法的定义 在数学中,算法通常是指按照一定规则解决某一类问题的明确 和有限的步骤.现在,算法通常可以编成计算机程序,让计算机执行 并解决问题. 2.算法的要求 (1)写出的算法,必须能解决一类问题(例如解任意一个二元一次方程 组),并且能重复使用; (2) 算法过程要能一步一步执行,每一步执行的操作,必须确切,不能 含混不清,而且在有限步之内完成后能得出结果.

讲授新课
3.算法的基本特征:

明确性:算法对每一个步骤都有确切的、非二义性的规定,即每一步对于 利用算法解决问题的人或计算机来说都是可读的、可执行的 , 而不需要 计算者临时动脑筋.
有效性:算法的每一个步骤都能够通过基本运算有效地进行 ,并得到确定 的结果;对于相同的输入 , 无论谁执行算法 , 都能够得到相同的最终结 果. 有限性:算法应由有限步组成,至少对某些输入,算法应在有限多步内结束, 并给出计算结果.

?数据输入:算法一定要根据输入的初始数据或给定的初值才能正确执行 它的每一步骤.

?信息输出 : 一个算法至少要有一个有效的信息输出 , 这就是问题求解 的结果.
?不唯一性 : 求解某一个题的解法不一定是唯一的 , 对于一个问题可 以有不同的算法.

4.算法的描述:
描述算法可以有不同的方式 , 常用的有自然语言、程序框图、程 序设计语言、伪代码等.

(1)自然语言
自然语言就是人们日常使用的语言 ,可以是汉语、英语或数学语言等 . 用自然语言描述算法的优点是通俗易懂 , 当算法中的操作步骤都是顺序 执行时比较容易理解 . 缺点是如果算法中包含判断和转向 , 并且操作步骤 较多时,就不那么直观清晰了. (2)程序框图 (3)程序设计语言 1.1.2程序框图中讲解 1.2基本算法语句中讲解

例1.(1)设计一个算法判断7是否为质数.
第一步, 第二步, 第三步, 用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.

第五步, 用6除7,得到余数1.因为余数不为0 , 因此,7是质数.

例1.(2)设计一个算法判断35是否为质数. 第一步, 第二步, 第三步, 用2除35,得到余数1.因为余数不为0,所以2不能整除35. 用3除35,得到余数2.因为余数不为0,以3不能整除35. 用4除35,得到余数3.因为余数不为0,以4不能整除35.

第四步, 用5除35,得到余数0.因为余数为0,所以5能整除35.因此,35 不是质数.

变式2:任意给定一个大于1的整数n,试设计一个程序或步骤对n是否为质 数做出判定.
分析:回顾这个问题的解题过程. 算法步骤: 第一步:判断n是否等于2. 若n=2,则n是质数; 若n>2,则执行第二步. 第二步:依次检验2~(n-1)这些整数是不是n的约数,即是不是整除n的 数.若有这样的数,则n不是质数;若没有这样的数,则n是质数.

例2.用二分法设计一个求方程 的近似根的算法.

二分法
对于区间[a,b ]上连续不断、且 f(a)f(b)<0的函数y=f(x),通过不断地把函数 f(x)的零点所在的区间一分为二,使区间 的两个端点逐步逼近零点,进而得到零点 或其近似值的方法叫做二分法.

算法步骤: 2 第一步,令 f ( x) ? x ? 2 ,给定精确度d.
第二步,给定区间[a,b],满足f(a) · f( b)< 0. 第四步,若f(a)· f(m) < 0,则含零点的区间为[a,m]; 否则,含零点的区间为[m, b].
a?b 第三步,取中间点 m ? . 2

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

当d=0.005时,按照以上算法,可得下面表和图. a b

1 1 1.25 1.375 1.375 1.406 25 1.406 25 1.414 625 1.414 062 5

2 1.5 1.5 1.5 1.437 5 1.437 5 1.421 875 1.421 875 1.417 968 75

| a- b| 1 0.5 0.25 0.125 0.062 5 0.031 25 0.015 625 0.007 812 5 0.003 906 25

y=x2-2

1

1.25 1.375

1.5

2

于是,开区间(1.4140625,1.41796875)中的实数都是当精确度 为0.005时的原方程的近似解.

练习2. 任意给定一个正实数,设计一个算法求以这个数为半径的圆的
面积.

算法步骤:
第一步:给定一个正实数r;

第二步:计算以r为半径的圆的面积S=πr2;
第三步:得到圆的面积S.

练习3. 任意给定一个大于 1 的正整数n,设计一个算法求出n的所有

因数. 算法步骤: 第一步,依次以2~(n–1)为除数除n,检查余数是否为0;若是, 则是n的因数;若不是,则不是n的因数;
第二步,在n的因数中加入1和n;

第三步,

输出n的所有因数.

练习4.

写出求一元二次方程 ax2+bx+c=0

的根的算法.

第一步,计算Δ=b2-4ac. 第二步,如果Δ<0,则原方程无实数解 ;否则(Δ≥0)时,

x1 ? ? b ? ? , 2a

x2 ? ? b ? ? . 2a

第三步:输出x1, x2或无实数解.

小结
算法的概念:算法通常指可以用来解决的某 一类问题的步骤或程序,这些步骤或程序必须是明

确的和有效的,而且能够在有限步之内完成的.

算法的特征是什么? 明确性 有效性 有限性

第 一 章 算 法 初 步


1.1.1算法的概念(练习题)

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...1.1.1算法的概念(练习题)_数学_高中教育_教育专区...π×32 5.下列语句表达中是算法的有( ) 1 ①...

1.1.1 算法的概念

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...1.1.1 算法的概念_数学_高中教育_教育专区。必修...某市的 3 个区共有高中学生 20 000 人,且 3 ...

1.1.1算法的概念

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高中教育 ...1.1.1算法的概念_高一数学_数学_高中教育_教育专区。课题 主备人 1.1.1 ...

1.1 算法的概念

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...1.1.1 算法的概念 教材知识检索考点知识清单 1....(本大题共 8 小题,每小题 5 分,共 40 分,...

1.1.1算法的概念

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高等教育 ...1.1.1算法的概念_理学_高等教育_教育专区。教案1.了解算法的含义,体会算法的...

1.1.1 算法的概念知识点练习及答案

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...1.1.1 算法的概念知识点练习及答案_数学_高中教育...的值不能用算法求解的是( A.T=12+22+32+42+...

高中数学必修3 1.1.1 算法的概念 习题及详解

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...高中数学必修3 1.1.1 算法的概念 习题及详解_高二...用算法求解的是___. ①S=12+22+32+42+?+1002...

人教版必修三 1-1-1 算法的概念(练)

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...人教版必修三 1-1-1 算法的概念(练)_数学_高中...共为 15 分钟. 8.已知两个单元分别存放了变量 x...

1.1.1算法的概念导学案 (1)

搜试试 7 悬赏文档 全部 DOC PPT TXT PDF XLS ...1.1.1算法的概念导学案 (1)_高一数学_数学_高中...“一群小兔一群鸡,两群合到一群里,要数腿共 48...

苏教版高一数学算法的概念1

搜试试 3 悬赏文档 全部 DOC PPT TXT PDF XLS ...1.1.1 算法的概念一、三维目标: 1、 知识与技能...2. 3 INPUT “请输入华氏温度: ”;x y=(x-32...