文档介绍：算法案例(3)
二分法求近似解
1
精选ppt
现有一商品，价格在0～8000元之间，采取怎样的策略才能在较短的时间内猜出正确的答案？
第一步：报“4000”；
第二步：若主持人说“高了”（说明答案在1～4000之间），就报“2000”，否则（答数在4000～8000之间）报“6000”；
第三步：重复第二步的报数方法，直至得到正确结果。
2
精选ppt
如何赋值
从第二步算法分析：答案x*肯定在两个端点a,b之间，只是这两个端点a,b不断变化，我们可以用赋值的手法使两个端点a,b相对固定,则x*=（a+b）/2
3
精选ppt
第一步：可以给指定的区间端点为a,b（a<b），计算分点值x0=（a+b）/2
第二步：判断分点值x0与x*差的符号，确定是“高了”还是“低了”；
第三步：若“高了”，则a不动，b赋值x0；若“低了”，则a赋值x0，b不动；
第四步：继续计算分点值
x0=（a+b）/2，进行循环计算，直至得到答案；
4
精选ppt
例1．写出用二分法求方程x3-x-1=0在区间[1,]内的一个近似解（）的一个算法．
算法步骤：
S1 取[a,b]的中点x0=(a+b)/2,将区间一分为二；
S2 若f(x0)=0,则x0就是根；否则判别根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
5
精选ppt
流程图与伪代码
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
6
精选ppt
数学理论
用二分法设计求方程f(x)＝0的近似根算法的基本步骤：
1．确定近似根所在的基础区间[a,b]和近似根的精确度c；
2. 求有根区间的中点,判断是否满足精度要求；
3