最新中南大学算法试验报告

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、建立顺序表存储数据(顺序表的第一存储单元不放数据，存储数据个数)SqLlst. crease (in匸 少一里 力叮-遊干衰L_ printrCWttX第M个整釵：; sca-f ( e 吉壬f &二, el err. ( z ); ,prlntEf输入的数据如下:n, j ;f Dzr ( int k=二；W+ + printf (IGa1,匸.eler Jr);printf (r, ,ntr 匸2、设置high与low指向表的两端，表的第一个数充当关键字依次从表的右端，左端 与high,low进行比较，是的比关键字大的在关键字的左边，比关键字小的在表的 有右边。以关键

3、字为枢轴位置，分为高低子表进行递归排序。int Part丄匸丄亡nf吕L丄stint 丄三 111匸一：_一匸)t 打交换負履字表L中子諄列丄上口:L*応药的逗睾.谨梃龜逗录劉位. /并运亘其庶在仕轻*此叭在它之前的运录均不大于它 in匸 pivatkey,l.elsnO - L,elem(LwJ ;/用子表的弟一己录作抠黯记录pivotlcey gel&nlowj/枢雜记录关键字while (lcwhigh (/从衆的两端交替地向中间扫捲While (lowpivotkeyJ -hiqb;L lJ - L. elm thigh /海比枢轴至冠、的逗录邕到底事while： (lo,hich.L

4、- eJLem 1 cvz t kyJ + +1 ow;L .-eleiL= I. . elelLlow ；/将比柩紬记录大的运录爸到高遴L. el on lew = L .elemfO ;/ 枢轴记录return lew;/邃回粽舗柚音 / Partitionvsid说巧匚工社仁qLXnt &兮丄冲乞lQwf xn& hiyh) /对顾浮表茲申的孕序列B云亟行快速昨HJCX 口二亡匸一口u：if (Lew ;珥对低子表谨归接承 piTOtlQSqkX (Lf pivotloclr ha-g?- j/ 対高子表通归母片I / 2crt学习 好资料学习-好资料四、实验结果更多精品文档五、源代码#

5、i ncludestdio.h# in eludestdlib.h-2# defineOVERFLOWtypedef struct int * elem;intlen gth;SqList;SqList create(int n) 建立一个顺序表 SqList L;L.elem = (int *)malloc( n*sizeof(int); if(!L.elem) exit(OVERFLOW);L.len gth=n;for(i nt j=1;j n;j+) printf(请输入第%d个整数:n,j); scan f(%d,&L.elemj); printf(输入的数据如下:n,j );for

6、(i nt k=1;k n ;k+)prin tf(%6d,L.elemk);prin tf(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 (lo

7、w=pivotkey) -high;L.elemlow = L.elemhigh;/ 将比枢轴记录小的记录移到低端while (lowhigh & L.elemlow=pivotkey) +low;L.elemhigh = L.elemlow;/ 将比枢轴记录大的记录移到高端L.elemlow = L.elem0;/ 枢轴记录到位return low; / 返回枢轴位置 / Partition void QSort(SqList &L, int low, int high) /对顺序表L中的子序列L.rlow.high进行快速排序int pivotloc;if (low high) pivot

8、loc = 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)(注:第一个存储单元不存放

9、数据)： 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皇后问题、实验原

10、理及部分代码1、检验是否发生冲突bo&l place (int百考察皇后放置在区住列是否发生冲裘int 1;far (i-1 jicjcj 亠+)if| |ab3(k-i)=ai!3(x2c-L)24 不在对角箋上:r皂t；urn false;匸亡匸urntme;2、先判断一行中某列可以放皇后，找到后移到下一行。某行不能放置时，回溯。void queue(int n _In匸-r K；x1)-0;Jc=L；while (kx二)玮町r 町十打在下_列放豊瓠个皇后wj;ileX璋=(H) st Lx k -H; /j# Fh if tx k:=6j /肄癬个輸出fi-n-)pzrititf (r

11、 x );pzin-cf (11;else if (x k =n&4k：r)k=lc+l 上疙書F 4、皇后else:讥门童2花尸巨磬五、源代码#include非递归的回溯#in clude int 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;/ 若

12、 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、预处理按性价比冒泡排序预处理按性斎比排序veld, sort ) (int rj ;for宣泡捧序for

13、 (：=i+ljif(Nodei value/(floatJNodei.w皀Iqht) j . va_ue/ t匸)! od.e - | . ;eicjnt)X-err =：Jgrle 1；No ds 丄r；ci ：_i亡_：:llcde ； =ter.匚：2、装载时先将性价比高的先放入背包中，直至背包装满装裁主要好法void Load () ine 1;forif (DTcd.eiweiglic-kcTurwexQhc) cu;ivalue4=Node i value; cxirweigtijt.+Made i . weigHt;ITc 己盘上二二 _r=2-; else 百:n_d.m _

14、 . f La=0 j更多精品文档四、实验结果4-0 01 40 I I I I I2 3i42 / / z / Jr Jz z n n Q n n n n ?包量qsi里量量量 :F- =F_ - Mrll 亠F壬E-=r二二 nd 农m曰白白白tr 皱H品口nn品品品兄品 .苛 TTTXAI cacal 2 3 4 5 6 7 su AAAAAAAAA 4刖a虫 患刖j翌更更更刖 主星 里垦垦垦皐 星月主冃SK0.Iff五、源代码#i nclude int M;struct no defloat value;float weight;int flag;Node20,temp;float V

15、alue,curvalue=O;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

16、+=Nodei.value; curweight+=Nodei.weight;Nodei.flag=1;elseNodei.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);,i+1);int main() int i; printf( 请输入物品的总数量： ); scanf(%d,&M); printf( 请输入物品的重量和价值： n); for(i=0;iM;i+) printf( 请输入第 %d 个物品的重量和价值更多