中南大学算法实验报告

算法分析与设计实验报告学院： 信息科学与工程学院专业班级：物联网工程1301班指导老师： 向瑶 学号： 姓名： 目 录实 验 一 -3 实验目的 -3 实验内容 -3实验原理及部分代码 -3 实验结果 -4 源代码 -4实 验 二 -7 实验目的 -7 实验内容 -7实验原理及部分代码 -7 实验结果 -8 源代码 -8实 验 三 -10 实验目的 -10 实验内容 -10实验原理及部分代码 -10 实验结果 -11 源代码 -11心得体会 -14实验一 递归与分治一、 实验目的1、理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。2、掌握分治算法的思想，对给定的问题能设计出分治算法予以解决。二、 实验内容设计算法并编程实现快速排序三、 实验原理及部分代码1、 建立顺序表存储数据（顺序表的第一存储单元不放数据，存储数据个数）2、 设置high与low指向表的两端，表的第一个数充当关键字依次从表的右端，左端与high,low进行比较，是的比关键字大的在关键字的左边，比关键字小的在表的有右边。以关键字为枢轴位置，分为高低子表进行递归排序。四、 实验结果五、 源代码#include stdio.h# include stdlib.h# define OVERFLOW -2typedef struct int * elem; int length;SqList;SqList create(int n)/建立一个顺序表 SqList L; L.elem = (int *)malloc( n*sizeof(int); if(!L.elem) exit(OVERFLOW); L.length=n; for(int j=1;jn;j+) printf(请输入第%d个整数:n,j ); scanf(%d,&L.elemj); printf(输入的数据如下:n,j ); for(int k=1;kn;k+) printf(%6d,L.elemk); printf(n); return L;int Partition(SqList &L, int low, int high) / 交换顺序表L中子序列L.elemlow.high的记录，使枢轴记录到位， / 并返回其所在位置，此时，在它之前（后）的记录均不大（小）于它 int pivotkey; L.elem0 = L.elemlow; / 用子表的第一个记录作枢轴记录 pivotkey = L.elemlow; / 枢轴记录关键字 while (lowhigh) / 从表的两端交替地向中间扫描 while (low=pivotkey) -high; L.elemlow = L.elemhigh; / 将比枢轴记录小的记录移到低端 while (lowhigh & L.elemlow=pivotkey) +low; L.elemhigh = L.elemlow; / 将比枢轴记录大的记录移到高端 L.elemlow = L.elem0; / 枢轴记录到位 return low; / 返回枢轴位置 / Partitionvoid QSort(SqList &L, int low, int high) / 对顺序表L中的子序列L.rlow.high进行快速排序 int pivotloc; if (low high) pivotloc = Partition(L, low, high); / 将L.elemlow.high一分为二 QSort(L, low, pivotloc-1); / 对低子表递归排序，pivotloc是枢轴位置 QSort(L, pivotloc+1, high); / 对高子表递归排序 / QSortSqList QuickSort(SqList &L) QSort(L,1,L.length); return L; void main() SqList T; int n,low, high; char yes_no; do do printf(请输入顺序表的长度(大于0)(注:第一个存储单元不存放数据)：n); scanf(%d,&n); while(n=0); T=create(n); T=QuickSort(T); printf(快速排序后数据如下：n); for(int k=2;k=n;k+) printf(%6d,T.elemk); printf(n); do printf(排序完毕); scanf(%s,&yes_no); while(yes_no!=Y&yes_no!=y&yes_no!=N&yes_no!=n); while(yes_no=Y|yes_no=y);实验二 回溯一、实验目的熟练掌握回溯算法二、 实验内容设计算法并编程用回溯算法实现n皇后问题三、 实验原理及部分代码1、 检验是否发生冲突2、 先判断一行中某列可以放皇后，找到后移到下一行。某行不能放置时，回溯。四、 实验结果五、源代码#include/非递归的回溯#includeint x100;bool place(int k)/考察皇后k放置在xk列是否发生冲突 int i; for(i=1;i=1) xk=xk+1; /在下一列放置第k个皇后 while(xk=n&!place(k) xk=xk+1;/搜索下一列 if(xk=n&k=n)/得到一个输出 for(i=1;i=n;i+) printf(%d ,xi); printf(n); /return;/若return则只求出其中一种解，若不return则可以继续回溯，求出全部的可能的解 else if(xk=n&kn) k=k+1;/放置下一个皇后 else xk=0;/重置xk,回溯 k=k-1; void main() int n; printf(输入皇后个数n:n); scanf(%d,&n); queue(n);实验三 贪心与随机算法一、 实验目的理解贪心算法的思想和执行过程，并能熟练编写程序。二、 实验内容设计算法并编程实现0/1背包问题三、 实验原理及部分代码1、 预处理按性价比冒泡排序 2、 装载时先将性价比高的先放入背包中，直至背包装满四、 实验结果五、 源代码#include int M;struct node float value; float weight; int flag; Node20,temp; float Value,curvalue=0; float Weight,curweight=0; /预处理按性价比排序 void sort() int i,j; for(i=0;iM-1;i+) /冒泡排序 for(j=i+1;jM;j+) if(Nodei.value/(float)Nodei.weight) Nodej.value/(float)Nodej.weight) temp=Nodei; Nodei=Nodej; Nodej=temp; /装载主要方法 void load() int i; for(i=0;iM;i+) if(Nodei.weight+curweight)=Weight) curvalue+=Nodei.value; curweight+=Nodei.weight; Nodei.flag=1; else Nodei.flag=0; /进行结果的输出 void putout() int i; printf(选中物品的重量分别为：n); for(i=0;iM;i+) if(Nodei.flag) printf(物品); printf(%d,i+1); printf(:); printf(%.2f ,Nodei.weight); printf(n); printf(n总价值为:%.2fn,curvalue); int main() int i; printf(请输入物品的总数量：); scanf(%d,&M); printf(请输入物品的重量和价值：n); for(i=0;iM;i+) printf(请输入第%d个物品的重量和价值,i+1); scanf(%f%f,&Nodei.weight,&Nodei.value); printf(n请输入背包容积：); scanf(%f,&Wei