发布时间 : 星期四 文章算法设计与分析习题答案1-6章更新完毕开始阅读2a298a22bb0d4a7302768e9951e79b89690268cd
图5.15 俄式乘法
×m,m作为算法结束的条件。例如,图5.15给出了利用俄式乘法计算50×65的例子。据
说十九世纪的俄国农夫使用该算法并因此得名,这个算法也使得乘法的硬件实现速度非常
快,因为只使用移位就可以完成二进制数的折半和加倍。请设计算法实现俄式乘法。
//俄式乘法
#include
if(m%2==0)//如果n是偶数 { n=n*2; m=m/2; }
else//如果n是奇数 { n=n*2; sum+=temp; m=(m-1)/2;
}
temp=n;//记录倒数第二个n的值 }
return sum+n; }
int main() { int a,b;
while(cin>>a>>b) {
cout< 8. 拿子游戏。考虑下面这个游戏:桌子上有一堆火柴,游戏开始时共有n根火柴,两 个玩家轮流拿走1,2,3或4根火柴,拿走最后一根火柴的玩家为获胜方。请为先走的玩 家设计一个制胜的策略(如果该策略存在)。 如果桌上有小于4根的火柴,先手必胜,如果是5根,先手必输;依次类推,同理15、20、25…….都是必输状态;所有每次把对手逼到15、20、25…….等必输状态,就可以获胜。 9. 竞赛树是一棵完全二叉树,它反映了一系列“淘汰赛”的结果:叶子代表参加比赛的n个选手,每个内部结点代表由该结点的孩子结点所代表的选手中的胜者,显然,树的根结点就代表了淘汰赛的冠军。请回答下列问题: (1)这一系列的淘汰赛中比赛的总场数是多少, (2)设计一个高效的算法,它能够利用比赛中产生的信息确定亚军。 (1)因为n人进行淘汰赛,要淘汰n-1人,所有要进行n-1场比赛。 (2) 10. 在120枚外观相同的硬币中,有一枚是假币,并且已知假币与真币的重量不同,但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币,最坏情况下,能不能只比较5次就检测出这枚假币, 将120枚平均分为三组,记为:A,B,C;先将A,B比较,如果A,B重量不同(假如B比A重),再将B与C比较,如果B,C相同,则A有假币;如果B,C不同,再将A,C比较,如果A,C相同,则B有假币;如果A,C不同,则B有假币;如果A,B相同,则C有假币; 习题6 1. 动态规划法为什么都需要填表,如何设计表格的结构, 在填写表格过程中,不仅可以使问题更加清晰,更重要的是可以确定问题的存储结构; 设计表格,以自底向上的方式计算各个子问题的解并填表。 2. 对于图6.26所示多段图,用动态规划法求从顶点0到顶点12的最短路径,写出求解过程。 1 6 3 8 1 7 3 3 3 5 6 5 10 4 4 5 5 8 2 0 12 3 3 5 8 3 3 11 7 9 8 2 6 6 6 4 图6.26 第2题图 将该多段图分为四段; 首先求解初始子问题,可直接获得: d(0, 1)=c,5(0?1) 01 d(0, 2)=c,3(0?1) 02 再求解下一个阶段的子问题,有: d(0,3)= d(0, 1)+ c =6(1?3) 13 d(0,4)=min{d(0,1)+ c ,d(0,2)+ c}=8(1?4) 1424 。。。。。。。。(以此类推) 最短路径为:0?1?3?8?11?12 3(用动态规划法求如下0/1背包问题的最优解:有5个物品,其重量分别为(3, 2, 1, 4,5), 价值分别为(25, 20, 15, 40, 50),背包容量为6。写出求解过程。 (x1, x2,x3,x4,x5) ?(1,1,1,0,0)(过程略) 4. 用动态规划法求两个字符串A=\和B=\的最长公共子序列。写出求 解过程。 略 5. 给定模式\和文本\,写出动态规划法求解K-近似匹配的过程。 略 6. 对于最优二叉查找树的动态规划算法,设计一个线性时间算法,从二维表R中生成 最优二叉查找树。 7. Ackermann函数A(m, n)的递归定义如下: n,1m,0, ,A(m,n),A(m,1,1)m,0,n,0 , ,A(m,1,A(m,n,1))m,0,n,0,