算法设计与分析习题集
一、假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M
＝150，使用回溯方法求解此背包问题。请写出状态空间搜索树（20分）。
答：按照单位效益从大到小依次排列这7个物品为：FBGDECA 。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】
5x =6x =7x =17分，
每个节点1分】
a ．1501154040305035190.62540
-++++?= 7(1,1,1,1,,0,0)8
b. 1501154040305030177.560
-++++?=7(1,1,1,1,0,,0)12
c ．4040305010170++++=
(1,1,1,1,0,0,1)
d. 1501054040303530167.560
-++++?= 3(1,1,1,0,1,,0)4
e. 150130404050353017560
-++++?=
1
(1,1,0,1,1,,0)3
f. 1501304040503510170.7135
-++++?=
4(1,1,0,1,1,0,)7
g. 40405030160+++=
(1,1,0,1,0,1,0)
h. 1501404040353010146.8535-++++?= 2(1,1,0,0,1,1,)7
i.1501254030503530167.560-++++?=5(1,0,1,1,1,,0)12 j. 150145
4030503530157.560-++++?
=1(0,1,1,1,1,,0)12
在Q 1处获得该问题的最优解为(1,1,1,1,0,0,1)，背包效益为170。即在背包中装入物品F 、B 、G 、D 、A 时达到最大效益，为170，重量为150。【结论2分】
一、
已知1()*()i i k k ij r r A a +=，k =1，2，3，4，5，6，r 1=5，r 2=10，r 3=3，r 4=12，r 5=5，r 6=50，r 7=6，
求矩阵链积A 1×A 2×A 3×A 4×A 5×A 6的最佳求积顺序。（要求：给出计算步骤）（20分）
答：使用动态规划算法进行求解。
因此，最佳乘积序列为（A 1A 2）（（A 3A 4）（A 5A 6）），共执行乘法2010次。【结论2分】 二、
假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容
量M ＝150，如果使用贪心方法求解此背包问题，请回答：（20分）。
（1） 对各个物品进行排序时，依据的标准都有哪些？
（2） 使用上述标准分别对7个物品进行排序，并给出利用各个顺序进行贪心求解时获得解。 （3） 上述解中哪个是最优的？
答：
（1）标准：重量、价值和单位价值。【3分，每个1分】
（2）使用重量从小到大：FGBAEDC 。得到贪心解为：FGBAE 全部放入，而D 放入20%，得到价值为165。【5分】
使用价值从大到小：DFBEGCA ，得到贪心解为：DFBE 全部放入，而G 放入80%，得到价值为：189。【5分】
使用单位价值从大到小：FBGDECA ，得到贪心解为：FBGD 全部放入，而E 放入87.5%，得到价值为190.625。【5分】
（3）显然使用单位价值作为标准得到的是最优解。【2分】 三、
对于下图使用Dijkstra 算法求由顶点a 到其他各个顶点的最短路径。并给出求各个顶点对
之间的最短路径的算法思想。（20分）。
答：三、用V 1表示已经找到最短路径的顶点，V 2表示与V 1中某个顶点相邻接且不在V 1中的顶点；
E 1表示加入到最短路径中的边，E 2为与V 1中的顶点相邻接且距离最短的路径。【1分】 步骤 V 1 V 2 E 1 E 2 1. {a} {b} {} {ab} 2. {a,b} {d} {ab} {bd} 3. {a,b,d} {c,f} {ab,bd} {dc,df} 4. {a,b,d,c} {f} {ab,bd} {df} 5. {a,b,c,d,f} {e} {ab,bd,dc,df} {fe} 6. {a,b,c,d,e,f} {g} {ab,bd,dc,df,fe} {eg} 7. {a,b,c,d,e,f,g} {h} {ab,bd,dc,df,fe,eg} {gh}
8. {a,b,c,d,e,f,g,h} {} {ab,bd,de,df,fe,eg,gh} {} 【以上每步2分】 结果：从a 到h 的最短路径为a b d f e g h →→→→→→，权值为18。【1分】 求所有顶点对之间的最短路径可以使用Dijkstra 算法，使其起始节点从a 循环到h ，每次求起始节点到其他节点的最短路径，最终可以求得所有顶点对之间的最短路径。【2分】
1 给出一个()()C A B B A =-?-的算法
解：假设A 中元素个数为n,B 中元素个数为m. 1. 算法思想：输入两个序列A 、B
a.分别对A 、B 进行归并排序
b.同时扫描A 、B,设两个指针分别指向A 、B 的当前扫描元素。初始时i 、j 分别指向A[0]、B[0]
c. 若A[i]< B[j]则将A[i]存入C 中，i 后移 若A[i]>B[j] 则将B[j]存入C 中，j 后移
若A[i]= B[j] 则同时将i 、j 后移，直到分别出现与其前一个元素值不同的元素为止。 d 重复c 直至A 、B 同时扫描完或某一个扫描完，此时将另一个序列所有剩余元素直接 插入C 中即可。
归并排序的时间复杂度为)log log (22m m n n O +,扫描的时间复杂度为)(m n O +，总的时间复杂度为)log log (22m m n n O +。
3输入n 个元素，输出其不同元素。（O(nlogn)）
答案：n 个元素保存在数组E[n]中；
(1) 对E[n]进行排序(归并等时间复杂度为)log (2n n O 的算法); (2) 直接输出E[0];
(3) FOR i=1 TO n-1, 如果(E[i]==E[i-1]) 忽略该元素;否则输出E[i]。
4 给出最坏情况下，只需7次比较的5个元素的排序算法
答：假设5个元素为a1，a2，a3，a4，a5 1.对a1,a2,a3,a4进行3次比较
a4
a1
a4
a2
若a3>a4,a3和a4对换；若a1>a2,a1和a2对换；若a2>a4,a2和a4
对换且a1和a3对换. 生成序列为
a1a2a3
a4
2.将a5插入以上序列（用折半查找思想，共需2次比较）结果可能为：
a1a2a3
a4
a5
a1
a2a3
a4
a5
a1a2a3
a4
a5
a1a2a3
a4a5
3.将a3插入到以上四种可能，用折半查找，最多需要2次比较 由1、2、3得，此方法只需7次比较。
5 输入n 个元素，输出其和为m 的全部整数对。
答：首先对n 个元素按升序排序，对排好序元素设置首尾两个指针low,high,当low 如果E[low]+E[high]=m,则; low++;high--,输出数对 如果E[low]+E[high] 6输入n 个元素，输出其包含的最长等差数列。 定义三元组),,(j i d e ，其中i 、j 为元素标号且i (3) 对于所有具有相同公差d 的三元组{ ),,(),,,(222111j i d e j i d e }，查找“最长链” x x x c b b a a j i j i j i j i →=→=→=→-1 ，就可以找到公差为d 的最长的等差数列x x b a j i i i →→→ ，长度为1+x 。具体方法如下： e_start ，e_end 分别记录具有同一公差的三元组在E[K]中的起始、终止位置，初始e_start=1， e_end=-1。 顺序遍历有序的三元组数组E[K]中每一个三元组),,(t t t t j i d e ，其中t 从2开始 如果1-=t t d d 且K t ≠，那么继续遍历下一个三元组； 否则，如果K t ≠置e_end=t-1；如果K t =置e_end=t ； 并对E[K]中标号从e_start 到e_end 的三元组 )},,(,),,,({________end e end e end e end e start e start e start e start e j i d e j i d e 执行找 “最长链”的操作，找出的最长链x x b a j i i i →→→ 长度为1+x ， 如果max 1>+x ，则1max +=x 并将x x b a j i i i →→→ 保存到result 中。之后，置e_start=t 。 查找)},,(,),,,({________end e end e end e end e start e start e start e start e j i d e j i d e 中“最长链”方法如下： 数组next[n]，next[i]初始值为-1，最终记录元素i 应该链接的下一个元素的标号； 数组label[n]，label[i]初始为false ，记录每一个元素是否已经被访问过。 顺序遍历E[k][]中的每一个元组),,(t t k t j i d e ，如果][t i next 为-1，则t t j i next =][；否则，继续遍历下一个三元组。 从当前未被遍历的最小下标s 开始遍历，直到所有元素都被遍历过，执行操作： 如果next[s]是-1，那么label[s]=true ，记录下整数对(s,1)； 否则执行①②③ ①start=s,counter=1； ②执行操作label[s]=true ，s=next[s]，counter++，直到next[s]是-1为止； ③记录下整数对(start,counter)。 综上，counter 值最大的整数对中的start 值，就是 )},,(,),,,({________end e end e end e end e start e start e start e start e j i d e j i d e 中最长的等差数列的 起始位置，对应的最长链为end ...start]]next[next[]next[start start →→→→， 其中next[end]=-1。 7.归并排序的优点及优化措施. 答: 基于比较的排序算法平均时间复杂度)log ()(2n n O n A ≥与最坏时间复杂度)log ()(2n n O n W ≥。 证明：对于n 个元素来说，判定树的叶子数为!n ，其高度对应最深叶子的深度，而最深叶子 的深度对应最坏时间，即若要证明最坏时间)log (2n n O ≥，就要证明高度)log (2n n O ≥。 判定树高度为0时，叶子数≤20 =1。 判定树高度为1时，叶子数≤21 =2。 假设高度≤h 的判定树，有≤2h 个叶子，那么高度为h+1的判定树，左子树高度≤h ，叶子数≤2h 。 右子树高度≤h ，叶子数≤2h ，于是高度为h+1的判定树叶子数≤2h +2h =2h+1 。 所以高度为h 的判定树，叶子数≤2h ，因而叶子数为!n 的判定树高度≥)!(log 2n 。 所以比较排序的最坏时间)(n W ≥判定树的最大高度≥)!(log 2n 。 log ()1(2 ln 1 log )]1(ln [2ln 1ln 2ln 1log log )!log(2 11 22n O n n n n n n xdx xdx i n n n n i =--=--==≥=?? ∑ 比较排序的平均时间)(n A =判定树的平均叶子深度。 )log (log 2 1 )!(log 21)!(log .2!.!1)!(log !1)(!1)(222 22 ! 12! 1n n O n n n n n n n n i h n n A n i n i =≥==≥= ∑∑==推导说明: 叶子数为!n 的判定树高度)!(log 2n ≥，当判定树高度1)!(log 2-≤n 时，至多有 2 ! n 个叶子，因此在高度)!(log 2n ≥的判定树中，至少有 2 ! n 个叶子结点的深度至少为)!(log 2n 。第一次放缩时，将深度小于)!(log 2n 的叶子结点的深度都缩为0，只考虑剩余的深度为)!(log 2n 的2 ! n 个叶 子结点。 归并排序算法时间复杂度分析 最坏情况 采用归并排序算法对n 个元素排序，在一趟归并操作中，要进行的比较次数至多为n-1， 合并操作的公式为，n 表示元素的个数，有 () ????1)2/()2/(-++=n n W n W n W 可以递归推导得 2/)1(log log log )(+-=n n n n n W 即 ) log ()(n n n W θ∈。 所以归并排序优点为:平均时间与最坏时间都达到了排序的最好指标，速度快。 归并排序改进方法： 1）：与插入排序相结合 2）：无逆序 3）：不递归 4）：不回写 具体改进的算法描述： 将原数据集合分成若干组，分组策略如下： 第一组：从第1个元素1a 开始到第20个元素20a ，用插入排序排成有序集，从第21个元素起，按无逆序原则向后找到第一个出现逆序的元素1+k a 为止。那么第一组的元素为1a ,2a …20a …k a . 第二组：从1+k a 开始按照找第一组的方法，找出第二组; 第三组、第四组……依次类推。 按此方法将数据集分成若干组，在分组的过程中体现出与插入排序相结合和无逆序的改进。 对划分的组进行如下处理： 假定初始的元素存放在数组A 中，申请同样大存储空间的数组B 。 奇数趟归并排序时（此时元素存储在数组A 中），从前向后，两两相邻的分组归并后存放到数组B 。 偶数趟归并排序时（此时元素存储在数组B 中），从后向前，两两相邻的分组归并后存放到数组A 。 重复上述操作，直到最后归并到成一个集合为止。 按此方法对组进行归并排序，体现了不回写和不递归的改进。 8 对一个数值在(1,100)之间的数组进行排序，假设共有n 个元素。 （1）试给出基数排序的空间消耗，桶数，总需要时间。 （2）给出在基数排序过程中找出n 个元素（n>10）前10个最大的算法思想。 答： （1）桶的个数m （如m 取100）,此时只需一次装桶倒桶完成排序。n 个元素需要n 个空间存放，还需要n 个链表（2n ）空间，因此总共需要（3n+m ）个空间。清桶的时间复杂度为)(m O ；在元素插入链表时，将元素插入链头，这样插入的时间为)(n O ；然后倒桶的时间复杂度为)(m n O +，所以基数排序所需的时间为)(m n O +。 （2）算法： 1 清桶 2 把a 0，a 2，…a n-1依次装桶，不考虑相同元素被选出的前后顺序。 3从最大的桶开始，依桶的序号递减依次倒桶，直至够10个元素为止。 9 给出n 个元素中选最大最小元素的好的算法，并解释好的理由。 答： (一) 算法：n 为偶数，将n 个元素的序列分组，每两个元素一组，每组经行比较，一共进行了n/2 次比较，称每组比较后大的那个元素为winner ，小的那个为loser ，在所有的winner 中找一个最大的需n/2-1次比较，再所有loser 中找一个最小的需n/2-1次比较，共需 31122222 n n n n +-+-=-次。 n 为奇数时，将前n-1个元素两两比较，选出winner 和loser ，需 1 2 n -次比较将最后一个复制为两个，即a[n]=a[n-1]，在所有的winner 和a[n]中选一个最大的，需112 1 -+-n 次比较，在所有的loser 和a[n-1]中选一个最小的需112 1 -+-n 次比较。 所以共11133 2222n n n n ----++=次比较。 即比较次数{ 为奇数当为偶数当n n n n 23 2322 3-- (二)①假定n 个元素(n 为偶数)互不相同，为确认x 为max ，y 为min 算法必须知道除了x 之外其他元素都在一些比较中失败过，除了y 外，其他元素都在一些比较中成功过。于是设win ，lose 各作为一个信息量。 找到max ：win 对应1个信息，找到min ：lose 对应一个信息，其余n-2个元素，至少胜利、失败各一次，2(n-2)个信息，故要找到max 、min 至少需要2n-2个信息量。 ②设状态如下：W ：至少在一次比较中胜利，且从未失败过。 L ：至少在一次比较中失败，且从未成功过。 WL ：有成功、有失败至少各一次。 N ：从未比较。 x ，y 比较时的状态 得到新状态 信息量 N,N W,L 2 N,W W,L 或 WL,W 最多2个，最少1个 N,L W,L 或L,WL 最多2个，最少1个 N,WL W,WL 或L,WL 最多2个，最少1个 W,W W,WL 1 W,L W,WL 或 W,L 最多1个，最少0个 W,WL W,WL 或 WL,WL 最多1个，最少0个 L,L WL,L 1 L,WL WL,WL 或 L,WL 最多1个，最少0个 WL,WL WL,WL 因为要最少次比较：必须保证每次得到最多信息量，由此表第一次元素均为N ，N 比较故经n/2次比较后得n 个信息量，共需2n-2个信息量，之后，为保证在任何顺序输入情况下都能得出结果，且最坏情况中每次比较最多得到1个信息，故还需要n-2次比较。故至少需要 32222 n n n +-=-次。 10 同时找n 个元素中最大与次大元素的好的算法，并说明你多给出算法 是好的理由。 解：算法：n 个元素的数据结构： 0 来自左孩子 Flag= 1 来自右孩子 首先n 个元素两两比较取最大者为父节点，并标记来自哪个孩子。再在较大者中两两比较去大者为父节点，并标记来源。以次类推，则根为最大者，根据根的flag 值向下找到次大元。 找最大元比较n-1次。有??n 2lo g 个元素与最大元直接比较过，所以找次大元比较2log 1n -??? ?次，则总的比较次数为2log 2n n +-????次。 证明：设k 为与最大元比较的元素个数，w 为权值。设每个元素初始值为1，经过1次比较后，胜利者得到失败者的权值，则最大元W max =n 。若x 与y 比较，权值为W x ，W y 若x 为胜利者： W x = 2W y W x = W y W x =W x +W y W x > 2W y W x >W y W x < 2W y W x 最坏情况时，胜者权值W i+1≤W i 。故n=W k ≤2W k-1≤…≤2k W 0 =2k 即n ≤2k ， k ≥2log n ????。由于次大元与最大元比较过而与最大元比较过的元素个数为树高，故找次大元比较次数为2log 1n -????，即总的比较次数为：221log 1log 2n n n n -+-=+-???????? 11． 对于n 个元素找中间元素的问题，3、5、7、9、15个元素一组对应的时间复杂度分析 答： 5个元素一组： 设从n 个元素中找到指定位置的元素时间为 W(n)。 从n 个元素中找中间元素的步骤： 1）：5个元素一组对n 个元素分组，一共分 n/5 组，从每一组中的5 中找出中间元素要 6 次比较， 时间总共：n/5*6； 2)：在n/5个组中间元素中再次找中间元素，时间为W(n/5)。 3）：通过1）、2），可粗略的得到元素的分别矩阵，矩阵的左上角的3n/10(3n/5*1/2)和右下角的3n/10(3n/5*1/2)个元素肯定不会是中间元素，排除。中间元素只可能存在于剩下的2n/5（1-3n/10-3n/10）个元素中。 4）：2n/5 个元素与当前中间元素比较，所用时间为 2n/5。比较结果最坏情况下为2n/5个元素均大于或小于当前中间元素。 5）：在2n/5+3n/10中找特定位置的元素，时间为 W(7n/10)。 由此的 )5 ()107(5265n )(n W n W n n W +++?≤ cn cn 2.07.0n 6.1++≤ 若要使 cn n W ≤)( 则要满足：cn n 1.06.1≤ 即 16≥c 3个元素一组进行分组时： 参照5个一组的情况，得出如下表达式： )3()32(333n )(n W n W n n W +++?≤ cn 3 1cn 3234n ++≤ 若使 cn n W ≤)( 则出现 03n 4≤ 于实际不符，故，不可以把元素分成三个一组。 7个元素一组进行分组时： 参照5个一组的情况，得出如下表达式： )7 ()75(73117n )(n W n W n n W +++?≤ cn 7 1cn 75n 2++≤ 若使 cn n W ≤)( 则要满足：cn n 7 1 2≤ 即 14≥c 9个元素一组进行分组时： 参照5个一组的情况，得出如下表达式： )9()1813(94169n )(n W n W n n W +++?≤ cn 9 1cn 1813n 920++≤ 若使 cn n W ≤)( 则要满足： cn n 18 3 920≤ 即 340≥c 15个元素一组进行分组时： 参照5个一组的情况，得出如下表达式： )15 ()1511(1573115n )(n W n W n n W +++?≤ cn 15 1cn 1511n 1538++≤ 若使 cn n W ≤)( 则要满足：cn n 15 3 1538≤ 即 338≥c 12 输入n 个元素，输出m 个最小的元素，其中(n>>m)。 (1) 将所有n 个元素放在数组A 中从第n 个位置开始的空间里(作为树的叶子)，之后n 个元素两两 一组(A[i],A[i+1])进行比较，使用较小元素的索引作为这两个节点的父亲结点(A[i/2])，之后向上一次建树。这样可以建立起一棵树T ，T 的内部结点都是索引值，叶子结点保存实际的数值。 (2) 输出当前树T 的根节点root 指向的单元的值，之后将该单元的值设置成∞+，对树T 中root 指向的单元从叶子结点到根结点经过的路径进行调整，使之满足父结点是两个儿子当中值较小者的单元地址。 (3)反复执行第2步，直到找够m 个最小元素。 算法的时间复杂度分析：第一次建树并找出最小元素需要1-n 次比较；之后重复进行(m-1)树的调整并输出树根指向的值，每次调整需要的比较次数为??1)1*2(log 2--n ；所以，算法的时间复杂度为??)1)1*2(log *)1(1(2---+-n m n O 。 13 当需要增大数组时，将当前数组大小乘4（代替乘2），评价在时间和空间的策略。 解：假定在有向序列中插入第（n+1）个元素的时候，触发了双倍复制序列操作。设当 从旧序列中复制一个元素到新序列时的时间消耗为t （在这里设定t 为某一固定值）。则在将旧序列复制到新序列的时候需要进行n 次传输操作。而这次之前的一次双倍复 制操作已经进行了2n 次传输，再前一次是4n ，并以此类推。则总的时间消耗为 ∑+∞ =≤=0 221i i tn tn T 。如果使用四倍复制策略，则总的时间消耗为,,,416n n nt t t ，即 ∑ +∞ =≤=0 344 1i i tn tn T 。对于空间消耗，四倍复制策略会分配所需求空间总量的四倍，而两倍复制策略会分配所需求空间总量的两倍。 14 证明引理6.2 证明： 1. 设h RB 树和h ARB 树的黑色高度为h 。 当0h =时，对于0RB 树，该树由一个外部结点组成，显然对于上述的定理是成立的。 当h=1时，对于1ARB 树，该树由一个内部红结点组成，显然对于上述的定理是成立的。 2. 1假定h>0,对所有h j 0<≤的所有j, j RB 至少有12j -个内部黑结点，且同时， 1+j ARB 至少有221j -+个内部黑结点。现证明h RB 至少有12h -个内部黑结点和1h ARB +至少有221h -+个内部黑结点。 1+h ARB 的内部黑结点个数 2 2)12()12(1-=-+-≥+=+h h h h h RB RB 的内部黑结点个数右子树的内部黑结点个数左子树 与此同时，假设h RB 有β()20≤≤β个高度为h 的h ARB 子树，则有β-2个高度为h -1的1-h RB 子树。所以h RB 的内部黑结点个数 ( )()() ( ) 1 2121212222111h -≥-+-=--+-+≥--h h h h βββ 2. 2假定0h >，对所有0j h ≤<的所有j ，j RB 至多有14j -个内部结点，且1 +j ARB 至多有1241 -+j 个内部结点。 现证明h RB 至多有14h -个内部结点和1h ARB +至多有12 41 -+h 个内部结点。 1 h ARB +有2个高度为h 的h RB ，其内部结点数 124)14()14(111-=-+-+≤++=+h h h h h RB RB 的内部结点数右子树的内部结点数左子树 与此同时，假设h RB 有β()20≤≤β个高度为h 的h ARB 子树，则有β-2个高度为h-1的1-h RB 子树。所以h RB 的内部结点个数 ()() 1 4142421 424142124111111 h -=-?+?≤-?+=--+? ?? ? ??-+≤-----h h h h h h βββ 3对于符合定义的h ARB 树和h RB 树，由于不允许存在红色结点指向红色结点的边，所以从根到任何黑色结点的路径上，所包含的红色结点数小于或等于黑色结点数，即红色结点数至多为路径上所有结点数目的一半。又因为每一个红色结点被一条非黑色边指向，非黑色边的数目至多为路径上所有边数目的一半，所以“任何黑色结点的深度至多为该结点黑色深度的两倍”。 15 给出Prim 算法的时间复杂度和正确性证明，算法描述，程序。 答： Prim 算法基本思想： 假设G=(V,E)是一个具有n 个结点的连通图，T=(U,TE)是G 的最小生成树,其中U 是的结点集，TE 是的T 边集,U 与TE 初始值为空。 算法描述： 算法采用三个一维数组: U 为顶点访问标志，W 为目前到达各点最近距离，B 为记录每个结点通过与哪个结点相连的边被并入生成树的顶点集。 (1)从V 中任取一个顶点设为v0,将他并入U 中,此时U={v0}，初始化 [v0]=1,U[i]=0,W[i]=G[0][i],B[i]=0。 (2)从V-U 中选择vj(W[vj]为到U 中结点最近距离)，修改U[vj](将vj 并入生成树的结点集),并更新从已到达点集到未到达点的最小距离数组W[]及相应的起点数组B[]。 (3)然后只要U 中结点个数少于n 个，就重复执行步骤(2)。 时间复杂度： 根据W 数组，从所有不在U 中的点中，选一个距离U 最近的点，时间复杂度为O(n)；选取点后，更新未到达点与已到达点连边的权重及起点数组，时间复杂度为O(n)。要对n-1个结点进行以上操作，所以总时间复杂度为)(2 n O 。 代码: for(i=0;i for(i=0;i for(l=1;l v=-1; for(i=1;i } } } //把找到的点加入已到达点集合，并更新到未到达点的距离 U[v]=1; for(i=1;i continue; if(g[v][i] } 正确性证明： （1）引理：对于该算法生成的MST记为T1，与任意e*∈E(G)且e* ?T1，有W(e*)>=W(e)，其中e为把e*添入T1后形成回路中不同于e*的任意一条边。 证明：反证法。 假设T1中存在至少一条边e’，W(e’)>W(e*)。设e=xy为在最小生成树T1中添入e*=st后所构成回路中权值最大的边，有W(e)>=W(e’)>W(e*)。不妨假设A为MST的源点且x先于y，s先于t被添加到MST中，A到x的路径为As1s2…x，A到s的路径为Aw1w2…s。在x被添入T1后，由于e的权重大于环路中的其他边，所以A到s路径上的边会先于e被选入T1。又由于W(e) >W(e*)，因此e*边会被选择进入T1，与假设e*不是MST中的边矛盾。所以原命题正确。 （2）设由算法得到的MST为T1，假定T2为具有与T1相同边最多的一棵实际上的MST。设e1为算法执行过程中找到的一条在T1且不在T2的最小权值的边。将e1添入T2中，必形成回路，回路中必存在一条在T2不在T1中的边,记为e2，删除e2得T2’。将e2添入T1中，e3为所形成回路中不在T2中的边， 若:①w(e1) ②w(e1)=w(e2),T2’与T1具有相同边数比T2与T1具有相同边数多1，与T2有相同边数最多的 假设矛盾； ③w(e1)>w(e2), 由引理W(e2)>=W(e3),得W(e1)>W(e3).与e1为在T1且不再T2中权最小的边 矛盾。 所以，Prim算法执行过程是正确的。 16 给出Kruscal算法的算法描述，时间复杂度和正确性证明，程序。 (1)算法思想：设G=(V,E)是一个具有n个顶点的连通图，T=(U,TE)是G的最小生成树。U的初值等于V，包含G的全部顶点，算法开始时，TE为空集。 预处理：①先将G中边按权值从小到大排序(O(mlogm))；②然后建立以每个结点为根的一棵只有一个结点的树，父结点均为空，同时记录结点个数为1。 合并：在排好序的边中，依次选取每一条边e，查找e两个结点所在树的树根过程中，把沿途各点改为根的儿子。若这两个结点所在树根不等，则不会形成回路，把结点数少的子树根结点作为另一棵子树的儿子（若结点数相等，默认前者为后者儿子），同时修改树的大小。若两个结点所在树根相等，则添加后会形成回路，舍弃e，选取下一条边，如此进行下去，直到找到能用的n-1条边为止。 (2)时间复杂度：该算法用可并堆实现。首先把所有边按权值大小排序O(mlogm)，依次考察所有边。每次主要做两个工作即移动顶点与合并。合并时，只把小树根改为大树根的儿子，代价为O(1)；移动顶点即在查找树根过程中，把结点到他所在树根途中的点都改为根的儿子，每个结点的父结点最多被修改logn次，n个结点最多不超过nlogn。所以时间复杂度不超过O(nlogn)。 (3)代码: (4)正确性证明: （1）引理：对于该算法生成的MST记为T，与任意e∈E(G)且e ?T，有W(e)>=W('e)，其中'e为 把e 添入T 后形成回路中任意一条边。 证明：反证法 在算法生成的最小生成树T 中任添一条不在其中的边e*后则构成回路。假设e*不是回路中权值最大的边，则回路中存在权值大于W(e*)的边。设边集合：E1={e|e 在T 中且W(e)>W(e*)}；E2={e|e 在T 中且W(e) 综上所述，往计算机生成的MST 中添加任意一条不在其中的边e*，则e*在所构造回路中权值最大。 （2）设由算法得到的MST 为T1，假定T2为具有与T1相同边最多的一棵实际上的MST 。设e1为算法执行过程中找到的一条在T1且不在T2的最小权值的边。将e1添入T2中，必存在回路，回路必存在一条在T2不在T1中的边,记为e2，将e2添入T1中，e3为所形成回路中不在T2中的边， ①若W(e1) ②若W(e1)=W(e2),与T2与T1具有相同边数最多矛盾; W(e1)>W(e2).由引理W(e2)>=W(e3),得W(e1)>W(e3).与e1为在T1且不再T2中权最小的边矛盾。 所以Kruscal 所得生成树为最小生成树。 17 给出Dijstral 算法的时间复杂度和正确性证明，算法描述，程序。 Dijstra 思路:设有向图G=(V ,E)，其中},,,{110-=n V V V V ，cost 是邻接矩阵，cost[i][j]表示 ( =??∞?且)其它) 0Vi S[i]1 Vi ???未找到原点到顶点的最短路径已找到原点到顶点的最短路径 Dist[i]记录从源点到其他各点当前最短距离，从S 外的集合V-S 中选出一个点Vu ，使Dist[u]值最小，于是从源点到Vu 只通过S 中的顶点，把u 加入S 中，调整集合dist[]中的值（从源点到v-s 中所有点的距离）,从原来的dist[j]与dist[u]+cost[u][j]中选择最小的值，更新dist[j]。重复上述过程，直到S 中包含其余各顶点. 时间复杂度：算法每次从V-S 中选j ，使dist[j]最小，这个过程最多检查n-1个值，重复n-1次，所以时间复杂度为)(2 n O 核心代码： 把Prim 代码中加//*行改为 if(g[v][i]+w[v] B[i]=v; } 其余不变。 (4)正确性证明： 假定计算机算法求出的从A 到X 的路径不是实际的最短路径，那么在这条路径上一定有一些出错的点O 1O 2…，O 1为第一个出错的位置。 设计算机算法给出的由A 到O 1的路径为P y =Ay 1…y t O 1，而实际的最短路径为P z =Az 1…z s O 1 。 ①如果s t z y =，那么W(Az 1…z s ) 若y t 先到达，当Z s 到达时，由于W(P z ) 因此，不会出现计算机算法给出的路径P y ，与计算机算法输出了路径Ay 1…y t O 1矛盾。 综上所述，假设不成立。即计算机找到的路径是A 到X 的最短路径，Dijkstra 算法正确。 18 给出Floyd 算法的时间复杂度和正确性证明，算法描述，程序。 答： 算法描述： (1) 用数组dis[i][j]来记录i,j 之间的最短距离。初始化dis[i][j],若i=j 则dis[i][j]=0, 若i,j 之间有边连接则dis[i][j]的值为该边的权值，否则dis[i][j]的值为∞+。 (2) 对所有的k 值从1到n ，修正任意两点之间的最短距离，计算dis[i][k]+dis[k][j]的值， 若小于dis[i][j],则dis[i][j]= dis[i][k]+dis[k][j]，否则dis[i][j]的值不变。 程序： void Floyd(int dis[n+1][n+1],int path[n+1][n+1],int n) { int i,j,k; for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(dis[i][k]+dis[k][j] { dis[i][j] = dis[i][k]+dis[k][j]; Path[i][j]=k; } } 正确性证明(归纳法) ： 对于任意两点A ，B ： （1） 当从A 到B 之间的最短路径，在中间没有经过顶点或经过1个顶点号为1的顶点 时，算法显然正确。 （2） 假设A 到B 经过的最大顶点号不超过k-1时，算法得到的最短距离是正确的 （3） 当A 到B 经过的最大顶点号为k 时，则从A 到顶点号为k 的顶点v k 之间的顶点 号均不大于k-1，从v k 到B 之间的顶点号也不大于k-1，由假设2得，A 到v k 的 距离是中间顶点号不超过k-1的最短距离，v k 到B 的距离是中间顶点号不超过k-1的最短距离，所以A 经v k 到B 为A ，B 之间经过最大号为k 的路径中距离最短的，由算法修正A ，B 的最短距离，即可得到A ，B 间顶点号不超过k 的最短距离。 （4） 综上所述，算法是正确的 时间复杂度：O （n 3） 19 n*n 的棋盘，从左下角A 至右上角B 不超过主对角线的走法有多少种，并证明。 走法有 n n 2C 1 n 1+种。 证明： 设'B 是B 关于次对角线的对称点，A 到'B 的任意一种走法对应A 到B 过对角线的一种走法： （1） 由A->B,共有x=C n n 2种走法 （2） 由A->'B 共有w=C 1-n n 2种走法 （3） 设由A->B ，超过主对角线的走法有y 种 （4） 设由A->B ，不超过主对角线的走法有z 种，z=x-y （5） 因为A 与'B 分别处在次对角线的两侧，所以，所有的从A->'B 的走法都必然要超过 次对角线，将其任意一种走法中第一次碰到次对角线之后的部分关于次对角线对称过来，就可以得到A->B 超过主对角线的一种走法，故w y ≤. 将从A->B 过主对角线的任意一种走法中第一次碰到次对角线之后的部分关于次对角线对称过去就可以得到A->'B 的一种走法，故y ≤w. 所以y=w 。 z=x-y=x-w= n n n n n n n n n n n n n n n n n n n n n n n C n 21 2n 2C 1 1 )11(!!)!2()1(!!)!2(!!)!2()!1()!1()!2(!!)!2(C +=+-=+-=+--= -- 20给出拓扑排序算法，并给出时间复杂度。 算法： 把图中节点的状态分成三种。white代表节点还未被搜索到，gray代表节点已被搜索到但 还未被处理完，black代表节点已被处理完。数组topo[]来记录每个顶点的编号。 （1）把图中所有的节点的状态初始化为white，topoNum=n,从顶点号为1的顶点开始搜索color[1]=gray. （2）设当前搜索到的节点为v，则按深度优先的方式搜索它的邻接点，若存在某个邻接点状态为white，则把该邻接点的状态改为gray，把它作为当前搜索到的节点， 继续按深度优先方式搜索；若所有的邻接点状态都不是white则把当前节点状态 改为black，topo[v]=topoNum,topoNum--,然后退回到上一个节点。若在搜索过程 中遇到顶点颜色为gray,说明有环路,程序退出。 （3）当所有节点的状态都为black时，退出循环。 时间复杂度： 设顶点数为n，边数为m。 算法分为两部分：初始化和搜索节点，显然初始化的时间复杂度是O（n），搜索 节点则是按按深度优先的方式查找所有的边，时间复杂度为O（m+n），故此时间 复杂度为O（m+n）。 《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 20. 矩阵连乘问题的算法可由（ B ）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 21. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。 一。选择题 1、二分搜索算法就是利用( A )实现的算法。 Ａ、分治策略B、动态规划法C、贪心法 D、回溯法 2、下列不就是动态规划算法基本步骤的就是( A )。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 ３、最大效益优先就是( A )的一搜索方式。 Ａ、分支界限法Ｂ、动态规划法Ｃ、贪心法Ｄ、回溯法 4、在下列算法中有时找不到问题解的就是( B )。 Ａ、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5、回溯法解旅行售货员问题时的解空间树就是( B )。 A、子集树???Ｂ、排列树C、深度优先生成树?D、广度优先生成树 6.下列算法中通常以自底向上的方式求解最优解的就是( Ｂ)。 Ａ、备忘录法?B、动态规划法?C、贪心法????D、回溯法 7、衡量一个算法好坏的标准就是(C )。?A 运行速度快Ｂ占用空间少 C 时间复杂度低 D 代码短?８、以下不可以使用分治法求解的就是(D )。?Ａ棋盘覆盖问题Ｂ选择问题 C 归并排序 D 0/1背包问题?9、实现循环赛日程表利用的算法就是( A )。 A、分治策略?? B、动态规划法 C、贪心法??Ｄ、回溯法 10、下列随机算法中运行时有时候成功有时候失败的就是(C ) A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11.下面不就是分支界限法搜索方式的就是( D )。 Ａ、广度优先?B、最小耗费优先C、最大效益优先D、深度优先 12、下列算法中通常以深度优先方式系统搜索问题解的就是( D )。 Ａ、备忘录法B、动态规划法??C、贪心法???D、回溯法 13、备忘录方法就是那种算法的变形。( B ) A、分治法? B、动态规划法? C、贪心法?? D、回溯法 1４、哈弗曼编码的贪心算法所需的计算时间为( B )。 A、Ｏ(n2n)?? B、O(nｌogｎ)? C、O(2ｎ) ??? D、Ｏ(n) 15.分支限界法解最大团问题时,活结点表的组织形式就是( B )。 A、最小堆???? B、最大堆?? C、栈???Ｄ、数组 １6.最长公共子序列算法利用的算法就是( B )。 A、分支界限法? B、动态规划法? C、贪心法 D、回溯法 17.实现棋盘覆盖算法利用的算法就是( A )。 Ａ、分治法??Ｂ、动态规划法C、贪心法??D、回溯法 18、下面就是贪心算法的基本要素的就是( C )。 A、重叠子问题?Ｂ、构造最优解??C、贪心选择性质??D、定义最优解 1９.回溯法的效率不依赖于下列哪些因素( D ) A、满足显约束的值的个数????Ｂ、计算约束函数的时间 C、计算限界函数的时间?? D、确定解空间的时间 ２０、下面哪种函数就是回溯法中为避免无效搜索采取的策略( B ) A.递归函数?B、剪枝函数? C。随机数函数???Ｄ、搜索函数 21、下面关于NＰ问题说法正确的就是(B )?A NＰ问题都就是不可能解决的问题?B P类问题包含在ＮＰ类问题中?C NP完全问题就是P类问题的子集 D ＮP类问题包含在P类问题中 22、蒙特卡罗算法就是( B )的一种。 Ａ、分支界限算法 B、概率算法C、贪心算法D、回溯算法 2３、下列哪一种算法不就是随机化算法( C ) A、蒙特卡罗算法 B、拉斯维加斯算法 C、动态规划算法 D、舍伍德算法 24、 ( D )就是贪心算法与动态规划算法的共同点。Ａ、重叠子问题B、构造最优解?C、贪心选择性质D、最优子结构性质２5、矩阵连乘问题的算法可由( B)设计实现。 考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 --------------------------------------------------------- 考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 --------------------------------------------------------- 参考答案 一、填空 1、空间复杂度 时间复杂度 2、回溯法 3、递归算法 4、渐进确界或紧致界 5、原问题的较小模式 递归技术 6、问题的计算复杂性分析有一个共同的客观尺度 7、②③④① 8、问题的最优解包含其子问题的最优解 9、局部最优 10、正确的 三、简答题 1、高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作； 高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高； 高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高； 把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。 2、 ①不能保证最后求得的解是最佳的；即多半是近似解。（少数问题除外） ②策略容易发现（关键：提取清楚问题中的维度）， 而且运用简单，被广泛运用。 ③策略多样，结果也多样。 ④算法实现过程中，通常用到辅助算法：排序 3、解：① 因为：;01 -10n n )1-10n n (lim 22 2=+-+→∞n n 由渐近表达式的定义易知： 1-10n n 2 2+是n ;的渐近表达式。 ② 因为：;0n 1/ 5/n 1414)n 1/ 5/n 14(lim 22=++-++∞→n 由渐近表达式的定义易知： 14是14+5/n+1/ n 2的渐近表达式。 4、 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 四、算法设计题 1、按照单位效益从大到小依次排列这7个物品为：FBGDECA 。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】 5x =6x =7x = 算法实现题3-7 数字三角形问题 问题描述： 给定一个由n行数字组成的数字三角形，如图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。编程任务： 对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。数据输入： 有文件input.txt提供输入数据。文件的第1行是数字三角形的行数n，1<=n<=100。接下来的n行是数字三角形各行的数字。所有数字在0-99之间。结果输出： 程序运行结束时，将计算结果输出到文件output.txt中。文件第1行中的数是计算出的最大值。 输入文件示例输出文件示 例 input.txt output.txt 5 30 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 源程序： #include "stdio.h" voidmain() { intn,triangle[100][100],i,j;//triangle数组用来存储金字塔数值,n表示行数 FILE *in,*out;//定义in，out两个文件指针变量 in=fopen("input.txt","r"); fscanf(in,"%d",&n);//将行数n读入到变量n中 for(i=0;i 本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼110 专业班级：物联网1601 学号： 05 学生姓名：俞梦真 指导教师：郝晓丽 2018年 05月 04 日 实验一递归与分治算法 实验目的与要求 1．进一步熟悉C/C++语言的集成开发环境； 2．通过本实验加深对递归与分治策略的理解和运用。 实验课时 2学时 实验原理 分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。 需要注意的是，分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同，可用相同的求解方法。最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。 实验题目 1．上机题目：格雷码构造问题 Gray码是一个长度为2n的序列。序列无相同元素，每个元素都是长度为n的串，相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码（分治、减治、变治皆可）。 对于给定的正整数n，格雷码为满足如下条件的一个编码序列。 （1）序列由2n个编码组成，每个编码都是长度为n的二进制位串。 （2）序列中无相同的编码。 （3）序列中位置相邻的两个编码恰有一位不同。 2．设计思想： 根据格雷码的性质，找到他的规律，可发现，1位是0 1。两位是00 01 11 10。三位是000 001 011 010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0，N-2为倒转再前面再加1。 3．代码设计： 归式，就是如何将原问题划分成子问题。 2.递归出口，递归终止的条件，即最小子问题的求解，可以允许多个出口。 3.界函数，问题规模变化的函数，它保证递归的规模向出口条件靠拢（2）递归与非递归之间如何实现程序的转换？ （3）分析二分查找和快速排序中使用的分治思想。 答： 1．一般根据是否需要回朔可以把递归分成简单递归和复杂递归，简单递归一般就是根据递归式来找出递推公式（这也就引申出分治思想和动态规划）。 2．复杂递归一般就是模拟系统处理递归的机制，使用栈或队列等数据结构保存回朔点来求解。 （4）分析二次取中法和锦标赛算法中的分治思想。 二次取中法：使用快速排序法中所采用的分划方法，以主元为基准，将一个表划分为左右两个子表，左子表中的元素均小于主元，右子表中的元素均大于主元。主元的选择是将表划分为r 算法设计与分析考试题及 答案 It was last revised on January 2, 2021 一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算， 此外，算法还应具有以下五个重要特性:确定性有穷性可行性 0个或多个输入一个或多 个输出 2.算法的复杂性有时间复杂性空间复杂性之分，衡量一个算法好坏的标准是时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列{BABCD}或{CABCD}或{CADCD｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题，先求解_子问题，然后从这些 子问题的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n) ,用动态规划算法所需的计算时间为o(min{nc,2n}) 9.动态规划算法的两个基本要素是最优子结构_和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式；③最优值的算法描述；④构造 最优解； 2.流水作业调度问题的johnson算法的思想。 ①令N 1={i|a i =b i }；②将N 1 中作业按a i 的非减序排序得到N 1 ’，将N 2 中作业按b i 的非增序排序得到N 2’；③N 1 ’中作业接N 2 ’中作业就构成了满足Johnson法则的最优调度。 3.若n=4，在机器M1和M2上加工作业i所需的时间分别为a i 和b i ，且 (a 1,a 2 ,a 3 ,a 4 )=(4,5,12,10)，(b 1 ,b 2 ,b 3 ,b 4 )=(8,2,15,9)求4个作业的最优调度方案，并计算最优 值。 步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2 ’={4，2}； 最优值为：38 4.使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为： 该问题的最优值为：16 最优解为：（1，1，0） 湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型：C 卷 考试时量：120 分钟 1. 用O 、Ω和θ表示函数f 与g 之间的关系______________________________。 ()()log log f n n n g n n == 2. 算法的时间复杂性为1, 1()8(3/7), 2 n f n f n n n =?=? +≥?，则算法的时间复杂性的阶 为__________________________。 3. 快速排序算法的性能取决于______________________________。 4. 算法是_______________________________________________________。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是_________________________。 6. 在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是_____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越___________，结果就越有价值。。 8. ____________________________是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指________________________________________________________ ____________________________________________________________。 题 号 一 二 三 四 五 总分 统分人 得 分 阅卷人 湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型:C卷考试时量:1２０分钟 题号一二三四五总分统分人 得分 阅卷人 复查人 一、填空题(每小题3 分，共计30 分) １、用O、Ω与θ表示函数f与g之间得关系＿__________＿__＿_＿_＿＿_＿__＿___＿＿。 2、算法得时间复杂性为,则算法得时间复杂性得阶为_＿__＿＿____＿_＿_＿____＿＿_＿__＿。 3、快速排序算法得性能取决于_＿_____＿_______＿__＿__＿_＿___＿__。 4、算法就是__＿_＿______＿＿_＿＿__＿________＿___＿___＿___＿___＿_＿_＿_＿＿_＿__。 5、在对问题得解空间树进行搜索得方法中,一个活结点最多有一次机会成为活结点得就是＿_______＿__＿____________＿。 6、在算法得三种情况下得复杂性中,可操作性最好且最有实际价值得就是__＿_＿情况下得时间复杂性。 7、大Ω符号用来描述增长率得下限,这个下限得阶越__＿________,结果就越有价值。。 8、_＿_＿__＿_＿____＿________＿_____就是问题能用动态规划算法求解得前提。 9、贪心选择性质就是指_＿____________＿______＿_＿__＿__＿______＿________________＿__＿_____＿____＿____＿_＿______＿__＿__＿___＿_＿__＿___＿_＿＿＿________＿__。 1０、回溯法在问题得解空间树中,按______＿＿＿_＿__＿策略,从根结点出发搜索解空间树。 二、简答题(每小题10分,共计3０分) １、试述回溯法得基本思想及用回溯法解题得步骤。 2、有８个作业{１,２,…,8}要在由2台机器M1与Ｍ２组成得流水线上完成加工。每个作业加工得顺序都就是先在M1上加工,然后在M2上加工。M１与M2加工作业ｉ所需得时间分别为: M１10 2 8 12 6 ９４14 精品文档习题胡明-版)-王红梅-算法设计与分析(第2答案 1 习题）—1783Leonhard Euler，17071.图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（提 出并解决了该问题。七桥问题是这样描述的：北区一个人是否能在一次步行中穿越哥尼斯堡（现东区在叫加里宁格勒，在波罗的海南岸）城中全部岛区的七座桥后回到起点，且每座桥只经过一次，南区是这条河以及河上的两个岛和七座桥的图1.7 1.7 七桥问题图草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点一次步行1，经过七座桥，且每次只经历过一次2，回到起点3，该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。）用的不是除法而是减最初的欧几里德算法2．在欧几里德提出的欧几里德算法中（即法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n r=0 循环直到2.m=n 2.1 n=r 2.2 r=m-n 2.3 m 输出3 ．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代3++描述。C码和 采用分治法// //对数组先进行快速排序在依次比较相邻的差//精品文档． 精品文档 #include 学号1607070212 《算法设计与分析》 实验报告一 学生姓名张曾然 专业、班级16软件二班 指导教师唐国峰 成绩 计算机与信息工程学院软件工程系 2018 年9 月19 日 实验一：递归策略运用练习 一、实验目的 本次实验是针对递归算法的算法设计及应用练习，旨在加深学生对该算法原理的理解，提高学生运用该算法解决问题的能力。 二、实验步骤与要求 1．实验前复习课程所学知识以及阅读和理解指定的课外阅读材料； 2．学生独自完成实验指定内容； 3．实验结束后，用统一的实验报告模板编写实验报告。 4．提交说明： （1）电子版提交说明： a 需要提交Winrar压缩包，文件名为“《算法设计与分析》实验一_学号_姓名”， 如“《算法设计与分析》实验一_09290101_张三”。 b 压缩包内为一个“《算法设计与分析》实验一_学号_姓名”命名的顶层文件夹， 其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验 报告电子版”。其下分别放置对应实验成果物。 （2）打印版提交说明： a 不可随意更改模板样式。 b 字体：中文为宋体，大小为10号字，英文为Time New Roman，大小为10号 字。 c 行间距：单倍行距。 （3）提交截止时间：2018年10月10日16:00。 三、实验项目 1．运用递归策略设计算法实现下述题目的求解过程。 题目列表如下： 【必做题】 （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？ 第一章 1. 算法分析题 算法分析题1－1 求下列函数的渐进表达式 (1). 3n^2 + 10n < 3n^2 + 10n^2 = 13n^2 = O(n^2) (2). n^2 / 10 + 2^n 当n>5是，n^2 < 2 ^n 所以，当n >= 1时，n^2/10 < 2 ^n 故: n^2/10 + 2^n < 2 ^n + 2^n = 2*2^n = O(2^n) (3). 21 + 1/n < 21 + 1 = 22 = O(1) (4). log(n^3)=3log(n)=O(log(n)) (5). 10log(3^n) = (10log3)n = O(n) 算法分析题1-6 (1)因为：f(n)=log(n^2) = 2log(n); g(n) = log(n) + 5 所以：f(n)=Θ(log(n)+5) =Θ(g(n)) (2)因为：log(n) < √n ; f(n) = 2log(n); g(n)= √n 所以：f(n) = O(g(n)) (3)因为：log(n) < n; f(n) = n; g(n) = log(n^2) = 2log(n) 所以；f(n) = Ω(g(n)) (4)因为：f(n) = nlogn +n; g(n) = logn 所以：f(n) =Ω(g(n)) (5)因为: f(n) = 10; g(n) = log(10) 所以:f(n) =Θ(g(n)) (6)因为: f(n)=log^2(n); g(n) = log(n) 所以: f(n) ==Ω(g(n)) (7)因为: f(n) = 2^n < 100*2^n; g(n)=100n^2; 2^n > n ^2 所以: f(n) = Ω(g(n)) (8)因为：f(n) = 2^n; g(n) = 3 ^n; 2 ^n < 3 ^n 所以: f(n) = O(g(n)) 习题1－9 证明：如果一个算法在平均情况下的计算时间复杂性为Θ(f(n)),该算法在最坏情况下所需的计算时间为Ω(f(n)). 分析与解答： 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： B 、D A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ C 、D A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： ABCD A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： C A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分，衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。 填空 1．直接或间接地调用自身的算法称为 递归 。 2．算法的复杂性是 算法效率 的度量，是评价算法优劣的重要依据。 3．以广度优先或以最小耗费方式搜索问题解的算法称为 分支限界法 。 4．回溯法解题的显著特点是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为 o(h(n)) 。 5．人们通常将问题的解决方案分为两大类：一类是可以通过执行若干个步骤就能得出问题 6．算法就是一组有穷的 规则 ，它们规定了解决某一特定类型问题的 一系列运算 。 7．在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型。3个基本计算模型是 随机存取机、 随机存取存储程序机 、 图灵机 。 8．快速排序算法的性能取决于 划分的对称性 。 9．计算机的资源最重要的是 内存 和 运算 资源。因而，算法的复杂性有时间 和 空间 之分。 10．贪心算法总是做出在当前看来 最优 的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的 局部最优解 。 11．许多可以用贪心算法求解的问题一般具有2个重要的性质： 最优子结构的 性质和 贪心选择的 性质。 12．常见的两种分支限界法为 队列式 和 优先队列式 。 13．解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中需要排序的是 回溯法 ，不需要排序的是 动态规划和分支限界法 。 14．f ( n ) = 6 × 2n + n 2，f(n)的渐进性态f ( n ) = O ( 2^n )。 15．对于含有n 个元素的排列树问题，最好情况下计算时间复杂性为 ，最坏情况下计算时间复杂性为 n! 。 16．在忽略常数因子的情况下，O 、Ω和Θ三个符号中， Θ 提供了算法运行时间的一个上界。 17．回溯法的求解过程，即在问题的解空间树中，按 深度优先 策略从根结点出发搜索解空间树。 18．分支限界法的求解过程，即在问题的解空间树中，按 广度优先 策略从根结点出发搜索解空间树。 19．多项式10()m m A n a n a n a =+ ++的上界为 2^n 。 20．用分支限界法解布线问题时，对空间树搜索结束的标志是 活结点表为空 。 21．使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N 皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14．广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．背包问题的贪心算法所需的计算时间为（ B ）。 分治法 1、二分搜索算法是利用（分治策略）实现的算法。 9. 实现循环赛日程表利用的算法是（分治策略） 27、Strassen矩阵乘法是利用（分治策略）实现的算法。 34．实现合并排序利用的算法是（分治策略）。 实现大整数的乘法是利用的算法（分治策略）。 17．实现棋盘覆盖算法利用的算法是（分治法）。 29、使用分治法求解不需要满足的条件是（子问题必须是一样的）。 不可以使用分治法求解的是（0/1背包问题）。 动态规划 下列不是动态规划算法基本步骤的是（构造最优解） 下列是动态规划算法基本要素的是（子问题重叠性质）。 下列算法中通常以自底向上的方式求解最优解的是（动态规划法） 备忘录方法是那种算法的变形。（动态规划法） 最长公共子序列算法利用的算法是（动态规划法）。 矩阵连乘问题的算法可由（动态规划算法B）设计实现。 实现最大子段和利用的算法是（动态规划法）。 贪心算法 能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题， 不能解决的问题：N皇后问题，0/1背包问题 是贪心算法的基本要素的是（贪心选择性质和最优子结构性质）。 回溯法 回溯法解旅行售货员问题时的解空间树是（排列树）。 剪枝函数是回溯法中为避免无效搜索采取的策略 回溯法的效率不依赖于下列哪些因素（确定解空间的时间） 分支限界法 最大效益优先是（分支界限法）的一搜索方式。 分支限界法解最大团问题时，活结点表的组织形式是（最大堆）。 分支限界法解旅行售货员问题时，活结点表的组织形式是（最小堆） 优先队列式分支限界法选取扩展结点的原则是（结点的优先级） 在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( 分支限界法 ). 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( 栈式分支限界法 )之外都是最常见的方式. （1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 （最优子结构性质）是贪心算法与动态规划算法的共同点。 贪心算法与动态规划算法的主要区别是（贪心选择性质）。 回溯算法和分支限界法的问题的解空间树不会是( 无序树 ). 14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 21、下面关于NP问题说法正确的是（B ） A NP问题都是不可能解决的问题 B P类问题包含在NP类问题中 C NP完全问题是P类问题的子集 D NP类问题包含在P类问题中 40、背包问题的贪心算法所需的计算时间为（ B ） 第一章作业 1.证明下列Ο、Ω和Θ的性质 1）f=Ο(g)当且仅当g=Ω(f) 证明：充分性。若f=Ο(g)，则必然存在常数c1>0和n0，使得?n≥n0，有f≤c1*g(n)。由于c1≠0，故g(n) ≥ 1/ c1 *f(n)，故g=Ω(f)。 必要性。同理，若g=Ω(f)，则必然存在c2>0和n0，使得?n≥n0，有g(n) ≥ c2 *f(n).由于c2≠0，故f(n) ≤ 1/ c2*f(n)，故f=Ο(g)。 2）若f=Θ(g)则g=Θ(f) 证明：若f=Θ(g)，则必然存在常数c1>0，c2>0和n0，使得?n≥n0，有c1*g(n) ≤f(n) ≤ c2*g(n)。由于c1≠0，c2≠0，f(n) ≥c1*g(n)可得g(n) ≤ 1/c1*f(n)，同时，f(n) ≤c2*g(n)，有g(n) ≥ 1/c2*f(n)，即1/c2*f(n) ≤g(n) ≤ 1/c1*f(n)，故g=Θ(f)。 3）Ο(f+g)= Ο(max(f,g))，对于Ω和Θ同样成立。 证明：设F(n)= Ο(f+g)，则存在c1>0，和n1，使得?n≥n1，有 F(n) ≤ c1 (f(n)+g(n)) = c1 f(n) + c1g(n) ≤ c1*max{f,g}+ c1*max{f,g} =2 c1*max{f,g} 所以，F(n)=Ο(max(f,g))，即Ο(f+g)= Ο(max(f,g)) 对于Ω和Θ同理证明可以成立。 4）log(n!)= Θ(nlogn) 证明： ?由于log(n!)=∑=n i i 1 log ≤∑=n i n 1 log =nlogn ，所以可得log(n!)= Ο(nlogn)。 ?由于对所有的偶数n 有， log(n!)= ∑=n i i 1 log ≥∑=n n i i 2 /log ≥∑=n n i n 2 /2/log ≥(n/2)log(n/2)=(nlogn)/2-n/2。 当n ≥4，(nlogn)/2-n/2≥(nlogn)/4，故可得?n ≥4，log(n!) ≥(nlogn)/4，即log(n!)= Ω(nlogn)。 综合以上两点可得log(n!)= Θ(nlogn) 2. 设计一个算法，求给定n 个元素的第二大元素，并给出算法在最坏情况下使用的比较次数。（复杂度至多为2n-3） 算法： V oid findsecond(ElemType A[]) { for (i=2; i<=n;i++) if (A[1] 实验报告 （2009/2010学年第一学期） 课程名称算法分析与设计A 实验名称动态规划法 实验时间2009 年11 月20 日指导单位计算机学院软件工程系 指导教师张怡婷 学生姓名丁力琪班级学号B07030907 学院(系) 计算机学院专业软件工程 实验报告 实验名称动态规划法指导教师张怡婷实验类型验证实验学时2×2实验时间2009-11-20一、实验目的和任务 目的：加深对动态规划法的算法原理及实现过程的理解，学习用动态规划法解决实际应用中的最长公共子序列问题。 任务：用动态规划法实现求两序列的最长公共子序列，其比较结果可用于基因比较、文章比较等多个领域。 要求：掌握动态规划法的思想，及动态规划法在实际中的应用；分析最长公共子序列的问题特征，选择算法策略并设计具体算法，编程实现两输入序列的比较，并输出它们的最长公共子序列。 二、实验环境(实验设备) 硬件：计算机 软件：Visual C++ 三、实验原理及内容（包括操作过程、结果分析等） 1、最长公共子序列（LCS）问题是：给定两个字符序列X={x1,x2,……,x m}和Y={y1,y2,……,y n}，要求找出X和Y的一个最长公共子序列。 例如：X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a}。它们的最长公共子序列LSC={b,c,d,a}。 通过“穷举法”列出所有X的所有子序列，检查其是否为Y的子序列并记录最长公共子序列并记录最长公共子序列的长度这种方法，求解时间为指数级别的，因此不可取。 2、分析LCS问题特征可知，如果Z={z1,z2,……，z k}为它们的最长公共子序列，则它们一定具有以下性质： （1）若x m=y n，则z k=x m=y n，且Z k-1是X m-1和Y n-1的最长公共子序列； （2）若x m≠y n且x m≠z k，则Z是X m-1和Y的最长公共子序列； （3）若x m≠y n且z k≠y n，则Z是X和Y的最长公共子序列。 这样就将求X和Y的最长公共子序列问题，分解为求解较小规模的问题： 若x m=y m，则进一步分解为求解两个（前缀）子字符序列X m-1和Y n-1的最长公共子序列问题； 如果x m≠y n，则原问题转化为求解两个子问题，即找出X m-1和Y的最长公共子序列与找出X 和Y n-1的最长公共子序列，取两者中较长者作为X和Y的最长公共子序列。 由此可见，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列，具有最优子结构性质。 3、令c[i][j]保存字符序列X i={x1,x2,……,x i}和Y j={y1,y2,……,y j}的最长公共子序列的长度，由上述分析可得如下递推式： 0 i=0或j=0 c[i][j]= c[i-1][j-1]+1 i,j>0且x i=y j max{c[i][j-1],c[i-1][j]} i,j>0且x i≠y j 由此可见，最长公共子序列的求解具有重叠子问题性质，如果采用递归算法实现，会得到一个指数时间算法，因此需要采用动态规划法自底向上求解，并保存子问题的解，这样可以避免重复计算子问题，在多项式时间内完成计算。 4、为了能由最优解值进一步得到最优解（即最长公共子序列），还需要一个二维数组s[][]，数组中的元素s[i][j]记录c[i][j]的值是由三个子问题c[i-1][j-1]+1,c[i][j-1]和c[i-1][j]中的哪一个计算得到，从而可以得到最优解的当前解分量（即最长公共子序列中的当前字符），最终构造出最长公共子序列自身。《计算机算法设计与分析》习题及答案
算法设计与分析复习题目及答案19874
算法设计与分析试卷A及答案
算法设计与分析课后部分习题答案
算法设计与分析实验报告
算法设计与分析考试题及答案
算法设计与分析试卷及答案
算法设计与分析试卷及答案
算法设计与分析第2版 王红梅 胡明 习题答案
《算法设计与分析》实验一
算法设计与分析课后习题
算法设计与分析试卷(2010)
算法设计与分析考试题及答案
《算法设计与分析》复习题(汇编)
计算机算法设计与分析期末考试复习题
算法设计与分析复习题目及答案doc
算法设计与分析习题解答
南京邮电大学算法设计实验报告——动态规划法
- 算法设计与分析期末总复习
- 计算机算法设计与分析总复习
- 算法设计与分析复习题目及答案
- 算法设计与分析(期末总复习)-推荐下载
- 最新计算机算法设计与分析期末考试复习题(1)
- 算法设计与分析考试题目及答案
- 算法设计与分析(期末总复习)
- 2015算法设计与分析复习试题及答案详解
- 算法设计与分析复习题
- 算法设计与分析(期末总复习)
- 2015算法设计与分析考试复习刚要习题
- 2014华南理工大学广州学院,算法设计与分析期末考试复习PPT
- 算法设计与分析复习要点
- !算法设计与分析总复习资料
- 2015算法设计与分析考试复习刚要及习题
- 计算机算法设计与分析期末考试复习题
- 《算法设计与分析》期末必考复习及答案题整理
- 计算机算法设计与分析总复习PPT课件
- 算法设计与分析复习题目含答案
- 《算法设计与分析》复习题(汇编)