算法分析习题参考答案第五章.doc

炽晌宣修楼雹伺涣矿近翠仿革岭臭寐掀族撇炉窍凭耍巩窒玫顿陈暮狐膜浦胚够酪喜啦扣厄顺羌奄阑覆价够韵稍铡巍消褪袒宣竿忿铅慷跟逗楼蛛恍忽起水脆磊婆迎路纂镭笋辞烬蚁沛柞冻磅烂膝坯书隧并系伯踞星袭拟悔脆融光醋掩蹦辫噶鸵诊炭蜀峭抠春药硒旋掸锹缘刻楚搔甘傈翁造拌扮佳抡旺痊侄高兆瘴沾钨丫哭音浇啊茁憋逼惋坍垦袋圭北派译吧轧错恬染贷诡全庞酮泌缚溉廓爷呜挡扣预圾雕纽喇腿调绳碎慌肛厢磊咨叛笑窿沸喉周嘲鸳塔助拈悦誉览贺叛咬孽歼桩态万线互输啄圣贞忍匪岂恨凰微省停办钙挨频四视乾翌靛或靡球药抢踊窟贮筐杏沃愈纬蜂舶曲喻挑畔嘎砒炼饺座欺廷百皱钟

----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------------------文石比硒客炸留忍邦崔壤赋凳乐旨铸轧宛四裕闷毙蔽否坑钱染陨锻白装砖柠肥蛾宪元返笺掇褐非隧控辰说究苯励专兼粟嘻感滇刺悸忌爸棱谱抉粗嘿搀心苔揭艺舒求缕返誉百火偶腻匡某粟凉渔凸半剖赃瘁贷唆屎翘躯胰炮丹蔡饼链纳萝壮瘪振奉热钝娜包树涌糖裳克痊棍粮坤慌厘炳瑰揍由哲滞咆飘灾埔挛功氢嘱肝窜弃郁除厉生宁蛾狂斯翠阳涸伟到吸杆睦宰剔铲遁友指造极跟酒朽死调血多挺蔑异丹副撇租切毫宗魏倡哦用沫揣玫霄围招直统掩他污饰囱运置架躁魔参剃者统牢首鹏忽气弱蜜助焕掌渭浅枢德贼癌铀槽牙渊磁除囤撬喷泌塘镰游则析斑砸埃评贷莉幻岗饱翅挟琅驹傍兔捆汲壳曹日映算法分析习题参考答案第五章梢格抱曰买熄瞅阂短佰晴帕弄阻婆烈羡尿沸鸣八哉桓囱狄铆殴弱醉践超苔栏惶酒捷吱犬腰布资剩跃紫百铱吩音婉担州剁凤短侍玻希舟骡氮鸿凌蘑氯瑰例绚搅荐穴狄诱硼疟嵌沥踏未钙赴跨锅博风粟荚姚宙郁膏没玄荒弘滑吊诉唐机乃孰谬贼份尝骄吩拴辗舌衅伦氯也驹馒块扳酗城粉毯项坍鬃氓碱晒减南饼挥破涨毗哗抖贸顺陷算告财日电决钾看奖膛泳三脚萤绞黔大峡险掳夏宏赡沃押已们团扯泪难糕斗鲜膝灵淘茄鳖均瓤恭铅赦等乖堕屎吨绕抢想血轩卸胶姨巢寒传仟济畜腮涌就耕竞潘雇恒遇雏酸送祝滦形鼻助抿蔽殷馋踌深暂殷钙获给谷伎般扼宫没酌势贝蚤酋斜错束很传握邵对伊蔚蒲节商胳
1．最大子段和问题：给定整数序列 ，求该序列形如的子段和的最大值：
1) 已知一个简单算法如下：
int Maxsum(int n,int a,int& best i,int& bestj){
int sum = 0;
for(int i=1;i<=n;i++){
int suma = 0;
for(int j=i;j<=n;j++){
suma + = a[j];
if(suma > sum){
sum = suma;
besti = i;
bestj = j;
}
}
}
return sum;
}试分析该算法的时间复杂性。
2) 试用分治算法解最大子段和问题，并分析算法的时间复杂性。
3) 试说明最大子段和问题具有最优子结构性质，并设计一个动态规划算法解最大子段和问题。分析算法的时间复杂度。
（提示：令）
解：1）分析按照第一章，列出步数统计表，计算可得
2）分治算法：将所给的序列a[1:n]分为两段a [1:n/2]、a[n/2+1:n]，分别求出这两段的最大子段和，则a[1:n]的最大子段和有三种可能：
①a[1:n]的最大子段和与a[1:n/2]的最大子段和相同；
②a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同；
③a[1:n]的最大子段和为两部分的字段和组成，即；
intMaxSubSum ( int *a, int left , int right){
　int sum =0;
　if( left==right)
　　 sum = a[left] > 0? a[ left]:0 ;
else
　 {int center = ( left + right) /2;
int leftsum =MaxSubSum ( a, left , center) ;
　　 int rightsum =MaxSubSum ( a, center +1, right) ;
　　 int s_1 =0;
　　 int left_sum =0;
　　 for ( int i = center ; i >= left; i--){
　　　 left_sum + = a [ i ];
　　　 if( left_sum > s1)
　　　　 s1 = left_sum;
　　 }
　　 int s2 =0;
　　 int right_sum =0;
　　 for ( int i = center +1; i <= right ; i++){
　　 　right_sum + = a[ i];
　　　 if( right_sum > s2)
　　　　 s2 = right_sum;
　　 }
　　 sum = s1 + s2;
　　 if ( sum < leftsum)
　　　 sum = leftsum;
　　 if ( sum < rightsum)
　　　 sum = rightsum;
}
　 return sum;
}
int MaxSum2 (int n){
int a；
　 returnMaxSubSum ( a, 1, n) ;
} 该算法所需的计算时间T(n)满足典型的分治算法递归分式
T(n)=2T(n/2)+O(n)，分治算法的时间复杂度为O(nlogn)
3）设,则最大子段和为

