算法設(shè)計(jì)實(shí)驗(yàn)題目匯總

1、ACM算法設(shè)計(jì)實(shí)驗(yàn)題目匯總1020 Permutation with Repetition11021 雙色Hanoi塔問(wèn)題 31022 Search Number41023 整數(shù)劃分問(wèn)題51024 Counting61025 輸油管道問(wèn)題81026 Integer Factorization91027 郵局選址問(wèn)題111031 矩陣連乘問(wèn)題131032 最長(zhǎng)公共子序列141033 MAX SUM161034 Number Triangles171035 編輯距離問(wèn)題 181036 Pebble Merging 191037 租用游艇問(wèn)題 211038 Minimal m Sums 221040

2、 Knapsack Problem 241041最優(yōu)裝載 251042 Lecture Halls 261043 程序存儲(chǔ)問(wèn)題 291048 Optimal Services 301049 汽車(chē)加油問(wèn)題 301059子集樹(shù)問(wèn)題 3210600-1 Knapsack 331061排列樹(shù)問(wèn)題 361062 Problem DGeneral Search 381020 Permutation with RepetitionDescription R= r1,r2, ,rn 是要進(jìn)行排列的n 個(gè)元素。其中元素r1,r2, ,rn可能相同。試設(shè)計(jì)一個(gè)算法，列出R的所有不同排列。 編程任務(wù)：給定n 以及待

3、排列的n 個(gè)元素。計(jì)算出這n 個(gè)元素的所有不同排列。Input 輸入由多組測(cè)試數(shù)據(jù)組成。每組測(cè)試數(shù)據(jù)的第1 行是元素個(gè)數(shù)n，1 = n = 500。接下來(lái)的1 行是待排列的n 個(gè)元素。 Output 對(duì)應(yīng)每組輸入，將計(jì)算出的n 個(gè)元素的所有不同排列輸出，每種排列單獨(dú)一行。最后1 行中的數(shù)是排列總數(shù)。Sample Input 4aaccSample Output aaccacacacca caac caca ccaa 6 #include #include using namespace std ;int ans ;int ok(char str,int a ,int b ) if( b a)

4、for(int i = a ; i b ; i+) if( stri = strb ) return 0 ; return 1 ;void perm(char str,int k ,int m) int i ; if( k = m ) ans + ; for( i = 0 ;i = m ;i+ ) printf(%c,stri ) ; printf(n) ; else for( i = k ; i = m ;i+) if( ok(str,k,i) ) swap ( strk,stri ); perm(str, k+1 , m ); swap(strk,stri ) ; int main(int

5、 argc, char* argv) char str1000; int n ; while( scanf(%d,&n) != EOF ) ans = 0 ; scanf(%s,str ) ; perm(str,0,n-1) ; printf(%dn,ans ); return 0;1021 雙色Hanoi塔問(wèn)題Description A、B、C 是3個(gè)塔座。開(kāi)始時(shí)，在塔座A 上有一疊共n 個(gè)圓盤(pán)，這些圓盤(pán)自下而上， 由大到小地疊在一起。各圓盤(pán)從小到大編號(hào)為1，2，n，奇數(shù)號(hào)圓盤(pán)著藍(lán)色，偶數(shù)號(hào)圓盤(pán)著紅色，如圖所示?，F(xiàn)要求將塔座A 上的這一疊圓盤(pán)移到塔座B 上，并仍按同樣順序疊置。在移動(dòng)圓盤(pán)時(shí)應(yīng)

