二分法c语言

我们先举例说明一下计算逻辑。对于给定的函数f(x)，如果知道f(x)=0在区间[a，b]上有解，是否可以不用解公式，只通过函数的数值计算就可以求出这个解？或者能不能找到一个近似的解？答案是肯定的。我们知道这个问题很有意义，因为在实际问题中，往往无法得到求解公式，只能用近似解代替真解。一般情况下，设这个真解为x0，如果我们找到一个近似解为x*，使得|x*-x0|≤10 -n，我们说x*是精确到10 -n的近似解..我们计算一个具体的例子，从中抽象出一种方法来求近似解。

设函数f(x)=x2+x-1，很容易验证f (0) =-1

第一个近似解是x(1)=(1-0)/2=1/2。因为f (1/2) =-1/4

第二个近似解是x(2)=1/2+(1-1/2)÷2=3/4。因为f (3/4) = 5/16 >: 0，所以解在[1/2，3/4]之间；

第三个近似解是x(3)=1/2+(3/4-1/2)÷2=5/8。因为f (5/8) = 1/64 >: 0，所以解在[1/2，5/8]之间；

第四个近似解是x(4)=1/2+(5/8-1/2)÷2=9/16。因为f(9/16)=-31/256，所以解在[9/16，5/8]之间；

第五个近似解是x(5)=9/16+(5/8-9/16)÷2=19/32。因为f(19/32)=-55/1024，所以解在[19/32，5/8]之间；

第六个近似解是x(6)=19/32+(5/8-19/32)÷2=39/64。因为f(39/64)=-79/4096，所以解在[39/64，5/8]之间；

第七个近似解是x(7)= 39/64+(5/8-39/64)÷2 = 79/128。因为f(79/128)=-31/16384，所以解在[79/128，5/8]之间。

这一计算过程的图示说明见图(1)。

图(1) 二分法的图形解释图(1)二分法的图解解释

大家可以看到，每一个解的过程都是逐渐接近真实解的，所以虽然我们不知道真实解是什么，因为

| x(7)-x0 |≤5/8-79/128 & lt；1/128 & lt；10-2

满足精度要求后，我们可以停止计算，作出如下近似解

x*=x(7) =17/128≈0.617

从上面的计算过程中很容易抽象出求近似解的规律:每个近似解都是前一个区间的中点。所以人们把这种解法叫做二分法，看似笨拙，实则有效，因为二分法的解法简单，可以任意逼近真解，计算的近似精度也很简单。但是我们上面描述的求解方法有一个致命的弱点，就是不知道上一步的计算结果就无法进行下一步的运算。这种方法不能用计算机自动计算，因为本质上这种运算方法还没有形成计算逻辑。那么，如何给出一个既符合上述运算规则，又能让计算机自动计算的计算逻辑呢？我们来详细讨论一下这个问题。

不失一般性，假设定义在区间[a，b]上的连续函数f(x)满足:f (a)

输入f(x)，a，b，n。

1.计算c=a+1/2(a+b)

2.如果|c-a|≤10 -n，转到说明7。否则

计算f(c)

4.如果f (c)

5.使b=c

6.返回说明1

7.设x * = C .停。

输出x*。

我们不用正式的计算机语言来表达，因为我们表达的是计算逻辑。虽然计算机使用的语言可以不同，但各种计算机语言遵循的计算逻辑是相同的。可以看出，遵循上述计算逻辑就可以达到我们的目的:在固定和有限步指令的帮助下，实现各种精度要求的各种自动化运算。正是因为这个计算程序的通用性，使得这个计算逻辑的实用性毋庸置疑。其次，如果仔细分析上述逻辑的叙述过程，可以发现这种逻辑叙述不仅要注意基本推理，还要注意系统推理，即注意整个推理过程的句子顺序，如:

使用一个可以连续替换的过渡符号C，每次运算后替换区间的端点A或B，解决了反复迭代运算的问题，也解决了自动运算的问题。

第二条指令是停止操作的指令，在正常操作中似乎是在操作之后，但从系统推理的角度来看，把这条指令作为第二条指令，然后用“否则”转到第三条指令是最合适的。

显然，一个算法的好坏与计算次数有关。在精度相同的要求下，计算次数越少越好(本质上是计算时间越少越好)。如果用m来表示计算次数，那么可以在上面的计算逻辑中添加什么地方、什么样的语句，使计算逻辑自动记录计算次数？我们可以这样设计它:

输入f(x)，a，b，n。

1.设m=0

2.m=m+l

3.计算c=a+1/2(a+b)

4.如果|c-a|≤10 -n，转到说明9。否则

5.计算，f(°c)

6.如果f (c)

7.使b=c

8.返回说明2

9.x*=c .停下来。

输出x*，m

在原有计算逻辑的基础上，增加替换符号m来表示计算次数。读者可以自己思考，把计算次数m放在指令1和指令2中。

二分法不仅是一种求解方法，也可用于实验设计。例如，当我们开发一种新的零食时，我们需要确定多少糖是合适的。如果口感好，应该如何确定糖的比例？显然，这是一个无法从理论上推理的问题，只能通过实验得出合适的结果。假设我们已经知道最合适的糖比在区间[a，b]内，f(x)代表糖比为x时的口感评价值，如果评价值越大越好，那么我们的问题就可以转化为求f(x)在[a，b]内的最大值。

因为无法给出f(x)的具体表达式，所以只能通过数值计算来求解。一个最简单的方法，可以取这个区间内的任意点，比如xl，…，xn。在这几个点上做实验，通过尝试可以得到f(x1)，…，f(xn)，然后取这几个值中的最大值作为最大值的近似值，比如这个近似值就是f( xm)，这样就可以在xm附近设定最合适的糖比例。可以想象，只要取足够多的点，就能得到很好的近似。但对于这样一类问题，人们不仅要得到一个近似值，还希望实验的次数越少越好，因为安排实验需要花费金钱和人力。一种简单易行的改进方法是分式法，可以看作是二分法的推广。其实这些方法都和黄金分割有关。