中南大学算法实验报告(共14页)

1、精选优质文档-倾情为你奉上算法分析与设计实验报告学院： 信息科学与工程学院专业班级：物联网工程1301班指导老师： 向瑶 学号： 姓名： 目 录实 验 一 -3 实验目的 -3 实验内容 -3实验原理及部分代码 -3 实验结果 -4 源代码 -4实 验 二 -7 实验目的 -7 实验内容 -7实验原理及部分代码 -7 实验结果 -8 源代码 -8实 验 三 -10 实验目的 -10 实验内容 -10实验原理及部分代码 -10 实验结果 -11 源代码 -11心得体会 -14实验一 递归与分治一、 实验目的1、理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。2、掌握分治算法的思想，

2、对给定的问题能设计出分治算法予以解决。二、 实验内容设计算法并编程实现快速排序三、 实验原理及部分代码1、 建立顺序表存储数据（顺序表的第一存储单元不放数据，存储数据个数）2、 设置high与low指向表的两端，表的第一个数充当关键字依次从表的右端，左端与high,low进行比较，是的比关键字大的在关键字的左边，比关键字小的在表的有右边。以关键字为枢轴位置，分为高低子表进行递归排序。四、 实验结果五、 源代码#include "stdio.h"# include "stdlib.h"# define OVERFLOW -2typedef struct i

3、nt * 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;j<n;j+) printf("请输入第%d个整数:n",j ); scanf("%d",&L.elemj); printf("输入的数据如下:n",j ); for(int k=1;k<n;k+) p

4、rintf("%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 (low<high) / 从表的两端交替地向中

5、间扫描 while (low<high && L.elemhigh>=pivotkey) -high; L.elemlow = L.elemhigh; / 将比枢轴记录小的记录移到低端 while (low<high && L.elemlow<=pivotkey) +low; L.elemhigh = L.elemlow; / 将比枢轴记录大的记录移到高端 L.elemlow = L.elem0; / 枢轴记录到位 return low; / 返回枢轴位置 / Partitionvoid QSort(SqList &L, int

6、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; voi

7、d 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

8、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、 先判断一行中某

9、列可以放皇后，找到后移到下一行。某行不能放置时，回溯。四、 实验结果五、源代码#include<stdio.h>/非递归的回溯#include<math.h>int x100;bool place(int k)/考察皇后k放置在xk列是否发生冲突 int i; for(i=1;i<k;i+) if(xk=xi|abs(k-i)=abs(xk-xi)/不在同一列，不在对角线上 return false; return true;void queue(int n) int i,k; x1=0; k=1; while(k>=1) xk=xk+1; /在下一列放置第

10、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&&k<n) k=k+1;/放置下一个皇后 else xk=0;/重置xk,回溯 k=k-1; void main() int

11、 n; printf("输入皇后个数n:n"); scanf("%d",&n); queue(n);实验三 贪心与随机算法一、 实验目的理解贪心算法的思想和执行过程，并能熟练编写程序。二、 实验内容设计算法并编程实现0/1背包问题三、 实验原理及部分代码1、 预处理按性价比冒泡排序 2、 装载时先将性价比高的先放入背包中，直至背包装满四、 实验结果五、 源代码#include <stdio.h> int M;struct node float value; float weight; int flag; Node20,temp; fl

12、oat Value,curvalue=0; float Weight,curweight=0; /预处理按性价比排序 void sort() int i,j; for(i=0;i<M-1;i+) /冒泡排序 for(j=i+1;j<M;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;i<M;i+) if(Nodei.weight+

13、curweight)<=Weight) curvalue+=Nodei.value; curweight+=Nodei.weight; Nodei.flag=1; else Nodei.flag=0; /进行结果的输出 void putout() int i; printf("选中物品的重量分别为：n"); for(i=0;i<M;i+) if(Nodei.flag) printf("物品"); printf("%d",i+1); printf(":"); printf("%.2f "

14、;,Nodei.weight); printf("n"); printf("n总价值为:%.2fn",curvalue); int main() int i; printf("请输入物品的总数量："); scanf("%d",&M); printf("请输入物品的重量和价值：n"); for(i=0;i<M;i+) printf("请输入第%d个物品的重量和价值",i+1); scanf("%f%f",&Nodei.weight,&Nodei.value); printf("n请输入背包容积：&qu