学生姓名： 学号： 序号 实验项目编号 实验项目名称 *实验项目类型 成绩 指导教师 1 20122229201 蛮力法 验证或设计（可选） 2 20122229202 分治算法 验证或设计（可选） 3 20122229203 减治法 验证 4 20122229204 时空权衡 验证 5 20122229205 动态规划 设计 6 20122229206 贪婪技术 验证或设计（可选） *实验项目类型：演示性、验证性、综合性、设计性实验。 *此表由学生按顺序填写。
本科实验报告专用纸
1
课程名称 算法设计与分析 成绩评定 实验项目名称 蛮力法 指导教师 实验项目编号 20122229201 实验项目类型 设计 实验地点 机房 学生姓名 学号
学院 信息科学技术学院数学 系 信息与计算科学 专业 级 实验时间 2012年 3月 1 日～6月30日 温度24℃ 1. 实验目的和要求： 熟悉蛮力法的设计思想。 2. 实验原理和主要内容：
实验原理：蛮力法常直接基于问题的描述和所涉及的概念解决问题。 实验内容：以下题目任选其一
1).为蛮力字符串匹配写一段可视化程序。 2).写一个程序，实现凸包问题的蛮力算法。
3).最著名的算式谜题是由大名鼎鼎的英国谜人
S ENDH.E.Dudeney(1857-1930)给出的：+MORE. 这里有两个前提假设：
MONEY第一，字母和十进制数字之间一一对应，也就是每个字母只代表一个数字，而且不同的字母代表不同的数字；第二，数字0不出现在任何数的最左边。求解一个字母算术意味着找到每个字母代表的是哪个数字。请注意，解可能并不是唯一的，不同人的解可能并不相同。 3. 实验结果及分析：
（将程序和实验结果粘贴，程序能够注释清楚更好。）
本科实验报告专用纸(附页)
该算法程序代码如下：
2
#include \"stdafx.h\" #include \"time.h\"
int main(int argc, char* argv[]) {
int x[100],y[100];
int a,b,c,i,j,k,l,m,n=0,p,t1[100],num; int xsat[100],ysat[100];
printf(\"请输入点的个数：\\n\"); scanf(\"%d\ getchar();
clock_t start,end; start=clock();
printf(\"请输入各点坐标:\\n\");
for(l=0;l for(i=0;;){//开始进行计算 for(j=0;j<=num-1;j++){ if(x[j]==xsat[i] && y[j]==ysat[i]){ continue; } if(xsat[i]==xsat[0] && ysat[i]==ysat[0] && y[j]==ysat[num]){ continue; } for(m=0;m<=n;m++) if(x[j]==xsat[m] && y[j]==ysat[m]) goto step; a=y[j]-ysat[i]; b=xsat[i]-x[j]; c=xsat[i]*y[j]-ysat[i]*x[j]; for(k=0,l=0;k<=num-1;k++,l++){ if(k==j || x[k]==xsat[i] && y[k]==ysat[i]){ l=l-1; continue;} x[j]==xsat[num] && 本科实验报告专用纸(附页) if(a*x[k]+b*y[k] 3 t1[l]=1; if(l!=0) if(t1[l]*t1[l-1]<0) break; } if(k==num){ i++; if(i==1 && p!=0){ xsat[num]=x[j];ysat[num]=y[j]; i--; p=0; n--; } else{ xsat[i]=x[j];ysat[i]=y[j]; } n++; break; } else continue; step:; } if(xsat[i]==xsat[num] && ysat[i]==ysat[num]) break; } //输出各点坐标 printf(\"\\n\\n该算法所得各点对应的坐标为 :\\n\"); for(int q=0;xsat[q]!=-858993460;q++) printf(\"(%d,%d)\\n\ end=clock(); printf(\"\\n该算法进行所需要的时间为：%f 秒\\n\ return 0; } 本科实验报告专用纸(附页) 运行结果如下： 4 4. 教师评语、评分： 本科实验报告专用纸 课程名称 算法设计与分析 成绩评定 实验项目名称 分治法 指导教师 实验项目编号20122229202实验项目类型 验证或设计 实验地点 机房 学生姓名 学号 5 学院 信息科学技术学院数学 系 信息与计算科学 专业 级 实验时间 2012年 3月 1 日～6月30日 温度24℃ 1. 实验目的和要求： 熟悉分治法的设计思想。 2. 实验原理和主要内容： 实验原理：分治法的三个步骤：分划、求解子问题、合并子问题的解。 实验内容：以下题目任选其一 1).写一个程序，实现快速排序算法。用该算法处理一批输入样本。 2).Tromino谜题：Tromino是一个由棋盘上的三个邻接方块组成的L形瓦片。我们的问题是，如何用Tromino覆盖一个缺少了一个方块（可以在棋盘上的任何位置），的2n2n棋盘。除了这个缺失的方块，Tromino应该覆盖棋盘上的所有方块，而且不能有重叠。为此问题设计一个分治算法。 3. 实验结果及分析： （将程序和实验结果粘贴，程序能够注释清楚更好。） 本科实验报告专用纸(附页) 该算法程序代码如下： #include \"stdafx.h\" void swap(int *x,int *y) { int t;t=*x;*x=*y;*y=t; 6 } int partition(int A[100],int l,int r) { int p,i,j; p=A[l]; i=l;j=r+1; do{ do{ i=i+1; if(i>j) break; }while(A[i] int quicksort(int A[100],int l,int r) { int s; if(l goto end; quicksort(A,l,s-1); quicksort(A,s+1,r); end: 本科实验报告专用纸(附页) return 0;} void main(int argc, char* argv[]) { int a[100],x,s,j,i; printf(\"请输入您要排序的样本：\\n\"); scanf(\"%d\ for(i=0;i } scanf(\"%d\s=partition(a,0,i-1); quicksort(a,1,s-1); quicksort(a,s+1,i-1); printf(\"排序后的结果为：\"); for(j=0;j 程序运行结果如下： 4. 教师评语、评分： 本科实验报告专用纸 课程名称 算法设计与分析 成绩评定 实验项目名称 减治法 指导教师 实验项目编号20122229203实验项目类型 验证 实验地点 机房 学生姓名 学号 学院 信息科学技术学院数学 系 信息与计算科学 专业 级 实验时间 2012年 3月 1 日～6月30日 温度24℃ 1. 实验目的和要求： 熟悉减治法的设计思想。 8 2. 实验原理和主要内容： 实验原理：减治法的三个步骤：将问题实例缩小为规模更小的实例、求解小规模实例、通过较小规模实例的解获得原问题的解。 实验内容：以下题目任选其一 1).利用深度或广度优先查找，设计一个程序，对于一个给定的图，它能够输出每一个连通分量的顶点，并且能输出图的回路，或者返回一个消息表明图是无环的。 2).设计一个程序实现两种拓扑排序算法：DFS算法和减一算法 并做一个实验来比较它们的运行时间。 3).编写程序实现选择问题，即求一个n个数列表的第k个最小元素。 3. 实验结果及分析： （将程序和实验结果粘贴，程序能够注释清楚更好。） 本科实验报告专用纸(附页) 算法程序代码如下： #include\"stdio.h\" int main() {int QSort(int [],int,int); int a[11]; int k; printf(\"请输入一个11个数的数列:\\n\"); 9 for(k=0;k<11;k++) scanf(\"%d\ QSort(a,0,10); } int QSort(int a[],int left,int right) { int i,j,temp,m=6; i=left; j=right; temp=a[left]; if(left>right) return 0; 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); //对左边的子表进行排序 else if(i else printf(\"这个数列中的第K小元素为：%d\\n\ 10 所得实验结果如下： 4. 教师评语、评分： 本科实验报告专用纸 课程名称 算法设计与分析 成绩评定 实验项目名称 时空权衡 指导教师 实验项目编号20122229204实验项目类型 验证 实验地点 机房 学生姓名 学号 学院 信息科学技术学院数学 系 信息与计算科学 专业 级 实验时间 2012年 3月 1 日～6月30日 温度24℃ 1. 实验目的和要求： 熟悉时空权衡的设计思想。 2. 实验原理和主要内容： 实验原理：时空权衡是利用空间换取时间的算法。 实验内容：设计一个程序实现Boyer-Moore算法。 3. 实验结果及分析： （将程序和实验结果粘贴，程序能够注释清楚更好。） 该算法程序如下： #include 11 #include int max(int n, int m) {if(n >= m) return n; else return m;} int * shifttable(char p[]) { int m,i; char c; m = strlen(p); for(c='a'; c<='z'; c++) table[c-97]=m; // table[' ']=100; for(i=0; i<=m-2; i++) table[p[i]-97]=m-1-i; // table['\\0'+27]=100; table[' '-6]=m; return table;} int * prefixtable(char p[]) 本科实验报告专用纸(附页) { int n, k, i,j,m; n = strlen(p); k=1; i=n-2; m=n-1; while(i>=0){ if(p[i]==p[n-1]) {pre[k]=n-1-i;break;} i--; } /* for(k=2; k<=n-1; k++){ i=k; while(p[n-i]!=p[0] && i>=0){ i--; } if(i>0){ j=0; while(p[n-i]==p[j] && i>0){ i--; j++; } if(0==i) pre[k]=n-j; } else pre[k]=n; }*/ for(k=2; k for(i=k; i>0; i--){ j=i; m=n-1; while(j>0 && p[j-1]==p[n-1+m-5]){ j--; m--; } if(j==0){ pre[k]=n-i;break;} } if(0==i) pre[k]=n; } return pre; } int boyer_moore(char p[], char text[]) { int *shi, *pre, i, k, m, n, d1, d2; shi = shifttable(p); pre = prefixtable(p); n = strlen(p); 本科实验报告专用纸(附页) m = strlen(text); i = n-1; while(i<=m-1){ k=0; while(k<=n-1 && p[n-k-1]==text[i-k]){ k++; } if(k==n) return i-n+1; else{ if(text[i-k]==' ') d1=max(shi[text[i-k]-6]-k,1); else d1 = max(shi[text[i-k]-97]-k,1); d2 = pre[k]; if(0==k) i = i + d1; else i = i + max(d1,d2);} } return -1;} void main() { // char p[]={\"barber\// char p[]={\"baobab\// char p[]={\"abcbab\// int *t,i=0,*r,a; // t = shifttable(p); // printf(\"input one number:\"); // scanf(\"%d\ 13 // while(i != 28) // printf(\"t[%d] point to : %d\\n\// r = prefixtable(p); // for(i=1;i<6;i++) // printf(\"r[%d]=%d\\n\// getch(); int i; char p[] = {\"baobab\ char text[] = {\"bess knew about baobabs\ i = boyer_moore(p, text); printf(\"i= %d\\n\} 运行结果如下： 本科实验报告专用纸(附页) 4. 教师评语、评分： 14 本科实验报告专用纸 课程名称 算法设计与分析 成绩评定 实验项目名称 动态规划 指导教师 实验项目编号20122229205实验项目类型 设计 实验地点 机房 学生姓名 学号 学院 信息科学技术学院数学 系 信息与计算科学 专业 级 实验时间 2012年 3月 1 日～6月30日 温度24℃ 1. 实验目的和要求： 熟悉动态规划算法的设计思想。 2. 实验原理和主要内容： 实验原理：动态规划算法的基本步骤是：建立问题的解与其子问题的解之间的递推关系、将子问题的解用表格记录下来（自底向上或自顶向下） ，避免子问题的重复计算、上述表格的最终状态即为（包含）最终解。 实验内容：分别用动态规划算法和备忘录方法求解找零问题：给定金额n以及各种硬币面额d1 3. 实验结果及分析： （将程序和实验结果粘贴，程序能够注释清楚更好。） 该算法程序如下： #include int d[3],i,n; int ZL(int [],int); printf(\"输入4种硬币面额：\\n\"); for(i=0;i<=3;i++) 本科实验报告专用纸(附页) {scanf(\"%d\ printf(\"输入要找零的金额：\\n\"); scanf(\"%d\ZL(d,n); } int ZL(int d[],int n) { int a,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\ } } 程序运行结果如下： 4. 教师评语、评分： 16 本科实验报告专用纸 课程名称 算法设计与分析 成绩评定 实验项目名称 贪婪算法 指导教师 实验项目编号20122229206实验项目类型 验证或设计 实验地点 机房 学生姓名 学号 学院 信息科学技术学院数学 系 信息与计算科学 专业 级 实验时间 2012年 3月 1 日～6月30日 温度24℃ 1. 实验目的和要求： 熟悉贪婪算法的设计思想。 2. 实验原理和主要内容： 实验原理：贪婪法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，该选择都不会改变。换言之，贪婪法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。 实验内容：以下题目任选其一 1).编写程序实现Prim算法。 2). 数列极差问题：在黑板上写了N个正整数作成的一个数列，进行如下操作：每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式 17 最后得到的数中，最大的记作max，最小的记作min，求该数列的极差M=max-min。利用贪婪算法编写程序实现数列极差问题。 3. 实验结果及分析：（将程序和实验结果粘贴，程序能够注释清楚更好。） 本科实验报告专用纸(附页) 该算法程序如下： #include void sort(int a[])//用蛮力法将数列按从小到大的顺序排列 { int i,j,k,t; for(i=0;i for(j=i+1;j int Max(int a[])//计算数列中a*b+1的最大值 { int i,j,t,m,n,b[N]; for(i=0;i if(t return b[N-1]; } int Min(int a[])//计算数列中a*b+1的最小值 { int i,t; t=a[N-2]; for(i=N-2;i>=0;i--) {t=t*a[i]+1;} 本科实验报告专用纸(附页) return t;} void main() { oid sort(int a[]); int Max(int a[]); int Min(int a[]); int a[N],i,max,min,M; printf(\"请输入一个数组:\\n\"); for(i=0;i printf(\"最小值为: %d\\n\ M=max-min; printf(\"该数组的极差为:%d\\n\ 运行结果如下： 4. 教师评语、评分： 19 因篇幅问题不能全部显示，请点此查看更多更全内容