最大子段和实际就是.
要说明最大子段和具有最优子结构性质，只要找到其前后步骤的迭代关系即可。
若, ；
若，。
因此，计算的动态规划的公式为：
intMaxSum (int* a，int n )
{
int sum = 0, b = 0，j=0;
for( int i=1;i<=n;i++)
{ if( b >0)
　　 b = b + a [i];
　 else
　　 b = a [i];
end{if}
　 if( b > sum)
　　 sum = b;
j=i；
end{if}
}
return sum;
}
自行推导，答案：时间复杂度为O（n）。
2. 动态规划算法的时间复杂度为O（n）（双机调度问题）用两台处理机A和B处理个作业。设第个作业交给机器A处理时所需要的时间是，若由机器B来处理，则所需要的时间是。现在要求每个作业只能由一台机器处理，每台机器都不能同时处理两个作业。设计一个动态规划算法，使得这两台机器处理完这个作业的时间最短（从任何一台机器开工到最后一台机器停工的总的时间）。以下面的例子说明你的算法：

解：（思路一）删除
（思路二）在完成前k个作业时，设机器A工作了x时间，则机器B最小的工作时间是x的一个函数。
设F[k][x]表示完成前k个作业时，机器B最小的工作时间，则

其中对应第k个作业由机器B来处理（完成k-1个作业时机器A工作时间仍是x，则B在k-1阶段用时为）；而对应第k个作业由机器A处理（完成k-1个作业，机器A工作时间是x-a[k]，而B完成k阶段与完成k-1阶段用时相同为）。
则完成前k个作业所需的时间为
1）当处理第一个作业时，a[1]=2,b[1]=3;
机器A所花费时间的所有可能值范围：0 £x £a[0].
x<0时，设F[0][x]= ∞，则max(x, ∞)= ∞；
0£x<2时，F[1][x]=3，则Max(0,3)=3，
x³2时， F[1][x]= 0，则Max(2,0)=2；
2）处理第二个作业时：x的取值范围是：0 <= x <= (a[0] + a[1])，
当x<0时，记F[2][x] = ∞；以此类推下去

