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

PAGEPAGE41ACM算法設(shè)計(jì)實(shí)驗(yàn)題目匯總1020PermutationwithRepetition11021雙色Hanoi塔問題31022SearchNumber41023整數(shù)劃分問題51024Counting61025輸油管道問題81026IntegerFactorization91027郵局選址問題111031矩陣連乘問題131032最長公共子序列141033MAXSUM161034NumberTriangles171035編輯距離問題181036PebbleMerging191037租用游艇問題211038MinimalmSums221040KnapsackProblem241041最優(yōu)裝載251042LectureHalls261043程序存儲(chǔ)問題291048OptimalServices301049汽車加油問題301059子集樹問題3210600-1Knapsack331061排列樹問題361062ProblemDGeneralSearch381020PermutationwithRepetitionDescriptionR={r1,r2,…,rn}是要進(jìn)行排列的n個(gè)元素。其中元素r1,r2,…,rn可能相同。試設(shè)計(jì)一個(gè)算法，列出R的所有不同排列。

編程任務(wù)：給定n以及待排列的n個(gè)元素。計(jì)算出這n個(gè)元素的所有不同排列。Input輸入由多組測試數(shù)據(jù)組成。每組測試數(shù)據(jù)的第1行是元素個(gè)數(shù)n，1<=n<=500。接下來的1行是待排列的n個(gè)元素。Output對應(yīng)每組輸入，將計(jì)算出的n個(gè)元素的所有不同排列輸出，每種排列單獨(dú)一行。最后1行中的數(shù)是排列總數(shù)。SampleInput4aaccSampleOutputaaccacacaccacaaccacaccaa6#include<stdio.h>#include<algorithm>usingnamespacestd;intans;intok(charstr[],inta,intb){if(b>a)for(inti=a;i<b;i++)if(str[i]==str[b])return0;return1;}voidperm(charstr[],intk,intm){inti;if(k==m){ans++;for(i=0;i<=m;i++){printf("%c",str[i]);}printf("\n");}else{for(i=k;i<=m;i++)if(ok(str,k,i)){swap(str[k],str[i]);perm(str,k+1,m);swap(str[k],str[i]);}}}intmain(intargc,char*argv[]){charstr[1000];intn;while(scanf("%d",&n)!=EOF){ans=0;scanf("%s",str);perm(str,0,n-1);printf("%d\n",ans);}return0;}1021雙色Hanoi塔問題DescriptionA、B、C是3個(gè)塔座。開始時(shí)，在塔座A上有一疊共n個(gè)圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號(hào)為1，2，……，n，奇數(shù)號(hào)圓盤著藍(lán)色，偶數(shù)號(hào)圓盤著紅色，如圖所示?，F(xiàn)要求將塔座A上的這一疊圓盤移到塔座B上，并仍按同樣順序疊置。在移動(dòng)圓盤時(shí)應(yīng)遵守以下移動(dòng)規(guī)則：

規(guī)則(1)：每次只能移動(dòng)1個(gè)圓盤；

規(guī)則(2)：任何時(shí)刻都不允許將較大的圓盤壓在較小的圓盤之上；

規(guī)則(3)：任何時(shí)刻都不允許將同色圓盤疊在一起；

規(guī)則(4)：在滿足移動(dòng)規(guī)則(1)-(3)的前提下，可將圓盤移至A，B，C中任一塔座上。

試設(shè)計(jì)一個(gè)算法，用最少的移動(dòng)次數(shù)將塔座A上的n個(gè)圓盤移到塔座B上，并仍按同樣順序疊置。

編程任務(wù)：對于給定的正整數(shù)n，編程計(jì)算最優(yōu)移動(dòng)方案。Input輸入由多組測試數(shù)據(jù)組成。每組測試數(shù)據(jù)的第1行是給定的正整數(shù)n。Output對應(yīng)每組輸入，輸出的每一行由一個(gè)正整數(shù)k和2個(gè)字符c1和c2組成，表示將第k個(gè)圓盤從塔座c1移到塔座c2上。SampleInput3SampleOutput1AB2AC1BC3AB1CA2CB1AB#include<iostream>usingnamespacestd;intmain(){voidhanoi(int,char,char,char);intm;cin>>m;hanoi(m,'A','B','C');return0;}voidhanoi(intn,chara,charb,charc){voidmove(int,char,char);if(n==1)move(n,a,b);else{hanoi(n-1,a,c,b);move(n,a,b);hanoi(n-1,c,b,a);}}voidmove(intn,charx,chary){cout<<n<<""<<x<<""<<y<<endl;}1022SearchNumberDescription科研調(diào)查時(shí)得到了n個(gè)自然數(shù)，每個(gè)數(shù)均不超過1500000000。已知不相同的數(shù)不超過10000個(gè)，現(xiàn)在需要在其中查找某個(gè)自然數(shù)，如找到則輸出并統(tǒng)計(jì)這個(gè)自然數(shù)出現(xiàn)的次數(shù)，如沒找到則輸出NO。Input輸入由多組測試數(shù)據(jù)組成。

每組測試數(shù)據(jù)輸入包含n+1行；

第一行是兩個(gè)整數(shù)n和x，n表示自然數(shù)的個(gè)數(shù),x表示要查找的自然數(shù)，兩者之間用空格隔開；

