!算法设计与分析总复习.ppt

7、简述确定性图灵机和非确定性图灵机的区别，并说明何为P类问题，何为NP类问题。 确定性图灵机与非确定性图灵机的区别在于，确定性图灵机的每一步只有一种选择，而非确定性图灵机却可以有多种选择。P类问题是确定性计算模型下的易解问题类，而NP类问题是非确定性计算模型下的易验证问题类。 六、设计计算题 1、假设每一步可迈一个或二个或三个阶梯，请给出爬n个阶梯的递推公式 。 F(n)=0 n0; F(n)=1 n=0; F(n)=F(n-1)+F(n-2)+F(n-3) n0 2、已知有7个独立作业{1,2,3,4,5,6,7}由3台机器M1，M2和M3加工处理。各作业所需的处理时间分别为{2,14,4,16,6,5,3}。请给出利用贪心算法实现多机调度问题的步骤。 解：（1）按处理时间非递减排序{16,14,6,5,4,3,2}； （2）按机器个数建立最小堆，将前三个作业插入最小堆； （3）从堆中移出Min元素； （4）将其加上后序作业的加工时间，插入堆； （5）从第（3）步循环执行，直到所有作业处理完毕。 4 ? 2 7 5 6 3 1 M1 M2 M3 6 11 15 17 3、给定n种物品和一个背包。物品ｉ的重量是ｗｉ，体积是ｂｉ，其价值为ｖｉ，背包的容量为ｃ，容积为ｄ。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？在选择装入背包的物品时，对每种物品只有两种选择，即装入或不装入背包。不能将物品ｉ装入背包多次，也不能只装入部分的物品ｉ。试设计一个解此问题的动态规划算法，并分析算法的计算复杂性。 解：该问题是二维0-1背包问题。问题的形式化描述是，给定c0,d0,wi0, bi0,vi0,1?i?n，要求找出n元0-1 向量(x1,x2,…,xn),xi∈{0,1},1?i?n使得 ， 而且 达到最大。 因此，二维0-1背包问题也是一个特殊的整数规划问题。 max 的最优值为m(i,j,k),即m(i,j,k)是背包容量为j，容积为k，可选物品为i,i+1,…,n时二维0-1背包问题的最优解。由二维0-1背包问题的最优子结构性质，可以建立计算m(i,j,k)的递归式如下: 按此递归式计算出的m(n,c,d)为最优值。算法所需的计算时间为O(ncd)。 七、完善下列算法 1、假设合并排序算法的抽象定义为： Public static void mergeSort(Comparable a[], int left, int right) { } 其中使用的合并及拷贝方法分别定义为： Public static void merge(Comparable []c, Comparable []d,int l,int m,int r) { } Public static void copy(Comparable []c, Comparable []d, int i, int j) { } 请补充完善递归方式实现的合并排序的细节。 1、Public static void mergeSort(Comparable a[], int left, int right) { If(leftright){ Int i=(left+right)/2; mergwSort(a,left,i); mergeSort(a,i+1,right); merge(a,b,left,i,right ); copy(a,b,left,right); } } 2、请完善下面用回溯法有哪些信誉好的足球投注网站子集树的一般算法描述，其中由output(x)记录或输出得到的可行解 x[t]表示当前的扩展节点 void backtrack(int t) { If (tn) _① else for(int i=0;_②_____;i++) {_______③_______; if (constraint(t)bound(t)) ______④________; } } 3、请完善下面用回溯法有哪些信誉好的足球投注网站排列树的一般算法描述 void backtrack(int t) { If (tn) output(x) else for(int i=__①__;____②_____;i++) {_______③_______; if (constraint(t)bound(t)) backtrack(t+1