算法案例二分法学习教案.ppt

会计学
*
算法(suàn fǎ)案例二分法
第一页，共11页。
现有(xiàn yǒu)一商品，价格在0～8000元之间，采取怎样的策略才能在较短的时间内猜出正确的答案？
第一步：报“4000”；
第二步：若主持人说“高了”（说明(shuōmíng)答案在1～4000之间），就报“2000”，否则（答数在4000～8000之间）报“6000”；
第三步：重复第二步的报数方法，直至得到正确结果。
第1页/共10页
第二页，共11页。
如何(rúhé)赋值
从第二步算法分析：答案x*肯定在两个端点a,b之间，只是这两个端点a,b不断变化，我们(wǒ men)可以用赋值的手法使两个端点a,b相对固定,则x*=（a+b）/2
第2页/共10页
第三页，共11页。
第一步：可以给指定的区间端点为a,b（a<b），计算分点值x0=（a+b）/2
第二步：判断(pànduàn)分点值x0与x*差的符号，确定是“高了”还是“低了”；
第三步：若“高了”，则a不动，b赋值x0；若“低了”，则a赋值x0，b不动；
第四步：继续计算分点值
x0=（a+b）/2，进行循环计算，直至得到答案；
第3页/共10页
第四页，共11页。
例1．写出用二分法求方程x3-x-1=0在区间[1,]内的一个近似解（误差不超过(chāoguò)）的一个算法．
算法步骤：
S1 取[a,b]的中点x0=(a+b)/2,将区间一分为二；
S2 若f(x0)=0,则x0就是(jiùshì)根；否则判别根x*在x0的左侧还是在右侧；
若f(a)*f x0)>0，则x*∈(x0,b),以x0代替a；
若f(a)*f(x0)<0，则x*∈(a, x0),以x0代替b；
S3 若|a-b|<c,计算终止,此时x*≈ x0，否则转S1
第4页/共10页
第五页，共11页。
流程图与伪代码(dài mǎ)
10 Rend a,b,c
20 x0 ←(a+b)/2
30 f(a) ←a3-a-1
40 f(x0) ←x03-x0-1
50 If f(x0)=0 Then Go To 120
60 If f(a)f(x0)<0 Then
70 b ←x0
80 Else
90 a ←x0
100 End If
110 If |a-b|≧c Then Go To 20
120 Print x0
输入a,b,c
输出x0
b←x0
a←x0
f(a)←a3-a-1
f(x0)←x03-x0-1
X0←(a+b)/2
|a-b|<c
f(a)f(x0)<0
f(x0)=0
Y
N
Y
N
Y
第5页/共10页
第六页，共11页。
数学(shùxué)理论
用二分法设计求方程f(x)＝0的近似根算法的基本步骤：
1．确定近似根所在的基础区间[a,b]和近似根的精确度c；
2. 求有根区间的中点,判断是否满足精度(jīnɡ dù)要求；
3．求区间端点的函数值，f(a),f(b)
4. 判断f(a)f(b)的符号，改变有根区间的下限或上限
5．循环求近似根
6．输出根的近似值
第6页/共10页
第七页，共11页。
巩固(gǒnggù)运用
例2 将以二分法求方程x2-2＝0的近似根（）的一个算法(suàn fǎ)补充完整．
解：Sl 令f(m)＝x2-2，因为f(1)<0，f(2)>0，所以设x1＝l，x2＝2．
S2 令m＝ ，判断f(m)是否(shì fǒu)为0。若是，则m为所求；若否，则继续判断
S3 若 ，则x1←m；否则令x2←m．
S4 判定 <(shì fǒu)成立。若是，则x1,x2之间的任意取值均为满足条什的近似根，若否，则
第7页/共10页
第八页，共11页。
例3仟意给定一个大于１的正整数ｎ，设计(shèjì)一个算法求ｎ的所有因数．
Ｓ１　依次以２～（ｎ－１）为除数去除ｎ，检查余数是否为０，若是，则是n的因数；若不是，则不是ｎ的因数；
　Ｓ２　在ｎ的因数中加入1和n；
　Ｓ３　输出(shūchū)ｎ的所有因数．
第8页/共10页
第九页，共11页。
回顾(huígù)反思
第9页/共10页
第十页，共11页。