6、遵守以下移動(dòng)規(guī)則： 規(guī)則(1)：每次只能移動(dòng)1個(gè)圓盤(pán)； 規(guī)則(2)：任何時(shí)刻都不允許將較大的圓盤(pán)壓在較小的圓盤(pán)之上； 規(guī)則(3)：任何時(shí)刻都不允許將同色圓盤(pán)疊在一起； 規(guī)則(4)：在滿足移動(dòng)規(guī)則(1)-(3)的前提下，可將圓盤(pán)移至A，B，C 中任一塔座上。 試設(shè)計(jì)一個(gè)算法，用最少的移動(dòng)次數(shù)將塔座A 上的n個(gè)圓盤(pán)移到塔座B 上，并仍按同樣順序疊置。編程任務(wù)：對(duì)于給定的正整數(shù)n，編程計(jì)算最優(yōu)移動(dòng)方案。Input 輸入由多組測(cè)試數(shù)據(jù)組成。每組測(cè)試數(shù)據(jù)的第1 行是給定的正整數(shù)n。Output 對(duì)應(yīng)每組輸入，輸出的每一行由一個(gè)正整數(shù)k和2 個(gè)字符c1 和c2 組成，表示將第k 個(gè)圓盤(pán)從塔座c1 移到塔座

7、c2 上。Sample Input 3Sample Output 1 A B 2 A C 1 B C 3 A B 1 C A 2 C B 1 A B #include using namespace std;int main() void hanoi(int,char,char,char); int m; cin m;hanoi(m,A,B,C); return 0; void hanoi(int n,char a,char b,char c) void move(int,char,char); if(n=1) move(n,a,b); else hanoi(n-1,a,c,b); move(

8、n,a,b); hanoi(n-1,c,b,a); void move(int n ,char x,char y) cout n x y endl;1022 Search NumberDescription 科研調(diào)查時(shí)得到了n個(gè)自然數(shù)，每個(gè)數(shù)均不超過(guò)1500000000。已知不相同的數(shù)不超過(guò)10000個(gè)，現(xiàn)在需要在其中查找某個(gè)自然數(shù)，如找到則輸出并統(tǒng)計(jì)這個(gè)自然數(shù)出現(xiàn)的次數(shù)，如沒(méi)找到則輸出NO。Input 輸入由多組測(cè)試數(shù)據(jù)組成。 每組測(cè)試數(shù)據(jù)輸入包含n+1行； 第一行是兩個(gè)整數(shù)n和x，n表示自然數(shù)的個(gè)數(shù),x表示要查找的自然數(shù)，兩者之間用空格隔開(kāi)； 第2至n+1每行一個(gè)自然數(shù)。Output 對(duì)應(yīng)

9、每組輸入，如果查找到x，則每行輸出兩個(gè)整數(shù)，分別是自然數(shù)和該數(shù)出現(xiàn)的次數(shù)，其間用一個(gè)空格隔開(kāi)；如果沒(méi)有查找到x，則每行輸出NO.Sample Input 8 1002424510021008 3242451002100Sample Output 100 2NO#include #include #define LEN 200000 int aLEN,temp,mid; int sort(int *a,int low,int high) /一趟快排 mid=alow; while (lowhigh) while (low=mid) high-; temp=alow;alow=ahigh;ahig

10、h=temp; while (lowhigh & ahigh=mid) low+; temp=alow;alow=ahigh;ahigh=temp; return low; void quicksort(int *a,int low,int high) /快排遞歸 /int mid; if (low high) mid=sort(a,low,high); quicksort(a,low,mid-1); quicksort(a,mid+1,high); int main() int i,n,s;int Sum=0;scanf(%d,&n); scanf(%d,&s); for (i=0;in;i

11、+) scanf(%d,&ai); quicksort(a,0,n-1); /調(diào)用快排 for (i=0;in;i+) /統(tǒng)計(jì)不同數(shù)字的個(gè)數(shù) if(ai=s)Sum+;if(Sum=0)printf(NO);else printf(%d %d,s,Sum);1023 整數(shù)劃分問(wèn)題Description 將正整數(shù)n表示成一系列正整數(shù)之和：n=n1+n2+nk，其中n1n2nk1，k1。 正整數(shù)n的這種表示稱(chēng)為正整數(shù)n的劃分。求正整數(shù)n的不同劃分個(gè)數(shù)。例如正整數(shù)6有如下11種不同的劃分： 6； 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1

