T
tony_sunway
Unregistered / Unconfirmed
GUEST, unregistred user!
1、求下列递推式的解的增长次数
(1) T
=T(n-a)+T(a)+n 其中a>0是一个常量，n<=2时,T=O(1).
(2) T=4T(n/2)+n*n,T(1)=1
2、考虑下面背包问题的实例
物品 重量 价值
1 3 25
2 2 20
3 1 15
4 4 40
5 5 50
承重量W=7
(1)用动态规划表求最优子集的组成元素
(2)写一段自底向上的动态规划算法的伪代码解决上述问题.
3、编码问题
（1）对于下面的数据构造一套哈夫曼编码，注：要写出求解过程
字符 A B C D -
出现概率 0.4 0.1 0.2 0.15 0.15
（2）用1中的编码对ABACABAD进行编码
4、算法分析
算法：Smp(A[0...n-1]
//输入包含n个实数的数组A[0...n-1]
if n=1 return A[0]
else
temp<-Smp(A[0...n-2])
if temp<A[n-1] return temp
else
return A[n-1]
(1)该算法计算的是什么？
(2)建立该算法所作的基本操作次数的递推关系并求解。
5、算法设计
某人开车通过高速公路从广州到北京，汽车的油箱在装满时能跑n公里。他带了一张地图，上面标出从广州到北京各加油站之间的距离。请设计一个算法（以伪代码表示），给出一个路上加油的方案，使得他一路上加油的次数最少。（设有m个加油站，起点为一个，各加油站距离分别用S[1]....S[m]表示）
6、题目为图片，在http://www.zgbg.com/images/tmp/tree.jpg
本人就这么点家当，全部奉上！先谢谢了！
(1) T
=T(n-a)+T(a)+n 其中a>0是一个常量，n<=2时,T=O(1).(2) T
=4T(n/2)+n*n,T(1)=1 2、考虑下面背包问题的实例
物品 重量 价值
1 3 25
2 2 20
3 1 15
4 4 40
5 5 50
承重量W=7
(1)用动态规划表求最优子集的组成元素
(2)写一段自底向上的动态规划算法的伪代码解决上述问题.
3、编码问题
（1）对于下面的数据构造一套哈夫曼编码，注：要写出求解过程
字符 A B C D -
出现概率 0.4 0.1 0.2 0.15 0.15
（2）用1中的编码对ABACABAD进行编码
4、算法分析
算法：Smp(A[0...n-1]
//输入包含n个实数的数组A[0...n-1]
if n=1 return A[0]
else
temp<-Smp(A[0...n-2])
if temp<A[n-1] return temp
else
return A[n-1]
(1)该算法计算的是什么？
(2)建立该算法所作的基本操作次数的递推关系并求解。
5、算法设计
某人开车通过高速公路从广州到北京，汽车的油箱在装满时能跑n公里。他带了一张地图，上面标出从广州到北京各加油站之间的距离。请设计一个算法（以伪代码表示），给出一个路上加油的方案，使得他一路上加油的次数最少。（设有m个加油站，起点为一个，各加油站距离分别用S[1]....S[m]表示）
6、题目为图片，在http://www.zgbg.com/images/tmp/tree.jpg
本人就这么点家当，全部奉上！先谢谢了！