《2023年新版算法设计与分析实验报告.docx》由会员分享，可在线阅读，更多相关《2023年新版算法设计与分析实验报告.docx（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法设计与分析课程实验项目目录学生姓名：学号:序号实脸项目编号实脸项目名称*实验项目类型成绩指导教师1蛮力法脸证或设计（可选）2分治算法脸证或设计（可选）3减治法验证4时空权衡验证5动态规划设计6贪婪技术验证或设计（可选）*实验项目类型：演示性、脸证性、综合性、设计性实验。*此表由学生按顺序填写。r et u rn 0;void mai n ( i nt argc, char* a r gv)(int a 100 , x, s, j, i;printf (请输入您要排序的样本: n )；sea n f (猊,& x);for( i = 0 ;ix; i +)8S c an f (% d & a
2、 i );s=partition(a, 0 , i-1);quick sort (a, 1, s 1)；q u i c ks o rt (a, s+ 1 , i 1 );pr intf (排序后的结果为:)；for(j=0;jx; j +)ep r in t f (%d , aj);)程序运营结果如下:请输入您要排序的样本：8643572109排序后的结果为：2345679 10 Press any key to cont inue4.教师评语、评分:本科实验报告专用纸课程名称 算法设计与分析 成绩评估实验项目名称 减治法 指导教师实验项目编号实验项目类型验证 实验地点 机房学生姓名 学号学院
3、信息科学技术学院数学系信息与计算科学专业虹实验时间2023年3月1日6月30日 温度24.实验目的和规定：熟悉减治法的设计思想。1 .实验原理和重要内容：实验原理：减治法的三个环节：将问题实例缩小为规模更小的实例、求 解小规模实例、通过较小规模实例的解获得原问题的解。实验内容：以下题目任选其一1) .运用深度或广度优先查找，设计一个程序，对于一个给定的图，它可 以输出每一个连通分量的顶点，并且能输出图的回路，或者返回一个消 息表白图是无环的。2) ).设计一个程序实现两种拓扑排序算法：DFS算法和减一算法并 做一个实验来比较它们的运营时间。3) .编写程序实现选择问题，即求一个n个数列表的第k
4、个最小元素。2 .实验结果及分析：（将程序和实验结果粘贴，程序可以注释清楚更好。）本科实验报告专用纸(附页)算法程序代码如下：#i n clu d e s t dio. h in t mainO i nt QSo r t (int , int, int);in t a 1 1;1 n t k ;P r intf (请输入一个11个数的数列：n);for(k=0;krig h t )r e t u rn 0;whi 1 e ( i ! =j ) wh i le(aj=tem p & j i)j；i f (ji)ai+ =aj;while (ai i) i +;本科实验报告专用纸(附页)if(ji
5、)aj- =ai ; a i=temp；i f (im)QS ort(a, left, i -1)；对左边的子表进行排序el s e i f ( i m)QSort(a, i + 1, r i ght); 对右边的子表进行排序else p rint f (这个数列中的第K小元素为:%dn w , a i );所得实验结果如下:请祠人一个11个数的数列:12413567142118923这个数列中的第M、元素为：13Press any key to continue.4.教师评语、评分:本科实验报告专用纸课程名称 算法设计与分析 成绩评估实验项目名称 时空权衡 指导教师实验项目编号实验项目类型
6、验证实验地点 机房学生姓名 学号学院信息科学技术学院数学 系信息与计算科学 专业 级实验时间2023年3月1日6月30日温度241 .实验目的和规定：熟悉时空权衡的设计思想。2 .实验原理和重要内容：实验原理：时空权衡是运用空间换取时间的算法。实验内容：设计一个程序实现Boye r Moore算法。3 .实验结果及分析：(将程序和实验结果粘贴，程序可以注释清楚更好。)该算法程序如下：include #i.nc 1 ud e i n t table 28;in t pre 10;int max(int n, int m)if (n = m) r etur n n;el s e r eturn m
7、;i n t * shi f t t abl e (ch a r p )int m, i;char c ;m = s t rl e n( p );for (c=a； c=, z; c+)tab 1 ec-97 =m;/f or (i=0; i= 0 ) if (pi = = P n-1 ) pre k =n-l i ;break；)o i 一;)/* fo r (k= 2 ； ki=k；wh ile(pn-i ! =p0 & i =0) g i 一;。 i f ( i 0 ) j =0;vhile(pn -i =pj & i 0) gi ；。j +； if (0=i) pre k = n j;
8、0 else p r e k =n;. */for(k=2： k0； i ) oj=i;网 n=n - 1;。 while(j0 & pj- 1 =p n - 1 +m-5) j；g m；ooa if(j=O) p r ek = n - i ； b rea k ； 。0 i f (0=i) pr e k =n;0)retur n pre;)i nt b oye r_moo re (c h ar p , char t ext)int *shi, * pre, i, k, m, n, d 1, d 2 ;shi = sh i ftt a b 1 e (p);op r e = p re f i x
9、tab 1 e (p)；n = strle n (p)；本科实验报告专用纸(附页)/ c h ar p = barber )；/ / o c h ar p = baobab );/ / ch a r p = a bcba b );/int * t , i =0, *r, a;/ /t = s h ift t a bl e (p);/叩 r i n t f (input one number/);/ / sc a nf (“与d , &a);/ while(i != 2 8)/ /pri n t f (t %d poi n t t o : %dnz，, i , t i+);/ / r = pre
10、f i x table (p);/for(i= 1 ;i6； i+)/ pr i ntf(r%d = %dn”, i, ri);/ / g e t c h ();i nt i ；char p = baobab;*ch a r t e xt = b ess knew ab o u t baobabs;i = b oyer_moore(p, text)；*pr i ntf (i= %d n”, i);)运营结果如下：c *C:DocuBents and SettingsAdBinist ratorli= 16 Press any key to continue本科实验报告专用纸（附页）4.教师评语
11、、评分:本科实验报告专用纸课程名称 算法设计与分析 成绩评估实验项目名称 蛮力法 指导教师实验项目编号 实验项目类型 设计 实验地点 机房学生姓名 学号学院信息科学技术学院数学系信息与计算科学专业_组实验时间2 0 23年3月1日6月30日 温度241 .实验目的和规定：熟悉蛮力法的设计思想。2 .实验原理和重要内容：实验原理：蛮力法常直接基于问题的描述和所涉及的概念解决问题。实验内容：以下题目任选其一1) .为蛮力字符串匹配写一段可视化程序。2) .写一个程序，实现凸包问题的蛮力算法。3) .最著名的算式谜题是由大名鼎鼎的英国谜人H. E. Dudeney(1857- SEND1930)给出
12、的：+MORE .这里有两个前提假设：第一，字母和十进制 MONEY数字之间一一相应，也就是每个字母只代表一个数字，并且不同的字母 代表不同的数字；第二，数字0不出现在任何数的最左边。求解一个字 母算术意味着找到每个字母代表的是哪个数字。请注意，解也许并不是 唯一的，不同人的解也许并不相同。3 .实验结果及分析：本科实验报告专用纸课程名称 算法设计与分析 成绩评估实验项目名称 动态规划 指导教师实验项目编号实验项目类型 设计 实验地点 机房学生姓名 学号学院 信息科学技术学院数学 系信息与计算科学 专业 级实验时间 2023年3月 1日6月30日 温度241 .实验目的和规定：熟悉动态规划算法
13、的设计思想。2 .实验原理和重要内容：实验原理：动态规划算法的基本环节是：建立问题的解与其子问题的解 之间的递推关系、将子问题的解用表格记录下来（自底向上或自顶向下）， 避免子问题的反复计算、上述表格的最终状态即为（包含）最终解。实验内容：分别用动态规划算法和备忘录方法求解找零问题：给定金额n 以及各种硬币面额dld2- d m，其中dl=l,求总金额等于n的硬币 的最少个数，并输出每种硬币的找零数量。规定测试数据:硬币面额dl, d2, dm） =1,5, 1 0, 2 1 , 25,找零金额 n=2730.实验结果及分析：（将程序和实验结果粘贴，程序可以注释清楚更好。）该算法程序如下：#i
14、 n elude i n t mai n （）i nt d3, i, n;i nt ZL (int ,int);prin t f （输入4种硬币面额： n ）；for（i=0； i = 0：k )c=a/d k；4)= a - c *dk;a=b;oprintf (面值为 d的找零个数为d个n, d k,c);0)程序运营结果如下:腌入4种硬币面额: 1 2510输入要找零的金额：28面值为1。的常个数为2个 面演为5的健个数为1个面苣为2的找差个数为1个面量为1的段凄个数为1个Press any key to continue4.教师评语、评分:本科实验报告专用纸课程名称 算法设计与分析 成
15、绩评估实验项目名称 贪婪算法 指导教师实验项目编号实验项目类型 验证或设计实验地点 机房学生姓名 学号学院信息科学技术学院数学 系 信息与计算科学专业级实验时间 2 023年3月1日6月30日 温度2 4.实验目的和规定：熟悉贪婪算法的设计思想。1 .实验原理和重要内容:实验原理：贪婪法在解决问题的策略上目光短浅，只根据当前已有的信 息就做出选择，并且一旦做出了选择，不管将来有什么结果，该选择都不会 改变。换言之，贪婪法并不是从整体最优考虑，它所做出的选择只是在某种 意义上的局部最优。实验内容：以下题目任选其一1 ）.编写程序实现Prim算法。2 ）.数列极差问题：在黑板上写了 N个正整数作成
16、的一个数列，进行 如下操作：每一次擦去其中的两个数a和b,然后在数列中加入一个数 aXb+1,如此下去直至黑板上剩下一个数，在所有按这种操作方式最后 得到的数中，最大的记作ma x,最小的记作min,求该数列的极差M =max-mino运用贪婪算法编写程序实现数列极差问题。2 .实验结果及分析：（将程序和实验结果粘贴，程序可以注释清楚更好。）本科实验报告专用纸（附页）该算法程序如下:#incl u de #i n c 1 ud e void sortCint a口）/用蛮力法将数列按从小到大的顺序排列f or(i=0 ;iN-l； i +)*k=i;，fo r (j=i+ 1 ;jN； j+)
17、o i f ( a j a k) k = j ；0t=ak ; a k =ai ;a i =t：int Max (i n t a ) / /计算数列中a* b + 1的最大值 i n t i, j, t, m, n, bN；for (i=0; i N； i+)b i =ai;0fo r (j=l; jN; j +)，t=bj-l *bj+l;f or(m = j + 1 ;m=N； m+ + )(i f (t b m I | m=N)3(。 f o r ( n = j; n =0 ;i) t =t* a i +l;本科实验报告专用纸(附页)return t；)void mainO o i d
18、sort ( i n t a );i n t Max (int a )：4 n t Mi n (i n t a );in t aN, i, max, min, M；pr i n t f (请输入一个数组：n);for(i=0 ;iN; i +)scanf&a i );0 s o rt ( a );pr i n tf （排序后的数组为：n）：for (i=0;iN;i+)printf(*%d ”, a i )；p ri n tf (n );max = Max (a)；p r in t f (最大值为：% d n , max);m in=Min(a)；pri n t f (最小值为:%dn, mi
19、n);M=ma x min;printf (该数组的极差为:%d n , M) ;运营结果如下:请输入一个数组:1243258靠序后的数组为：2 5 6 8 12 43最大值为：280365最小苴为：69673该数组的极差为：210692Press any key to continue.4.教师评语、评分:(将程序和实验结果粘贴，程序可以注释清楚更好。)本科实验报告专用纸(附页)该算法程序代码如下：# i n c lude stda f x. h #inc 1 u de time, h”int main(int argc, ch a r* argv )int x100, y100；i n t
20、 a , b , c, i, j, k, L m, n=0, p, t 1 100, num；int xsa t 100,ysat100;叩ri n if (请输入点的个数：n)；sca n f (“%d”, &num)；a g et c h a r();oc 1 ock_ t st a rt, end;s tar t =clo c k();叩rintf (”请输入各点坐标：n );o f or ( 1 = 0 ; Knum; 1+) / /输入各点坐标sc a nf& x 1 , &yl);o get char ();。xsa t 0 =x 0;oys a t 0 =y 0;of o r (
21、 i=0; ) 开始进行计算fo r (j =0; j =n u m- 1 ； j+) 3i f(x j =x sati & yj =y s a t i ) 3 oc o nti n ue;必,if(xsat i=xsat0 & ys a ti = y sat0 & xj = = xsatnum & y j = jrsatn u m)(：o n tinue;a of o r(m=0； m goto s tep;。 a =yjysat i ;a b= x sat i-xj;3c = xsat i*yjysat i*xj;， f o r (k=0, 1 = 0； k=num 1 ;k+, 1+)
22、。i f (k= j I I xk= x s ati & y k=y sat i ) 。ol=l-l ;必 ocont inue;本科实验报告专用纸(附页)i f (a*xk+b*ykc)8tl 1 =-1 ；gelse8t 1 1=1；。 if( 1 != 0)。i f( t 1 1 * t 1 1 -l0)break；。if(k=num) 。i+;。nf(i=l & p!=0)g xsat n u m=x j; y s atn u m=yj;i .00op=0 ：aon-；o )。 else ax sat i=x j ;ysati=y j ;0 oMOOI1+；a b reak;00 第1
23、 s eg c o n t inue;ste p ：;0 )， i f (x s at i =xsat num & ysa t i=ysa t num)。 bre a k;。输出各点坐标叩ri n t f (nn该算法所得各点相应的坐标为八n ); f o r (in t q=0;xsat q ! =-； q+ + )p r i n t f ( (%d, %d) n , x sa t q, y sa t q);end=clo c k ();p r i n tf (n 该算法进行所需要的时间为:%f 秒n，(d o ub 1 e) (end-sta r t)/1000);*return 0 ；本
24、科实验报告专用纸(附页)运营结果如下:请输入点的个数:3输入各点坐标:2 21 34 54 26 3修算法所得各点对应的坐标为:2,2)4,2)6,3)4,5)1,3)1,3)该算法进行所需要的时间为：12.922000秒Press any key to continue4.教师评语、评分:本科实验报告专用纸课程名称 算法设计与分析 成绩评估实验项目名称 分治法 指导教师实验项目编号实验项目类型 验证或设计 实验地点 机房学生姓名 学号学院信息科学技术学院数学系 信息与计算科学 专业级实验时间202 3年3月1日6月30日 温度24.实验目的和规定：熟悉分治法的设计思想。1 .实验原理和重要内
25、容：实验原理:分治法的三个环节：分划、求解子问题、合并子问题的解。实验内容：以下题目任选其一1 ).写一个程序，实现快速排序算法。用该算法解决一批输入样本。2 ). Tromi n o谜题：Trom i n o是一个由棋盘上的三个邻接方块组 成的L形瓦片。我们的问题是,如何用Tromino覆盖一个缺少了 一个 方块(可以在棋盘上的任何位置)，的2” x2棋盘。除了这个缺失的方块,Tromin。应当覆盖棋盘上的所有方块，并且不能有重叠。为此问 题设计一个分治算法。.实验结果及分析:（将程序和实验结果粘贴，程序可以注释清楚更好。）本科实验报告专用纸（附页）该算法程序代码如下:#includ e s
26、tda fx. h void sw a p (i n t *x, i n t *y)1 nt t; t =*x; * x=*y； * y =t；)int partiti o n(in t A 1 0 0, int 1, int r)int p, i,j;P=A 1；i = l; j =r+l;dood o (a i= i +1;。b r ea k ;)w h i le(A ip);do(对二 jT;if ( j p);。sw a p(&A i , &Aj)；)w h il e (i=j 时最后一次互换 swap(&Al,&Aj);a r et u rn j;i n t q u i c ks o
27、 rt (int A 1 0 0 , int 1, in t r) (“nt s;if(Kr)s= par tition ( A, 1, r );i f ( 1 =r)8g oto end;oquick s ort (A, 1, s-1);qu i cksort(A, s + 1 , r);end:本科实验报告专用纸（附页）m = s trie n ( t e x t );i = n-1;*w h i 1 e(i=m1) k=0 ;while (ki f (k=n) re t ur n i-n+1; elseif (text i- k =, * 1 )o od l=max(s h i t ext i- k -6 -k, 1 );g e 1 seo 1 = max (shi t e xti-k -9 7 k, 1);M2 = prek;。oi f ( 0=k) i = i + dl;else i = i + max(dl, d2) ； re t u rn -1; v o i d ma i n ()