第2至n+1每行一個(gè)自然數(shù)。Output對應(yīng)每組輸入，如果查找到x，則每行輸出兩個(gè)整數(shù)，分別是自然數(shù)和該數(shù)出現(xiàn)的次數(shù)，其間用一個(gè)空格隔開；如果沒有查找到x，則每行輸出NO.SampleInput810024245100210083242451002100SampleOutput1002NO#include<stdio.h>#include<string.h>#defineLEN200000inta[LEN],temp,mid;intsort(int*a,intlow,inthigh)//一趟快排{mid=a[low];while(low<high){while(low<high&&a[high]>=mid)high--;temp=a[low];a[low]=a[high];a[high]=temp;while(low<high&&a[high]<=mid)low++;temp=a[low];a[low]=a[high];a[high]=temp;}returnlow;}voidquicksort(int*a,intlow,inthigh)//快排遞歸{//intmid;if(low<high){mid=sort(a,low,high);quicksort(a,low,mid-1);quicksort(a,mid+1,high);}}intmain(){inti,n,s;intSum=0;scanf("%d",&n);scanf("%d",&s);for(i=0;i<n;i++){scanf("%d",&a[i]);}quicksort(a,0,n-1);//調(diào)用快排for(i=0;i<n;i++)//統(tǒng)計(jì)不同數(shù)字的個(gè)數(shù){ if(a[i]==s) { Sum++; } }if(Sum==0){ printf("NO");}else{printf("%d%d",s,Sum);}}1023整數(shù)劃分問題Description將正整數(shù)n表示成一系列正整數(shù)之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。

正整數(shù)n的這種表示稱為正整數(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+1+1+1；

1+1+1+1+1+1。Input輸入包含n+1行；

第一行是一個(gè)整數(shù)n，表示有n個(gè)測試用例；

第2至n+1每行一個(gè)正整數(shù)。Output對應(yīng)每組輸入，輸出正整數(shù)n的不同劃分個(gè)數(shù)。SampleInput256SampleOutput711#include<stdio.h>intsplit(intn,intm){if(n<1||m<1)return0;if(n==1||m==1)return1;if(n<m)returnsplit(n,n);if(n==m)return(split(n,m-1)+1);if(n>m)return(split(n,m-1)+split((n-m),m));}intmain(){intk,i;inta[100];scanf("%d",&k);for(i=0;i<k;i++){scanf("%d",&a[i]);}for(i=0;i<k;i++){printf("%d\n",split(a[i],a[i]));}}1024ProblemA:CountingDescription問題描述：

一本書的頁碼從自然數(shù)1開始順序編碼直到自然數(shù)n。書的頁碼按照通常的習(xí)慣編排，每個(gè)頁碼都不含多余的前導(dǎo)數(shù)字0。例如，第6頁用數(shù)字6表示，而不是06或006等。數(shù)字計(jì)數(shù)問題要求對給定書的總頁碼n，計(jì)算出書的全部頁碼中分別用到多少次數(shù)字0，1，2，…，9。

編程任務(wù)：給定表示書的總頁碼的10進(jìn)制整數(shù)n(1≤n≤109)。編程計(jì)算書的全部頁碼中分別用到多少次數(shù)字0，1，2，…，9。Input輸入由多組測試數(shù)據(jù)組成。

每組測試數(shù)據(jù)輸入只有1行，給出表示書的總頁碼的整數(shù)n。Output對應(yīng)每組輸入，輸出共有10行，在第k行輸出頁碼中用到數(shù)字k-1的次數(shù)，k=1，2，…，10。SampleInput11SampleOutput1411111111程序代碼：#include<iostream.h>voidstatNum(longintsn[10],intn){inti,c,k,s,pown;for(i=0;i<10;i++)sn[i]=0;for(k=s=0,pown=1;n>0;k++,n/=10,pown*=10){c=n%10;for(i=0;i<10;i++)sn[i]+=c*k*(pown/10);for(i=0;i<c;i++)sn[i]+=pown;sn[c]+=1+s;sn[0]-=pown;s+=c*pown;}}intmain(){inti,n;longintsn[10];cin>>n;statNum(sn,n);for(i=0;i<10;i++)cout<<sn[i]<<endl;return0;}1025ProblemB:輸油管道問題Description問題描述：

某石油公司計(jì)劃建造一條由東向西的主輸油管道。該管道要穿過一個(gè)有n口油井的油田。從每口油井都要有一條輸油管道沿最短路經(jīng)(或南或北)與主管道相連。如果給定n口油井的位置,即它們的x坐標(biāo)（東西向）和y坐標(biāo)（南北向）,應(yīng)如何確定主管道的最優(yōu)位置,即使各油井到主管道之間的輸油管道長度總和最小的位置?

編程任務(wù)：

給定n口油井的位置,編程計(jì)算各油井到主管道之間的輸油管道最小長度總和。Input輸入由多組測試數(shù)據(jù)組成。

每組測試數(shù)據(jù)輸入的第1行是油井?dāng)?shù)n，1≤n≤10000。接下來n行是油井的位置，每行2個(gè)整數(shù)x和y，-10000≤x，y≤10000。Output對應(yīng)每組輸入，輸出的第1行中的數(shù)是油井到主管道之間的輸油管道最小長度總和。SampleInput51222133-233SampleOutput6#include<iostream>usingstd::cout;usingstd::endl;usingstd::cin;intsPath(int*,int,int);intaSize=0;intmain(){// freopen("input.txt","r",stdin);// freopen("output.txt","w",stdout); cin>>aSize; int*x=newint[aSize]; int*y=newint[aSize]; for(inti=0;i<aSize;i++){ cin>>x[i]; cin>>y[i]; } intp=0; p=sPath(y,0,aSize-1); cout<<p; return0;}intsPath(inta[],intx,inty){ intf,b,total=0; if(x==y){//計(jì)算該點(diǎn)到其他點(diǎn)的距離 for(inti=0;i<aSize;i++) total+=abs(a[x]-a[i]); returntotal; } //分兩部分計(jì)算各自的最優(yōu)值 f=sPath(a,x,(x+y)/2); b=sPath(a,(x+y)/2+1,y); returnf<b?f:b;//歸并操作，返回這兩部分中更優(yōu)解}1026ProblemC:IntegerFactorizationDescription問題描述：

