NOIP初赛复习 - 算法1

其中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} 【例题廿九】行程问题

A与B两地相距s公里,甲乙两人同时从A地出发要尽快同时赶到B地完成一项任务。出发时,A地有一辆出租车,只能带一人。若已知甲、乙步行速度为a公里/小时,出租车速度为b公里/小时(b>a)。试问怎样利用出租车才能使甲乙两人尽快到达B,共同完成任务。 输入:

s a b 输出:

甲乙两人到达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

联系客服:779662525#qq.com(#替换为@)