计算机算法计与分析.doc

《计算机算法计与分析.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、<<计算机算法设计与分析>>课程报告一.分治法问题陈述:对所给元素存储于数组中和存储于链表中两中情况，写出自然合并排序算法.解题思路:将待排序元素分成大小大相同的两个集合,分别对两个集合进行排序,最终将排好序的子集合合并成为所要求的排好序的集合.自然排序是通过一次扫描待排元素中自然排好序的子数组,再进行子数组的合并排序.程序代码:#includeconstintN=100;voidScanTarget(inttarget[],intn,inthead[],inttail[

2、]);intCountHead(inthead[]);voidMergeSort(inta[],inthead[],inttail[],intm);voidMergePass(intx[],inty[],ints,inta[],intb[],intm);voidMerge(intc[],intd[],intl,intm,intr);voidmain(){chara;do{inttarget[N],head[N],tail[N];inti=0,n,m;for(;i

3、1;tail[i]=-1;}cout<<"请输入要排序的总数:"<>n;cout<<"请输入要排序的数列:"<>target[i];ScanTarget(target,n,head,tail);m=CountHead(head);MergeSort(target,head,tail,m);cout<<"排序后:"<

4、t<<"是否继续(y/n):"<>a;}while(a!='n'&&a!='N');}voidScanTarget(inttarget[],intn,inthead[],inttail[])//扫描待排数组；{inti,j=0,k=0;head[k]=0;k++;for(i=1;itarget[i]){tail[j++]=i-1;head[k++]=i;}}tail[j]=n-1;}intCountHead(inthead[])/

5、/求长度；{inti(0);while(head[i]!=-1){i++;}returni;}voidMergeSort(inta[],inthead[],inttail[],intm){intb[N];ints=1;while(s

6、while(i<=m-2*s){Merge(x,y,a[i],b[i+s-1],b[i+2*s-1]);i=i+2*s;}if(i+s

7、{if(c[i]<=c[j])d[k++]=c[i++];elsed[k++]=c[j++];}if(i>m){for(intq=j;q<=r;q++)d[k++]=c[q];}else{for(intq=i;q<=m;q++)d[k++]=c[q];}}时间复杂度:通常情况下用自然合并排序所需要的合并次数较少。例如，对于所给的n元素数组已排好序的极端情况，自然合并排序算法不需要执行合并步，而合并排序算法需要执行n的指数次合并。因此，在这种情况下，自然合并排序算法需要O（n）时间，而合并排序算法

8、需要O（n*log(n)）,所以自然合并排序在一般情况下较更优。运行结果:二.动态规划问题陈述:设A和B是2个字符串.要用最少的字符操作将字符串A转换为字符串B.这里所说的字符操作包括:(1)删除一个字符;(2)插入一个字符;(3)将一个字符x改为另一个字符y.将字符串A变换为字符串B所言的最少字符操作数称为字符串A到B的编辑距离,记为d(A,B).试设计一个有效算法,对任给的2个字符串A和B,计算出它们的编辑距离d(A,B).解题思路:计算两个字符串A+x,B+y的编辑距离有这样的性质:1.