大于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ù)：對于給定的正整數(shù)n，編程計(jì)算n共有多少種不同的分解式。Input輸入由多組測試數(shù)據(jù)組成。每組測試數(shù)據(jù)輸入第一行有1個(gè)正整數(shù)n(1≤n≤2000000000)。Output對應(yīng)每組輸入，輸出計(jì)算出的不同的分解式數(shù)。SampleInput12SampleOutput8#include<stdio.h>

#include<math.h>

structDP

{

intnum;

intsum;

}d[50000]={0};

intmax=0;

voidqsort(intlow,inthigh,structDPkey[])

{

inti=low,j=high;

structDPtag=key[i];

if(i<j)

{

do

{

while(tag.num<key[j].num&&i<j)j--;

if(i<j)

{

key[i]=key[j];

i++;

while(tag.num>=key[i].num&&i<j)i++;

if(i<j)

{

key[j]=key[i];

j--;

}

}

}while(i<j);

key[i]=tag;

qsort(low,j-1,key);

qsort(i+1,high,key);

}

}

intdfs(intleft)

{

inti,p;

intl,r,m;

intcount=0;

l=0;r=max;

while(l<=r)

{

m=(l+r)>>1;

if(d[m].num<left)l=m+1;elser=m-1;

}

p=l;if(d[p].sum)returnd[p].sum;

for(i=1;i<=d[i].num;i++)

{

if(left%d[i].num==0)count+=dfs(left/d[i].num);

}

d[p].sum=count;

returncount;

}

intmain(void)

{

inti,j,tmp;

intn;

scanf("%d",&n);tmp=sqrt(n);

for(i=1;i<=tmp;i++)

{

if(n%i==0)

{

d[max].num=i;max++;

d[max].num=n/i;max++;

}

}max--;

qsort(0,max,d);

d[0].sum=1;

printf("%d\n",dfs(n));

return0;

}1027ProblemD:郵局選址問題Description問題描述：

在一個(gè)按照東西和南北方向劃分成規(guī)整街區(qū)的城市里，n個(gè)居民點(diǎn)散亂地分布在不同的街區(qū)中。用x坐標(biāo)表示東西向，用y坐標(biāo)表示南北向。各居民點(diǎn)的位置可以由坐標(biāo)(x,y)表示。街區(qū)中任意2點(diǎn)(x1,y1)和(x2,y2)之間的距離可以用數(shù)值|x1-x2|+|y1-y2|度量。居民們希望在城市中選擇建立郵局的最佳位置，使n個(gè)居民點(diǎn)到郵局的距離總和最小。

編程任務(wù)：給定n個(gè)居民點(diǎn)的位置,編程計(jì)算n個(gè)居民點(diǎn)到郵局的距離總和的最小值。Input輸入由多組測試數(shù)據(jù)組成。每組測試數(shù)據(jù)輸入的第1行是居民點(diǎn)數(shù)n，1≤n≤10000。接下來n行是居民點(diǎn)的位置，每行2個(gè)整數(shù)x和y，-10000≤x，y≤10000。Output對應(yīng)每組輸入，輸出的第1行中的數(shù)是n個(gè)居民點(diǎn)到郵局的距離總和的最小值。SampleInput51222133-233SampleOutput10#include<iostream>usingnamespacestd;voidQuickSort(intarry[],intl,inth);intmain(){inti,j,n,l,h,x,y,a,b; intsum1=0,sum2=0; cin>>n; l=0; h=n-1; intarry[10000][2]; int*x1=newint[n]; int*y1=newint[n]; for(i=0;i<n;i++) for(j=0;j<2;j++) { scanf("%d",&arry[i][j]); } for(i=0;i<n;i++) { x1[i]=arry[i][0]; y1[i]=arry[i][1]; }QuickSort(x1,l,h); QuickSort(y1,l,h); x=x1[(n-1)/2]; y=y1[(n-1)/2]; for(i=0;i<n;i++) { a=arry[i][0]-x; if((arry[i][0]-x)<0) { a=x-arry[i][0]; } b=arry[i][1]-y; if((arry[i][1]-y)<0) { b=y-arry[i][1]; } sum1+=a; sum2+=b; } cout<<sum1+sum2<<endl; return0;}voidQuickSort(intarry[],intl,inth) { inti=l,j=h;//低LOW，高HIGH inttemp=arry[l];//取第一個(gè)做標(biāo)準(zhǔn)數(shù)據(jù)元書的 while(i<j) { while(i<j&&temp<=arry[j])j--;//右端掃描 if(i<j) { arry[i]=arry[j]; i++; } while(i<j&&arry[i]<temp)i++; if(i<j) { arry[j]=arry[i]; j--; } } arry[i]=temp; if(l<i)QuickSort(arry,l,i-1); if(i<h)QuickSort(arry,j+1,h); } 1031ProblemA:矩陣連乘問題Description給定n個(gè)矩陣｛A1,A2,…,An｝，其中Ai與Ai+1是可乘的，i=1,2,…,n-1。如何確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少。Input輸入包含多組測試數(shù)據(jù)。第一行為一個(gè)整數(shù)C，表示有C組測試數(shù)據(jù)，接下來有2*C行數(shù)據(jù)，每組測試數(shù)據(jù)占2行，每組測試數(shù)據(jù)第一行是1個(gè)整數(shù)n，表示有n個(gè)矩陣連乘,接下來一行有n+1個(gè)數(shù),表示是n個(gè)矩陣的行及第n個(gè)矩陣的列,它們之間用空格隔開.Output你的輸出應(yīng)該有C行，即每組測試數(shù)據(jù)的輸出占一行，它是計(jì)算出的矩陣最少連乘積次數(shù).SampleInput1310100550SampleOutput7500#include<stdio.h>

intmain()

