算法复习资料(共5页).doc

《算法复习资料(共5页).doc》由会员分享，可在线阅读，更多相关《算法复习资料(共5页).doc（5页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上 1.在33个方格的方阵中要填入数字1到N（N10）内的某9个数字，每个方格填一个整数，使得所有相邻两个方格内的两个整数之和为质数。试给出该问题的回溯算法，求出所有满足这个要求的各种数字填法。递归形式的回溯算法：INPUT: 数字1到N（N10）。OUTPUT: 所有满足条件的填充方法。 1. For k =1to 9 2. ck =0 3. End for 4. flag=false 5. tianzi(1) 6. if flag=false then output “no solution”过程 tianzi(k) 1. For m=1 to N 2. ck =m

2、 3. If c为合法填充方法的then得到一个填充方法，输出c数组，flag=true4. Else if c是部分的 then tianzi(k+1) 5. End for 非递归的回溯算法：INPUT: 数字1到N（N10）。OUTPUT: 所有满足条件的填充方法。1. For k =1 to 9 2. ck =0 3.End for4. falg=false5. k =1 6. While k17.While ckN-1 8.ck =ck+19.If c为合法的填充方法 then得到一个填充方法，输出c数组，flag=true10.Else if c是部分解 then k =k+1 1

3、1 End while12.ck =013.k =k-114.End while 15. if flag=false then output “no solution 2.分数背包问题的贪心算法给出n个物品，它们的体积为，价值为，并设背包的容量为C。我们想找到一种选择将物品放入背包使得所得的价值最大。即要找，在约束条件下最大。其中， 是非负实数，要求输出每种物品装入背包的体积，即每种物品对应的。算法：INPUT: n个物品，体积为,价值为 ，背包的容量为C。OUTPUT: 总价值最大，并且满足，其中是非负实数。1. 对n个物品求出每个物品的，并按降序排列，相应的体积和价值存入vn和sn数组中。

4、2. x1n=0, value=0，space=C3. for i=1 to n 4. if si=space then5. xi=si ; space=space-si; value=value+vi; 6. else xi=space; value=value+space*vi/si; break; 7. end for 8. output x1n和总的最大价值value;时间复杂度：算法的时间复杂性可描述为O(n)。3 钱币问题的动态规划算法有一个货币系统，它有n种硬币，它们的面值为v1,v2,vn，其中v1=1。想要兑换的钱数为y，给出兑换的最少硬币个数。 算法：INPUT: n种硬币

5、，以及它们的面值v1,v2,vn，要换的钱数y。OUTPUT:兑换y钱的最少硬币个数。1. for i=0 to n2. Ni,0=03. end for 4. for j=0 to y5. N0,j=06. end for7. for i=1 to n8. for j=1 to y9. Ni,j=Ni-1,j10. if jvi then 11. 12. Ni,j=min Ni,j, Ni-1,j-kvi+k13. end if 14. end for15. end for 16. return Nn,y时间复杂性：钱币兑换问题的动态规划算法有典型的循环迭代结构，并且每次循环都是在填一个表项

6、，算法的时间复杂性刚好是表的大小，即(ny)。4. 合并排序的分治算法已知数组A1.n，要求算法首先把输入数组A1n划分成4个部分A1, A2, A3和A4，然后分别对每部分递归排序，最后将4个已排序部分合并得到排好序的数组A。假定数组大小n是4的整数幂。要求：(1) 写出该问题的分治算法；(2) 求解递推式，给出算法的最大元素比较次数。(1) 写出该问题的分治算法；算法：输入：n个元素的数组A1n输出：按非降序排列的数组A1n 1. fourmergesort(A, 1, n)过程 fourmergesort(A, low, high) 1.if low1，则执行了步骤2到11，算法中执行步

7、骤5，6，7，8的最大元素比较次数为C(n/4)。步骤9，10，11主要是合并算法MERGE的比较次数，因此，步骤9，10的最大比较次数为n/2-1, 步骤11的最大元素比较次数为n-1。因此可以得到求解最大元素比较次数的递推公式为：简化为：利用展开法求解递推式如下：5.程序存储问题的贪心算法设有n个程序1，2，n要存放在长度为L的磁带上。程序i存放在磁带上的长度是li，1in。要求确定这n个程序在磁带上的一个存储方案，使得能够在磁带上存放尽可能多的程序。 (1) 程序存储问题的贪心算法INPUT: n个程序的长度l1, l2 , ln, 磁带的长度L。OUTPUT: 磁带上存放的最多的程序个数num，以及存入磁带的每个程序的编号数组pron。1. 对n个程序按长度升序排列，存入pn数组中。2. i=1，j=1, sum=03. while (sum+pi)d2dm作为输入.以n的函数形式给出该算法的效率类型.Algorithms change(n,D1.m)/输出:数组A1.m-每种面额硬币的数量,或者无解贪心策略： 依据顾客的服务时间首先进行排序，然后从中依次安排每一个人进行服务，其中要注意s是提供服务的处所。 （算法略，请自己写）