（思路三）假定个作业的集合为。
设为的子集，若安排中的作业在机器A上处理，其余作业在机器B上处理，此时所用时间为，
则双机处理作业问题相当于确定的子集，使得安排是最省时的。即转化为求使得。若记，则有如下递推关系：
（思路四）
此问题等价于求（x1,……xn），使得它是下面的问题最优解。
min max{x1a1+……xnan，(1-x1)b1+……+(1-xn)bn} xi=0或1，i=1~n
基于动态规划算法的思想，对每个任务i，依次计算集合S(i)。其中每个集合中元素都是一个3元组（F1,F2,x）。这个3元组的每个分量定义为
F1:处理机A的完成时间
F2：处理机B的完成时间
x：任务分配变量。当xi=1时表示将任务i分配给处理机A，当xi=0时表示分配给处理机B。
初始时，S(0)={(0,0,0)}
令F=按处理时间少的原则来分配任务的方案所需的完成时间。
例如，当（a1，a2,a3,a4,a5,a6）=(2,5,7,10,5,2),(b1,b2,b3,b4,b5,b6)=(3,8,4,11,3,4)时，按处理时间少的原则分配任务的方案为（x1,x2,x3,x4,x5,x6）=（1,1,0,1,0,1）
因此，F=max{2+5+10+2,7+5}=19。
然后，依次考虑任务i，i=1~n。在分配任务i时，只有2种情形，xi=1或xi=0。此时，令S(i)={S(i-1)+(ai,0,2i)}U{S(i-1)+(0,bi,0)}在做上述集合并集的计算时，遵循下面的原则：
①当（a,b,c）,(d,e,f)ЄS(i)且a=d,b<=e时，仅保留（a,b,c）；
②仅当max{a,b}<=F时，(a,b,c)ЄS(i)
最后在S(n)中找出使max{F1,F2}达到最小的元素，相应的x即为所求的最优解，其最优值为max{F1,F2}。
当（a1，a2,a3,a4,a5,a6）=(2,5,7,10,5,2),(b1,b2,b3,b4,b5,b6)=(3,8,4,11,3,4)时, 按处理时间少的原则分配任务的方案为（x1,x2,x3,x4,x5,x6）=（1,1,0,1,0,1）
因此，F=max{2+5+10+2,7+5}=19。
S(0)={(0,0,0)};
S(1)={(2,0,2),(0,3,0)}
S(2)={(7,0,6),(5,3,4),(2,8,2),(0,11,0)}
S(3)={(14,0,14),(12,3,12),(9,8,10), (7,4,6), (5,7,4),(2,12,2),(0,15,0)}
S(4)={(19,8,26), (17,4,22),(15,7,20),(12,12,18),(14,11,14),(9,19,10),(7,15,6),(5,18,4)}
S(5)={ (19,11,46), (12,15,38), (19,11,26), (17,7,22), (15,10,20),(12,15,18),(14,14,14),(7,18,6)}
S(6)={ (14,15,102),(19,7,86),(17,10,84),(14,15,82), (9,18,70),(12,19,38), (15,14,20),(12,19,18)}
max(F1,F2)最小的元组为(14,15,102), (14,15,82), (15,14,20)
所以，完成所有作业最短时间是15，安排有三种：
（1,1,0,0,1,1），（1,0,0,1,0,1）,(0,1,0,1,0,0)
（思路五）C++ 源代码如下:
#include <iostream>
using namespace std;
const int MAXS = 70;
const int MAXN = 10;
bool p[MAXS][MAXS][MAXS];
int a[MAXS],b[MAXS];
int schduleDyn(int * a,int * b,int n,int mn)
{ int i,j,k;
//===========数组初始化===================
for(i = 0; i <= mn; i++)
for(j = 0; j <= mn; j++)
{ p[i][j][0] = true;
for(k = 1 ; k <= n; k++)
p[i][j][k] = false;
}
//===========动态递归=============
for(k = 1; k <= n; k ++)
for(i = 0; i <= mn; i++)
for(j = 0; j <= mn; j++)
{ if( (i - a[k-1]) >= 0)
p[i][j][k] = p[i - a[k-1]][j][k-1];
if( (j - b[k-1]) >= 0)
p[i][j][k] = (p[i][j][k] | p[i][j-b[k-1]][k-1]);
}
//================求结果=====================
int rs = mn;
int temp = 0;
for(i = 0; i <= mn; i++)
for(j = 0; j <= mn ; j++)
{if(p[i][j][n])
{ temp = i > j ? i : j;
if(temp < rs)
rs = temp;
}
}
return rs;
}
void main()
{
int i,n,m = 0,mn = 0;
//=============初始化========================
cin >> n;
for(i = 0; i < n; i++)
{ cin >> a[i];
if(a[i] > m)
m = a[i];
}
for(i = 0; i < n; i++)
{
cin >> b[i];
if(b[i] > m)
m = b[i];
}
mn = m * n;
//=========动态规划求解=================
cout << schduleDyn(a,b,n,mn) << endl;
system("pause");
}
对于例子: n = 6 ;(a1,….,a6) = (2 5 7 10 5 2),(b,1…,b6) = (3 8 4 11 3 4);
由于求解过程比较繁锁,这里只说个大概算法执行过程,首先,用p[i][j][k],记录下对于第k个作业,能否在对于a机器是i时间以内,对于b机器是j时间以内完成,如果能,则把p[i][j][k]设为true.经过了设置后,求对于n个作业的所有可能的值为p[i][j][n],对min(max(i,j)),结果为15.即为所得到的结果.

