《算法分析与设计》实验指导

《《算法分析与设计》实验指导》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法分析与设计》实验指导书何敏编著计算机综合实验中心目录实验一分治法...................................................................................................3实验二贪心方法...............................................................................................6实验三动态规划.............................

2、................................................................10实验四回溯法.................................................................................................152实验一分治法一、实验目的1．掌握分治法思想；2．熟练运用分治法解决相应的问题。二、实验内容分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。如果原问题可

3、分割成k个子问题，1

4、集合单独分类，然后将已分类的两个序列归并成一个含n个元素的分好类的序列。这种思想是典型的分治设计思想。过程MERGESORT通过使用地规和调用把两个已分类集合归并在一起的子过程MERGE非常简洁地刻画了这一处理过程。算法1．1归并分类procedureMERGESORT(low,high)//A（low：high）是一个全程数组，它含有high-low+1≥0个待分类的元素//integerlow,high;iflow

5、//将一个子集合分类//3callMERGESORT(mid+1,high)//将另一个子集合分类//callMERGE(low,mid,high)//归并两个已分类的子集合//endifendMERGESORT2．快速分类实现的基本思想：选取A（1：n）的某个元素，譬如说t=A（s），然后将其他元素重新排列，使A（1：n）中所有在t以前出现的元素都小于或等于t，而所有在t后面出现的元素都大于或等于t。文件的这种重新整理叫做划分，元素t称为划分元素。因此，所谓快速分类就是通过反复对产生的文件进行划分来实现的。下列算法描述了这种分类的全过程。算

6、法1．2快速分类procedureQUICKSORT(p,q)//将全程数组A（1：n）中的元素A（p），…，A（q）按递增的方式分类。认为A（n+1）已被定义，且大于或等于A（p：q）的所有元素；即A（n+1）=+//integerp,q；globaln,A(1:n);ifp

7、的元素。如果划分元素v测定在A（j）的位置上，则有j-1个元素小于或等于A（j），且有n-j个元素大于或等于A（j）。因此，若kj，则第k小元素是A（j+1：n）中第（k-j）小元素。所导出的算法如果成SELECT。此过程把第k小元素放在A（k），并划分剩余的元素，使得A（i）≤A（k），1≤i

8、，假设1≤k≤n。将剩下的元素按如下方式重新排列，使A（k）=t，对于1≤m