算法设计与分析实验报告.docx

《算法设计与分析实验报告.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析实验报告2016—2017学年第二学期老师：姓名：学号：班级：用分治法求解众数问题•给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。•例如，S={1,2,2,2,3,5}。多重集S的众数是2，其重数为3。•对于给定的n个自然数组成的多重集S，计算S的众数及其重数。问题分析：利用中位数将集合分成左右两部分，比较左右两侧数字个数与中位数个数的大小，在数字个数多的一侧递归，直到中位数的个数大于左右两侧数字的个数。程序代码：#include"algorithm"#include#

2、includeusingnamespacestd;voidsplit(ints[],intn,int&l,int&r){intmid=n/2;for(l=0;lmaxCnt){maxCnt=cnt;mid

3、=s[num];}if(l+1>maxCnt){getMaxCnt(mid,maxCnt,s,l+1);}if(n-r>maxCnt){getMaxCnt(mid,maxCnt,s+r,n-r);}}intmain(){ints[]={1,2,2,2,3,5};intn=sizeof(s)/sizeof(s[0]);intmaxCnt=0;intnum=0;getMaxCnt(num,maxCnt,s,n);cout<

4、符串B，这里所说的字符操作包括：①删除一个字符；②插入一个字符；③将一个字符改为另一个字符。•将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A,B)。•试设计一个有效算法，对任意两个字符串A和B，计算出它们的编辑距离d(A,B)。•以字符串A=“abc”和B=“cbcd”为例,给出动态规划算法求解过程.问题分析：状态：DP[L][R]子串a的前L个字符和子串b的前R个字符的编辑距离DP[L][R]=min(DP[L-1][R-1]+1,DP[L-1][R]+1,DP[L][R-1]+1)a中插入b[R]，则子问题为DP[L][

5、R-1]a中删除a[L],则子问题为DP[L-1][R]程序代码：#include#include#includeusingnamespacestd;#definesz2000chara[sz],b[sz];intdp[sz][sz];intmain(){while(scanf("%s%s",a,b)!=EOF){intna=strlen(a);intnb=strlen(b);memset(dp,0x3f,sizeof(dp));dp[0][0]=0;for(inti=0;i<=na;i++)for(in

6、tj=0;j<=nb;j++){dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]+(a[i]==b[j]?0:1));dp[i+1][j]=min(dp[i+1][j],dp[i][j]+1);dp[i][j+1]=min(dp[i][j+1],dp[i][j]+1);}printf("%d",dp[na][nb]);}}}运行结果：用贪心算法解决删数问题•给定n位正整数a,去掉其中任意k<=n个数字后,剩下的数字按原次序排列组成一个新的正整数.•对于给定的正整数a和正整数k,设计一个算法找出剩下数字组成的新数最小的删数方案.问

7、题分析：为了得到的数最小，将整数转换成数组，每次从高位开始，寻找降序子串的第一个数字并删除，直到删除要求的个数。每次删除，都是全局最优选择。程序代码：#include#includeintmain(){inta,n,k;inti,j,s=1;scanf("%d",&a);scanf("%d",&k);n=log10(a)+1;intp[n];j=a;for(i=n-1;i>=0;i--){p[i]=j%10;j/=10;}for(i=1;i<=k;i++){for(j=0;j

8、continue;}else{p[j]