12、+1+1+1； 1+1+1+1+1+1。Input 輸入包含n+1行； 第一行是一個(gè)整數(shù)n，表示有n個(gè)測(cè)試用例； 第2至n+1每行一個(gè)正整數(shù)。 Output 對(duì)應(yīng)每組輸入，輸出正整數(shù)n的不同劃分個(gè)數(shù)。 Sample Input 256Sample Output 711#include int split(int n, int m) if(n 1 | m 1) return 0; if(n = 1 | m = 1) return 1; if(n m) return (split(n, m - 1) + split(n - m), m); int main() int k,i; int a100;

13、 scanf(%d,&k); for(i=0;ik;i+) scanf(%d,&ai); for(i=0;ik;i+) printf(%dn,split(ai,ai); 1024 Problem A:CountingDescription 問(wèn)題描述：一本書(shū)的頁(yè)碼從自然數(shù)1開(kāi)始順序編碼直到自然數(shù)n。書(shū)的頁(yè)碼按照通常的習(xí)慣編排，每個(gè)頁(yè)碼都不含多余的前導(dǎo)數(shù)字0。例如，第6 頁(yè)用數(shù)字6 表示，而不是06 或006等。數(shù)字計(jì)數(shù)問(wèn)題要求對(duì)給定書(shū)的總頁(yè)碼n，計(jì)算出書(shū)的全部頁(yè)碼中分別用到多少次數(shù)字0，1，2，9。編程任務(wù)：給定表示書(shū)的總頁(yè)碼的10進(jìn)制整數(shù)n (1n109) 。編程計(jì)算書(shū)的全部頁(yè)碼中分別用到多少

14、次數(shù)字0，1，2，9。Input 輸入由多組測(cè)試數(shù)據(jù)組成。每組測(cè)試數(shù)據(jù)輸入只有1行，給出表示書(shū)的總頁(yè)碼的整數(shù)n。Output 對(duì)應(yīng)每組輸入，輸出共有10行，在第k行輸出頁(yè)碼中用到數(shù)字k-1的次數(shù)，k=1，2，10。Sample Input 11Sample Output 1411111111程序代碼：#include void statNum(long int sn10, int n) int i, c, k, s, pown; for( i = 0; i 0; k+, n /=10, pown *=10) c = n%10; for(i=0; i 10; i+) sni += c*k*(po

15、wn/10); for(i=0; i n; statNum(sn, n); for(i=0; i 10; i+) cout sniendl; return 0; 1025 Problem B:輸油管道問(wèn)題Description 問(wèn)題描述：某石油公司計(jì)劃建造一條由東向西的主輸油管道。該管道要穿過(guò)一個(gè)有n口油井的油田。從每口油井都要有一條輸油管道沿最短路經(jīng)(或南或北)與主管道相連。如果給定n口油井的位置,即它們的x 坐標(biāo)（東西向）和y坐標(biāo)（南北向）,應(yīng)如何確定主管道的最優(yōu)位置,即使各油井到主管道之間的輸油管道長(zhǎng)度總和最小的位置?編程任務(wù)：給定n口油井的位置,編程計(jì)算各油井到主管道之間的輸油管道最小

16、長(zhǎng)度總和。Input 輸入由多組測(cè)試數(shù)據(jù)組成。每組測(cè)試數(shù)據(jù)輸入的第1行是油井?dāng)?shù)n，1n10000。接下來(lái)n 行是油井的位置，每行2個(gè)整數(shù)x和y，-10000x，y10000。Output 對(duì)應(yīng)每組輸入，輸出的第1行中的數(shù)是油井到主管道之間的輸油管道最小長(zhǎng)度總和。Sample Input 51 22 21 33 -23 3Sample Output 6#includeusing std:cout;using std:endl;using std:cin;int sPath(int*,int,int);int aSize=0;int main()/freopen(input.txt,r,stdin

