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

最新2019-2020人教B版高中数学必修三课件:1.1.1《算法的概念》1优质课件_图文

高中数学课件
精心整理 欢迎使用

1.1.1算法的概念

算法作为一个名词,在中学教科书中并 没有出现过,我们在基础教育阶段还没 有接触算法概念。但是我们却从小学就 开始接触算法,熟悉许多问题的算法。 如,做四则运算要先乘除后加减,从里 往外脱括弧,竖式笔算等都是算法,至 于乘法口诀、珠算口诀更是算法的具体 体现。

我们知道解一元二次方程的算法,求 解一元一次不等式、一元二次函数图象 的画法,解线性方程组的算法,求两个 数的最大公因数的算法等。因此,
算法其实是重要的数学对象。

一、算法的概念
算法(algorithm)一词源于算术(algorism), 即算术方法,是指一个由已知推求未知的 运算过程。后来,人们把它推广到一般, 把进行某一工作的方法和步骤称为算法。

广义地说,算法就是做某一件事的步 骤或程序。菜谱是做菜肴的算法,洗衣 机的使用说明书是操作洗衣机的算法, 歌谱是一首歌曲的算法。
在数学中,主要研究计算机能实现的 算法,即按照某种机械程序步骤一定可 以得到结果的解决问题的程序。比如解 方程的算法、函数求值的算法、作图的 算法,等等。

例1 “一群小兔一群鸡,两群合到一群里, 要数腿共48,要数脑袋整17,多少小兔 多少鸡?” 解:算术方法:如果没有小兔,那么小鸡 应为17只,总的腿数应为2×17=34条, 但现在有48条腿,造成腿的数目不够是由 于小兔的数目为0,每有一只小兔便会增 加两条腿,故应有(48-17×2) ÷2=7只小 兔。相应的,小鸡有10只。

代数方法:设有x只小鸡,y只小兔. 则
? x ? y ? 17 ??2x ? 4 y ? 48
将第一个方程的两边同乘以-2加到第二 个方程中去,得到
? x ? y ? 17 ??(4 ? 2) y ? 48 ?17 ? 2
解第二个方程得y=7.
把y代入到第一个方程得x=10.

思考1教材中例1是著名的“鸡兔同笼” 问题,其中第一种解法是算术方法,教 材中对它的评价是“简单直观,却包含 着深刻的算法思想”,那么它是如何体 现算法的思想呢? S1 假设没有小兔,则小鸡应为n只; S2 计算总腿数为2n只; S3 计算实际总腿数与假设总腿数的差值 为m-2n; S4 计算小兔只数为 m ? 2n ;
2
S5 小鸡的只数为n-m ? 2n .
2

思考2教材中例1的第二种解法是列方程组 的方法,它是否也是一种算法呢? 探究:是的,其算法步骤为:
S1 设未知数; S2 根据题意列方程组; S3 解方程组; S4 还原实际问题,得到实际问题的答案。

在实际中,很多问题可以归结为求解

二元一次方程组,下面我们用消元法来

解一般的二元一次方程组

???aa2111xx11

? a12 x2 ? a22 x2

? ?

b1 b2

① ②

S1 假定a11≠0,②×a11-①×a21得

? ??(a11a22

a11x1 ? a12 x2 ? a21a12 )x2 ?

? b1 a11b2

?

a21b1

③ ④

S2 如果a11a22-a12a21≠0,则执行下步;

否则执行S6

S3 ④两边同除以a11a22-a12a21≠0得

? ?

a11

x1

?

a12 x2

? b1



? ??

x2

?

a11b2 a11a22

? a21b1 ? a21a12



S4 ⑥代入⑤.得

? ??

x1

?

a22b1 a11a22

? ?

a12b2 a21a12



?

? ??

x2

?

a11b2 a11a22

? a21b1 ? a21a12



S5 输出结果x1,x2, S6 若a11b2-a21b1≠0. 则执行下一步;否 则执行S8 S7 输出“方程组无解”.
S8 输出“方程组有无穷多个解”
以上解二元一次方程组的方法,叫做 高斯消去法

二、算法的特点
不论在哪一种算法中,它们都是经有限 次步骤完成的,因而它们体现了算法的有 穷性。
在算法中,每一步都能明确地执行, 且有确定的结果,因此具有确定性。
在所有算法中,每一步操作都是可以 执行的,也就是具有可行性。

为了便于计算机运算,它们必须先输入 已知数据,而计算的目的分别是解方程组 和求最大值等,因此必须输出结果,也就 是必须有输入和输出。
算法解决的都是一类问题(分别是解决 求方程组的解和确定一个有理整数序列中 的最大值问题),因此具有普适性。

