算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告(共5頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告20162017學(xué)年第二學(xué)期老師： 姓名： 學(xué)號： 班級： 用分治法求解眾數(shù)問題 給定含有n個元素的多重集合S，每個元 素在S中出現(xiàn)的次數(shù)稱為該元素的重?cái)?shù)。 多重集S中重?cái)?shù)最大的元素稱為眾數(shù)。 例如，S=1,2,2,2,3,5。多重集S的眾數(shù) 是2，其重?cái)?shù)為3。 對于給定的n個自然數(shù)組成的多重集S， 計(jì)算S的眾數(shù)及其重?cái)?shù) 。問題分析：利用中位數(shù)將集合分成左右兩部分，比較左右兩側(cè)數(shù)字個數(shù)與中位數(shù)個數(shù)的大小，在數(shù)字個數(shù)多的一側(cè)遞歸，直到中位數(shù)的個數(shù)大于左右兩側(cè)數(shù)字的個數(shù)。程序代碼：#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;用動態(tài)規(guī)劃算法實(shí)現(xiàn)下列問題： 設(shè)A和B是兩個字符串。我們要用最少的字符 操作將字符串A轉(zhuǎn)換為字符串B，這里所說的 字符操作包括： 刪除一個字符； 插入一個字符； 將一個字符改為另一個字符。 將字符串A變換為字符串B所用的最少字符操 作數(shù)稱為字符串A到B的編輯距離，記為d(A,B)。 試設(shè)計(jì)一個有效算法，對任意兩個字符串A和 B，計(jì)算出它們的編輯距離d(A,B) 。 以字符串A=“abc”和B=“cbcd”為例, 給出動態(tài)規(guī) 劃算法求解過程.問題分析：狀態(tài)： DPLR

5、 子串a(chǎn)的前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); 運(yùn)行結(jié)果：用貪心算法解決刪數(shù)問題 給定n位正整數(shù)a, 去掉其

7、中任意k<=n個數(shù) 字后, 剩下的數(shù)字按原次序排列組成一個 新的正整數(shù). 對于給定的正整數(shù)a和正整數(shù)k, 設(shè)計(jì)一個 算法找出剩下數(shù)字組成的新數(shù)最小的刪數(shù)方案.問題分析：為了得到的數(shù)最小，將整數(shù)轉(zhuǎn)換成數(shù)組，每次從高位開始，尋找降序子串的第一個數(shù)字并刪除，直到刪除要求的個數(shù)。每次刪除，都是全局最優(yōu)選擇。程序代碼：#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