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

1.1.1 算法的概念_图文

1.1 算法与程序框图
1.1.1 算法的概念

新课导入
假如你的朋友不会发电子邮件,你怎么教会他? 发电子邮件的方法很多,下面是其中的一种 操作步骤:

第一步 第二步 第三步 第四步 第五步

登录电子信箱; 点击 “写信” ; 输入收件人地址; 输入主题; 输入信件内容;

第六步 点击“发送”.

我们做任何事情都是在一定条件下按某种 顺序执行的一系列操作。解决数学问题也是如 此。例如用加减消元法解二元一次方程组时, 就可以按照某一步骤进行操作。

请你写出解下面二元一次方程组的详细过程. ? x ? 2 y ? ?1 ①

② ③ 解:第一步, ① +②×2得 5x=1; 1 第二步, 解③得 x ? ; 5 第三步, ② -① ×2得 5y=3; ④ 3 第四步, 解④得 y ? ; 1 ? x? , 5 ? ? 5 第五步, 得到方程组的解为 ?
?y ? 3. ? 5 ?

? ?2 x ? y ? 1

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

?a1 x ? b1 y ? c1 ? ?a2 x ? b2 y ? c2
第一步,

(1) (2)

? a1b2 ? a2b1 ? 0?

c1b2 ? c2b1 . 第二步,解(3)得 x ? a1b2 ? a2b1

第三步,

? a2b1 ? a1b2 ? y ? a2c1 ? a1c2.
第四步,解(4)得

(1) ? a2 ? (2) ? a1 得:

(4)

a2c1 ? a1c2 y? . a2b1 ? a1b2
c1b2 ? c2b1 ? ?x ? a b ? a b , ? 1 2 2 1 ? a c ? a c 2 1 1 2 ?y ? . ? a2b1 ? a1b2 ?

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

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

探究新知 1.算法的定义
在数学中,算法通常是指按照一定规则 解决某一类问题的明确和有限的步骤.现在, 算法通常可以编成计算机程序,让计算机执 行并解决问题.

2.算法的要求
(1)写出的算法,必须能解决一类问题(例如解任 意一个二元一次方程组),并且能重复使用; (2) 算法过程要能一步一步执行,每一步执行的 操作,必须确切,不能含混不清,而且在有限步之 内完成后能得出结果.

3.算法的基本特征:
?明确性:算法对每一个步骤都有确切的、非二 义性的规定,即每一步对于利用算法解决问题的 人或计算机来说都是可读的、可执行的,而不需 要计算者临时动脑筋.

?有效性:算法的每一个步骤都能够通过基本运 算有效地进行,并得到确定的结果;对于相同的 输入, 无论谁执行算法 , 都能够得到相同的最终 结果.
?有限性:算法应由有限步组成,至少对某些输入 ,算法应在有限多步内结束,并给出计算结果.

?数据输入:算法一定要根据输入的初始数据或 给定的初值才能正确执行它的每一步骤. ?信息输出 : 一个算法至少要有一个有效的信 息输出,这就是问题求解的结果. ?不唯一性 : 求解某一个题的解法不一定是唯 一的, 对于一个问题可以有不同的算法.

例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,得到余数1.因为余数不为0, 所以6不能整除7.因此,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不是质数.

任意给定一个大于1的整数n,试设计一个程序 或步骤对n是否为质数做出判定. 分析:回顾这个问题的解题过程.

算法步骤:
第一步:判断n是否等于2. 若n=2,则n是质数;
若n>2,则执行第二步. 第二步:依次检验2~(n-1)这些整数是不是n的 约数,即是不是整除n的数.若有这样的数,则n 不是质数;若没有这样的数,则n是质数.

例2:用二分法设计一个求方程 x2 ? 2 ? 0 ? x ? 0? 的近似根的算法 分析:
2 2

令f ( x) ? x ? 2, 则方程x ? 2 ? 0的解就是函数f ( x)的零点。

二分法的基本思想:

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

算法步骤:
第一步, 令 f ( x) ? x ? 2 ,给定精确度d.
2

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

当d=0.005时,按照以上算法,可得下面表和图. a 1 1 1.25 1.375 1.375 1.406 25 1.406 25 1.414 625 1.414 062 5 b 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时的原方程的近 似解.

课堂小结 1.算法的概念
算法通常指可以用来解决的某一类问题的 步骤或程序,这些步骤或程序必须是明确的和 有效的,而且能够在有限步之内完成的.

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

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

算法步骤:
第一步:给定一个正实数r; 第二步:计算以r为半径的圆的面积S=πr2; 第三步:得到圆的面积S.