《算法设计与分析实验报告(共5页)》由会员分享，可在线阅读，更多相关《算法设计与分析实验报告(共5页)（5页珍藏版）》请在金锄头文库上搜索。
1、精选优质文档-倾情为你奉上算法设计与分析实验报告20162017学年第二学期老师： 姓名： 学号： 班级： 用分治法求解众数问题 给定含有n个元素的多重集合S，每个元 素在S中出现的次数称为该元素的重数。 多重集S中重数最大的元素称为众数。 例如，S=1,2,2,2,3,5。多重集S的众数 是2，其重数为3。 对于给定的n个自然数组成的多重集S， 计算S的众数及其重数 。问题分析：利用中位数将集合分成左右两部分，比较左右两侧数字个数与中位数个数的大小，在数字个数多的一侧递归，直到中位数的个数大于左右两侧数字的个数。程序代码：#include algorithm#include #include
2、 using namespace std;void split(int s,int n,int &l,int &r) int mid = n/2; for(l = 0; ln; +l) if(sl = smid) break; for(r = l+1;r maxCnt) maxCnt = cnt; mid = snum; if(l+1 maxCnt) getMaxCnt(mid, maxCnt, s, l+1); if(n-r maxCnt) getMaxCnt(mid, maxCnt, s+r, n-r); int main() int s = 1,2,2,2,3,5; int n = si
3、zeof(s)/sizeof(s0); int maxCnt = 0; int num = 0; getMaxCnt(num ,maxCnt, s, n); coutnum maxCnt; return 0;用动态规划算法实现下列问题： 设A和B是两个字符串。我们要用最少的字符 操作将字符串A转换为字符串B，这里所说的 字符操作包括： 删除一个字符； 插入一个字符； 将一个字符改为另一个字符。 将字符串A变换为字符串B所用的最少字符操 作数称为字符串A到B的编辑距离，记为d(A,B)。 试设计一个有效算法，对任意两个字符串A和 B，计算出它们的编辑距离d(A,B) 。 以字符串A=“abc”和
4、B=“cbcd”为例, 给出动态规 划算法求解过程.问题分析：状态： DPLR 子串a的前L个字符和子串b的前R个字符的编辑距离 DPLR = min (DPL-1R-1 + 1, DPL-1R + 1, DPLR-1 + 1) a中插入bR，则子问题为 DPLR-1 a中删除aL, 则子问题为 DPL-1R程序代码：#include#include#includeusing namespace std;#define sz 2000char asz, bsz;int dpszsz;int main() while(scanf(%s%s,a,b)!=EOF) int na = strlen(a
5、); int nb = strlen(b); memset(dp,0x3f,sizeof(dp); dp00 = 0; for(int i=0;i=na;i+) for(int j=0;j=nb;j+) dpi+1j+1 = min(dpi+1j+1, dpij + (ai=bj?0:1); dpi+1j = min(dpi+1j, dpij + 1); dpij+1 = min(dpij+1, dpij + 1); printf(%dn,dpnanb); 运行结果：用贪心算法解决删数问题 给定n位正整数a, 去掉其中任意k=n个数 字后, 剩下的数字按原次序排列组成一个 新的正整数. 对于给
6、定的正整数a和正整数k, 设计一个 算法找出剩下数字组成的新数最小的删数方案.问题分析：为了得到的数最小，将整数转换成数组，每次从高位开始，寻找降序子串的第一个数字并删除，直到删除要求的个数。每次删除，都是全局最优选择。程序代码：#include#includeint main() int a,n,k; int i,j,s=1; scanf(%d,&a); scanf(%d,&k); n=log10(a)+1; int pn; j=a; for(i=n-1;i=0;i-) pi=j%10; j/=10; for(i=1;i=k;i+) for(j=0;jn-i;j+) if(pjpj+1) continue; else pj=-1; break; for(j=0;jn-i;j+) if(pj=-1) pj=pj+1; pj+1=-1; for(i=0;in-k;i+) printf(%d,pi); return 0;运行结果：专心-专注-专业