17、);/freopen(output.txt,w,stdout);cinaSize;int *x=new intaSize;int *y=new intaSize;for(int i=0;ixi;cinyi;int p=0;p=sPath(y,0,aSize-1);coutp;return 0;int sPath(int a,int x,int y)int f,b,total=0;if(x=y)/計(jì)算該點(diǎn)到其他點(diǎn)的距離for(int i=0;iaSize;i+)total+=abs(ax-ai);return total;/分兩部分計(jì)算各自的最優(yōu)值f=sPath(a,x,(x+y)/2);b=s

18、Path(a,(x+y)/2+1,y);return fb?f:b;/歸并操作，返回這兩部分中更優(yōu)解1026 Problem C:Integer FactorizationDescription 問(wèn)題描述：大于1 的正整數(shù)n可以分解為：n=X1*X2*Xm。例如，當(dāng)n=12 時(shí)，共有8 種不同的分解式：12=12；12=6*2；12=4*3；12=3*4；12=3*2*2；12=2*6；12=2*3*2；12=2*2*3。編程任務(wù)：對(duì)于給定的正整數(shù)n，編程計(jì)算n共有多少種不同的分解式。Input 輸入由多組測(cè)試數(shù)據(jù)組成。每組測(cè)試數(shù)據(jù)輸入第一行有1 個(gè)正整數(shù)n(1n2000000000)。Out

19、put 對(duì)應(yīng)每組輸入，輸出計(jì)算出的不同的分解式數(shù)。Sample Input 12Sample Output 8#include #include struct DP int num; int sum; d50000=0; int max=0; void qsort(int low,int high,struct DP key) int i=low,j=high; struct DP tag=keyi; if(ij) do while(tag.numkeyj.num & ij) j-; if(i=keyi.num & ij) i+; if(ij) keyj=keyi; j-; while(ij)

20、; keyi=tag; qsort(low,j-1,key); qsort(i+1,high,key); int dfs(int left) int i,p; int l,r,m; int count=0; l=0; r=max; while(l1; if(dm.numleft) l=m+1; else r=m-1; p=l; if(dp.sum) return dp.sum; for(i=1;i=di.num;i+) if(left%di.num=0) count+=dfs(left/di.num); dp.sum=count; return count; int main(void) in

21、t i,j,tmp; int n; scanf(%d,&n); tmp=sqrt(n); for(i=1;i=tmp;i+) if(n%i=0) dmax.num=i; max+; dmax.num=n/i; max+; max-; qsort(0,max,d); d0.sum=1; printf(%dn,dfs(n); return 0; 1027 Problem D:郵局選址問(wèn)題Description 問(wèn)題描述：在一個(gè)按照東西和南北方向劃分成規(guī)整街區(qū)的城市里，n個(gè)居民點(diǎn)散亂地分布在不同的街區(qū)中。用x坐標(biāo)表示東西向，用y坐標(biāo)表示南北向。各居民點(diǎn)的位置可以由坐標(biāo)(x,y)表示。街區(qū)中任意2點(diǎn)(

22、x1,y1)和(x2,y2)之間的距離可以用數(shù)值|x1-x2|+|y1-y2|度量。居民們希望在城市中選擇建立郵局的最佳位置，使n個(gè)居民點(diǎn)到郵局的距離總和最小。編程任務(wù)：給定n 個(gè)居民點(diǎn)的位置,編程計(jì)算n 個(gè)居民點(diǎn)到郵局的距離總和的最小值。Input 輸入由多組測(cè)試數(shù)據(jù)組成。每組測(cè)試數(shù)據(jù)輸入的第1行是居民點(diǎn)數(shù)n，1n10000。接下來(lái)n 行是居民點(diǎn)的位置，每行2 個(gè)整數(shù)x 和y，-10000x，y10000。Output 對(duì)應(yīng)每組輸入，輸出的第1 行中的數(shù)是n個(gè)居民點(diǎn)到郵局的距離總和的最小值。Sample Input 51 22 21 33 -23 3Sample Output 10#incl

23、udeusing namespace std;void QuickSort(int arry,int l,int h);int main() int i,j,n,l,h,x,y,a,b;int sum1=0,sum2=0;cin n;l=0;h=n-1;int arry100002;int *x1=new intn;int *y1=new intn; for(i=0;in;i+)for(j=0;j2;j+)scanf(%d,&arryij);for(i=0;in;i+)x1i=arryi0;y1i=arryi1; QuickSort( x1,l, h);QuickSort( y1,l, h);

24、x=x1(n -1)/2;y=y1(n -1)/2;for(i=0;in;i+)a=arryi0-x;if(arryi0-x)0)a=x-arryi0;b=arryi1-y;if(arryi1-y)0)b=y-arryi1;sum1+=a;sum2+=b;coutsum1+sum2endl;return 0;void QuickSort(int arry,int l,int h)int i=l, j=h; /低LOW ，高HIGHint temp = arryl; /取第一個(gè)做標(biāo)準(zhǔn)數(shù)據(jù)元書(shū)的while(ij)while(ij & temp =arryj)j-;/右端掃描if(ij)arryi=

25、arryj;i+;while(ij & arryi temp)i+;if(ij)arryj=arryi;j-;arryi=temp;if(li)QuickSort( arry, l,i-1);if(ih)QuickSort( arry, j+1,h);1031 Problem A:矩陣連乘問(wèn)題Description 給定n個(gè)矩陣A1,A2,An，其中Ai與Ai+1是可乘的，i=1,2 ,n-1。如何確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少。 Input 輸入包含多組測(cè)試數(shù)據(jù)。第一行為一個(gè)整數(shù)C，表示有C組測(cè)試數(shù)據(jù)，接下來(lái)有2*C行數(shù)據(jù)，每組測(cè)試數(shù)據(jù)占2行，每組

26、測(cè)試數(shù)據(jù)第一行是1個(gè)整數(shù)n，表示有n個(gè)矩陣連乘,接下來(lái)一行有n+1個(gè)數(shù),表示是n個(gè)矩陣的行及第n個(gè)矩陣的列,它們之間用空格隔開(kāi). Output 你的輸出應(yīng)該有C行，即每組測(cè)試數(shù)據(jù)的輸出占一行，它是計(jì)算出的矩陣最少連乘積次數(shù).Sample Input 1310 100 5 50Sample Output 7500#include int main() int p101,i,j,k,r,t,n; int m101101; /為了跟講解時(shí)保持一致數(shù)組從1開(kāi)始 int s101101; /記錄從第i到第j個(gè)矩陣連乘的斷開(kāi)位置 scanf(%d,&n); for(i=0;i=n;i+) scanf(%d

27、,&pi); /讀入pi的值(注意：p0到pn共n+1項(xiàng)) for(i=1;i=n;i+) /初始化mii=0 mii=0; for(r=1;rn;r+) /r為i、j相差的值 for(i=1;in;i+) /i為行 j=i+r; /j為列 mij=mi+1j+pi-1*pi*pj; /給mij賦初值 sij=i; for(k=i+1;kj;k+) t=mik+mk+1j+pi-1*pk*pj; if(tmij) mij=t; /mij取最小值 sij=k; printf(%d,m1n); 1032 Problem C:最長(zhǎng)公共子序列Description 一個(gè)給定序列的子序列是在該序列中刪去