{

intp[101],i,j,k,r,t,n;

intm[101][101];//為了跟講解時(shí)保持一致數(shù)組從1開始

ints[101][101];//記錄從第i到第j個(gè)矩陣連乘的斷開位置

scanf("%d",&n);

for(i=0;i<=n;i++)

scanf("%d",&p[i]);//讀入p[i]的值(注意：p[0]到p[n]共n+1項(xiàng))

for(i=1;i<=n;i++)//初始化m[i][i]=0

m[i][i]=0;

for(r=1;r<n;r++)//r為i、j相差的值

for(i=1;i<n;i++)//i為行

{

j=i+r;//j為列

m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//給m[i][j]賦初值

s[i][j]=i;

for(k=i+1;k<j;k++)

{

t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];

if(t<m[i][j])

{

m[i][j]=t;//m[i][j]取最小值

s[i][j]=k;

}

}

}

printf("%d",m[1][n]);

}1032ProblemC:最長公共子序列Description一個(gè)給定序列的子序列是在該序列中刪去若干元素后得到的序列。給定兩個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱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è)最長公共子序列。序列{B，C，B，A}也是X和Y的一個(gè)公共子序列，它的長度為4，而且它是X和Y的一個(gè)最長公共子序列，因?yàn)閄和Y沒有長度大于4的公共子序列。最長公共子序列問題就是給定兩個(gè)序列X={x1,x2,...xm}和Y={y1,y2,...yn}，找出X和Y的一個(gè)最長公共子序列。Input輸入包含多組測試數(shù)據(jù)。第一行為一個(gè)整數(shù)C，表示有C組測試數(shù)據(jù)，接下來有C行數(shù)據(jù)，每組測試數(shù)據(jù)占1行，它由2個(gè)給定序列的字符串組成，兩個(gè)字符串之間用空格隔開.Output你的輸出應(yīng)該有C行，即每組測試數(shù)據(jù)的輸出占一行，它是計(jì)算出的最長公共子序列長度。SampleInput1ABCBDBABDCABASampleOutput4#include<stdio.h>#include<string.h>#include<stdlib.h>voidprt_lcs(int,int,char[],int**);intmain(intargc,char*argv[]){charx[100],y[100];inti,j,m,n,**a,**b;gets(x);gets(y);m=strlen(x)+1;n=strlen(y)+1;if(((a=(int**)malloc(m*sizeof(int*)))==NULL)||((b=(int**)\malloc(m*sizeof(int*)))==NULL)){printf("Thereisnoenoughmemory!\n");exit(1);}for(i=0;i<m;i++)if(((a[i]=(int*)malloc(n*sizeof(int)))==NULL)||((b[i]=\(int*)malloc(n*sizeof(int)))==NULL)){printf("Thereisnoenoughmemory!\n");exit(2);}for(i=0;i<m;i++)a[i][0]=0;for(i=0;i<n;i++)a[0][i]=0;for(i=1;i<m;i++)for(j=1;j<n;j++)if(x[i-1]==y[j-1]){a[i][j]=a[i-1][j-1]+1;b[i][j]=1;}elseif(a[i-1][j]>=a[i][j-1]){a[i][j]=a[i-1][j];b[i][j]=2;}else{a[i][j]=a[i][j-1];b[i][j]=3;}printf("%d\n",a[m-1][n-1]);prt_lcs(m-1,n-1,x,b);printf("\n");for(i=0;i<m;i++){free(a[i]);free(b[i]);}free(a);free(b);return0;}voidprt_lcs(inti,intj,charx[],int**b){if(i<0||j<0)return;if(b[i][j]==1){prt_lcs(i-1,j-1,x,b);printf("%c",x[i-1]);}elseif(b[i][j]==2)prt_lcs(i-1,j,x,b);elseprt_lcs(i,j-1,x,b);}1033ProblemB:MAXSUMDescription給定由n整數(shù)(可能為負(fù)數(shù))組成的序列{a1,a2,…,an}，求該序列形如ai+ai+1,…,+aj的子段和的最大值。當(dāng)所有的整數(shù)均為負(fù)數(shù)時(shí)定義其最大子段和為0。Input輸入包含多組測試數(shù)據(jù)。第一行為一個(gè)整數(shù)C，表示有C組測試數(shù)據(jù)，接下來有2*C行數(shù)據(jù)，每組測試數(shù)據(jù)占2行，每組測試數(shù)據(jù)第一行是1個(gè)整數(shù)n，表示有n個(gè)整數(shù),接下來一行有n個(gè)整數(shù),它們之間用空格隔開.Output你的輸出應(yīng)該有C行，即每組測試數(shù)據(jù)的輸出占一行，它是計(jì)算出的最大子段和.SampleInput16-211-413-5-2SampleOutput20#include<stdio.h>intmaxsum(intn,int*a){intsum=0,b=0,i,j;for(i=1;i<=n;i++){if(b>0)b+=a[i];elseb=a[i];if(b>sum)sum=b;}returnsum;}main(){intm;scanf("%d",&m);while(m--){inta[100],i,max,n;scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);max=maxsum(n,a);printf("%d\n",max);}}1034ProblemD:NumberTrianglesDescription給定一個(gè)由n行數(shù)字組成的數(shù)字三角形如下圖所示。試設(shè)計(jì)一個(gè)算法，計(jì)算出從三角形的頂至底的一條路徑，使該路徑經(jīng)過的數(shù)字總和最大。

編程任務(wù)：對于給定的由n行數(shù)字組成的數(shù)字三角形，編程計(jì)算從三角形的頂至底的路徑經(jīng)過的數(shù)字和的最大值。Input輸入數(shù)據(jù)是由多組測試數(shù)據(jù)組成。第1行是數(shù)字三角形的行數(shù)n，1≤n≤100。接下來n行是數(shù)字三角形各行中的數(shù)字。所有數(shù)字在0至99之間。Output對應(yīng)每組測試數(shù)據(jù)，每行輸出的是計(jì)算出的最大值。SampleInput5738810274445265SampleOutput30#include<stdio.h>intmain(){intinta[102][102];inti,j;intn;//freopen("in.txt","r",stdin);while(scanf("%d",&n)!=EOF){for(i=1;i<=n;i++)for(j=1;j<=i;j++)scanf("%d",&inta[i][j]);for(i=n-1;i>0;i--)for(j=i;j>0;j--){inta[i][j]+=inta[i+1][j+1]>inta[i+1][j]?inta[i+1][j+1]:inta[i+1][j];}printf("%d\n",inta[1][1]);}return0;}1035編輯距離問題Description設(shè)A和B是2個(gè)字符串。要用最少的字符操作將字符串A轉(zhuǎn)換為字符串B。這里所說的字符操作包括

