c语言算法 - 分而治之算法

练习

1.将例1 4 - 1的分而治之算法扩充到n> 1个硬币的情形。需要进行多少次重量的比较？

2.考虑例1 4 - 1的伪币问题。假设把条件“伪币比真币轻”改为“伪币与真币的重量不同”，同样假定袋中有n个硬币。

1)给出相应分而治之算法的形式化描述，该算法可输出信息“不存在伪币”或找出伪币。算法应递归地将大的问题划分成两个较小的问题。需要多少次比较才能找到伪币（如果存在伪币）？

2)重复1)，但把大问题划分为三个较小问题。

3.1)编写一个C++ 程序，实现例1 4 - 2中寻找n个元素中最大值和最小值的两种方案。使用递归来完成分而治之方案。

2)程序2 - 2 6和2 - 2 7是另外两个寻找n个元素中最大值和最小值的代码。试分别计算出每段程序所需要的最少和最大比较次数。

3)在n 分别等于1 0 0，1 0 0 0或10 000的情况下，比较1）、2）中的程序和程序1 4 - 1的运行时间。对于程序2 - 2 7，使用平均时间和最坏情况下的时间。1）中的程序和程序2 - 2 6应具有相同的平均时间和最坏情况下的时间。

4)注意到如果比较操作的开销不是很高，分而治之算法在最坏情况下不会比其他算法优越，为什么？它的平均时间优于程序2 - 2 7吗？为什么？

4.证明直接运用公式（1 4 -2）~（1 4 - 5）得出结果的矩阵乘法的分而治之算法的复杂性为(n3)。因此相应的分而治之程序将比程序2 - 2 4要慢。

5.用迭代的方法来证明公式（1 4 - 6）的递归值为(n l og27)。

*6.编写S t r a s s e n矩阵乘法程序。利用不同的k 值（见公式（1 4 - 6））进行实验，以确定k为何值时程序性能最佳。比较程序及程序2 - 2 4的运行时间。可取n为2的幂来进行比较。

7.当n 不是2的幂时，可以通过增加矩阵的行和列来得到一个大小为2的幂的矩阵。假设使用最少的行数和列数将矩阵扩充为m阶矩阵，其中m为2的幂。

1)求m/n。

2)可使用哪些矩阵项组成新的行和列，以使新矩阵A'和B' 相乘时，原来的矩阵A和B相乘的结果会出现在C' 的左上角？

3)使用S t r a s s e n方法计算A' * B' 所需要的时间为(m2.81)。给出以n为变量的运行时间表达式。