其中sn上承载m+1+f[n-1]=2*(m+1)只青蛙，sn-1，…，s1上承载f[n-1]=(2-1)*(m+1)只青蛙。
2、计算能够过河的青蛙数的最大值 当f[n]只青蛙移至河心n个石墩后，按照站队和移动规则，首先应将左岸石墩A上的m+1只青蛙移至右岸石墩D。然后将河心n个石墩上的f[n]只青蛙移至D。设
g[n]—河心有n个石墩、m片荷叶时能够过河的最大青蛙数。显然，如果河心n个石墩
上的f[n]只青蛙能够顺利移至D，则g[n]可达到最大值g[n]=m+1+f[n]；
首先我们将s1上的m+1只青蛙移至右岸的石墩D，s1变空；然后将s2上的前m+1只青蛙移至s1，后m+1只青蛙移至D，s1上的m+1只青蛙移至D，s1和s2变空；??；在移动si上的m+1+f[i-1]只青蛙前，si-1，?，s1为空。我们先依照A上的f[i-1]只青蛙移至si-1，?s1的顺序，将si上的前f[i-1]只青蛙过渡至si-1?s1上；然后将si上未尾的m+1只青蛙移至D；最后重复si-1?s1上的f[i-1]只青蛙移至D的顺序，将si-1?s1上暂放的青蛙全部移走；?；依次类推，直至sn上的青蛙移至D为止。
n-1n-1
由此可见，g[n]=m+1+f[n]
n
=m+1+(2-1)*(m+1)
n
=2*(m+1) 计算过程如下： g←1；
for i：=1 to n do g←g*2； 输出g*(m+1)；
§5．2 分治策略
将问题的规模逐渐减少，可明显降低解决问题复杂程度。算法设计的这种策略称之为分治策略，即对问题分而治之。用分治策略求解一个问题，所需的时间是由子问题的个数、大小以及把这个问题分解为子问题所需的工作总量来确定。一般来说，把任意大小的问题尽可能地等分成两个子问题较为有效。竞赛中常用的分治策略有 ●减半递推技术 ●二分法
一、减半递推技术
所谓“减半”是指将问题的规模减半，而问题的性质不变。假设原问题的规模为n，则可以采用与问题有关的特定方法将原问题化为c (c是与规模无关而只与问题有关的常数)个
n规模减半的问题，然后通过研究规模为2的问题(显然与原问题性质相同，只是规模不同而
已)来解决问题。问题的规模减少了，会给解决问题带来不少方便。但是，在规模减半过程中，势必增加某些辅助工作，在分析工作量时必须予以考虑。
n 所谓“递推”是指重复上述“减半”过程。因为规模为2的问题又可以化为c个规模n为4的相同性质的问题。依此类推，直至使用问题的规模减少到最小，以致于很方便地解
决为止。
【例题廿八】计算方程根
设方程f(x)=0在区间[a，b]内且仅有一个实数根，且f(x)在区间的两个端点处的函数值异号，即f(a)*f(b)<0。 输入：
an an-1?a0，表明f(x)=anxn+an-1xn-1+?+a1x+a0
a b，表明f(x)在[a，b]内仅有一个实数根且f(a)与f(b)异号 输出：
c，即f(c)=0 算法分析
首先取区间[a，b]的中点c=(a+b)/2，然后判断f(c)是否为0。若f(c)=0，则c即为所求的根，求解过程结束；否则根据以下原则将原求解区间减半：
若f(a)*f(c)<0，则取区间前半部分，即b←c（图5．2—1(a)） 若f(a)*f(c)>0，则取区间后半部分，即a←c(图5．2—1(b))
然后判断减半后的区间是否已经很小（设精度为?）
a?b 若|a-b|
若|a-b|≥?，则重复上述减半过程。
设f0，f1—当前区间左端处函数值和中点处函数值； 我们按照下述方法计算f函数的实数根：
function f(x)：real； {计算自变量为x时的
函数值}
begin
f←anxn+an-1xn-1+?+a1x+a0； end；{f}
begin
f0←f(a)； {计算左端处的函数值}
while |b-a|≥? do {若实根未满足精度要求，则循环}
begin
a?b c←2； f1←f(c)； {计算中点和中点处的
函数值}
if f1=0 then 输出根为c并退出程序
if f0*f1>0 then begin a←c； f0←f(a)； end； {取区间后半部分}
else b←c； {否则取区间前半部分}
end；{while}
a?b c←2； 输出实根c；
end；{main} 【例题廿九】行程问题
Ａ与B两地相距s公里，甲乙两人同时从A地出发要尽快同时赶到B地完成一项任务。出发时，A地有一辆出租车，只能带一人。若已知甲、乙步行速度为a公里/小时，出租车速度为b公里/小时（b>a）。试问怎样利用出租车才能使甲乙两人尽快到达B，共同完成任务。 输入：
s a b 输出：
甲乙两人到达Ｂ地的时间 算法分析
我们将行程问题描述为
甲先乘车到达C点后下车，此时乙步行到E。甲由C点出发往B点步行，出租车回头接乙，在D点相遇乙，乙坐上出租车驶往B点。当出租车到达B点时，甲亦步行至该点。 设
Tac—甲乘车到C点下车的时间。
Tac?lb；
Tcd—坐出租车从C点回头行驶，相遇步行的乙时行驶的时间(出租车由C→D的时间)
Tcd?l?Tac*aEC?a?ba?b
T1?Tac?s?la；
T1—甲从A点至B点的时间。
T2—乙从A点至B点的时间。
T2?Tac?Tcd?s?(Tac?Tdc)*aDB?Tac?Tcd?bb。
T1?T22； 当|T1-T2|<精度?时，认为甲和乙同时到达B点，他们花费的时间近似为
本题的关键是求C点的位置，我们采用减半递推技术，将C点取为区间[l0，l1]的中点，即
l?l0?l12。初始时l0=0，l1=s。然后按照上式计算T1和T2。
若T1>T2（乙最先到达B），则取区间后半部分，即l0←l； 若T1 T1?T22为甲乙两人到达B点的近似时间； 若|T1-T2| 若|T1-T2|≥?，则重复上述减半过程。 由此得出算法： l0←0；l1←s； repeat l1?l0 l←2； {取区间 中点} l?Tac*a Tac←l/b； Tcd←a?b； {分别计算甲和乙到达B点 的时间} Tac? T1← s?ls?(Tac?Tcd)*aTac?Tcd?;a;；T2←b