第22卷第3期2006年6月 河北北方学院学报(自然科学版)Journal of Hebei Nort h University (Nat ural Science Edition )
Vol 122No 13J une 2006 收稿日期:20060424
作者简介:乔月圆(19702),男,山西大同人,山西大同大学讲师.
运动估计块匹配算法分析与研究
乔月圆1,冯贵良2,兰安怡2
(11山西大同大学,山西大同037003;21河北北方学院计算机科学系,河北张家口075000)
摘要:视频序列图像存在很强的相关性,采用运动估计和运动补偿技术可以消除时间冗余以提高编码效
率,本文介绍了运动估计的原理以及一些常用的块匹配算法,并对这些算法的优劣性作了分析比较.
关键词:运动估计;块匹配;算法
中图分类号:TP 30116 文献标识码:A 文章编号:167321492(2006)0320067204
The R esearch of B lock Matching Algorithms for Motion Estimation
Q IAO Yue 2yuan 1,FEN G Gui 2liang ,L AN An 2yi 2
(11Shanxi Datong University ,Datong ,Shanxi 037003,China ;
21Department of Computer Science ,Hebei North University ,Zhangjiakou ,Hebei 075000,China )
Abstrcat :There is a st rong relativity between video f requency images.To improve t he coding efficien 2cy ,we can remove redundancy information by using motion estimation and compensation techniques.This paper introduces t he t heory of motion estimation and some block matching algorit hms being used f requent 2ly ,and compares t he virt ues and shortcomings between t his algorit hms.
K ey w ord :motio n estimation ;block matching ;algorit hms
自然视频序编码的运动估计方法,就是计算当前帧(待编码的图像)的各像素块与其相邻帧(预测图像)的像素块的运动矢量,然后由其构成一个对当前帧的预测帧,求得其最佳预测误差,编码时只须传送预测误差值和运动矢量.由于预测误差的信息量通常会大大少于原图像的信息量,再对其施以适当的统计编码方法,则可以得到比较大的视频数据压缩.而在解码端,根据接收的运动矢量,采用运动补偿,将预测误差与己知的预测图像重合,生成解码.近年来,研究人员提出了很多运动估计块匹配算法,但是每种算法各有其优缺点和适用范围.
1 运动估计的块匹配算法原理
运动估计块匹配法的基本思想是将每一帧图像分割成一系列子块图像,宏块大小为M ×N (一般取16×16).计算当前帧中每一子块与相邻帧中的各子块的误差函数,
把具有最小误差的相邻帧的对应子块
图1 运动估计块基本原理
作为当前块的预测块,并把两块的相对位移定义为位移矢量(运动矢量).其基本原理如图1所示.
设当前帧的图像亮度信号为f k(m,n),前次传送的相邻帧的图像亮度信号为f k2N
5
(m,n),其中N s
为帧差数目(通常N s可取1,3,5,…,15).假定当前帧f k(m,n)中当前块是从前帧f k2N
5
(m,n)平行移而来,并设该子块内M×N个像素都具有同一个位移值(i,j),假定运动物体在帧差Ns时间内水
平和垂直方向的最大位移都为w,则我们可以在前帧f k2N
5
(m,n)对应的搜索区内进行搜索,寻找当前帧中的当前块在前帧对应的匹配块,搜索区面积为(M+2w)(N+2w).
2 块匹配的准则
运动估计算法中常用的准则有以下3种:
1)归一化相关函数NCCF(Normalized Cro ss2Correctio n Function)
N CC F(i,j)=
∑
M-1
m=0
∑
N-1
n=0
f k(m,n)f k-N s(m+i,n+j)
∑
M-1
m=0
∑
N-1
n=0
f2k(m,n)12∑
M-1
m=0
∑
N-1
n=0
f2k-N
5
k(m+i,n+j)12
归一化相关函数NCCF的计算工作量很大,在实际应用中
,一般用以下的均方误差函数和平均绝对
误差函数来代替.
2)平均均方误差函数MSD(Mean Square Difference)
M S D(i,f)=
1
M N
∑
M-1
m=0
∑
N-1
n=0
f k(m,n)-f k-N s(m+i,n+j)2
3)平均绝对差函数MAD(Mean Absolute Difference)
M A D(i,f)=
1
M N
∑
M-1
m=0
∑
N-1
n=0
|f k(m,n)-f k-N s(m+i,n+j)|
通常使用求和绝对差SAD代替MAD,即SAD(i,j)=MN3MAD(i,j))
在搜索区域内,如果某子块使得以上公式所计算的均方差值或绝对差值达到最小,该块就是所要找的匹配块,其位移量(i,j)就是当前帧中的当前块相对于其前帧的匹配块的运动矢量.匹配准则对匹配的精度影响不大,所以上面不含乘除法的求和绝对差SAD成为最常用的匹配准则FS(Full Search).
全搜索匹配法对搜索区内的所有子块进行搜索,因此能够得到搜索区内与当前块最为匹配的块.其中前向水平、垂直搜索窗口高度和反向水平、垂直搜索窗口高度应当根据具体图像特征进行选择.如果图像变化不大,则为了提高搜索速度,可以用小的搜索窗口;反之,如果处理的序列有很多的激烈场面,帧与帧之间的变化很大,则必须用大的窗口进行搜索,以达到要求的编码质量.
由于全搜索法需要对搜索窗口内每个宏块进行匹配,运算量非常大,有时甚至能占去整个编码器资源消耗的近80%.
3 三步搜索法TSS(Three Step Search)
如图2所示,TSS算法的基本思想是采用一种由粗到细的搜索模式.其搜索步骤一般为:第一步,从原点开始,以最大搜索长度的一半为步长检测中心点及周围8个相邻点的SAD值,找到SAD值最小点;第二步,以该SAD最小点为中心,搜索步长减半,并在缩小的方形的中心点及周围8个点找SAD最小点;第三步,重复第二步,直到步长为1,得到最后的运动向量.
三步搜索法在搜索的第一步采用固定步长的搜索模式,这样可能导致该算法对细小的运动进行估计时效果不理想,并且极有可能陷入局部最小点.现实中很多图像序列的运动经常是平稳、光滑和变化缓慢的,这时全局最小值一般是基于中心分布的,而不是均匀分布的.新三步搜索法算法就是基于中心的测试模式,在原有的三步搜索法的第一步的测试点的基础上再增加了中心点的82邻域作为测试点,并且采用了半途终止的策略(Halfway2stop Technique),若最小的块位移量矩(BDM,Block Distortion Measure) 2006年6月 河北北方学院学报(自然科学版) 第3期
出现在82邻域的中心点则停止搜索.
具体算法为:
第一步,在原有的三步搜索法的第一步的测试点的基础上再增加中心点82邻域作为测试点;
第二步,如果最小BDM 在第一步出现在搜索窗口的中心则停止搜索,如果最小的BDM 出现在中心点的82邻域中,则以最小BDM 为中心计算其82邻域,找出最小BDM .半途终止策略用于有效地估计静止及半静止块的运动向量;
重复上面的步骤,直到最小BDM 出现在中心,搜索停止.如果最小的BDM 出现在(±w/2,±w/2)上,则执行三步搜速算法的第二步和第三步
.
图2 三步搜索法图3 新三步搜速算法
4 钻石搜索法DS (Diamond Search )
钻石搜索法又叫菱形搜索法,以其搜索模式的形状而得名,其思想是减少进行块匹配的搜索点,具有简单、鲁棒和高效的特点.如图4所示,可以看到搜索点大都位于图像的水平和垂直方向上,这是考虑到现实中的物体在这两个方向运动的概率比较大,图像的频谱多呈菱形分布,也就是说,图像在水平和垂直方向的相关性大于斜线方向.
钻石搜索法使用两个搜索模板,第一个为大钻石搜索模板(LDSP ,large diamond search pattern ),该模板包括围绕中心点的8个点,从而形成一个大钻石形(图a ).另一个为小钻石搜索模板(SDSP ,small diamond search pattern ),包含了5个点,形成一个较小规模的钻石形(图c ).搜索时首先可以进行粗定位,使搜索过程不会陷于局部最小;当粗定位结束后,可以认为最优点就在LDSP 周围8个点所围的菱形区域中;最后以上一次找到的MBD 点作为中心点,用小钻石型模式做匹配运算,MBD 点的位置即为最佳运动矢量(图b ).DS 算法的性能优于上述其它快速算法,是一种被M PEG 24校验模型所采纳的运动估计算法之一.
5 运动向量场自适应搜索法MV FAS T (Motion Vector Field Adaptive Search Technique )
运动向量场自适应搜索法首先设定一组预测器,一般为坐标(0,0)处的运动向量,或与(0,0)相邻的左边、顶上和右上处的运动向量.MV FAST 不仅仅是采用了一个大的菱形(图a ),而且还采用了一个可移动的小菱形(图c ).大菱形或者小菱形不断移动,直到发现最佳匹配点终止,此处即为菱形中央处,该点的SAD 值最小
.
图4 钻石搜索法图5 运动向量场自适应搜索法
MV FAST 也有两种搜索模式:一种是小菱形模式,就是使用小菱形进行运动搜索,最佳点为其中心,找到该点后算法搜索终止;另一种是大菱形模式,在这种模式下,大菱形被使用,但最后一步的搜索还要使用小菱形(图b ).
初始到底是选用大菱形还是小菱形进行搜索,这由运动类型的初始特性决定.如果相邻三个宏块运动
2006年6月 乔月圆等:运动估计块匹配算法分析与研究 第3期
2006年6月 河北北方学院学报(自然科学版) 第3期
向量的最大值低于一个阈值Ll,我们称其为低速运动;如果它介于L1和另一个较大的阈值L2之间,为中速运动;如果它大于阈值L2,为高速运动.如果是低速运动,那么小菱形被使用,且(0,0)处的运动向量位于菱形的中央;若是中速运动,那么大菱形参与搜索,依然用(0,0)作为其中心;如果运动是剧烈的,使用小菱形进行搜索,此时检测(0,0)处的运动向量和其它几个预测器,最佳预测器作为小菱形的中心,同时还设定一个固定的阈值T,首先以它为限测试(0,0)处的运动向量,如果位移小于T,那么搜索终止,不再搜索其它位置.MV FAST运动估计算法无论是编码质量还是编码效率都比己有的菱形搜索算法提高了很多.
6 结 论
在各种基于块的运动估计算法中,以全搜索法的峰值信噪比最大,但是速度最慢.这表明全搜索法是以牺牲时间的因素来提高压缩质量的,原因是全搜索法是在整个搜索空间中进行的匹配查找,这样就可以保证完成匹配的象素是全局最优的,从而使得最终结果的信噪比最高.而其他快速搜索方法不可避免地找到的只是局部最优解,所以搜索时间虽然提高了,但编码后的质量却下降了.
相比较三步搜索法(TSS),新三步搜索法(N TSS)在不损失信噪比的情况下,搜索速度明显提高了.这种搜索算法原理简单,可以比较容易地在硬件上实现.MV FAST的压缩速度明显高于其它算法,而且同时能获得相同的甚至更好的峰值信噪比,在搜索区域为16h,MV FAST的平均压缩速度提高了4到5倍,同时它的峰值信噪比分别比三步搜索法、新三步搜索法和菱形搜索法高有很大的提高.
参考文献:
[1] Zhu S,Ma KK.A new diamond search algorithm for fast block2matching motion estimation[J].IEEE Trans.Image
Processing,2000,9(2):2872290
[2] Wang YK,Kuroda H.Hilbert Scanning search algorithm for motion estimation[J].IEEE Trans.Circuits Systems
for Video Technology,1999,6(5):6832691
[3] 向友君,郭宝龙.运动估计快速块匹配算法[J].计算机工程,2003,256(13):62264
[4] 王赜,梁川,王光兴.块匹配运动估计算法的速度优化[J].东北大学学报,2003,238(4):3152318
[5] 周铁,丁钟琦.运动估值块匹配算法的一种改进[J].海南大学学报,2005,169(2):1402149
[6] 全子一,门爱东,杨波.数字视频图像处理[M].北京:电子工业出版社,2005.75289
[7] 容观澳.计算机图象处理[M].北京:清华大学出版社,2000.2602300[责任编辑:刘守义]
(上接第66页)
疾病防疫再加上自己的努力就一定能够成功.
参考文献
[1] 王加志.养貉技术纵深谈[M].北京:农业出版社,1989.1162144
[2] 华树芳,佟煜人,籍玉林.貉的饲养[M].吉林:吉林科学技术出版社,1988.28274
[3] 覃能斌,孙海霞,刘春龙.实用养狐技术大全[M].北京:中国农业出版社,2004.1772180
[4] 闰庆华.充分认识初乳对仔狐、貉生长的重要性[J].特种经济动植物,2005,8(5):2
[5] 宋锦英,邓龙江.狐貉的过继技术[J].现代化农业,2005,27(6):20221
[6] 樊兵菊.仔貉常见病的防治[J].河北畜牧兽医,2005,21(8):33
[7] 边桂萍.防止母貉吃仔的措施[J].河北畜牧兽医,2005,21(9):33
[8] 陈艳军,赵秀凤.保证仔貉全活全壮的重要措施[J].河北农业科技,2004,33(1):36
[9] 华盛.维生素在毛皮兽上的应用[J].特种经济动植物,2004,7(10):223
[10] 苑彪.貉妊娠期严把饲料关[J].黑龙江动物繁殖,2003,11(2):40241
[11] 华丽.妊娠期和产仔泌乳期的饲养管理要点[J].农村养殖技术,2003,8(10):19
[12] 华树芳.幼貉育成期的饲养管理要点[J].农村养殖技术,2003,8(11):21[责任编辑:刘守义]
网络教育课程考试复习题及参考答案算法分析与设计一、名词解释：1.算法 2.程序 3.递归函数 4.子问题的重叠性质 5.队列式分支限界法 6.多机调度问题7.最小生成树二、简答题： 1.备忘录方法和动态规划算法相 比有何异同？简述之。 2.简述回溯法解题的主要步骤。 3.简述动态规划算法求解的基本要素。 4.简述回溯法的基本思想。 5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。 6.简要分析分支限界法与回溯法的异同。7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？8.贪心算法求解的问题主要具有哪些性质？简述之。9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。10.简述分析贪心算法与动态规划 算法的异同。三、算法编写及算法应用分析题： 1.已知有3个物品： (w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。 2.按要求完成以下关于排序和查找的问题。①对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。③给出上述算法的递归算法。④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。已知，=1，2，3，4，5，6，=5，=10，=3，=12，=5，=50，=6，kijr*r1234567ii1求矩阵链积A×A×A×A×A×A的最佳求积顺序（要求给出计算步骤）。1234564.根据分枝限界算法基本过程,求解0-1背包问题。已知n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。 5.试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。6.试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括：①删除一个字符。②插入一个字符。③将一个字符改为另一个字符。请写出该算法。7.对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。be2g212ad323182cf2h 8.试写出用分治法对数组A[n]实现快速排序的算法。9.有n个活动争用一个活动室。已知活动i占用的时间区域为[s，f ]，活动i,j相容的条件是：sj≥f ii，问题的解表示为(x| x =1，2…，n,)，x表示顺序为i的活动编号活动，求一个相容的活动子集，iiii且安排的活动数目最多。xxx10.设、、是一个三角形的三条边，而且x+x+x=14。请问有多少种不同的三角形？给出解答过程。12312311.
算法设计与分析实验报告 学院信息科学与技术学院 专业班级软件工程3班 学号 20122668 姓名王建君 指导教师尹治本 2014年10月
实验四 矩阵相乘次序 一、问题提出 用动态规划算法解矩阵连乘问题。给定n 个矩阵{A 1,A 2,…,A n }，其中A i 与A i+1是可乘的，i=1,2,…,n-1。要算出这n 个矩阵的连乘积A 1A 2…A n 。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为： （1）单个矩阵是完全加括号的； （2）矩阵连乘积A 是完全加括号的，则A 可表示为2个完全加括号的矩阵连乘积B 和C 的乘积并加括号，即A=(BC)。 例如，矩阵连乘积A 1A 2A 3A 4有5种不同的完全加括号的方式：（A 1（A 2（A 3A 4））），（A 1（（A 2A 3）A 4）），（（A 1A 2）（A 3A 4）），（（A 1（A 2A 3））A 4），（（（A 1A 2）A 3）A 4）。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A 是一个p ×q 矩阵，B 是一个q ×r 矩阵，则计算其乘积C=AB 的标准算法中，需要进行pqr 次数乘。 （3）为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先考察3个矩阵{A 1,A 2,A 3}连乘的情况。设这三个矩阵的维数分别为10×100，100×5，5×50。加括号的方式只有两种：（（A 1A 2）A 3），（A 1（A 2A 3）），第一种方式需要的数乘次数为10×100×5＋10×5×50＝7500，第二种方式需要的数乘次数为100×5×50＋10×100×50＝75000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大的影响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n 个矩阵{A 1,A 2,…,A n }（其中矩阵Ai 的维数为p i-1×p i ，i ＝1,2,…,n ），如何确定计算矩阵连乘积A 1A 2…A n 的计算次序（完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。 二、求解思路 本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。本实验的算法思路是： 1)计算最优值算法MatrixChain()：建立两张表（即程序中的**m 和**s ，利用二维指针存放），一张表存储矩阵相乘的最小运算量，主对角线上的值为0，依次求2个矩阵、3个矩阵…、直到n 个矩阵相乘的最小运算量，其中每次矩阵相乘的最小运算量都在上一次矩阵相乘的最小运算量的基础上求得，最后一次求得的值即为n 个矩阵相乘的最小运算量；另一张表存储最优断开位置。 2)输出矩阵结合方式算法Traceback()：矩阵结合即是给矩阵加括号，打印出矩阵结合方式，由递归过程Traceback()完成。分三种情况： （1）只有一个矩阵，则只需打印出A1； （2）有两个矩阵，则需打印出（A1A2）； （3）对于矩阵数目大于2，则应该调用递归过程Traceback()两次，构造出最优加括号方式。 三、算法复杂度 该算法时间复杂度最高为）（n 3 O 。 四、实验源代码
2.3 课后习题解答 2.3.2 判断题 1．线性表的逻辑顺序与存储顺序总是一致的。（×） 2．顺序存储的线性表可以按序号随机存取。（√） 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。（×） 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（√） 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（×） 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（√）7．线性表的链式存储结构优于顺序存储结构。（×） 8．在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。（√） 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（√）10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（×） 11．静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。（×） 12．线性表的特点是每个元素都有一个前驱和一个后继。（×） 2.3.3 算法设计题 1．设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，（也可以从高下标端开始一边比较，一边移位）然后插入x ，最后修改表示表长的变量。 int insert (datatype A[],int *elenum,datatype x) /*设elenum为表的最大下标*/ {if (*elenum==arrsize-1) return 0; /*表已满，无法插入*/ else {i=*elenum; while (i>=0 && A[i]>x) /*边找位置边移动*/ {A[i+1]=A[i]; i--; } A[i+1]=x; /*找到的位置是插入位的下一位*/ (*elenum)++; return 1; /*插入成功*/ } } 时间复杂度为O(n)。
一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ B ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（ B ）。 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、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。（ B ）
《算法分析与设计》作业( 一) 本课程作业由两部分组成。第一部分为”客观题部分”, 由 15个选择题组成, 每题1分, 共15分。第二部分为”主观题部分”, 由简答题和论述题组成, 共15分。作业总分30分, 将作为平时成 绩记入课程总成绩。 客观题部分: 一、选择题( 每题1分, 共15题) 1、递归算法: ( C ) A、直接调用自身 B、间接调用自身 C、直接或间接 调用自身 D、不调用自身 2、分治法的基本思想是将一个规模为n的问题分解为k个规模 较小的字问题, 这些子问题: ( D ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 3、备忘录方法的递归方式是: ( C ) A、自顶向下 B、自底向上 C、和动态规划算法相同 D、非递归的 4、回溯法的求解目标是找出解空间中满足约束条件的: ( A )
A、所有解 B、一些解 C、极大解 D、极小解 5、贪心算法和动态规划算法共有特点是: ( A ) A、最优子结构 B、重叠子问题 C、贪心选择 D、 形函数 6、哈夫曼编码是: ( B) A、定长编码 B、变长编码 C、随机编码 D、定 长或变长编码 7、多机调度的贪心策略是: ( A) A、最长处理时间作业优先 B、最短处理时间作业优 先 C、随机调度 D、最优调度 8、程序能够不满足如下性质: ( D ) A、零个或多个外部输入 B、至少一个输出 C、指令的确定性 D、指令的有限性 9、用分治法设计出的程序一般是: ( A ) A、递归算法 B、动态规划算法
C、贪心算法 D、回溯法 10、采用动态规划算法分解得到的子问题: ( C ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 11、回溯法搜索解空间的方法是: ( A ) A、深度优先 B、广度优先 C、最小耗费优先 D、随机搜索 12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策 有可能导致算法: ( C ) A、所需时间变化 B、一定找到解 C、找不到所需的解 D、性能变差 13、贪心算法能得到: ( C ) A、全局最优解 B、 0-1背包问题的解 C、背包问题的 解 D、无解 14、能求解单源最短路径问题的算法是: ( A ) A、分支限界法 B、动态规划 C、线形规划 D、蒙特卡罗算法 15、快速排序算法和线性时间选择算法的随机化版本是:
算法实现题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
《算法分析与设计》作业（一） 本课程作业由两部分组成。第一部分为“客观题部分”，由15个选择题组成，每题1分，共15分。第二部分为“主观题部分”，由简答题和论述题组成，共15分。作业总分30分，将作为平时成绩记入课程总成绩。 客观题部分： 一、选择题（每题1分，共15题） 1、递归算法：（C ） A、直接调用自身 B、间接调用自身 C、直接或间接调用自身 D、不调用自身 2、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题，这些子问题：（D ） A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 3、备忘录方法的递归方式是：（C ） A、自顶向下 B、自底向上 C、和动态规划算法相同 D、非递归的 4、回溯法的求解目标是找出解空间中满足约束条件的：（A ） A、所有解 B、一些解 C、极大解 D、极小解 5、贪心算法和动态规划算法共有特点是：（ A ） A、最优子结构 B、重叠子问题 C、贪心选择 D、形函数 6、哈夫曼编码是：（B） A、定长编码 B、变长编码 C、随机编码 D、定长或变长编码 7、多机调度的贪心策略是：（A） A、最长处理时间作业优先 B、最短处理时间作业优先 C、随机调度 D、最优调度 8、程序可以不满足如下性质：（D ） A、零个或多个外部输入 B、至少一个输出 C、指令的确定性 D、指令的有限性 9、用分治法设计出的程序一般是：（A ） A、递归算法 B、动态规划算法
C、贪心算法 D、回溯法 10、采用动态规划算法分解得到的子问题：（ C ） A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 11、回溯法搜索解空间的方法是：（A ） A、深度优先 B、广度优先 C、最小耗费优先 D、随机搜索 12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法：（ C ） A、所需时间变化 B、一定找到解 C、找不到所需的解 D、性能变差 13、贪心算法能得到：（C ） A、全局最优解 B、0-1背包问题的解 C、背包问题的解 D、无解 14、能求解单源最短路径问题的算法是：（A ） A、分支限界法 B、动态规划 C、线形规划 D、蒙特卡罗算法 15、快速排序算法和线性时间选择算法的随机化版本是：（ A ） A、舍伍德算法 B、蒙特卡罗算法 C、拉斯维加斯算法 D、数值随机化算法 主观题部分： 二、写出下列程序的答案（每题2.5分，共2题） 1、请写出批处理作业调度的回溯算法。 #include
第一章 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)). 分析与解答：
《算法分析与设计》作业参考答案 作业一 一、名词解释： 1.递归算法：直接或间接地调用自身的算法称为递归算法。 2.程序：程序是算法用某种程序设计语言的具体实现。 二、简答题： 1.算法需要满足哪些性质？简述之。 答：算法是若干指令的有穷序列，满足性质： （1）输入：有零个或多个外部量作为算法的输入。（2）输出：算法产生至少一个量作为输出。 （3）确定性：组成算法的每条指令清晰、无歧义。 （4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。 2.简要分析分治法能解决的问题具有的特征。 答：分析分治法能解决的问题主要具有如下特征： （1）该问题的规模缩小到一定的程度就可以容易地解决； （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； （3）利用该问题分解出的子问题的解可以合并为该问题的解； （4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 3.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。 答：将递归算法转化为非递归算法的方法主要有： （1）采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归， 只不过人工做了本来由编译器做的事情，优化效果不明显。（2）用递推来实现递归函数。 （3）通过Cooper 变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。 后两种方法在时空复杂度上均有较大改善，但其适用范围有限。 三、算法编写及算法应用分析题： 1.冒泡排序算法的基本运算如下： for i ←1 to n-1 do for j ←1 to n-i do if a[j] 运动功能评定 一、肌力评定 肌力是指肌肉收缩的力量。肌力评定是测定受试者在主动运动时肌肉和肌群产生的最大收缩力量。肌力评定是对神经、肌肉功能状态的一种检查方法，也是评定神经、肌肉损害程度和范围的一种重要手段。 及评定分徒手肌力检查和器械肌力测定。 （一）徒手肌力的检查 1、概念根据受检肌肉和肌群的功能，当受试者处于不同的检查体 位，然后嘱其分别在去除重力、抗重力和抗阻力的条件下做一定的动 作，按照动作的活动范围及抗重力和抗阻力的情况将肌力进行分级。2、标准国际上普遍应用的图，手机的检查方法是Lovett6 级分级 法。 1983 年，美国医学研究委员会在此分级基础上进一步细分，即 MRC肌力分级法，表3-1肌力评定标准 分级评级标准 5肌肉抗最大阻力，活动关节达到全范围 － 5肌肉抗较大阻力，活动关节达到全范围 + 4肌肉抗比中等度稍大的阻力，活动关节达到全范围 4肌肉抗中等度阻力，活动关节达到全范围 4－肌肉抗比中度稍小的阻力，活动关节达到全范围 + 肌肉抗重力时活动关节达到全范围，肌肉抗较小阻力时活动关节达到部分范围3 3肌肉抗重力，活动关节达到全范围 3－肌肉抗重力，活动关节达到最大范围的50%以上 + 肌肉减重活动关节达到全范围，肌肉抗重力活动关节达到最大范围的50%以 下 2 2 肌肉减重活动关节达到全范围 － 肌肉减重活动关节达到最大范围的50%以上 2 1+ 肌肉减重活动关节达到最大范围的50%以下 1可触及肌肉收缩，但无关节运动 0没有可以测到的肌肉收缩 肢体肌群的手法肌力检查方法表3-2。 表 3-2上肢和下肢主要肌肉的手法肌力检查 肌检查方法 群 1 级 2 级 3 级 4 级 5 级 肩仰卧，试向对侧侧前图屈肩时卧，上侧屈可触及三上肢放在滑肌角肌前部板上，肩可群收缩主动屈曲坐位，肩内坐位，肩内旋，坐位，肩内旋，掌心向掌心向下，阻旋，掌心向下，可克服重力加于上臂下，阻力加于力屈肩远端，能抗中上臂远端，能 等阻力屈肩抗较大阻力 屈肩 肩仰卧，试同左，上肢坐位，屈肘肩坐位，屈肘，坐位，屈肘，外图肩外展放在滑板外展 90°，可肩外展 90°，肩外展 90°，展时可触及上，肩主动克服重力外阻力加于上臂阻力加于上肌三角肌收外展展远端，能抗中臂远端，能抗群缩等阻力较大阻力 屈坐位，肩同左，肘可坐位，上肢下坐位，上肢下坐位，上肢下肘外展，上主动屈曲垂；前臂旋后垂；前臂旋（检垂；前臂旋后肌肢放在滑（检查肱二查肱二头肌）（检查肱二群板上；试头肌）或旋（或旋前（检查头肌）或旋前图肘屈曲检查肱肌）或肱肌）或中立（检查肱 第一章习题 一、问答题 1.什么是数据结构？ 2.叙述四类基本数据结构的名称与含义。 3.叙述算法的定义与特性。 4.叙述算法的时间复杂度。 5.叙述数据类型的概念。 6.叙述线性结构与非线性结构的差别。 7.叙述面向对象程序设计语言的特点。 8.在面向对象程序设计中，类的作用是什么？ 9.叙述参数传递的主要方式及特点。 10.叙述抽象数据类型的概念。 二、判断题（在各题后填写“√”或“×”） 1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（） 2.算法就是程序。（） 3.在高级语言（如C或 PASCAL）中，指针类型是原子类型。（） 三、计算下列程序段中X=X+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 四、试编写算法，求一元多项式P n (x)=a +a 1 x+a 2 x2+a 3 x3+…a n x n的值P n (x )，并确定算法中的每 一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用 求幂函数。注意：本题中的输入a i (i=0,1,…,n),x和n，输出为P n (x )。通常算法的输入和输 出可采用下列两种方式之一： （1）通过参数表中的参数显式传递。 （2）通过全局变量隐式传递。 试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。 实习题 设计实现抽象数据类型“有理数”。基本操作包括有理数的加法、减法、乘法、除法，以及求有理数的分子、分母。 第一章答案 1.3计算下列程序中x=x+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 【解答】x=x+1的语句频度为： T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/6 1.4试编写算法，求p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并确定算法中每一语句的执 行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为a i(i=0,1,…n)、x和n,输出为P n(x0)。算法的输入和输出采用下列方法（1）通过参数表中的参数显式传递（2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。 【解答】 （1）通过参数表中的参数显式传递 优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。 缺点：形参须与实参对应，且返回值数量有限。 （2）通过全局变量隐式传递 优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗 Program算法设计与分析基础中文版答案 习题 5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立. Hint: 根据除法的定义不难证明: 如果d整除u和v, 那么d一定能整除u±v; 如果d整除u,那么d也能够整除u的任何整数倍ku. 对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。 数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。故gcd(m,n)=gcd(n,r) 6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次? Hint: 对于任何形如0<=m 设sqrt(x)是求平方根的函数) 算法Quadratic(a,b,c) 描述将十进制整数表达为二进制整数的标准算法 a.用文字描述 b.用伪代码描述 解答： a.将十进制整数转换为二进制整数的算法 输入：一个正整数n 输出：正整数n相应的二进制数 第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n 第二步：如果n=0，则到第三步，否则重复第一步 第三步：将Ki按照i从高到低的顺序输出 b.伪代码 算法 DectoBin(n) .n]中 i=1 while n!=0 do { Bin[i]=n%2; n=(int)n/2; i++; } while i!=0 do{ print Bin[i]; i--; } 9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略)对这个算法做尽可能多的改进. 算法 MinDistance(A[0..n-1]) 习题1 3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C++描述。 //采用分治法 //对数组先进行快速排序 //在依次比较相邻的差 #include qsort(l,1,n); //第一个作为枢轴，从第一个排到第n个 } int main() { int a[11]={0,2,32,43,23,45,36,57,14,27,39}; int value=0;//将最小差的值赋值给value for (int b=1;b<11;b++) cout< 《算法分析与设计》 学习中心： 专业： 学号： 姓名： 作业练习二 一、名词解释 1、MST性质 2、子问题的重叠性质 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次，这种性质称为子问题的重叠性质。 二、简答题 1、简述动态规划算法求解的基本要素。 答：动态规划算法求解的基本要素包括： 1)最优子结构是问题能用动态规划算法求解的前提； 2)动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果，即重叠子问题。 2、备忘录方法和动态规划算法相比有何异同简述之。 答：备忘录方法是动态规划算法的变形。与动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案，在下次需要解此问题时，只要简单地查看该子问题的解答，而不必重新计算。备忘录方法与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同的子问题的重复求解，而直接递归方法没有此功能。 3、贪心算法求解的问题主要具有哪些性质简述之。 答：贪心算法求解的问题一般具有二个重要的性质： 一是贪心选择性质，这是贪心算法可行的第一个基本要素； 另一个是最优子结构性质，问题的最优子结构性质是该问题可用贪心算法求解的关键特征。 三、算法编写及算法应用分析题 1、设计求解如下最大子段和问题的动态规划算法。只需给出其递推计算公式即可。 最大子段和问题：给定由n 个整数（可能为负整数）组成的序列a1a2 … an，求该序列形如Σi≤k≤j ak的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依次定义，所求的最优值为max{0, max1≤i≤j≤n Σi≤k≤j ak }。 粗大运动功能测试量表 （一）量表基本知识 GMFM是Russell等人于1989年设计的测量脑瘫儿童粗大运动功能改变的测量工具，属于标准对照发展性量表，能有效反映脑瘫儿童运动功能改变，已成为国际上公认的脑瘫粗大运动功能测试工具。GMFM量表主要用于评估脑瘫儿童粗大运动功能，具有正常运动功能的儿童在5岁以内能完成所有项目，虽然是针对脑瘫儿童设计的，但也可使用于Down syndrome儿童，近年来也有不少研究者用来测定其它类型的运动障碍儿童的粗大运动功能。GMFM来那个表的不同版本： GMFM最初通过文献回顾和临床医师判断筛选85个项目，在经过信效度研究后，增加了3个项目，形成了GMFM-88项版本，2000年Russell等人使用Rasch分析法对GMFM量表进行了信度和效度分析，最后确立了GMFM-66项。国内任永平等将GMFM修订成80项，增加了原始反射和平衡反应等项目，同时删除了部分评估项目，但是由于没有进行严格的心理测量学特性检验，反射和反应项目的增加与原版量表以功能测试为主的目的相违，在国内未得到广泛使用。 GMFM-88结构： GMFM-88包括88个项目，分5个能区：A区（卧位与翻身）；B区（坐位）：C区（爬行与跪）；D区（站立位）；E区（行走于跑跳）。每项均采用4级评分法，其中A区总分为51分（17项）；B区为60分（20项）；C区总分为42分（14项）；D总分为39分（13项）；E区总分为72分（24项）。 GMFM-88评分标准与结果： GMFM的每一个都为4级评分，具体标准：0分：动作还没有出现的迹象；1分：动作开始出现—只完成整个动作的10％以下；2分：部分完成动作—可以完成整个动作的10％-90％；3分：整个动作可以全部完成。当无法确定分数时，按照较低的等级给分。 GMFM-88提供五种评分结果： 原始分：五个能区的原始分 各能区百分比：能区原始分与各自总分相除，乘以100％ 总百分比：五个能区原始分与各自总分相除，乘以100％之和再除以5 目标区分值：选定目标能区原始分与各自总分相除，乘以100％之和再除以选定能区数GMFM-66的特点： GMFM-66的项目由GMFM-88经过Rasch分析后，筛选出具有线性特征（项目特性线）的项目所组成，GMFM-66项目需要使用电脑程序（Gross Motor Ability Estimator,GMFM软件）输入每个项目的得分，并经分析转化后得到GMFM-66分值。与GMFM-88相比GMFM-66具有如下特点：①属于等距量表，它提高了总分和变化分数的可理解性，能够合理、客观地反映脑瘫患儿的粗大运动发育变化；②重新确立了项目难度顺序；③删除22项不适合项目后，增加了评估的单维性；④重新确定GMFM测定在脑瘫人群中信效度（比GMFM-88建立时使用的样本更大，共537例）。但是GMFM-66不能提供各个功能分区的分值，因此GMFM-88目前依然得到广泛使用。 算法分析与设计习题集 基础篇 1、算法有哪些特点？它有哪些特征？它和程序的主要区别是什么？ 2、算法的时间复杂度指的是什么？如何表示？ 3、算法的空间复杂度指的是什么？如何表示？ 4、设某一函数定义如下： 编写一个递归函数计算给定x的M（x）的值。 本函数是一个递归函数，其递归出口是： M（x）= x-10x>100 递归体是： M（M（x+11））x ≤100 实现本题功能的递归函数如下： intm ( intx ) { int y; if ( x>100 )return(x-10 ); else { y =m(x+11) ; return (m (y )); } } 5、已知一个顺序表中的元素按元素值非递减有序排列，编写一个函数删除表中多余的值相 同的元素。 本题的算法思想是：由于顺序表中元素已按元素值非递减有序排列，值相同的元素比为相邻的元素，因此依次比较相邻两个元素，若值相等，则删除其中一个，否则继续向后查找，直到最后一个元素。实现本题功能的函数如下： voiddel ( seqlist*a ) { inti=0, j; while ( i ①计算结点总数 int CountNode(BinTree *root) { int num1,num2; if(root==Null) return(0); else if(root->lchild==Null&&rooot->rchild==Null) return(1); else { num1=CountNode(root->lchild); num2=CountNode(root->rchild); return(num1+num2+1); } } ②计算叶子总数 int CountLeafs(BinTree *root) { int num1,num2; if(root==Null) return(0); else if(root->lchild==Null&&root->rchild==Null) return(1); else { num1=CountLeafs(root->lchild); num2=CountLeafs(root->rchild); return(num1+num2); } } 分治术 7、有金币15枚，已知其中有一枚是假的，而且它的重量比真币轻。要求用一个天平将假 的金币找出来，试设计一种算法（方案），使在最坏情况下用天平的次数最少。 8、利用分治策略，在n个不同元素中找出第k个最小元素。 9、设有n个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表。 （1）每个选手必须与其它n-1选手各赛一次； （2）每个选手一天只能赛一次。 10、已知序列{503，87，512，61，908，170，897，275，652，462}，写一个自底向上的 归并分类算法对该序列作升序排序，写出算法中每一次归并执行的结果。 void Merge(ElemType *r，ElemType *rf，int u，int v，int t) { f or(i=u，j=v，k=u；i 《算法分析与设计》实验指导. 实验一锦标赛问题 [实验目的] 1.基本掌握分治算法的原理. 2.能用程序设计语言求解锦标赛等问题的算法; [预习要求] 1.认真阅读数据结构教材和算法设计教材,了解分治算法原理; 2.设计用分治算法求解背包问题的数据结构与程序代码. [实验题] 【问题描述】设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表： （1）每个选手必须与其他n-1个选手各赛一次； （2）每个选手一天只能参赛一次； （3）循环赛在n-1天内结束。 请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。其中1≤i≤n，1≤j≤n-1。 [实验提示] 我们可以按分治策略将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。 1 2 3 4 5 6 7 1 （1）（2）（3） 图1 2个、4个和8个选手的比赛日程表 图1所列出的正方形表（3）是8个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这 样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。 [实验步骤] 1.设计并实现算法并准备测试用例,修改并调试程序,直至正确为止; 2.应用设计的算法和程序求锦标赛问题; 3.去掉测试程序,将你的程序整理成功能模块存盘备用. [实验报告要求] 1.阐述实验目的和实验内容; 2.阐述分治算法原理; 3.提交实验程序的功能模块; 4.记录最终测试数据和测试结果。 [思考与练习] 【金块问题】老板有一袋金块(共n块，n是2的幂（n>=2）），将有两名最优秀的雇员每人得到其中的一块，排名第一的得到最重的那块，排名第二的雇员得到袋子中最轻的金块。假设有一台比较重量的仪器，请用最少的比较次数找出最重和最轻的金块。运动功能评定.doc
数据结构课后习题及解析第一章
算法设计与分析基础课后习题答案
算法分析与设计重点课后习题答案
算法分析与设计(线下作业二)
粗大运动功能测试量表
算法分析与设计习题集
《算法设计与分析》实验指导
相关主题
文本预览