计算机算法设计与分析（课程设计）

1、计算机算法设计与分析（课程设计） 用分治法解决合并排序问题及用贪心法解 决单源最短路径问题及用回溯法解决0-1背 包问题 一.课程设计目的 本课程是一门实践性非常强的课程，要求学生能够将所学算法应用到实际中，灵活解决实际问题。通过课程设计，能够培养学生独立思考，综合分析与动手能力，并能加深对课堂所学理论和概念的理解，可以训练学生的算法设计的思维，培养学生算法的分析能力。 二课程设计内容 通过设计，在逻辑特性和物理表示，数据结构的选择应用，算法的设计及实现等方面加深对课程基本内容的理解和综合应用。 1 用分治法解决合并排序的问题 2 用贪心法解决单源最短路径问题 3 用回溯法解决0-1背包问题

2、三概要设计 1合并排序问题：将待排序元素分成大小大致相同的两个子集合，分别对两个子集合进行排序，最终将排好序的子集合合并成所要求的排好序的集合。 解合并排序问题的分治法的主要程序代码描述如下： template void mergesort(t a,int left,int right) t *b=new intright-left+1; if(leftint i=(left+right)/2;/取中点 mergesort(a,left,i);/左半边进行合并排序 mergesort(a,i+1,right);/右半边进行合并排序 merge(a,b,left,i,right);/左右合并到b

3、中 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就记录了从源到所有其他顶点之间的最短路径长度。 解单源最短路径问题的贪心算法主要程序代码描述如下：

4、for(i = 0; i wi=new intn; cout cinwij;/输入邻接矩阵w(n)(n) for(s0=1,i=1;i disti=w0i;/ if(disti pi=-1;/没路径的记为-1 for(i=1;i t=maxint; k=1; 3.0-1背包问题：0-1背包问题可用子集数表示。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当右子树中有可能包含最优解时才进入右子树搜索。否则将右子树剪去。设r是当前剩余物品价值总和；cp是当前价值;bestp是当前最优价值。 当cp+r typep knap:bound(int i) /计算上界 typew

5、cleft=c-cw;/剩余容量 typep b=cp; /以物品单位重量价值递减序装入物品 while(iif(i四详细设计与实现 1用分治法解决合并排序源代码描述如下： #include #include /这个函数将b0至bright-left+1拷贝到aleft至aright template void copy(t a,t b,int left,int right) int size=right-left+1; for(int i=0;ialeft+=bi; /这个函数合并有序数组aleft:i,ai+1:right到b,得到新的有序数组b template void merge(t

6、 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;jif(a1couta1end)bbcout+=aa2cout+;continue;/如果第一个数组结束，拷贝第二个数组的元素到b if(a2couta2end)bbcout+=aa1cout+;continue;/如果第二个数组结束，拷贝第一个数组的元素到b if(aa1coutbbcout+=aa2cout+;continue; /对数组aleft:right进行合并排序 template void mergesort(t a,int left,int right) t *b=new intright-left+1; if(leftint i=(left+right)/2;/取中点 mergesort(a,left,i);/左半边进行合并排序 mergesort(a,i+1,right);/右半边进行合并排序 me