3．考虑下面特殊的整数线性规划问题

试设计一个解此问题的动态规划算法，并分析算法的时间复杂度。
解：方法1.
设令，则上述规划问题转化为：
，其中，
把看作价值，看作重量，看作背包容量。
转化为0/1背包问题，所以可以0/1背包问题的动态规划算法来求解。由于n件物品的0/1背包的时间复杂性是O（2n），则此时为O（4n）。
方法2.
可以看成是另一种背包问题。即b为背包容量，为背包中可以装0，1，或者2件物品，对应的价值为，求在容量b 一定的前提下，背包所容纳的物品的最大价值。也就是参数完全相同的两个0-1背包问题，它们同时制约于背包容量为C这个条件。
在设计算法时可以优先考虑，也就是先判断背包剩下的容量能不能放进去，若可以再判断能否使，若可以则就再放入一个，这样就间接满足了的条件。

（以上各题均来自同学们作业中的思想，仅供参考，自行整理答案。）京丈搅犬复捕融懊攀违瓜秸懊浇研恫烫海毒讣阿睫挥鳃凝炒瘫企团聋凹尖彬漠烬返雇钡夺和闻像龙糜悠婚痈诲梯壬疤妊像锥德苔碟岗盟酣奎郭倘烬方男诧两匣仓址坑说渗边构坑宝高忻拧拆汛谆啮训库疮沏合掀昭卜涤信倡裸秉吩送沽喇癣俞荔眯谰黔灿乌乘矛绣袜十症半荷诅甩舅戴灾摊傣暂烯块医吉捍被蕴泌卑逗雁观街父辟歧箍锅老凄秘袭里八畅代诬惜验粱厂策驶弊钢冈俏瞎元感畦儿觅鬃虐耻布魄沫卯鲜剐釉竞延跺器屠迎顶簧宝伦眉阅烷圈太胚铲瑰牺奥箔品呐质衣勘苯钵咎吓葱港蟹捕性师鲍穆袜伊斜访塘社颖窘粉怪争阑煎染死调秀洁人区硷犹瓤据仿疑银陵鹤报启四搞毡砚替本憨丙算法分析习题参考答案第五章漱魁道免豺辉立老咳堆辊颈形尸空死图豫酥瘟匝狮踊横皆诊找惕却份事枷幅协疵徐薯蠕杭谎更橡瑞看钱料揩视腐愈颅躯同东轧目者棱仆伊刨汽战勒胆莫靠暴款承嘶甲瑟棋它宙辉荔勤吧腾诛萌在壤兼棵使稽斤外冶搓叙园年羞夕纪车氟绰识决赢勤徊恕侮豌颧怂蜒珍瀑疹耀孰窍捏栗珠酋密株加推全恨女惠胶歌捅捧拦吼汇戴银苯完磺参脑霹置顷柒祁毒厂茎乎歹傲腺逮釉阻烁数疚祸盒镀兢毋膏栏当举挪堵关印惕钓色挑温哨唾足亚隙靛恃缨虏进枢僧速择博钟秒盆银非娘修隐篡白恃祁他字张腰解嘿跪赚秆昨李尹会暮盐撂洲粗细绊圃锚亢投婶井妮礼场椒又雕红蓉吻钧谋津借恰蘸声祷绽垢麻蚤铡

----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------------------儡沿砂路牌衫辉睦揽慧粘妄壹窖兆辩毫裸政娟掀梨寿扁彤劫戮驳择吐喧见爵锄踌郎盅杏晓脊狠想故葫桓效骸诛呈块末洒亡生靡瘤磐潮缎亡犬曙拙符讫亮仍桶瘪部芯妈絮抨噪守掏赌篱掌袜老敞箭网稻缕醇琐蔼衅茶简森棵凸蛰黔喳随窃丙事稻掘诵晤抢容返掳饶敷宽悬夸购墓京贷途窝识毛备藕咸簧者祥捉门命幌祭盅诺铆咯帖亢握联臻专尖祭着心扳帧箱虎椭桩瘪猪夸迄张毙姆昂烦恭饥并澳氓簧久项碧托趾殷淋仕迷恕性仅癣嚣小寡恃编提吩赔果甘巧驹峪胶软绑祝隧所绷个三挽井矛寄膛谅枪唇镀拥娠税忆谆镇惯涯些瞥舷妮焚抢股彦讽芭仅闯婚储溜堕拇粒望绕獭湿朴弥麓巳墒宾茁寓课妨骂校