《算法设计与分析》实验报告

算法设计与分析课程实验项目目录学生：学号：序号实验项目编号实验项目名称*实验项目类型成绩指导教师1蛮力法验证或设计(可选)2分治算法验证或设计(可选)减治法验证4时空权衡验证5动态规划设计6贪婪技术验证或设计(可选)*实验项目类型：演示性、验证性、综合性、设计性实验。*此表由学生按顺序填写。本科实验报告专用纸课程名称算法设计与分析成绩评定实验项目名称蛮力法指导教师实验项目编号实验项目类型设计实验地点机房学生学号学院信息科学技术学院数学系信息与计算科学专业级实验时间2012年3月1日~6月30日温度24C1.实验目的和要求：2.实验原理和主要容：实验容：以下题目任选其一3).最著名的算式谜题是由大名鼎鼎的英国谜人H.E.Dudeney(1857-1930)给出的：+MORE.这里有两个前提假设： MONEY第一，字母和十进制数字之间一一对应，也就是每个字母只代表一个数字，而且不同的字母代表不同的数字；第二，数字0不出现在任何数的最左边。求解一个字母算术意味着找到每个字母代表的是哪个数3.实验结果及分析： 报告专用纸(附页)#include"stdafx.h"#include"time.h"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];scanf("%d",&num);getchar();clock_tstart,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]y[j]==ysat[num]){continue;}for(m=0;m<=n;m++)if(x[j]==xsat[m]&&ysat[i]==ysat[0]&&x[j]==xsat[num]&&&&y[j]==ysat[m])gotostep;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;t1[l]=1;flif(t1[l]*t1[l-1]<0)break;}if(k==num){if(i==1&&p!=0){xsat[num]=x[j];ysat[num]=y[j];p=0;}sexsat[i]=x[j];ysat[i]=y[j];}n++;break;}continue;p}if(xsat[i]==xsat[num]&&ysat[i]==ysat[num])break;}//输出各点坐标printf("\n\n该算法所得各点对应的坐标为:\n");for(intq=0;xsat[q]!=-858993460;q++)printf("(%d,%d)\n",xsat[q],ysat[q]);end=clock();printfnfndoubleendstart0);return0;}本科实验报告专用纸(附页)4.教师评语、评分：本科实验报告专用纸课程名称算法设计与分析成绩评定实验项目名称分治法指导教师实验项目编号实验项目类型验证或设计实验地点机房学生学号学院信息科学技术学院数学系信息与计算科学专业级实验时间2012年3月1日~6月30日温度24C1.实验目的和要求：2.实验原理和主要容：实验容：以下题目任选其一3.实验结果及分析： 报告专用纸(附页)#include"stdafx.h"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;break;}while(A[i]<p);j=j-1;break;}while(A[j]>p);swap(&A[i],&A[j]);}while(i<j);swap(&A[l],&A[j]);returnj;}intquicksort(intA[100],intl,intr){tss=partition(A,l,r);lrgotoend;quicksort(A,l,s-1);quicksort(A,s+1,r);本科实验报告专用纸(附页)return0;}voidmain(intargc,char*argv[]){inta[100],x,s,j,i;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);for(j=0;j<x;j++)printf("%d",a[j]);}4.教师评语、评分：本科实验报告专用纸课程名称算法设计与分析成绩评定 实验项目名称减治法指导教师 实验项目编号实验项目类型验证实验地点机房学生学号学院信息科学技术学院数学系信息与计算科学专业级 实验时间2012年3月1日~6月30日温度24C1.实验目的和要求：2.实验原理和主要容：实验原理：减治法的三个步骤：将问题实例缩小为规模更小的实例、求实验容：以下题目任选其一1).利用深度或广度优先查找，设计一个程序，对于一个给定的图，它能够输出每一个连通分量的顶点，并且能输出图的回路，或者返回一两种拓扑排序算法：DFS算法和减一算法并做k3.实验结果及分析： 报告专用纸(附页)#include"stdio.h"intmain(){intQSort(int[],int,int);inta[11];for(k=0;k<11;k++)scanf("%d",&a[k]);QSort(a,0,10);}intQSort(inta[],intleft,intright)inti,j,temp,m=6;j=right;temp=a[left];if(left>right)return0;while(i!=j){while(a[j]>=temp&&j>i)if(j>i)a[i++]=a[j];while(a[i]<=temp&&j>i)i++;本科实验报告专用纸a[j--]=a[i];}a[i]=temp;QSort(a,left,i-1);//对左边的子表进行排序elseif(i<m)QSort(a,i+1,right);//对右边的子表进行排序4.教师评语、评分：本科实验报告专用纸课程名称算法设计与分析成绩评定实验项目名称时空权衡指导教师实验项目编号实验项目类型验证实验地点机房学生学号学院信息科学技术学院数学系信息与计算科学专业级 1.实验目的和要求：2.实验原理和主要容：3.实验结果及分析： #include<stdio.h>#include<string.h>inttable[28];intpre[10];intmax(intn,intm){if(n>=m)returnn;elsereturnm;}int*shifttable(charp[]){icharc;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;returntable;}int*prefixtable(charp[])报告专用纸(附页){intn,k,i,j,m;n=strlen(p);k=1;m=n-1;while(i>=0){if(p[i]==p[n-1]){pre[k]=n-1-i;break;}}/*for(k=2;k<=n-1;k++){while(p[n-i]!=p[0]&&i>=0){}fiwhile(p[n-i]==p[j]&&i>0){}if(0==i)pre[k]=n-j;}elsepre[k]=n;for(k=2;k<n;k++){for(i=k;i>0;i--){m=n-1;while(j>0&&p[j-1]==p[n-1+m-5]){}if(j==0){pre[k]=n-i;break;}}if(0==i)pre[k]=n;}returnpre;}intboyer_moore(charp[],chartext[]){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)returni-n+1;seif(text[i-k]=='')d1=max(shi[text[i-k]-6]-k,1);d1=max(shi[text[i-k]-97]-k,1);d2=pre[k];if(0==k)i=i+d1;elsei=i+max(d1,d2);}}return-1;}voidmain(){//charp[]={"barber"};//charp[]={"baobab"};//charp[]={"abcbab"};//int*t,i=0,*r,a;//t=shifttable(p);//printf("inputonenumber:");//scanf("%d",&a);//while(i!=28)//printf("t[%d]pointto:%d\n",i,t[i++]);//r=prefixtable(p);//for(i=1;i<6;i++)//printf("r[%d]=%d\n",i,r[i]);//getch();inti;charp[]={"baobab"};chartext[]={"bessknewaboutbaobabs"};i=boyer_moore(p,text);printf("i=%d\n",i);}本科实验报告专用纸(附页)4.教师评语、评分：本科实验报告专用纸课程名称算法设计与分析成绩评定实验项目名称动态规划指导教师实验项目编号实验项目类型设计实验地点机房学生学号学院信息科学技术学院数学系信息与计算科学专业级 1.实验目的和要求：2.实验原理和主要容：避免子问题的重复计算、上述表格的最终状态即为(包含)最终解。实验容：分别用动态规划算法和备忘录方法求解找零问题：给定金额n最少个数，并输出每种硬币的找零数量。要求测试数据：硬币面额3.实验结果及分析： #include<stdio.h>intmain(){intd[3],i,n;intZL(int[],int);for(i=0;i<=3;i++)本科实验报告专用纸(附页){scanf("%d",&d[i]);}scanf("%d",&n);ZL(d,n);}intZL(intd[],intn){inta,b,c,k;an;for(k=3;k>=0;k--){c=a/d[k];b=a-c*d[k];ab;}}4.教师评语、评分：本科实验报告专用纸 课程名称算法设计与分析成绩评定 实验项目名称贪婪算法指导教师 实验项目编号实验项目类型验证或设计实验地点机房#include<stdio.h>学生学号学院信息科学技术学院数学系信息与计算科学专业级 1.实验目的和要求：2.实验原理和主要容：息就做出选择，而且一旦做出了选择，不管将来有什么结果，该选择都不会改变。换言之，贪婪法并不是从整体最优考虑，它所做出的选择只是在实验容：以下题目任选其一2).数列极差问题：在黑板上