28、若干元素后得到的序列。給定兩個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱(chēng)Z是序列X和Y的公共子序列。例如，若X=A，B，C，B，D，B，A，Y=B，D，C，A，B，A，則序列B，C，A是X和Y的一個(gè)公共子序列，但它不是X和Y的一個(gè)最長(zhǎng)公共子序列。序列B，C，B，A也是X和Y的一個(gè)公共子序列，它的長(zhǎng)度為4，而且它是X和Y的一個(gè)最長(zhǎng)公共子序列，因?yàn)閄和Y沒(méi)有長(zhǎng)度大于4的公共子序列。 最長(zhǎng)公共子序列問(wèn)題就是給定兩個(gè)序列X=x1,x2,.xm和Y=y1,y2,.yn，找出X和Y的一個(gè)最長(zhǎng)公共子序列。 Input 輸入包含多組測(cè)試數(shù)據(jù)。第一行為一個(gè)整數(shù)C，表示有C組測(cè)試數(shù)據(jù)，接下來(lái)有C行

29、數(shù)據(jù)，每組測(cè)試數(shù)據(jù)占1行，它由2個(gè)給定序列的字符串組成，兩個(gè)字符串之間用空格隔開(kāi). Output 你的輸出應(yīng)該有C行，即每組測(cè)試數(shù)據(jù)的輸出占一行，它是計(jì)算出的最長(zhǎng)公共子序列長(zhǎng)度。Sample Input 1ABCBDBA BDCABASample Output 4#include #include #include void prt_lcs(int, int, char , int*);int main(int argc, char* argv) char x100, y100; int i, j, m, n, * a, * b; gets(x); gets(y); m = strlen(x)