(1)刪除一個(gè)字符；

(2)插入一個(gè)字符；

(3)將一個(gè)字符改為另一個(gè)字符。

將字符串A變換為字符串B所用的最少字符操作數(shù)稱為字符串A到B的編輯距離，記為d(A,B)。試設(shè)計(jì)一個(gè)有效算法，對任給的2個(gè)字符串A和B，計(jì)算出它們的編輯距離d(A,B)。

編程任務(wù)：

對于給定的字符串A和字符串B，編程計(jì)算其編輯距離d(A,B)。Input輸入由多組測試數(shù)據(jù)組成。

每組測試數(shù)據(jù)輸入的第1行是字符串A，第2行是字符串B。Output對應(yīng)每組輸入，輸出的每行中的數(shù)是編輯距離d(A,B)。SampleInputfxpimuxwrsSampleOutput5#include<iostream>#include<string>usingnamespacestd;intmain(){stringA1,A2;cin>>A1>>A2;intm=A1.length();intn=A2.length();int*d=newint[n+1];inti;for(i=1;i<=n;i++)d[i]=i;for(i=1;i<=m;i++){inty=i-1;for(intj=1;j<=n;j++){intx=y;y=d[j];intz=j>1?d[j-1]:i;intdel=A1[i-1]==A2[j-1]?0:1;d[j]=x+del;if(d[j]>y+1)d[j]=y+1;if(d[j]>z+1)d[j]=z+1;}}cout<<d[n]<<endl;return0;}PebbleMergingDescription在一個(gè)圓形操場的四周擺放著n堆石子?，F(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的2堆石子合并成新的一堆，并將新的一堆石子數(shù)記為該次合并的得分。試設(shè)計(jì)一個(gè)算法，計(jì)算出將n堆石子合并成一堆的最小得分和最大得分。

編程任務(wù)：

對于給定n堆石子,編程計(jì)算合并成一堆的最小得分和最大得分。Input輸入由多組測試數(shù)據(jù)組成。

每組測試數(shù)據(jù)輸入的第1行是正整數(shù)n，1≤n≤100，表示有n堆石子。第二行有n個(gè)數(shù)，分別表示每堆石子的個(gè)數(shù)。Output對應(yīng)每組輸入，輸出的第1行中的數(shù)是最小得分；第2行中的數(shù)是最大得分。SampleInput44459SampleOutputHint43

54#include<stdio.h>#include<memory.h>intn;inta[101],s[101][101],t[101][101];inti,j,k,temp,max,min;intmain(){while(scanf("%d",&n)!=-1){i=1;while(i<=n){scanf("%d",&a[i++]);}memset(t,0,sizeof(t));for(i=1;i<=n;i++){for(j=1;j<=n;j++){for(k=i;k<=i+j-1;k++){if(k>n)temp=k%n;elsetemp=k;t[i][j]+=a[temp];}}}memset(s,0,sizeof(s));for(j=2;j<=n;j++){for(i=1;i<=n;i++){for(k=1;k<=j-1;k++){if(i+k>n)temp=(i+k)%n;elsetemp=i+k;max=s[i][k]+s[temp][j-k]+t[i][j];if(s[i][j]<max)s[i][j]=max;}}}max=0;for(i=1;i<=n;i++){if(max<s[i][n])max=s[i][n];}memset(s,0,sizeof(s));for(j=2;j<=n;j++){for(i=1;i<=n;i++){min=9999999;for(k=1;k<=j-1;k++){if(i+k>n)temp=(i+k)%n;elsetemp=i+k;s[i][j]=s[i][k]+s[temp][j-k]+t[i][j];if(min>s[i][j])min=s[i][j];}s[i][j]=min;}}min=9999999;for(i=1;i<=n;i++){if(min>s[i][n])min=s[i][n];}printf("%d\n",min);printf("%d\n",max);}return0;}租用游艇問題Description長江游艇俱樂部在長江上設(shè)置了n個(gè)游艇出租站1，2，…，n。游客可在這些游艇出租站租用游艇，并在下游的任何一個(gè)游艇出租站歸還游艇。游艇出租站i到游艇出租站j之間的租金為r(i,j),1≤i＜j≤n。試設(shè)計(jì)一個(gè)算法，計(jì)算出從游艇出租站1到游艇出租站n所需的最少租金。

編程任務(wù)：

對于給定的游艇出租站i到游艇出租站j之間的租金為r(i,j),1≤i＜j≤n，編程計(jì)算從游艇出租站1到游艇出租站n所需的最少租金。Input輸入由多組測試數(shù)據(jù)組成。

每組測試數(shù)據(jù)輸入的第1行中有1個(gè)正整數(shù)n（n≤200），表示有n個(gè)游艇出租站。接下來的n-1行是r(i,j),1≤i＜j≤n。Output對應(yīng)每組輸入，輸出的每行是計(jì)算出的從游艇出租站1到游艇出租站n所需的最少租金。SampleInput35157SampleOutput12#include<stdio.h>intinta[200][200];intn;intdyna(){inti,j,k,p;for(k=2;k<n;k++){for(i=1;i<=n-k;i++){j=i+k;for(p=i+1;p<j;p++){intt=inta[i][p]+inta[p][j];if(inta[i][j]>t)inta[i][j]=t;}}}returninta[1][n];}intmain(){inti,j;while(scanf("%d",&n)!=EOF){for(i=1;i<n;i++)for(j=i+1;j<=n;j++)scanf("%d",&inta[i][j]);printf("%d\n",dyna());}return0;}MinimalmSumsDescription給定n個(gè)整數(shù)組成的序列，現(xiàn)在要求將序列分割為m段，每段子序列中的數(shù)在原序列中連續(xù)排列。如何分割才能使這m段子序列的和的最大值達(dá)到最??？

