1
华中科技大学文华学院
《算法分析与设计》
课程设计报告
专业：计算机科学与技术
班级：2班
姓名：肖红红
学号：070104021117
指导老师：秦明
设计时间：5周-12周
2 目录
实验1 用分治法进行归并分类
1.1归并分类思想……………………………………. …3
1.2归并分类流程图……………………………………3
1.3归并分类源程序…………………………………….4
1.4归并分类结果截图………………………………….5
实验2 用分治法进行快速分类
2.1快速分类思想及代码………………………………..6
2.2快速分类流程图…………………………..................7
2.3快速分类源程序…………………………..................8
2.4快速分类结果截图…………………………………8
实验3 贪心算法求背包问题
3.1 背包问题思想…………………………….. ………9
3.2 背包问题流程图…………………………..............9
3.3背包问题源程序…………………………................10
3.3 背包问题结果截图………………………………..11
实验4 贪心算法求单源点最短路径
4.1单源点最短路径思想………………………………12
4.2单源点最短路径流程图…………………................12
4.3单源点最短路径源程序……………………………13
4.4单源点最短路径结果截图…………………………14
心得体会………………………………………………………15
3 实验一：《归并排序》
1.1归并排序设计思想：
归并排序采用的是分治策略，主要分为3个过程。
第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2
个元素。
第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作。
第三, 合并: 将已分类的两个序列合并成一个含有n个元素的分好累的序列,并生成最后的排序结果。
1.2归并排序流程图如下：
开始，输入数组A（1：n）
将A分为2个集合A(1)„A(n/2)和A(n/2+1)„A(n)
注：A(n/2)和A(n)均取下限值
分别对两个集合单独分类并按非降次序列分别A(1)„A(n/是否归并完全
输出最后序列，结束 否
是
4 1.3源程序如下：
#include
#define LENGTH 50
int a[LENGTH],b[LENGTH]; 设置数组
void Mergr(int low,int mid,int high) //使用辅助数组归并两个已经分类的集合
{
int h,j,k,i;
h=low;
j=mid+1;
k=low;
while(h<=mid&&j<=high) //当2个集合都没有取尽时
{
if(a[h]<=a[j])
{
b[k]=a[h];
h++;
}
else
{
b[k]=a[j];
j++;
}
k++;
}
if(h>mid) //处理剩余的元素
{
for(i=j;i<=high;i++)
{
b[k]=a[i];
k++;
}
}
else
{
for(i=h;i<=mid;i++)
{
b[k]=a[i];
k++;
}
}
for(i=low;i<=high;i++) //将已经归并的集合复制到数组A
{
a[i]=b[i];
5 }
}
void Mergesort(int low,int high) //归并分类
{
int mid;
if(low { mid=(int)((high+low)/2); Mergesort(low,mid); //将一个子集合分类 Mergesort(mid+1,high); //将另一个子集合分类 Mergr(low,mid,high); //归并2个已经分类的集合 } } void main() { int i,length; printf("Please input the total numbers:\n"); scanf("%d",&length); printf(" input your members:\n"); for(i=0;i scanf("%d",&a[i]); } Mergesort(0,length-1); printf("The new Mergesort numbers:\n"); for(i=0;i printf("%d ",a[i]); } } 1.4结果截图： 6 实验二：《快速分类》 2.1快速分类设计思想： 快速分类是通过反复对产生的文件进行划分来实现的。其主要过程大致可以分为以下3个步骤。 第一，划分元素 ：将A[p..q]划分成两个非空的子序列A[p..j]和A[j+1..q]，使得A[p..j]中的任一元素小于或等于A[j+1..q]中的任一元素。下标j在划分过程中确定. 具体的划分过程可由如下的方法来实现：选取A[p..q]的某个元素，譬如说v=A(s)，然后将其它元素重新排列，使A[p..q]中所有在v以前出现的元素都小于或等于v，而所有在v后面出现的元素都大于或等于v。 第二，递归求解 ：通过递归调用快速分类算法分别对A[p..j-1]和A[j+1..q]进行分类 第三，合并(Merger) ：由划分的特点知，在A[p..j-1]和A[j+1..q]都分好类后不就已分好类。 1.2快速分类算法流程图如下： 开始初始化待排序链表L 选取划分元素，排序 将小于或等于该元素的数的值移到元素前面 将大于或等于该元素的数移到元素后 L最后的顺序就是排序后的结果，结 7 2.3源程序如下： #include #define LENGTH 50 int a[LENGTH],b[LENGTH]; void Qicksort(int b[],int s,int t) //对集合快速分类 { int i=s,j=t; if(i { b[0]=b[i]; do{ while(i j--; if(i { b[i]=b[j]; i++; } while(i i++; if(i { b[j]=b[i]; j--; } }while(i b[i]=b[0]; //划分元素位置 Qicksort(b,s,j-1); Qicksort(b,j+1,t); } } void main() { int i,length; printf("Please input the total numbers:\n"); scanf("%d",&length); printf("input your members:\n"); for(i=1;i<=length;i++) scanf("%d",&b[i]); 8 Qicksort(b,1,length); printf("The result is:\n"); for(i=1;i<=length;i++) printf("%d ",b[i]); printf("\n"); } 2.4结果截图： 首先输入需要分类的数组的个数，然后继续输入数组元素，调用快速分类算法，将最后的结果输出。 9 实验三：《背包问题》 3.1贪心算法求解背包问题思想： 贪心方法，总是对当前的问题作最好的选择，也就是局部寻优，每一步只考虑一个数据，它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加为止。最后得到整体最优解法。在背包问题中，将物体事先按照Pi/Wi的非增次序分好类，用一个一维数组来存放好该项的值，再采用贪心算法从第一项开始装背包，然后是第二项，依次类推，尽可能的多放，直到装满背包为止。 3.2背包问题流程图如下： 开始对p,w,M,N 初始化 求p/w 按非降次序列排列数组b存p/w的值 数组a存排序后b 依次装入背包记 整理最优解，算出最大效益值，结束
