发布时间 : 星期六 文章算法设计与分析习题答案1-6章更新完毕开始阅读
图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,