編程任務(wù)：

給定n個(gè)整數(shù)組成的序列,編程計(jì)算該序列的最優(yōu)m段分割，使m段子序列的和的最大值達(dá)到最小。Input輸入由多組測試數(shù)據(jù)組成。

每組測試數(shù)據(jù)輸入的第1行中有2個(gè)正整數(shù)n和m。正整數(shù)n是序列的長度；正整數(shù)m是分割的段數(shù)。接下來的一行中有n個(gè)整數(shù)。Output對應(yīng)每組輸入，輸出的每行是計(jì)算出的m段子序列的和的最大值的最小值。SampleInput1110SampleOutput10#include<iostream>usingnamespacestd;intt[100];intf[100][100];voidsolve(intn,intm){inti,j,k,temp,maxt;for(i=1;i<=n;i++)f[i][1]=f[i-1][1]+t[i];for(j=2;j<=m;j++)for(i=j;i<=n;i++){for(k=1,temp=INT_MAX;k<i;k++){maxt=(f[i][1]-f[k][1])>f[k][j-1]?(f[i][1]-f[k][1]):f[k][j-1];if(temp>maxt)temp=maxt;}f[i][j]=temp;}}intmain(){inti,n,m;cin>>n>>m;if((n<m)||(n==0)){cout<<0<<endl;return0;}for(i=1;i<=n;i++)cin>>t[i];solve(n,m);cout<<f[n][m]<<endl;return0;}1040KnapsackProblem給定n種物品和一個(gè)背包。物品i的重量是Wi，其價(jià)值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?在選擇物品i裝入背包時(shí)，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。

編程任務(wù)：

對于給定的n種物品和一個(gè)背包容量C，編程計(jì)算裝入背包中最大的物品總價(jià)值。Input輸入由多組測試數(shù)據(jù)組成。

每組測試數(shù)據(jù)輸入的第1行中有2個(gè)正整數(shù)n和C。正整數(shù)n是物品個(gè)數(shù)；正整數(shù)C是背包的容量。接下來的2行中，第一行有n個(gè)正整數(shù)，分別表示n個(gè)物品的重量，它們之間用空格分隔；第二行有n個(gè)正整數(shù)，分別表示n個(gè)物品的價(jià)值，它們之間用空格分隔。Output對應(yīng)每組輸入，輸出的每行是計(jì)算出的裝入背包中最大的物品總價(jià)值，保留一位有效數(shù)字。SampleInput35010203060100120SampleOutput240.0#include<iostream>#include<stdio.h>#include<algorithm>usingnamespacestd;structNode{ doubleweight; doublevalue; };boolcomp(Nodea,Nodeb){ returna.value/a.weight>b.value/b.weight;}intmain(){ intn,i; doublec,w,v; while(scanf("%d%lf",&n,&c)!=EOF) { Nodeinfor[2001]; for(i=0;i<n;i++) scanf("%lf",&infor[i].weight); for(i=0;i<n;i++) scanf("%lf",&infor[i].value); sort(infor,infor+n,comp); v=0.0; w=0.0; for(i=0;i<n;i++) { if(infor[i].weight+w<=c) { w+=infor[i].weight; v+=infor[i].value; } else { v+=(c-w)/infor[i].weight*infor[i].value; break; } } printf("%.1lf\n",v); } return0;}1041最優(yōu)裝載有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。

編程任務(wù)：

對于給定的n個(gè)集裝箱和輪船的載重量C，編程計(jì)算裝入最多時(shí)的集裝箱個(gè)數(shù)。Input輸入由多組測試數(shù)據(jù)組成。

每組測試數(shù)據(jù)輸入的第1行中有2個(gè)正整數(shù)n和C。正整數(shù)n是集裝箱個(gè)數(shù)；正整數(shù)C是輪船的載重量。接下來的一行中有n個(gè)整數(shù)，分別表示n個(gè)集裝箱的重量，它們之間用空格分隔。Output對應(yīng)每組輸入，輸出的每行是計(jì)算出的裝入最多時(shí)的集裝箱個(gè)數(shù)。SampleInput453521SampleOutput2#include<iostream>#include<stdio.h>#include<queue>usingnamespacestd;structNode{ intweight; friendbooloperator<(Nodea,Nodeb) { returna.weight>b.weight; }};intmain(){ intn,c,num,sum; Nodep; while(cin>>n>>c) { priority_queue<Node>Q; while(n--) { scanf("%d",&p.weight); Q.push(p); } num=sum=0; while(!Q.empty()) { p=Q.top(); Q.pop(); sum+=p.weight; num++; if(sum>c) { num--; break; } } cout<<num<<endl; } return0;}1042LectureHalls假設(shè)要在足夠多的會(huì)場里安排一批活動(dòng)，并希望使用盡可能少的會(huì)場。設(shè)計(jì)一個(gè)有效的算法進(jìn)行安排。(這個(gè)問題實(shí)際上是著名的圖著色問題。若將每一個(gè)活動(dòng)作為圖的一個(gè)頂點(diǎn)，不相容活動(dòng)間用邊相連。使相鄰頂點(diǎn)著有不同顏色的最小著色數(shù)，相應(yīng)于要找的最小會(huì)場數(shù)。)

