1、算法设计与分析实验报告指导老师：沙莎学 院：信息科学与工程学院班 级：计科 0508姓 名：戚婕学 号：10完成日期：2007 年 12 月1目 录实验一 分治法 21.1 实验要求 21.2 实验内容 21.3 核心算法 21.4 程序代码 41.5 实验结果 8实验二 贪心法 102.1 实验要求 102.2 实验内容 102.3 核心算法 102.4 程序代码 122.5 实验结果 18实验三 动态规划 203.1 实验要求 203.2 实验内容 203.3 核心算法 203.4 程序代码 213.5 实验结果 24实验四 深度优先搜索 264.1 实验要求 264.2 实验内容 264
2、.3 核心算法 264.4 程序代码 274.5 实验结果 28实验五 回溯法 305.1 实验要求 305.2 实验内容 305.3 核心算法 305.4 程序代码 315.5 实验结果 332实验一 分治法一.实验要求1. 了解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大的问题时，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1mid then for kj to high do /处理剩余的元素/B(i) A(k)；ii+1repeatelse for kh to mid do B(i) A(k)；ii+1repeatendif将已归并的集合复制
3、到A end MERGE2. 快速排序算法QuickSort(p,q) /将数组A1:n中的元素Ap, Ap+1, , Aq按不降次序排列，并假定An+1是一个确定的、且大于A1:n中所有的数。/int p,q; global n, A1:n;if p#include#include#include#define M 11typedef int KeyType;typedef int ElemType;struct recKeyType key;ElemType data; ;typedef rec sqlistM;class guibingpublic:guibing(sqlist b)fo
4、r(int i=0;ibj.key) k=j;if(k!=i)rec temp=bk;bk=bi;bi=temp;void merge(int l,int m,int h,sqlist r2)xuanze(r,l,m);xuanze(r,m,h);output(r,M);int i,j,k;k=i=l;for(j=m;i#include#include#include#define MAXI 10typedef int KeyType;typedef int ElemType;struct recKeyType key;ElemType data; ;typedef rec sqlistMAX
5、I;class kuaisupublic:kuaisu(sqlist a,int m):n(m)for(int i=0;i=p.key)j-;8bi=bj;while(ijbj=bi;bi=p;output();return i;void output()for(int i=0;in;i+)coutsetw(4)bi.key;coutendl;private:sqlist b;int n;void main()cout“kuaisu1.cpp运行结果:n“;sqlist a1;int i,n=MAXI,low=0,high=9;srand(time(0);for(i=0;in;i+)a1i.key=rand()%80;kuaisu px(a1,n);cout“数组排序过程演示:n“;px.quicksort(low,high);cout“排序后数组:n“;px.output();cin.get();五.实验结果1. 归并排序92. 快速排序