体验 :写出解方程x2-2x-3=0的一个算法.

配方法:

S1 移项,得x2-2x=3



S2 ①式两边同加1并配方得 (x-1)2=4 ②

S3 ②式两边开方,得x-1=±2



S4 解③式得x=3或x=-1

因式分解法:

S1 将方程左边因式分解得(x-3)(x+1)=0 ①

S2 由①得x-3=0或x+1=0



S3 解②得x=3或x-1

公式法: S1 计算方程的判别式,判断其符号 △=(-2)2-4×(-3)>0; S2 将a=1,b=-2,c=-3代入求根公式,
得x=3或x=-1

例2 写出一个求有限整数列中的最大值 的算法。
解:算法如下: S1 先假定序列中的第一个整数为“最大值”; S2 将序列中的下一个整数值与“最大值”比较, 如果它大于此“最大值”,这时你就假定“最 大值”是这个整数; S3 如果序列中还有其他整数,重复S2; S4 在序列中一直到没有可比的数为止,这时假 定的“最大值”就是这个序列中的最大值。

如果让你去找,你可能不会这样做,可 能认为,这样太机械、太枯燥。不要忘了, 我们写的是算法。算法要求按部就班地做, 每一步都有唯一的结果,又要求写出的算 法对任意整数序列都适用,总能得到结果。 所以上面写的,符合算法的要求。
下面我们用数学语言,写出对任意3个 整数a,b,c求出最大值的算法。

S1 max=a S2 如果b>max, 则max=b. S3 如果C>max, 则max=c. S4 max就是a, b, c中的最大值。

例3 写出求1+2+3+4+5+6的一个算法。
解:算法1: S1 计算1+2得到3; S2 将第一步中的运算结果3与3相加得到6 S3 将第二步中的运算结果6与4相加得到10 S4 将第三步中的运算结果10与5相加得到15 S5 将第四步中的运算结果15与6相加得到21

算法2: S1:取n=6; S2:计算 n(n ? 1) S3:输出运算2结果。
算法3: S1 将原式变形为(1+6)+(2+5)+(3+4)=3×7; S2 计算3×7; S3 输出运算结果。

例4. 求1×3×5×7×9×11的值,写出其 算法。
算法1; 第一步,先求1×3,得到结果3; 第二步,将第一步所得结果3再乘以5,得 到结果15; 第三步,再将15乘以7,得到结果105; 第四步,再将105乘以9,得到945; 第五步,再将945乘以11,得到10395,即 是最后结果。

算法2:用P表示被乘数,i表示乘数。 S1 使P=1; S2 使i=3; S3 使P=P×i; S4 使i=i+2; S5 若i≤11,则返回到S3继续执行;否则 算法结束。
由于计算机动是高速计算的自动机器, 实现循环的语句可以在很短的时间内完成。 对于循环结构的详细情况,我们将在以后 的学习中介绍。

例6. 利用二分法求函数y=f(x) (x在定义区 间D) 上的一个变号零点x0的近似值x,使 它与零点的误差不超过正数ε,即使|x- x0|<ε,写出它的一个算法.

S1 在D内取一个闭区间[a,b],使f(a)与 f(b)异号,即f(a)f(b)<0;

S2 令x0=

a?b 2

,计算f(x0);

S3 若f(x0)=0,则x0就是y=f(x)的零点; 若f(x0)与f(a)异号,则a=a,b=x0,否则 a=x0,b=b; S4 判断|a-b|<ε是否成立,若成立,则
区间[a,b]内任意实数都是x0的近似值; 否则,返回S2,直到不等式 |a-b|<ε成
立为止。
S5 输出x0.

例7. 设计算法解决下面的问题:已知点P
的坐标为(x0,y0),直线l的方程为 ax+by+c=0 (ab≠0),求点P到直线l的距离.

算法一:

S1

求出直线l的斜率为k,k

?

?

a b



S2 求出与l垂直的直线的斜率k’,k ' ? b ;
a

S3 求出过点P且与直线l垂直的直线l’方程,

直线l’的方程为

y

?

y0

?

b a

(x

?

x0 )

S4 求出直线l和l’的交点M的坐标;把l和l’

联立,得方程组

? ?

ax ? by ? c ? 0

? ??

y

?

y0

?

b a

(x

?

x0 )

由此可以得到点M的坐标为

(

?[a(by0 ? c) ? a2 ? b2

b2

x0

]

,

a

2

y0 ? abx0 a2 ? b2

?

bc

)

