《算法设计与分析》实验报告.docx
- 文档编号:15843025
- 上传时间:2023-07-08
- 格式:DOCX
- 页数:14
- 大小:35.42KB
《算法设计与分析》实验报告.docx
《《算法设计与分析》实验报告.docx》由会员分享,可在线阅读,更多相关《《算法设计与分析》实验报告.docx(14页珍藏版)》请在冰点文库上搜索。
《算法设计与分析》实验报告
算法设计与分析课程实验项目目录
学生姓名:
学号:
序号
实验项目编号
实验项目名称
*实验项目类型
成绩
指导教师
1
201
蛮力法
验证或设计(可选)
2
202
分治算法
验证或设计(可选)
3
203
减治法
验证
4
204
时空权衡
验证
5
205
动态规划
设计
6
206
贪婪技术
验证或设计(可选)
*实验项目类型:
演示性、验证性、综合性、设计性实验。
*此表由学生按顺序填写。
本科实验报告专用纸
课程名称算法设计与分析成绩评定
实验项目名称蛮力法指导教师
实验项目编号201实验项目类型设计实验地点机房
学生姓名学号
学院信息科学技术学院数学系信息与计算科学专业级
实验时间2012年3月1日~6月30日温度24℃
1.实验目的和要求:
熟悉蛮力法的设计思想。
2.实验原理和主要内容:
实验原理:
蛮力法常直接基于问题的描述和所涉及的概念解决问题。
实验内容:
以下题目任选其一
1).为蛮力字符串匹配写一段可视化程序。
2).写一个程序,实现凸包问题的蛮力算法。
3).最著名的算式谜题是由大名鼎鼎的英国谜人给出的:
.这里有两个前提假设:
第一,字母和十进制数字之间一一对应,也就是每个字母只代表一个数字,而且不同的字母代表不同的数字;第二,数字0不出现在任何数的最左边。
求解一个字母算术意味着找到每个字母代表的是哪个数字。
请注意,解可能并不是唯一的,不同人的解可能并不相同。
3.实验结果及分析:
(将程序和实验结果粘贴,程序能够注释清楚更好。
)
本科实验报告专用纸(附页)
该算法程序代码如下:
#include""
#include""
intmain(intargc,char*argv[])
{
intx[100],y[100];
inta,b,c,i,j,k,l,m,n=0,p,t1[100],num;
intxsat[100],ysat[100];
printf("请输入点的个数:
\n");
scanf("%d",&num);
getchar();
clock_tstart,end;
start=clock();
printf("请输入各点坐标:
\n");
for(l=0;l 24℃一个程序,实现快速排序算法。 用该算法处理一批输入样本。 2).Tromino谜题: Tromino是一个由棋盘上的三个邻接方块组成的L形瓦片。 我们的问题是,如何用Tromino覆盖一个缺少了一个方块(可以在棋盘上的任何位置),的 棋盘。 除了这个缺失的方块,Tromino应该覆盖棋盘上的所有方块,而且不能有重叠。 为此问题设计一个分治算法。 1.实验结果及分析: (将程序和实验结果粘贴,程序能够注释清楚更好。 ) 本科实验报告专用纸(附页) 该算法程序代码如下: #include"" voidswap(int*x,int*y) { intt;t=*x;*x=*y;*y=t; } intpartition(intA[100],intl,intr) { intp,i,j; p=A[l]; i=l;j=r+1; do{ do{ i=i+1; if(i>j) break; }while(A[i] do{ j=j-1; if(j break; }while(A[j]>p); swap(&A[i],&A[j]); }while(i swap(&A[i],&A[j]); 24℃用深度或广度优先查找,设计一个程序,对于一个给定的图,它能够输出每一个连通分量的顶点,并且能输出图的回路,或者返回一个消息表明图是无环的。 2).设计一个程序实现两种拓扑排序算法: DFS算法和减一算法并做一个实验来比较它们的运行时间。 3).编写程序实现选择问题,即求一个n个数列表的第k个最小元素。 1.实验结果及分析: (将程序和实验结果粘贴,程序能够注释清楚更好。 ) 本科实验报告专用纸(附页) 算法程序代码如下: #include"" intmain() {intQSort(int[],int,int); inta[11]; intk; printf("请输入一个11个数的数列: \n"); for(k=0;k<11;k++) scanf("%d",&a[k]); QSort(a,0,10); } intQSort(inta[],intleft,intright) {inti,j,temp,m=6; i=left; j=right; temp=a[left]; if(left>right) return0; while(i! =j) {while(a[j]>=temp&&j>i) j--; if(j>i) a[i++]=a[j]; while(a[i]<=temp&&j>i)i++; 本科实验报告专用纸(附页) if(j>i) a[j--]=a[i];} a[i]=temp; if(i>m) QSort(a,left,i-1); 24℃ 24℃求总金额等于n的硬币的最少个数,并输出每种硬币的找零数量。 要求测试数据: 硬币面额{d1,d2,…,dm}={1,5,10,21,25},找零金额n=273。 1.实验结果及分析: (将程序和实验结果粘贴,程序能够注释清楚更好。 ) 该算法程序如下: #include<> intmain() { intd[3],i,n; intZL(int[],int); printf("输入4种硬币面额: \n"); for(i=0;i<=3;i++) 本科实验报告专用纸(附页) {scanf("%d",&d[i]);} printf("输入要找零的金额: \n"); scanf("%d",&n); ZL(d,n); } intZL(intd[],intn) { inta,b,c,k; a=n; for(k=3;k>=0;k--) { c=a/d[k]; b=a-c*d[k]; a=b; printf("面值为%d的找零个数为%d个\n",d[k],c); } } 程序运行结果如下: 2.教师评语、评分: 本科实验报告专用纸 课程名称算法设计与分析成绩评定 实验项目名称贪婪算法指导教师 实验项目编号206实验项目类型验证或设计实验地点机房 学生姓名学号 学院信息科学技术学院数学系信息与计算科学专业级 实验时间2012年3月1日~6月30日温度24℃ 1.实验目的和要求: 熟悉贪婪算法的设计思想。 2.实验原理和主要内容: 实验原理: 贪婪法在解决问题的策略上目光短浅,只根据当前已有的信息就做出选择,而且一旦做出了选择,不管将来有什么结果,该选择都不会改变。 换言之,贪婪法并不是从整体最优考虑,它所做出的选择只是在某种意义上的局部最优。 实验内容: 以下题目任选其一 1).编写程序实现Prim算法。 2).数列极差问题: 在黑板上写了N个正整数作成的一个数列,进行如下操作: 每一次擦去其中的两个数a和b,然后在数列中加入一个数a×b+1,如此下去直至黑板上剩下一个数,在所有按这种操作方式最后得到的数中,最大的记作max,最小的记作min,求该数列的极差M=max-min。 利用贪婪算法编写程序实现数列极差问题。 3.实验结果及分析: (将程序和实验结果粘贴,程序能够注释清楚更好。 ) 本科实验报告专用纸(附页) 该算法程序如下: #include<> #include<> #defineN6 voidsort(inta[])//用蛮力法将数列按从小到大的顺序排列 { inti,j,k,t;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法设计与分析 算法 设计 分析 实验 报告