編程任務(wù)：對于給定的k個(gè)待安排的活動(dòng)，編程計(jì)算使用最少會(huì)場的時(shí)間表。Input輸入數(shù)據(jù)是由多組測試數(shù)據(jù)組成。每組測試數(shù)據(jù)輸入的第一行有1個(gè)正整數(shù)k，表示有k個(gè)待安排的活動(dòng)。接下來的k行中，每行有2個(gè)正整數(shù)，分別表示k個(gè)待安排的活動(dòng)開始時(shí)間和結(jié)束時(shí)間。時(shí)間以0點(diǎn)開始的分鐘計(jì)。Output對應(yīng)每組輸入，輸出的每行是計(jì)算出的最少會(huì)場數(shù)。SampleInput51231228253527803650SampleOutput3#include<iostream>usingnamespacestd;intPartition(inta[],intlow,inthigh)//????{inti,j;intx=a[low];i=low;j=high;while(i<j){while(i<j&&x<a[j]){j=j-1;}if(i<j){a[i]=a[j];i=i+1;}while(i<j&&x>=a[i]){i=i+1;}if(i<j){a[j]=a[i];j=j-1;}}a[i]=x;returni;}voidQuickSort(inta[],intlow,inthigh){intPosition;if(low<high){Position=Partition(a,low,high);QuickSort(a,low,Position-1);QuickSort(a,Position+1,high);}}intschedule(inta[],intb[],ints,inte){intn=0;inti=s+1;if(a[s]>-1){n=1;for(;i<=e;i++)if(a[i]>=b[s])s++;elsen++;}returnn;}intmain(){intn;cin>>n;int*st=newint[n];int*et=newint[n];for(inti=0;i<n;i++)cin>>st[i]>>et[i];QuickSort(st,0,n-1);QuickSort(et,0,n-1);cout<<schedule(st,et,0,n-1)<<endl;delete[]st;delete[]et;return0;}1043程序存儲(chǔ)問題設(shè)有n個(gè)程序{1,2,…,n}要存放在長度為L的磁帶上。程序i存放在磁帶上的長度是li，1≤i≤n。程序存儲(chǔ)問題要求確定這n個(gè)程序在磁帶上的一個(gè)存儲(chǔ)方案，使得能夠在磁帶上存儲(chǔ)盡可能多的程序。

編程任務(wù)：

對于給定的n個(gè)程序存放在磁帶上的長度，編程計(jì)算磁帶上最多可以存儲(chǔ)的程序數(shù)。Input輸入由多組測試數(shù)據(jù)組成。

每組測試數(shù)據(jù)輸入的第一行是2個(gè)正整數(shù)，分別表示文件個(gè)數(shù)n和磁帶的長度L。接下來的1行中，有n個(gè)正整數(shù)，表示程序存放在磁帶上的長度。Output對應(yīng)每組輸入，每行輸出的是計(jì)算出的最多可以存儲(chǔ)的程序數(shù)。SampleInput650231388020SampleOutput5#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;intn,l;intgreedy(vector<int>x,intm){inti=0,sum=0,n=x.size();sort(x.begin(),x.end());while(i<n){sum+=x[i];if(sum<=m)i++;elsereturni;}returnn;}intmain(){inti,a[1000];vector<int>x;cin>>n>>l;for(i=0;i<n;i++){cin>>a[i];x.push_back(a[i]);}cout<<greedy(x,l)<<endl;return0;}1048OptimalServices設(shè)有n個(gè)顧客同時(shí)等待一項(xiàng)服務(wù)。顧客i需要的服務(wù)時(shí)間為ti，1≤i≤n。應(yīng)如何安排n個(gè)顧客的服務(wù)次序才能使平均等待時(shí)間達(dá)到最小?平均等待時(shí)間是n個(gè)顧客等待服務(wù)時(shí)間的總和除以n。

編程任務(wù)：

對于給定的n個(gè)顧客需要的服務(wù)時(shí)間，編程計(jì)算最優(yōu)服務(wù)次序。Input輸入由多組測試數(shù)據(jù)組成。

每組測試數(shù)據(jù)輸入的第一行是正整數(shù)n，表示有n個(gè)顧客。接下來的1行中，有n個(gè)正整數(shù)，表示n個(gè)顧客需要的服務(wù)時(shí)間。Output對應(yīng)每組輸入，輸出的每行是計(jì)算出的最小平均等待時(shí)間。SampleInput1056121991000234335599812SampleOutput532.00#include<iostream>#include<algorithm>usingnamespacestd;ints[100000],n,i;intmain(){while(scanf("%d",&n)!=EOF){for(i=0;i<n;i++)scanf("%d",&s[i]);sort(&s[0],&s[n]);intsum=0;for(i=0;i<n;i++){sum+=s[i]*(n-i);}floatans=float(sum)/float(n);printf("%.2f\n",ans);}return0;}1049汽車加油問題一輛汽車加滿油后可行駛n公里。旅途中有若干個(gè)加油站。設(shè)計(jì)一個(gè)有效算法，指出應(yīng)在哪些加油站?？考佑?，使沿途加油次數(shù)最少。并證明算法能產(chǎn)生一個(gè)最優(yōu)解。

編程任務(wù)：

對于給定的n和k個(gè)加油站位置，編程計(jì)算最少加油次數(shù)。Input輸入由多組測試數(shù)據(jù)組成。

