当前位置:首页 >> 数学 >>

习题讲解2_图文

习题讲解

王培崇

? 一、
a.为一个分治算法编写伪代码,该算法求一个n个元素数组中 最大元素的位置.

b.如果数组中的若干个元素都具有最大值,该算法的输出是怎 样的呢?
c.建立该算法的键值比较次数的递推关系式并求解. d.请拿该算法与解同样问题的蛮力算法做一个比较

b.返回数组中位于最左边的最 大元素的序号.

? 二、

a.为一个分治算法编写伪代码,该算法 同时求出一个n元数组的最大元素和最 小元素的值。 b.请拿该算法与解同样问题的蛮力算法 做一个比较。

a.同时求出最大值和最小值,只需要将原数组一分为二, 再使用相同的方法找出这两个部分中的最大值和最小值,然后 经过比较就可以得到整个问题的最大值和最小值。 算法 MaxMin(A[l..r],Max,Min) //该算法利用分治技术得到数组A中的最大值和最小值 //输入:数值数组A[l..r] //输出:最大值Max和最小值Min if(r=l) Max←A[l];Min←A[l]; //只有一个元素时 else if r-l=1 //有两个元素时 if A[l]≤A[r] Max←A[r]; Min←A[l] else Max←A[l]; Min←A[r]

? else

//r-l>1

?
? ?

MaxMin(A[l,(l+r)/2],Max1,Min1); //递归 解决前一部分
MaxMin(A[(l+r/)2..r],Max2,Min2); //递 归解决后一部分 if Max1<Max2 个最大值中选择大值 Max= Max2 //从两部分的两

?

if Min2<Min1 小值中选择小值

Min=Min2; //从两部分的两个最

?}

b.假设n=2k,比较次数的递推关系式: C(n)=2C(n/2)+2 for n>2 C(1)=0, C(2)=1 C(n)=C(2k)=2C(2k-1)+2 =2[2C(2k-2)+2]+2 =22C(2k-2)+22+2 =22[2C(2k-3)+2]+22+2 =23C(2k-3)+23+22+2 ... =2k-1C(2)+2k-1+2k-2+...+2 //C(2)=1 =2k-1+2k-1+2k-2+...+2 //后面部分为等比数列求和 =2k-1+2k-2 //2(k-1)=n/2,2k=n =n/2+n-2 =3n/2-2

b.蛮力法的算法如下: 算法 simpleMaxMin(A[l..r]) //用蛮力法得到数组A的最大值和最小值 //输入:数值数组A[l..r] //输出:最大值Max和最小值Min Max=Min=A[l]; for i=l+1 to r do if A[i]>Max Max←A[i]; else if A[i]<Min Min←A[i] return Max,Min } 时间复杂度t(n)=2(n-1) (一共有n个数,n-1次比较能找到max,n-1次比较找到min, 所以是2n-2) 算法MaxMin的时间复杂度为3n/2-2,simpleMaxMin的时间 复杂度为2n-2,都属于Θ(n),但比较一下发现,MaxMin的速 度要比simpleMaxMin的快一些。

三、给出一个找零问题的实例,使得贪婪算法不能输出一个最 优解. 四、为找零问题写一个贪心算法的伪代码,它以金额n和硬币 的面额d1>d2>…>dm作为输入.以n的函数形式给出该算法的 效率类型. 三、找零实例略(参考课件) 四、Algorithms change(n,D[1..m]) //用贪婪法求找零问题 //输入:非负整数n,硬币面额以降序排列的数组D //输出:数组A[1..m]----每种面额硬币的数量,或者无解

五、排序和查找是经常遇到的问题。按照要求完成以下各题。 (1)对数组A={15,29,135,18,32,1,27,25,5},用快速排 序方法将其排成递减序。 (2)请描述递减数组进行二分搜索的基本思想,并给出非递归算 法。 (3)给出上述算法的递归算法。 (4)使用上述算法对(1)所得到的结果搜索如下元素,并给出搜 索过程:18,31,135。

六、假设有7个物品,它们的重量和价 值如下表所示。若这些物品均不能被分 割,且背包容量M=150,使用回溯方法 求解此背包问题。请写出状态空间搜索 树(20分)。 物品 A B C D E F G 容量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30

? 如果上述物品可以被分割,使用贪心算法求解 (1)首先依据下述标准进行: 重量、价值和单位价值。 (2)使用重量从小到大:FGBAEDC。得到贪心解 为:FGBAE全部放入,而D放入20%,得到价值 为165。 使用价值从大到小:DFBEGCA,得到贪心解 为:DFBE全部放入,而G放入80%,得到价值为: 189。 使用单位价值从大到小:FBGDECA,得到贪心 解为:FBGD全部放入,而E放入87.5%,得到价 值为190.625。 (3)显然使用单位价值作为标准得到的是最优解。

七:已知:

Ak ? (aij )ri *ri?1
(k )

k=1,2,3,4,5,6,r1=5,r2=10,r3=3, r4=12,r5=5,r6=50,r7=6, 求矩阵链积A1×A2×A3×A4×A5×A6的最佳求 积顺序。(要求:给出计算步骤)

求解矩阵为:【每个矩阵18分】 1 2 3 1 0 150 330 2 0 360 3 0 4 5 6

4 405 330 180 0

5 1655 2430 930 3000 0

6 2010 1950 1770 1860 1500 0

1 2 3 4 5 6

1 0

2 1 0

3 2 2 0

4 2 2 3 0

5 4 2 4 4 0

6 2 2 4 4 5 0

因此,最佳乘积序列为(A1A2)((A3A4)(A5A6)),共执行乘法 2010次。【结论2分】

? 八、 设x1、x2、x3是一个三角形的三条边,而且 x1+x2+x3=14。使用回溯法求解有多少种不同的三角形? 给出解答过程。

贪心策略: 依据顾客的服务时间首先进行排序,然后从中依 次安排每一个人进行服务,其中要注意s是提供服务的 处所。 (算法略,请自己写)

? 考试重点: 1、渐近线时间复杂度; 2、算法的设计与改进能力; 3、递推式求解; 4、分治法; 5、动态规划法; 6、回溯法;