资源描述:
《算法设计与分析实验报告.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;j8、continue;}else{p[j]