算法设计与分析实验报告(共5页)

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

2、ude <stdio.h>#include <iostream>using namespace std;void split(int s,int n,int &l,int &r) int mid = n/2; for(l = 0; l<n; +l) if(sl = smid) break; for(r = l+1;r<n;+r) if(sr != smid) break; void getMaxCnt(int &mid,int &maxCnt, int s,int n) int l ,r; split(s,n,l,r); in

3、t num = n/2; int cnt = r - 1; if(cnt > 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 = sizeof(s)/sizeof(s0); int maxCnt = 0; int num = 0; getMaxCnt(num ,maxCnt, s, n

4、); cout<<num <<" "<<maxCnt; return 0;用动态规划算法实现下列问题： 设A和B是两个字符串。我们要用最少的字符 操作将字符串A转换为字符串B，这里所说的 字符操作包括： 删除一个字符； 插入一个字符； 将一个字符改为另一个字符。 将字符串A变换为字符串B所用的最少字符操 作数称为字符串A到B的编辑距离，记为d(A,B)。 试设计一个有效算法，对任意两个字符串A和 B，计算出它们的编辑距离d(A,B) 。 以字符串A=“abc”和B=“cbcd”为例, 给出动态规 划算法求解过程.问题分析：状态： DPLR

5、 子串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<cstdio>#include<cstring>#include<algorithm>using namespace std;#define sz 2000char asz, bsz;int dpszsz;int main() while(scanf("%s%s",a,b)!=EOF

6、) int na = strlen(a); 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, 去掉其

7、中任意k<=n个数 字后, 剩下的数字按原次序排列组成一个 新的正整数. 对于给定的正整数a和正整数k, 设计一个 算法找出剩下数字组成的新数最小的删数方案.问题分析：为了得到的数最小，将整数转换成数组，每次从高位开始，寻找降序子串的第一个数字并删除，直到删除要求的个数。每次删除，都是全局最优选择。程序代码：#include<stdio.h>#include<math.h>int 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;j<n-i;j+) if(pj<pj+1) continue; else pj=-1; break; f