分治算法策略文档格式.docx
- 文档编号:7116341
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:15
- 大小:23.97KB
分治算法策略文档格式.docx
《分治算法策略文档格式.docx》由会员分享,可在线阅读,更多相关《分治算法策略文档格式.docx(15页珍藏版)》请在冰点文库上搜索。
1.枚举法
根据根的值域和根与根之间的间距要求(≥1),我们不妨将根的值域扩大100倍(-10000
≤x≤10000),依次枚举该区间的每一个整数值x,并在题目要求的精度内设定区间:
若区间端点的函数值f’(x1)和f’(x2)异号或者在区间端点x1的函数值f’(x1)=0,则确定为f’(x)=0的一个根。
由此得出算法:
2.分治法
枚举根的值域中的每一个整数x(-100≤x≤100)。
由于根与根之差的绝对值≥1,因此设定搜索区间[x1,x2],其中x1=x,x2=x+1。
若
⑴f’(x1)=0,则确定x1为f’(x)的根;
⑵f’(x1)*f’(x2)>
0,则确定根x不在区间[x1,x2]内,设定[x2,x2+1]为下一个搜索区间
⑶f’(x1)*f’(x2)<
0,则确定根x在区间[x1,x2]内。
如果确定根x在区间[x1,x2]内的话(f’(x1)*f’(x2)<
0),如何在该区间找到根的确切位置。
采用二分法,将区间[x1,x2]分成左右两个子区间:
左子区间[x1,x]和右子区间[x,x2](其中
):
如果f’(x1)*f’(x)≤0,则确定根在左区间[x1,x]内,将x设为该区间的右指针(x2=x),
继续对左区间进行对分;
如果f’(x1)*f’(x)>
0,则确定根在右区间[x,x2]内,将x设为
该区间的左指针(x1=x),继续对右区间进行对分;
上述对分过程一直进行到区间的间距满足精度要求为止(x2-x1<
0.001)。
此时确定x1
为f’(x)的根。
其中f(x)的函数说明如枚举法所示。
【例4】小车问题(car)
【问题描述】
甲、乙两人同时从A地出发要尽快同时赶到B地。
出发时A地有一辆小车,可是这辆小车除了驾驶员外只能带一人。
已知甲、乙两人的步行速度一样,且小于车的速度。
问:
怎样利用小车才能使两人尽快同时到达。
【问题输入】
仅一行,三个数据分别表示AB两地的距离s,人的步行速度a,车的速度b。
【问题输出】
两人同时到达B地需要的最短时间。
【输入输出样例】
car.in
120525
car.out
9.6000000000E+00
【算法分析】最佳方案为:
甲先乘车到达K处后下车步行,小车再回头接已走到C处的乙,在D处相遇后,乙再乘车赶往B,最后甲、乙一起到达B地。
如下图所示,这时所用的时间最短。
这样问题就转换成了求K处的位置,我们用二分法,不断尝试,直到满足同时到达的时间精度。
算法框架如下:
1、输入s,a,b;
2、c0:
=0;
c1:
=s;
c:
=(c0+c1)/2;
3、求t1,t2;
4、如果t1<
t2,那么c:
=(c0+c)/2否则c:
=(c+c1)/2;
反复执行3和4,直到abs(t1-t2)满足精度要求(即小于误差标准)。
参考程序(略)
【例5】循环比赛日程表(match.?
?
)
设有n个选手的循环比赛,其中n=2m,要求每名选手要与其他n-1名选手都赛一次。
每名选手每天比赛一次,循环赛共进行n-1天。
要求每天没有选手轮空.以下是八名选手时的循环比赛表,表中第一行为八位选手的编号,下面七行依次是每位选手每天的对手。
12345678
21436587
34127856
43218765
56781234
65872143
78563412
87654321
[问题分析]
从八位选手的循环比赛表中可以看出,这是一个具有对称性的方阵,可以把方阵一分为四来看,那么左上角的4*4的方阵就是前四位选手的循环比赛表,而右上角的4*4的方阵就是后四位选手的循环比赛表,它们在本质上是一样的,都是4个选手的循环比赛表,所不同的只是选手编号不同而已,将左上角中方阵的所有元素加上4就能得到右上角的方阵.下方的两个方阵表示前四位选手和后四位选手进行交叉循环比赛的情况,同样具有对称性,将右上角方阵复制到左下角即得到1,2,3,4四位选手和5,6,7,8四位选手的循环比赛表,根据对称性,右下角的方阵应与左上角的方阵相同.这样,八名选手的循环比赛表可以由四名选手的循环比赛表根据对称性生成出来.同样地,四名选手的循环比赛表可以由二名选手的循环比赛表根据对称性生成出来,而两名选手的循环比赛表可以说是已知的,这种程序设计方法叫做分治法,其基本思想是把一个规模为n的问题分成若干个规模较小的问题,使得从这些较小问题的解易于构造出整个问题的解.
程序中用数组matchlist记录n名选手的循环比赛表,整个循环比赛表从最初的1*1的方阵按上述规则生成出2*2的方阵,再生成出4*4的方阵,……,直到生成出整个循环比赛表为止.变量half表示当前方阵的大小,也是要生成的下一个方阵的大小的一半.
[参考程序]
constmaxn=32;
maxm=5;
vari,j,k,m,n,half:
integer;
matchlist:
array[1..maxn,1..maxn]ofinteger;
begin
write('
Inputm:
'
);
readln(m);
n:
=1;
fori:
=1tomdon:
=n*2;
k:
matchlist[1,1]:
half:
whilek<
=mdo
begin
=1tohalfdo{构造右上角方阵}
forj:
=1tohalfdomatchlist[i,j+half]:
=matchlist[i,j]+half;
=1tohalfdo{对称交换构造下半部分方阵}
=1tohalfdo
matchlist[i+half,j]:
=matchlist[i,j+half];
matchlist[i+half,j+half]:
=matchlist[i,j]
end;
=half*2;
=k+1
=1tondo
=1tondowrite(matchlist[i,j]:
4);
writeln
end.
[样例]Inputm:
4
Output:
12345678910111213141516
21436587109121114131615
34127856111291015161314
43218765121110916151413
56781234131415169101112
65872143141316151091211
78563412151613141112910
87654321161514131211109
91011121314151612345678
10912111413161521436587
11129101516131434127856
12111091615141343218765
13141516910111256781234
14131615109121165872143
15161314111291078563412
16151413121110987654321
【例6】残缺棋盘问置
【问题描述】
残缺棋盘是一个2k×
2k个方格的棋盘.其中恰好有一个方格残缺,现在要求三格板覆盖棋盘,在此覆盖中两块三格板不能重叠,三格板也不能覆盖在残缺的方格上。
当k=l时各种可能的的残缺的棋盘如图4-3所示,其中残缺部分用阴影表示。
三格板的四个不同方向如下图4—4所示:
第一行输入棋盘总行敷.第二行输入残缺的格子坐标。
覆盖的矩阵图
【样例输入】
4
41
【样例输出】
2233
2113
4415
0455
【问题分析】:
很明显,当K=0时是不需要三格板的,而当K=1时只需要1块三格扳就够了。
那么关键在于K>
1时情况就有些复杂了,以K=2时的某种情况(如图4-5所示)为例,如果我们按一般的搜索来实现也是可行的,但在时问上会有很多浪费。
不妨先归纳一下放三格板时是否有规律可循:
如果将第一块三格板放在如图4-5所示的位置上时,让区域居中的原来无阴影的小区域都变成有一个阴影,这样四个相等小区域都缺了一角,问题一下子明朗了。
在本例中需要的数据有:
(1)用一个二维数组board[i,j]表示棋盘,其中i表示棋盘的行,j表示棋盘的列;
(2)一个表示三格板数目的全局变量title,该变量同时也用来表示每次覆盖的三格板的编号。
递归中所使用的函数为:
fugai(tr,tc,dr,dc,size)
tr整型,表示区域左上角的行号;
tc整型,表示区域左上角的列号;
dr整型,表示残缺格所在的行号;
dc整型,表示残缺格所在的列号:
size整型,表示待放置区域的总行数或总列数。
【算法描述】
functionfugai(tr,tc,dr,dc,size:
integer);
ifsize=1then结束;
title:
=title+1;
{三格板的数目+1}
size:
=sizediv2;
{区域大小减半}
if残缺格在下部
thenif残缺格在右部
thenbegin将右下角设为阴影,填上三格板编号;
分别对四个小区域进行覆盖
end
elsebegin将左下角设为阴影,填上三格板编号:
elseif残缺格在右部
thenbegin将右上角设为阴影,填上三格板编号;
elsebegin将左上角设为阴影,填上三格板编号;
end
【参考程序】:
programp4_2(input,output);
varn,x,y,title:
board:
array[1..100,1..100]ofinteger;
procedurefugai(tr,tc,dr,dc,size:
varxr,xc,yr,yc:
ifsize=1
thenexit
elsetitle:
ifdr>
=tr+sizethen
ifdc>
=tc+size
then
board[tr+size-1,tc+size-1]:
=title;
board[tr+size-1,tc+size]:
board[tr+size,tc+size-1]:
fugai(tr,tc,tr+size-1,tc+size-1,size);
fugai(tr+size,tc,tr+size,tc+size-1,size);
fugai(tr,tc+size,tr+size-1,tc+size,size);
fugai(tr+size,tc+size,dr,dc,size);
else
board[tr+size,tc+size]:
fugai(tr+size,tc,dr,dc,size);
fugai(tr+size,tc+size,tr+size,tc+size,size);
fugai(tr,tc+size,dr,dc,size);
fugai(tr,tc,dr,dc,size);
end;
procedureprint(n:
vari,j:
=1tondowrite(board[i,j]:
5);
assign(input,'
word.in'
reset(input);
assign(output,'
word.out'
rewrite(output);
readln(n);
readln(x,y);
fugai(1,1,x,y,n);
print(n);
上机练习题:
1、一元三次方程求解(equ)
:
9000/vijos/Problem_Show.asp?
id=1022
ax^3+bx^2+cx+d=0这样的一个一元三次方程。
给出该方程中各项的系数(a,b,c,d均为实数),并约定该方程存在三个不同实根(根的范围在-100至100之间),且根与根之差的绝对值>
=1。
要求由小到大依次在同一行输出这三个实根(根与根之间留有空格),并精确到小数点后2位。
记方程f(x)=0,若存在2个数x1和x2,且x1<
x2,f(x1)*f(x2)<
0,则在(x1,x2)之间一定有一个根。
样例
输入:
1-5-420
输出:
-2.002.005.00
2、小车问题(car)
id=1455
甲、乙两人同时从A地出发要尽快同时赶到B地。
两人同时到达B地需要的最短时间。
(保留5位小数)
【输入输出样例】
9.60000
3、取余运算(mod)
:
id=1457
输入b,p,k的值,求bpmodk的值。
其中b,p,k*k为长整型数。
【样例】
mod.inmod.out
21092^10mod9=7
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 分治 算法 策略