计算机算法设计与分析(课程设计)

用分治法解决合并排序问题及用贪心法解决单源最短路径问题及用回溯法解决0-1背 包问题

一.课程设计目的 本课程是一门实践性非常强的课程，要求学生能够将所学算法应用到实际中，灵活解决实际问题。通过课程设计，能够培养学生独立思考，综合分析与动手能力，并能加深对课堂所学理论和概念的理解，可以训练学生的算法设计的思维，培养学生算法的分析能力。 二．课程设计内容 通过设计，在逻辑特性和物理表示，数据结构的选择应用，算法的设计及实现等方面加深对课程基本内容的理解和综合应用。 1． 用分治法解决合并排序的问题 2． 用贪心法解决单源最短路径问题 3． 用回溯法解决0-1背包问题 三．概要设计 1．合并排序问题：将待排序元素分成大小大致相同的两个子集合，分别对两个子集合进行排序，最终将排好序的子集合合并成所要求的排好序的集合。 解合并排序问题的分治法的主要程序代码描述如下： template void MergeSort(T a[],int left,int right) { T *b=new int[right-left+1]; if(leftint i=(left+right)/2;//取中点 MergeSort(a,left,i);//左半边进行合并排序 MergeSort(a,i+1,right);//右半边进行合并排序 Merge(a,b,left,i,right);//左右合并到b中 Copy(a,b,left,right);//从b拷贝回来 } } 2．单源最短路径问题：设置顶点集合s并不断地做贪心选择来扩充这个集合。一个顶点属于集合s，当且仅当从源到该顶点的最短路径长度已知。初始时，s中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路径长度的顶点u,将u添加到S中，同时对数组dist做必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。 解单源最短路径问题的贪心算法主要程序代码描述如下： for(i = 0; i < n; i++) { w[i]=new int[n]; } cout<<"input the value of w[n][n]:"; for(i=0;i for(j=0;j cin>>w[i][j];//输入邻接矩阵w(n)(n)

for(s[0]=1,i=1;i { s[i]=0; dist[i]=w[0][i];// if(dist[i] < maxint) //判断此时是是否有路径 p[i]=0;//有路径的记为0 else p[i]=-1;//没路径的记为-1 } for(i=1;i { t=maxint; k=1; 3.0-1背包问题：0-1背包问题可用子集数表示。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当右子树中有可能包含最优解时才进入右子树搜索。否则将右子树剪去。设r是当前剩余物品价值总和；cp是当前价值;bestp是当前最优价值。 当cp+r<=bestp时，可剪去右子树。计算右子树中解的上界的更好方法是将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。 解0-1背包问题的回溯算法主要程序代码描述如下： Template Typep Knap::Bound(int i) {//计算上界 Typew cleft=c-cw;//剩余容量 Typep b=cp; //以物品单位重量价值递减序装入物品 While(i<=n&&w[i]<=cleft){ Cleft-=w[i]; b+=p[i]; i++; } //装满背包 if(i<=n)b+=p[i]*cleft/w[i]; return b; }

四．详细设计与实现 1．用分治法解决合并排序源代码描述如下： #include #include //这个函数将b[0]至b[right-left+1]拷贝到a[left]至a[right] template void Copy(T a[],T b[],int left,int right) { int size=right-left+1; for(int i=0;i{ a[left++]=b[i]; }

} //这个函数合并有序数组a[left:i],a[i+1:right]到b,得到新的有序数组b

template void Merge(T a[],T b[],int left,int i,int right) { int a1cout=left,//指向第一个数组开头 a1end=i,//指向第一个数组结尾 a2cout=i+1,//指向第二个数组开头 a2end=right,//指向第二个数组结尾 bcout=0;//指向b中的元素 for(int j=0;j{

if(a1cout>a1end){b[bcout++]=a[a2cout++];continue;}//如果第一个数组结束，拷贝第二个数组的元素到b if(a2cout>a2end){b[bcout++]=a[a1cout++];continue;}//如果第二个数组结束，拷贝第一个数组的元素到b if(a[a1cout]束，比较元素大小，把较小的放入b else {b[bcout++]=a[a2cout++];continue;} } } //对数组a[left:right]进行合并排序

template void MergeSort(T a[],int left,int right) { T *b=new int[right-left+1]; if(leftint i=(left+right)/2;//取中点 MergeSort(a,left,i);//左半边进行合并排序 MergeSort(a,i+1,right);//右半边进行合并排序 Merge(a,b,left,i,right);//左右合并到b中 Copy(a,b,left,right);//从b拷贝回来 } }

int main() { int n; cout<<"how many numbers to sort:"; cin>>n; int *a=new int[n]; cout<<"input ">a[i];} MergeSort( a, 0, n-1); for(int j=0;j{ cout<} return 1; } 运行结果截图如下：

2．用贪心法解决单源最短路径问题的源代码描述如下： #include using namespace std; #define maxint 1000 void main() { int j,i,n,k,t,**w,*s,*p,*dist; cout<<"input the value of n:"; cin>>n;//输入顶点个数 cout<

dist=new int[n];//从第一个点到其他点最短距离矩阵 s=new int[n]; p=new int[n]; w=new int*[n];//邻接矩阵

for(i = 0; i < n; i++) { w[i]=new int[n]; } cout<<"input the value of w[n][n]:"; for(i=0;i for(j=0;j cin>>w[i][j];//输入邻接矩阵w(n)(n)

for(s[0]=1,i=1;i { s[i]=0; dist[i]=w[0][i];// if(dist[i] < maxint) //判断此时是是否有路径 p[i]=0;//有路径的记为0 else p[i]=-1;//没路径的记为-1 }

for(i=1;i