ACM算法设计实验题目汇总

ACM算法设计实验题目汇总1020PermutationwithRepetition11036PebbleMerging191021双色Hanoi塔问题31037租用游艇问题211022SearchNumber41038MinimalmSums221023整数划分问题51040KnapsackProblem241024Counting61041最优装载251025输油管道问题81042LectureHalls261026IntegerFactorization91043程序存储问题291027邮局选址问题111048OptimalServices301031矩阵连乘问题131049汽车加油问题301032最长公共子序列141059子集树问题321033MAXSUM1610600-1Knapsack331034NumberTriangles171061排列树问题361035编辑距离问题181062ProblemDGeneralSearch381020PermutationwithRepetitionDescriptionR={r1,r2,…，rn}是要进行排列的n个元素。其中元素r1,r2,…，rn可能相同。试设计一个算法，列出R的所有不同排列。编程任务：给定n以及待排列的n个元素。计算出这n个元素的所有不同排列。Input输入由多组测试数据组成。每组测试数据的第1行是元素个数n，1<=n<=500。接下来的1行是待排列的n个元素。Output对应每组输入，将计算出的n个元素的所有不同排列输出，每种排列单独一行。最后1行中的数是排列总数。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个塔座。开始时，在塔座A上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1，2,……，n，奇数号圆盘着蓝色，偶数号圆盘着红色，如图所示。现要求将塔座A上的这一叠圆盘移到塔座B上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：规则(1):每次只能移动1个圆盘；规则(2)：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则(3)：任何时刻都不允许将同色圆盘叠在一起；规则(4)：在满足移动规则(1)-(3)的前提下，可将圆盘移至A，B，C中任一塔座上。试设计一个算法，用最少的移动次数将塔座A上的n个圆盘移到塔座B上，并仍按同样顺序叠置。编程任务：对于给定的正整数n，编程计算最优移动方案。Input输入由多组测试数据组成。每组测试数据的第1行是给定的正整数n。Output对应每组输入，输出的每一行由一个正整数k和2个字符cl和c2组成，表示将第k个圆盘从塔座cl移到塔座c2上。SampleInput3SampleOutputABTOC\o"1-5"\h\z\o"CurrentDocument"ACBCABCACB1AB#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科研调查时得到了n个自然数，每个数均不超知不相同的数不超过10000个，现在需要在其中查找某个自然数，如找到则输出并统计这个自然数出现的次数，如没找到则输出NOoInput输入由多组测试数据组成。每组测试数据输入包含n+1行；第一行是两个整数n和x，n表示自然数的个数,x表示要查找的自然数，两者之间用空格隔开；第2至n+1每行一个自然数。Output对应每组输入，如果查找到x，则每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开；如果没有查找到x，则每行输出NO.SampleInput810010022244100528310042254100SampleOutput1002NO#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);〃调用快排for(i=0;i<n;i++)//统计不同数字的个数{if(a[i]==s){Sum++;}}if(Sum==0){printf(〃NO〃)；}else{printf("%d%d",s,Sum);}}1023整数划分问题Description将正整数n表示成一系列正整数之和：n=n1+n2+…+业,其中nimn2M"3nkmi,kmi。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。例如正整数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行；第一行是一个整数n,表示有n个测试用例；第2至n+1每行一个正整数。Output对应每组输入，输出正整数n的不同划分个数。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]));}}1024 ProblemA:CountingDescription问题描述：一本书的页码从自然数1开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6页用数字6表示，而不是06或006等。数字计数问题要求对给定书的总页码n,计算出书的全部页码中分别用到多少次数字0,1,2,…，9。编程任务：给定表示书的总页码的10进制整数n(1WnW109)。编程计算书的全部页码中分别用到多少次数字0,1,2,…，9。Input输入由多组测试数据组成。每组测试数据输入只有1行，给出表示书的总页码的整数n。Output对应每组输入，输出共有10行，在第k行输出页码中用到数字k-1的次数，k=1,2,…，10。SampleInput11SampleOutput1114 1 11111程序代码：#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问题描述：某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置，即它们的x坐标(东西向)和y坐标(南北向)，应如何确定主管道的最优位置，即使各油井到主管道之间的输油管道长度总和最小的位置？编程任务：给定n口油井的位置，编程计算各油井到主管道之间的输油管道最小长度总和。Input输入由多组测试数据组成。每组测试数据输入的第1行是油井数n,IWnWIOOOO。接下来n行是油井的位置，每行2个整数x和y,-lOOOOWx,yWlOOOO。Output对应每组输入，输出的第1行中的数是油井到主管道之间的输油管道最小长度总和。SampleInput52213-233SampleOutput6#include<iostream>usingstd::cout;usingstd::endl;usingstd::cin;intsPath(int*,int,int);intaSize=O;intmain()(//freopen("input.txt”,"r”,stdin);//freopen("output.txt”,"w”,stdout);cin>>aSize;int*x=newint[aSize];int*y=newint[aSize];for(inti=O;i<aSize;i++){cin>>x[i];cin>>y[i];}intp=O;p=sPath(y,0,aSize-1);cout<<p;return0;}intsPath(inta[],intx,inty)(intf,b,total=0;if(x==y){//计算该点到其他点的距离for(inti=0;i<aSize;i++)total+=abs(a[x]-a[i]);returntotal;}〃分两部分计算各自的最优值f=sPath(a,x,(x+y)/2);b=sPath(a,(x+y)/2+1,y);returnf<b?f:b;〃归并操作，返回这两部分中更优解}1026ProblemC:IntegerFactorizationDescription问题描述：大于1的正整数n可以分解为：n=X1*X2*…*Xm。例如，当n=12时，共有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。编程任务:对于给定的正整数n，编程计算n共有多少种不同的分解式。编程任务:Input输入由多组测试数据组成。每组测试数据输入第一行有1个正整数n(1WnW2000000000)。Output对应每组输入，输出计算出的不同的分解式数。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问题描述：在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的街区中。用x坐标表示东西向，用y坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。街区中任意2点(x1,y1)和(x2,y2)之间的距离可以用数值Ix1-x2l+ly1-y2l度量。居民们希望在城市中选择建立邮局的最佳位置，使n个居民点到邮局的距离总和最小。编程任务：给定n个居民点的位置，编程计算n个居民点到邮局的距离总和的最小值。Input输入由多组测试数据组成。每组测试数据输入的第1行是居民点数n,1WnW10000。接下来n行是居民点的位置，每行2个整数x和y,-10000Wx,yW10000。Output对应每组输入，输出的第1行中的数是n个居民点到邮局的距离总和的最小值。SampleInput52213-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，高HIGHinttemp=arry[l];//取第一个做标准数据元书的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:1031ProblemA:矩阵连乘问题Description给定n个矩阵｛A1,A2,…，An｝，其中Ai与Ai+1是可乘的,i=1,2,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。Input输入包含多组测试数据。第一行为一个整数C,表示有C组测试数据，接下来有2*C行数据，每组测试数据占2行，每组测试数据第一行是1个整数n，表示有n个矩阵连乘，接下来一行有n+1个数,表示是n个矩阵的行及第n个矩阵的列，它们之间用空格隔开.Output你的输出应该有C行，即每组测试数据的输出占一行，它是计算出的矩阵最少连乘积次数.SampleInput1310100550SampleOutput7500#include<stdio.h>intmain(){intp[101],i,j,k,r,t,n;intm[101][101];//为了跟讲解时保持一致数组从1开始ints[101][101];〃记录从第i到第j个矩阵连乘的断开位置scanf(〃%d〃,&n);for(i=0;i<=n;i++)scanf(〃%d〃,&p[i]);//读入p[i]的值(注意：p[0]到p[n]共n+1项)for(i=1;i<=n;i++)//初始化m[i][i]=0m[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]);}1032 ProblemC:最长公共子序列Description一个给定序列的子序列是在该序列中删去若干元素后得到的序列。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如，若X={A，B，C，B，D，B，A}，Y={B，D，C，A，B，A}，则序列{B，C，A}是X和Y的一个公共子序列，但它不是X和Y的一个最长公共子序列。序列{B，C，B，A}也是X和Y的一个公共子序列，它的长度为4,而且它是X和Y的一个最长公共子序列，因为X和Y没有长度大于4的公共子序列。最长公共子序列问题就是给定两个序列X={x1,x2,...xm}和Y={y1,y2,...yn}，找出X和Y的一个最长公共子序列。Input输入包含多组测试数据。第一行为一个整数C，表示有C组测试数据，接下来有C行数据，每组测试数据占1行，它由2个给定序列的字符串组成，两个字符串之间用空格隔开.Output你的输出应该有C行，即每组测试数据的输出占一行，它是计算出的最长公共子序列长度。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);}1033 ProblemB:MAXSUMDescription给定由n整数(可能为负数)组成的序列{a1,a2,…,an}，求该序列形如ai+ai+1,…,+aj的子段和的最大值。当所有的整数均为负数时定义其最大子段和为0。Input输入包含多组测试数据。第一行为一个整数C，表示有C组测试数据，接下来有2*C行数据，每组测试数据占2行，每组测试数据第一行是1个整数n，表示有n个整数，接下来一行有n个整数，它们之间用空格隔开.Output你的输出应该有C行，即每组测试数据的输出占一行，它是计算出的最大子段和.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);}}1034 ProblemD:NumberTrianglesDescription给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。TOC\o"1-5"\h\zb： ■ 02 7 4 44 5 2 G 5编程任务：对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。Input输入数据是由多组测试数据组成。第1行是数字三角形的行数n,1WnW100。接下来n行是数字三角形各行中的数字。所有数字在0至99之间。Output对应每组测试数据，每行输出的是计算出的最大值。SampleInput57881027445265SampleOutput30#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设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括删除一个字符；插入一个字符；将一个字符改为另一个字符。将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的2个字符串A和B，计算出它们的编辑距离d(A,B)。编程任务：对于给定的字符串A和字符串B，编程计算其编辑距离d(A,B)。Input输入由多组测试数据组成。每组测试数据输入的第1行是字符串A，第2行是字符串B。Output对应每组输入，输出的每行中的数是编辑距离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;}1036PebbleMergingDescription在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。编程任务：对于给定n堆石子，编程计算合并成一堆的最小得分和最大得分。Input输入由多组测试数据组成。每组测试数据输入的第1行是正整数n,1WnW100,表示有n堆石子。第二行有n个数，分别表示每堆石子的个数。Output对应每组输入，输出的第1行中的数是最小得分；第2行中的数是最大得分。SampleInput44459SampleOutputHint4354#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;}1037 租用游艇问题Description长江游艇俱乐部在长江上设置了n个游艇出租站1,2,…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1Wi〈jWn。试设计一个算法，计算出从游艇出租站1到游艇出租站n所需的最少租金。编程任务：对于给定的游艇出租站i到游艇出租站j之间的租金为r(i,j),1Wi〈jWn,编程计算从游艇出租站1到游艇出租站n所需的最少租金。Input输入由多组测试数据组成。每组测试数据输入的第1行中有1个正整数n(nW200)，表示有n个游艇出租站。接下来的n-1行是r(i,j),1WiVjWn。Output对应每组输入，输出的每行是计算出的从游艇出租站1到游艇出租站n所需的最少租金。SampleInput3157SampleOutput12#include<stdio.h>intinta[200][200];int n;int dyna(){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;}1038MinimalmSumsDescription给定n个整数组成的序列，现在要求将序列分割为m段，每段子序列中的数在原序列中连续排列。如何分割才能使这m段子序列的和的最大值达到最小？编程任务：给定n个整数组成的序列，编程计算该序列的最优m段分割，使m段子序列的和的最大值达到最小。Input输入由多组测试数据组成。每组测试数据输入的第1行中有2个正整数n和m。正整数n是序列的长度；正整数m是分割的段数。接下来的一行中有n个整数。Output对应每组输入，输出的每行是计算出的m段子序列的和的最大值的最小值。SampleInput1110SampleOutput10#include<iostream>usingnamespacestd;intt[100];intf[100][100];voidsolve(intn,intm)TOC\o"1-5"\h\z{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种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1ViVn编程任务：对于给定的n种物品和一个背包容量C，编程计算装入背包中最大的物品总价值。Input输入由多组测试数据组成。每组测试数据输入的第1行中有2个正整数n和C。正整数n是物品个数；正整数C是背包的容量。接下来的2行中，第一行有n个正整数，分别表示n个物品的重量，它们之间用空格分隔；第二行有n个正整数，分别表示n个物品的价值，它们之间用空格分隔。Output对应每组输入，输出的每行是计算出的装入背包中最大的物品总价值，保留一位有效数字。SampleInput5010203060100120SampleOutput240.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最优装载有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。编程任务：对于给定的n个集装箱和轮船的载重量C，编程计算装入最多时的集装箱个数。Input输入由多组测试数据组成。每组测试数据输入的第1行中有2个正整数n和C。正整数n是集装箱个数；正整数C是轮船的载重量。接下来的一行中有n个整数，分别表示n个集装箱的重量，它们之间用空格分隔。Output对应每组输入，输出的每行是计算出的装入最多时的集装箱个数。SampleInput53521SampleOutput2#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假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的算法进行安排。（这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。）编程任务：对于给定的k个待安排的活动，编程计算使用最少会场的时间表。Input输入数据是由多组测试数据组成。每组测试数据输入的第一行有1个正整数k，表示有k个待安排的活动。接下来的k行中，每行有2个正整数，分别表示k个待安排的活动开始时间和结束时间。时间以0点开始的分钟计。Output对应每组输入，输出的每行是计算出的最少会场数。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程序存储问题设有n个程序{1,2,...,n}要存放在长度为L的磁带上。程序i存放在磁带上的长度是li,1<i<n。程序存储问题要求确定这n个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。编程任务：对于给定的n个程序存放在磁带上的长度，编程计算磁带上最多可以存储的程序数。Input输入由多组测试数据组成。每组测试数据输入的第一行是2个正整数，分别表示文件个数n和磁带的长度L。接下来的1行中，有n个正整数，表示程序存放在磁带上的长度。Output对应每组输入，每行输出的是计算出的最多可以存储的程序数。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设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti,1<i^应如何安排n个顾客的服务次序才能使平均等待时间达到最小？平均等待时间是n个顾客等待服务时间的总和除以n。编程任务：对于给定的n个顾客需要的服务时间，编程计算最优服务次序。Input输入由多组测试数据组成。每组测试数据输入的第一行是正整数n，表示有n个顾客。接下来的1行中，有n个正整数，表示n个顾客需要的服务时间。Output对应每组输入，输出的每行是计算出的最小平均等待时间。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公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。并证明算法能产生一个最优解。编程任务：对于给定的n和k个加油站位置，编程计算最少加油次数。Input输入由多组测试数据组成。每组测试数据输入的第一行有2个正整数n和k,表示汽车加满油后可行驶n公里，且旅途中有k个加油站。接下来的1行中，有k+1个整数，表示第k个加油站与第k-1个加油站之间的距离。第0个加油站表示出发地，汽车已加满油。第k+1个加油站表示目的地。Output对应每组输入，输出的每行是计算出的最少加油次数。如果无法到达目的地，则输出”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;}ProblemA子集树问题DesciptOn试设计一个用回溯法搜索子集空间树的函数。该函数的参数包括结点可行性判定函数和上界函数等必要的函数，并将此函数用于解装载问题。装载问题描述如下：有一批共n(nW三10)个集装箱要装上艘载重量为c的轮船，其中集装箱i的重量为wi。找出一种最优装载方案，将轮船尽可能装满，即在装载体积不受限制的情况下，将尽可能重的集装箱装上轮船。Input输入由多组测试数据组成。每组测试数据输入的第一行有2个正整数n和c，n是集装箱数，c是轮船的载重量。接下来的1行中有n个正整数，表示集装箱的重量。Outpt对应每组输入，输出的每行是将计算出的最大装载重量。SampeIn)ut51072654SampeOitpit10#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;elsereturnb;}voidKnapsack(){inti,j;for(i=0;i<=m;i++){if(i>=data[n].w)dp[i]=data[n].w;elsedp[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);}elsebreak;}}intmain(){while(scanf(〃％d%d〃，&n,&m)!=EOF){Init();Knapsack();printf(〃%d\n〃,dp[m]);}return0;}ProblemB0-1KnapsackDesciptbn试设计一个用回溯法搜索子集空间树的函数。该函数的参数包括结点可行性判定函数和上界函数等必要的函数，并将此函数用于解0-1背包问题。0-1背包问题描述如下：给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大？在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。Input输入由多组测试数据组成。每组测试数据输入的第一行有2个正整数n和c。n是物品数，c是背包的容量。接下来的1行中有n个正整数，表示物品的价值。第3行中有n个正整数，表示物品的重量。Outpt对应每组输入，输出的2行是装入背包物品的最大价值和最优装入方案。SampfeIn)ut10354622654SampfeOutput1511001#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⑵[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;}ProblemC 排列树问题DesciptOn试设计一个用回溯法搜索排列空间树的函数。该函数的参数包括结点可行性判定函数和上界函数等必要的函数，并将此函数用于解圆排列问题。圆排列问题描述如下：给定n个大小不等的圆cl,c2,...,cn，现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。例如，当n=3，且所给的3个圆的半径分别为1，1，2时，这3个圆的最小长度的圆排列是1,2,1，其最小长度为2+4*sqr(2)。编程任务：对于给定的n(nW三10)个圆，编程计算最小长度排列。Input输入由多组测试数据组成。每组测试数据输入的第一行是1个正整数n，表示有n个圆。第2行有n个正数，分别表示n个圆的半径。Outpt对应每组输入，输出的每行是计算出的最小长度，保留3位小数。SampeIn)ut3112SampeOitpit7.657#include<iostream>#include<io