算法设计与分析课程实验项目目录学生：学号：*实验项目类型：演示性、验证性、综合性、设计性实验。

*此表由学生按顺序填写。

本科实验报告专用纸课程名称算法设计与分析成绩评定实验项目名称蛮力法指导教师实验项目编号实验项目类型设计实验地点机房学生学号学院信息科学技术学院数学系信息与计算科学专业级实验时间2012年3月1 日～6月30日温度24℃1.实验目的和要求：熟悉蛮力法的设计思想。

2.实验原理和主要容：实验原理：蛮力法常直接基于问题的描述和所涉及的概念解决问题。

实验容：以下题目任选其一1).为蛮力字符串匹配写一段可视化程序。

2).写一个程序，实现凸包问题的蛮力算法。

3).最著名的算式谜题是由大名鼎鼎的英国谜人H.E.Dudeney(1857-1930)给出的： S END+MOREMONEY. 这里有两个前提假设：第一，字母和十进制数字之间一一对应，也就是每个字母只代表一个数字，而且不同的字母代表不同的数字；第二，数字0不出现在任何数的最左边。

求解一个字母算术意味着找到每个字母代表的是哪个数字。

请注意，解可能并不是唯一的，不同人的解可能并不相同。

3.实验结果及分析：（将程序和实验结果粘贴，程序能够注释清楚更好。

）该算法程序代码如下：#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",&num);getchar();clock_t start,end;start=clock();printf("请输入各点坐标:\n");for(l=0;l<num;l++){//输入各点坐标scanf("%d%d",&x[l],&y[l]);getchar();}xsat[0]=x[0];ysat[0]=y[0];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] && x[j]==xsat[num] && 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;}if(a*x[k]+b*y[k]<c)t1[l]=-1;elset1[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;}elsecontinue;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",xsat[q],ysat[q]);end=clock();printf("\n该算法进行所需要的时间为：%f 秒\n",(double)(end-start)/1000);return 0;}本科实验报告专用纸(附页)运行结果如下：4.教师评语、评分：本科实验报告专用纸课程名称算法设计与分析成绩评定实验项目名称分治法指导教师实验项目编号实验项目类型验证或设计实验地点机房学生学号学院信息科学技术学院数学系信息与计算科学专业级实验时间2012年3月1 日～6月30日温度24℃1.实验目的和要求：熟悉分治法的设计思想。

2.实验原理和主要容：实验原理：分治法的三个步骤：分划、求解子问题、合并子问题的解。

实验容：以下题目任选其一1).写一个程序，实现快速排序算法。

用该算法处理一批输入样本。

2).Tromino谜题：Tromino是一个由棋盘上的三个邻接方块组成的L形瓦片。

我们的问题是，如何用Tromino覆盖一个缺少了一个方块（可以在棋盘上的任何位置），的22n n棋盘。

除了这个缺失的方块，Tromino应该覆盖棋盘上的所有方块，而且不能有重叠。

为此问题设计一个分治算法。

3.实验结果及分析：（将程序和实验结果粘贴，程序能够注释清楚更好。

）该算法程序代码如下：#include "stdafx.h"void swap(int *x,int *y){int t;t=*x;*x=*y;*y=t;}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]<p);do{j=j-1;if(j<i)break;}while(A[j]>p);swap(&A[i],&A[j]);}while(i<j);swap(&A[i],&A[j]);//撤销i>=j时最后一次交换swap(&A[l],&A[j]);return j;}int quicksort(int A[100],int l,int r){int s;if(l<r)s=partition(A,l,r);if(l>=r)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",&x);for(i=0;i<x;i++)scanf("%d",&a[i]);s=partition(a,0,i-1);quicksort(a,1,s-1);quicksort(a,s+1,i-1);printf("排序后的结果为：");for(j=0;j<x;j++)printf("%d ",a[j]);}程序运行结果如下：4.教师评语、评分：本科实验报告专用纸课程名称算法设计与分析成绩评定实验项目名称减治法指导教师实验项目编号实验项目类型验证实验地点机房学生学号学院信息科学技术学院数学系信息与计算科学专业级实验时间2012年3月1 日～6月30日温度24℃1.实验目的和要求：熟悉减治法的设计思想。

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");for(k=0;k<11;k++)scanf("%d",&a[k]);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<m)QSort(a,i+1,right); //对右边的子表进行排序else printf("这个数列中的第K小元素为：%d\n",a[i]); }所得实验结果如下：4.教师评语、评分：本科实验报告专用纸课程名称算法设计与分析成绩评定实验项目名称时空权衡指导教师实验项目编号实验项目类型验证实验地点机房学生学号学院信息科学技术学院数学系信息与计算科学专业级实验时间2012年3月1 日～6月30日温度24℃1.实验目的和要求：熟悉时空权衡的设计思想。

2.实验原理和主要容：实验原理：时空权衡是利用空间换取时间的算法。

实验容：设计一个程序实现Boyer-Moore算法。

3.实验结果及分析：（将程序和实验结果粘贴，程序能够注释清楚更好。

）该算法程序如下：#include <stdio.h>#include <string.h>int table[28];int pre[10];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<n; 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);elsed1 = 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", &a);// while(i != 28)// printf("t[%d] point to : %d\n", i, t[i++]);// r = prefixtable(p);// for(i=1;i<6;i++)// printf("r[%d]=%d\n", i, r[i]);// getch();int i;char p[] = {"baobab"};char text[] = {"bess knew about baobabs"};i = boyer_moore(p, text);printf("i= %d\n", i);}运行结果如下：本科实验报告专用纸(附页) 4.教师评语、评分：本科实验报告专用纸课程名称算法设计与分析成绩评定实验项目名称动态规划指导教师实验项目编号实验项目类型设计实验地点机房学生学号学院信息科学技术学院数学系信息与计算科学专业级实验时间2012年3月1 日～6月30日温度24℃1.实验目的和要求：熟悉动态规划算法的设计思想。