S5 把点M的横坐标和纵坐标分别赋值给

变量x1,y1;

S6 把点(x1,y1)代入两点间距离公式,计 算求得d的值;
d ? (x0 ? x1)2 ? ( y0 ? y1)2
算法二: S1 计算z ? a2 ? b2 的值 S2 计算z0=|ax0+by0+c|的值. S3 计算d ? z0 得所求的距离.
z

例8 一位商人有9枚银元,其中有1枚略轻 的是假银元,你能用天平(不用砝码)将 假银元找出来吗?
算法一: S1 任取2枚银元分别放在天平的两边,如 果天平左右不平衡,则轻的一边就是假银 元;如果天平平衡,则进行S2; S2 取下右边的银元放在一边,然后把剩余 的7枚银元依次在右边进行称量,直到天 平不平衡,偏轻的那一枚就是假银元。

算法二: S1 任取2枚银元分别放在天平的两边,如 果天平左右不平衡,则轻的一边就是假银 元;如果天平平衡,则进行S2; S2 从余下的7枚银元中再任取2枚分别放 在天平的两边,如果天平左右不平衡则轻 的一边就是假银元;如果天平平衡,则进 行S3;

S3 从余下的5枚银元中再任取2枚分别放 在天平的两边,如果天平左右不平衡,则 轻的一边就是假银元;如果天平平衡,则 进行S4; S4 从余下的3枚银元中再任取2枚分别放 在天平的两边,如果天平左右不平衡,则 轻的一边就是假银元;如果天平平衡,则 最后剩下的还未称的1枚银元就是假银元。

算法三: S1 任取4枚银元分别放在天平的两边,各 2枚,如果天平左右不平衡,则轻的一边中 含有假银元,并进行S2;如果天平平衡, 则进行S3; S2 将轻的一边的两枚银元分别放在天平 的两边,则轻的一边的那枚银元就是假银 元,称量结束;

S3 从余下的5枚银元中再任取4枚分别放 在天平的两边,各2枚,如果天平左右不 平衡,则轻的一边就含有假银元,并转向 S2;如果天平平衡,则最后剩下的还未称 的1枚银元就是假银元,称量结束。

算法四: S1 把银元分成3组,每组3枚; S2 先将两组分别放在天平的两边,如果 天平不平衡,那么假银元就在轻的那一组; 如果天平左右平衡,则假银元就在未称的 第3组里; S3 取出含假银元的那一组,从中任取两 枚银元放在天平的两边,如果左右不平衡, 则轻的那一边就是假银元;如果天平两边 平衡,则未称的那一枚就是假银元.

练习题
1.下面的四种叙述不能称为算法的是 (C ) (A)广播的广播操图解 (B)歌曲的歌谱 (C)做饭用米 (D)做米饭需要刷锅、淘米、添水、加 热这些步骤

2.下列关于算法的说法正确的是( D ) (A)某算法可以无止境地运算下去 (B)一个问题的算法步骤可以是可逆的 (C)完成一件事情的算法有且只有一种 (D)设计算法要本着简单、方便、可操 作的原则

3.下列关于算法的说法中,正确的是 ( C ). A. 算法就是某个问题的解题过程 B. 算法执行后可以不产生确定的结果 C. 解决某类问题的算法不是惟一的 D. 算法可以无限地操作下去不停止

4.下列运算中不属于我们所讨论算法范 畴的是( B ). A. 已知圆的半径求圆的面积 B. 从一副扑克牌随意抽取3张扑克牌抽到 24点的可能性 C. 已知坐标平面内的两点求直线的方程 D. 加减乘除运算法则

5.下列语句表达中是算法的有( C ). ① 从济南到巴黎可以先乘火车到北京再坐 飞机抵达; ②利用公式 S = ah÷2 计算底为1高为2的 三角形的面积; ③ 1 x>2x +4;
2
④求M(1,2)与N(3,5)两点连线的方程可 先求MN的斜率再利用点斜式方程求得. A. 1 个 B. 2 个 C. 3 个 D. 4 个

6.写出求1+2+3+…+100的一个算法.

可以运用公式1+2+3+…+n= n(n ?1)
2
直接计算.

第一步



; ①取n=100

第二步



; ②计算 n(n ?1)

第三步 输出运算结果.

2

7.已知一个学生的语文成绩为89,数学

成绩为96,外语成绩为99,求他的总分和

平均成绩的一个算法为:

第一步 取A=89,B=96,C=99;

第二步





第三步





第四步 输出D,E.

①计算总分D=A+B+C ②计算平均成绩E=D
3