算法分析与设计实验报告
学院：信息科学与工程学院
专业班级：物联网工程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 -2
typedef 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;j { printf("请输入第%d个整数:\n",j ); scanf("%d",&L.elem[j]); } printf("输入的数据如下:\n",j ); for(int k=1;k printf("%6d",L.elem[k]); printf("\n"); return L; } int Partition(SqList &L, int low, int high) { // 交换顺序表L中子序列L.elem[low..high]的记录，使枢轴记录到位，// 并返回其所在位置，此时，在它之前（后）的记录均不大（小）于它 int pivotkey; L.elem[0] = L.elem[low]; // 用子表的第一个记录作枢轴记录 pivotkey = L.elem[low]; // 枢轴记录关键字 while (low while (low L.elem[low] = L.elem[high]; // 将比枢轴记录小的记录移到低端 while (low L.elem[high] = L.elem[low]; // 将比枢轴记录大的记录移到高端} L.elem[low] = L.elem[0]; // 枢轴记录到位 return low; // 返回枢轴位置 } // Partition void QSort(SqList &L, int low, int high) { // 对顺序表L中的子序列L.r[low..high]进行快速排序 int pivotloc; if (low < high) { pivotloc = Partition(L, low, high); // 将L.elem[low..high]一分为二 QSort(L, low, pivotloc-1); // 对低子表递归排序，pivotloc是枢轴位置QSort(L, pivotloc+1, high); // 对高子表递归排序 } } // QSort SqList 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.elem[k]); 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 #include int x[100]; bool place(int k)//考察皇后k放置在x[k]列是否发生冲突 { int i; for(i=1;i if(x[k]==x[i]||abs(k-i)==abs(x[k]-x[i]))//不在同一列，不在对角线上return false; return true; } void queue(int n) { int i,k; x[1]=0; k=1; while(k>=1) { x[k]=x[k]+1; //在下一列放置第k个皇后 while(x[k]<=n&&!place(k)) x[k]=x[k]+1;//搜索下一列 if(x[k]<=n&&k==n)//得到一个输出 { for(i=1;i<=n;i++) printf("%d ",x[i]); printf("\n"); //return;//若return则只求出其中一种解，若不return则可以继续回溯，求出全部的可能的解 } else if(x[k]<=n&&k k=k+1;//放置下一个皇后 else { x[k]=0;//重置x[k],回溯 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; }Node[20],temp; float Value,curvalue=0; float Weight,curweight=0; //预处理按性价比排序 void sort(){ int i,j; for(i=0;i for(j=i+1;j if((Node[i].value/(float)Node[i].weight) Node[i]=Node[j]; Node[j]=temp; } } } } //装载主要方法 void load(){ int i; for(i=0;i if((Node[i].weight+curweight)<=Weight){ curvalue+=Node[i].value; curweight+=Node[i].weight; Node[i].flag=1; }else{ Node[i].flag=0; } } } //进行结果的输出 void putout(){ int i; printf("选中物品的重量分别为：\n"); for(i=0;i if(Node[i].flag){ printf("物品"); printf("%d",i+1); printf(":"); printf("%.2f ",Node[i].weight); printf("\n"); } } printf("\n总价值为:%.2f\n",curvalue); } int main(){ int i; printf("请输入物品的总数量："); scanf("%d",&M); printf("请输入物品的重量和价值：\n"); for(i=0;i printf("请输入第%d个物品的重量和价值",i+1); scanf("%f%f",&Node[i].weight,&Node[i].value); } printf("\n请输入背包容积："); scanf("%f",&Weight); sort(); load(); putout(); return 0; } 心得体会 许多算法老师上课时讲的比较详细，加上上学期数据结构的基础，总体来说本次实验完成的还比较顺利。虽然这个过程中也遇到了一些小问题，通过翻书基本可以解决。通过本次实验，更加深刻的了解了分治，回溯，贪心算法，也增强了对这门课的兴趣，同时也锻炼了自己动手将算法变为代码的能力。
相关主题
文本预览