算法设计与分析实验报告

《算法设计与分析实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法设计与分析实验报告指导老师：沙莎学院：信息科学与工程学院班级：计科0508姓名：戚婕学号：10完成日期：2007年12月33目录实验一分治法…………………………………………………………………………21.1实验要求………………………………………………………………………21.2实验内容………………………………………………………………………21.3核心算法………………………………………………………………………21.4程序代码………………………………………………………………………41.5实验结果………………………………………………………………………8实验二贪心法………………………………

2、………………………………………102.1实验要求……………………………………………………………………102.2实验内容……………………………………………………………………102.3核心算法……………………………………………………………………102.4程序代码……………………………………………………………………122.5实验结果……………………………………………………………………18实验三动态规划…………………………………………………………………203.1实验要求……………………………………………………………………203.2实验内容……………………………………………………………………

3、203.3核心算法……………………………………………………………………203.4程序代码……………………………………………………………………213.5实验结果……………………………………………………………………24实验四深度优先搜索……………………………………………………………264.1实验要求……………………………………………………………………264.2实验内容……………………………………………………………………264.3核心算法……………………………………………………………………264.4程序代码……………………………………………………………………274.5实验结果………………

4、……………………………………………………28实验五回溯法………………………………………………………………………305.1实验要求……………………………………………………………………305.2实验内容……………………………………………………………………305.3核心算法……………………………………………………………………305.4程序代码……………………………………………………………………315.5实验结果……………………………………………………………………3333实验一分治法一.实验要求1.了解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大的问题时，如果问题可以分成

5、k个不同子集合，得到k个不同的可独立求解的子问题，其中1

6、归并排序算法和快速排序算法，程序中加入比较次数的计数功能，输出排序结果和比较次数。2.输入10组相同的数据，验证排序结果和完成排序的比较次数。3.与复杂性函数所计算的比较次数比较。4.用表格列出比较结果。5.给出文字分析。三.程序算法1.归并排序算法procedureMERGESORT(low，high)//A(low；high)是一个全程数组，它含有high-low+1≥0个待排序的元素//integerlow，high；iflow

7、(mid+1，high)//将另一个子集合排序callMERGE(low，mid，high)//归并两个已排序的子集合//endif33endMERGESORT归并两个已排序的集合procedureMERGE(low，mid，high)//A(low：high)是一个全程数组////辅助数组B(low；high)//integerh，i，j，k；h←low；i←low；j←mid+1；whileh≤midandj≤highdo//当两个集合都没取尽时//ifA(h)≤