30、 + 1; n = strlen(y) + 1; if (a = (int*)malloc(m * sizeof(int*) = NULL) | (b = (int*) malloc(m * sizeof(int*) = NULL) printf(There is no enough memory!n); exit(1); for (i = 0; i m; i +) if (ai = (int*)malloc(n * sizeof(int) = NULL) | (bi = (int*)malloc(n * sizeof(int) = NULL) printf(There is no enoug

31、h memory!n); exit(2); for (i = 0; i m; i +) ai0 = 0; for (i = 0; i n; i +) a0i = 0; for (i = 1; i m; i +) for (j = 1; j = aij - 1) aij = ai - 1j; bij = 2; else aij = aij - 1; bij = 3; printf(%dn, am - 1n - 1); prt_lcs(m - 1, n - 1, x, b); printf(n); for (i = 0; i m; i +) free(ai); free(bi); free(a);

32、 free(b); return 0;void prt_lcs(int i, int j, char x, int* b) if (i 0 | j 0) return; if (bij = 1) prt_lcs(i - 1, j - 1, x, b); printf(%c, xi - 1); else if (bij = 2) prt_lcs(i - 1, j, x, b); else prt_lcs(i, j - 1, x, b);1033 Problem B:MAX SUMDescription 給定由n整數(shù)(可能為負(fù)數(shù))組成的序列 a1,a2,an，求該序列形如ai+ai+1,+aj的子

33、段和的最大值。當(dāng)所有的整數(shù)均為負(fù)數(shù)時(shí)定義其最大子段和為0。 Input 輸入包含多組測(cè)試數(shù)據(jù)。第一行為一個(gè)整數(shù)C，表示有C組測(cè)試數(shù)據(jù)，接下來(lái)有2*C行數(shù)據(jù)，每組測(cè)試數(shù)據(jù)占2行，每組測(cè)試數(shù)據(jù)第一行是1個(gè)整數(shù)n，表示有n個(gè)整數(shù),接下來(lái)一行有n個(gè)整數(shù),它們之間用空格隔開(kāi). Output 你的輸出應(yīng)該有C行，即每組測(cè)試數(shù)據(jù)的輸出占一行，它是計(jì)算出的最大子段和.Sample Input 16-2 11 -4 13 -5 -2Sample Output 20#include int maxsum(int n,int *a) int sum=0,b=0,i,j; for(i=1;i0) b+=ai; els

34、e b=ai; if(bsum) sum=b; return sum;main() int m; scanf(%d,&m); while(m-) int a100,i,max,n; scanf(%d,&n); for(i=1;i=n;i+) scanf(%d,&ai); max=maxsum(n,a); printf(%dn,max); 1034 Problem D:Number TrianglesDescription 給定一個(gè)由n行數(shù)字組成的數(shù)字三角形如下圖所示。試設(shè)計(jì)一個(gè)算法，計(jì)算出從三角形的頂至底的一條路徑，使該路徑經(jīng)過(guò)的數(shù)字總和最大。 編程任務(wù)：對(duì)于給定的由n 行數(shù)字組成的數(shù)字三角形

35、，編程計(jì)算從三角形的頂至底的路徑經(jīng)過(guò)的數(shù)字和的最大值。Input 輸入數(shù)據(jù)是由多組測(cè)試數(shù)據(jù)組成。第1 行是數(shù)字三角形的行數(shù)n，1n100。接下來(lái)n行是數(shù)字三角形各行中的數(shù)字。所有數(shù)字在0至99之間。Output 對(duì)應(yīng)每組測(cè)試數(shù)據(jù)，每行輸出的是計(jì)算出的最大值。Sample Input 573 88 1 02 7 4 44 5 2 6 5Sample Output 30#include int main()int inta102102;int i , j ;int n ;/ freopen(in.txt,r,stdin ) ;while(scanf(%d,&n) != EOF ) for(i =

36、1 ; i = n ; i + ) for( j =1 ;j 0 ; i - ) for( j = i ; j 0 ; j - ) intaij += intai+1j+1 intai+1j ? intai+1j+1 : intai+1j; printf(%dn,inta11 ) ;return 0 ;1035 編輯距離問(wèn)題Description 設(shè)A 和B 是2 個(gè)字符串。要用最少的字符操作將字符串A 轉(zhuǎn)換為字符串B。這里所說(shuō)的字符操作包括 (1)刪除一個(gè)字符； (2)插入一個(gè)字符； (3)將一個(gè)字符改為另一個(gè)字符。 將字符串A變換為字符串B 所用的最少字符操作數(shù)稱(chēng)為字符串A到B 的編輯距離

37、，記為d(A,B)。試設(shè)計(jì)一個(gè)有效算法，對(duì)任給的2 個(gè)字符串A和B，計(jì)算出它們的編輯距離d(A,B)。 編程任務(wù)： 對(duì)于給定的字符串A和字符串B，編程計(jì)算其編輯距離d(A,B)。Input 輸入由多組測(cè)試數(shù)據(jù)組成。 每組測(cè)試數(shù)據(jù)輸入的第1 行是字符串A，第2行是字符串B。Output 對(duì)應(yīng)每組輸入，輸出的每行中的數(shù)是編輯距離d(A,B)。Sample Input fxpimuxwrsSample Output 5#include #include using namespace std;int main() string A1, A2; cin A1 A2; int m = A1.length

38、(); int n = A2.length(); int *d = new int n + 1; int i ; for( i = 1; i = n; i+) di = i; for( i = 1; i = m; i+) int y = i - 1; for(int j = 1; j 1 ? dj - 1:i; int del = A1i - 1 = A2j - 1 ? 0:1; dj = x + del; if (dj y + 1) dj = y + 1; if (dj z + 1) dj = z + 1; cout dn endl; return 0;1036 Pebble Merging

39、Description 在一個(gè)圓形操場(chǎng)的四周擺放著n 堆石子?，F(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的2 堆石子合并成新的一堆，并將新的一堆石子數(shù)記為該次合并的得分。試設(shè)計(jì)一個(gè)算法，計(jì)算出將n堆石子合并成一堆的最小得分和最大得分。 編程任務(wù)： 對(duì)于給定n堆石子,編程計(jì)算合并成一堆的最小得分和最大得分。Input 輸入由多組測(cè)試數(shù)據(jù)組成。 每組測(cè)試數(shù)據(jù)輸入的第1 行是正整數(shù)n，1n100，表示有n堆石子。第二行有n個(gè)數(shù)，分別表示每堆石子的個(gè)數(shù)。Output 對(duì)應(yīng)每組輸入，輸出的第1 行中的數(shù)是最小得分；第2 行中的數(shù)是最大得分。Sample Input 44 4 5 9Sample O

40、utput Hint 43 54#include#includeint n;int a101,s101101,t101101;int i,j,k,temp,max,min;int main() while(scanf(%d,&n)!=-1) i=1; while(i=n) scanf(%d,&ai+); memset(t,0,sizeof(t); for(i=1;i=n;i+) for(j=1;j=n;j+) for(k=i;kn) temp=k%n; else temp=k; tij+=atemp; memset(s,0,sizeof(s); for(j=2;j=n;j+) for(i=1;

41、i=n;i+) for(k=1;kn) temp=(i+k)%n; else temp=i+k; max=sik+stempj-k+tij; if(sijmax) sij=max; max=0; for(i=1;i=n;i+) if(maxsin) max=sin; memset(s,0,sizeof(s); for(j=2;j=n;j+) for(i=1;i=n;i+) min=9999999; for(k=1;kn) temp=(i+k)%n; else temp=i+k; sij=sik+stempj-k+tij; if(minsij) min=sij; sij=min; min=9999999; for(i=1;isin) min=sin; printf(%dn,min);