每組測試數(shù)據(jù)輸入的第一行有2個(gè)正整數(shù)n和k，表示汽車加滿油后可行駛n公里，且旅途中有k個(gè)加油站。接下來的1行中，有k+1個(gè)整數(shù)，表示第k個(gè)加油站與第k-1個(gè)加油站之間的距離。第0個(gè)加油站表示出發(fā)地，汽車已加滿油。第k+1個(gè)加油站表示目的地。Output對應(yīng)每組輸入，輸出的每行是計(jì)算出的最少加油次數(shù)。如果無法到達(dá)目的地，則輸出”NoSolution”。SampleInput7712345166SampleOutput4#include<iostream>#include<vector>usingnamespacestd;inta[1000];intg(vector<int>x,intn){inti,j,s;intsum=0,k=x.size();for(j=0;j<k;j++)if(x[j]>n){cout<<"NoSolution!"<<endl;return-1;}for(i=0,s=0;i<k;i++){s+=x[i];if(s>n){sum++;s=x[i];}}returnsum;}intmain(){inti,n,k,tmp;vector<int>x;cin>>n>>k;for(i=0;i<=k;i++){cin>>a[i];x.push_back(a[i]);}tmp=g(x,n);if(tmp!=-1)cout<<tmp<<endl;return0;}1059ProblemA子集樹問題試設(shè)計(jì)一個(gè)用回溯法搜索子集空間樹的函數(shù)。該函數(shù)的參數(shù)包括結(jié)點(diǎn)可行性判定函數(shù)和上界函數(shù)等必要的函數(shù)，并將此函數(shù)用于解裝載問題。

裝載問題描述如下：有一批共n(n≤≡10)個(gè)集裝箱要裝上艘載重量為c的輪船，其中集裝箱i的重量為wi。找出一種最優(yōu)裝載方案，將輪船盡可能裝滿，即在裝載體積不受限制的情況下，將盡可能重的集裝箱裝上輪船。輸入由多組測試數(shù)據(jù)組成。

每組測試數(shù)據(jù)輸入的第一行有2個(gè)正整數(shù)n和c，n是集裝箱數(shù)，c是輪船的載重量。接下來的1行中有n個(gè)正整數(shù)，表示集裝箱的重量。對應(yīng)每組輸入，輸出的每行是將計(jì)算出的最大裝載重量。5107265410#include<iostream>#defineMAX12882usingnamespacestd;structnode{

intw;}data[MAX];intdp[MAX],n,m;voidInit(){

inti;

for(i=1;i<=n;i++)

scanf("%d",&data[i].w);}intGetMax(inta,intb){

if(a>b)

returna;

else

returnb;}voidKnapsack(){

inti,j;

for(i=0;i<=m;i++)

{

if(i>=data[n].w)

dp[i]=data[n].w;

else

dp[i]=0;

}

for(i=n-1;i>=1;i--)

for(j=m;j>=1;j--)

{

if(j>=data[i].w)

{

dp[j]=GetMax(dp[j],dp[j-data[i].w]+data[i].w);

}

else

break;

}}intmain(){

while(scanf("%d%d",&n,&m)!=EOF)

{

Init();

Knapsack();

printf("%d\n",dp[m]);

}

return0;}1060ProblemB0-1Knapsack試設(shè)計(jì)一個(gè)用回溯法搜索子集空間樹的函數(shù)。該函數(shù)的參數(shù)包括結(jié)點(diǎn)可行性判定函數(shù)和上界函數(shù)等必要的函數(shù)，并將此函數(shù)用于解0-1背包問題。

0-1背包問題描述如下：給定n種物品和一個(gè)背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?在選擇裝入背包的物品時(shí)，對每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。輸入由多組測試數(shù)據(jù)組成。

每組測試數(shù)據(jù)輸入的第一行有2個(gè)正整數(shù)n和c。n是物品數(shù)，c是背包的容量。接下來的1行中有n個(gè)正整數(shù)，表示物品的價(jià)值。第3行中有n個(gè)正整數(shù)，表示物品的重量。對應(yīng)每組輸入，輸出的2行是裝入背包物品的最大價(jià)值和最優(yōu)裝入方案。51063546226541511001#include<iostream.h>#include<iomanip.h>#include<string.h>intmin(intw,intc){inttemp;if(w<c)temp=w;elsetemp=c;returntemp;}intmax(intw,intc){inttemp;if(w>c)temp=w;elsetemp=c;returntemp;}voidknapsack(intv[],intw[],intc,intn,int**m)

{

intjmax=min(w[n]-1,c);

for(intj=0;j<=jmax;j++)

m[n][j]=0;

for(intjj=w[n];jj<=c;jj++)

m[n][jj]=v[n];

for(inti=n-1;i>1;i--){

jmax=min(w[i]-1,c);

for(intj=0;j<=jmax;j++)

m[i][j]=m[i+1][j];

for(intjj=w[i];jj<=c;jj++)

m[i][jj]=max(m[i+1][jj],m[i+1][jj-w[i]]+v[i]);

}

m[1][c]=m[2][c];

if(c>=w[1])

m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);cout<<m[1][c]<<endl;}inttraceback(int**m,intw[],intc,intn,intx[])

{

for(inti=1;i<n;i++)

if(m[i][c]==m[i+1][c])x[i]=0;

else{x[i]=1;

c-=w[i];}

x[n]=(m[n][c])?1:0;

for(inty=1;y<=n;y++)

{

cout<<x[y]<<"";

}

cout<<endl;

returnx[n];}intmain(){intn,c;int**m;cin>>n>>c;

int*v=newint[n+1];for(inti=1;i<=n;i++)

cin>>v[i];int*w=newint[n+1];for(intj=1;j<=n;j++)

cin>>w[j];int*x=newint[n+1];m=newint*[n+1];

for(intp=0;p<n+1;p++){

m[p]=newint[c+1];}knapsack(v,w,c,n,m);traceback(m,w,c,n,x);delete[]x;delete[]w;delete[]v;return0;}1061ProblemC排列樹問題試設(shè)計(jì)一個(gè)用回溯法搜索排列空間樹的函數(shù)。該函數(shù)的參數(shù)包括結(jié)點(diǎn)可行性判定函數(shù)和上界函數(shù)等必要的函數(shù)，并將此函數(shù)用于解圓排列問題。

圓排列問題描述如下：給定n個(gè)大小不等的圓c1,c2,...,cn，現(xiàn)要將這n個(gè)圓排進(jìn)一個(gè)矩形框中，且要求各圓與矩形框的底邊相切。圓排列問題要求從n個(gè)圓的所有排列中找出有最小長度的圓排列。例