ACM算法设计实验题目汇总.doc

ACM算法设计实验题目汇总411020 Permutation with Repetition 1 1021 双色Hanoi塔问题 31022 Search Number 4 1023 整数划分问题 51024 Counting 61025 输油管道问题 81026 Integer Factorization 91027 邮局选址问题 111031 矩阵连乘问题 131032 最长公共子序列 141033 MAX SUM 161034 Number Triangles 171035 编辑距离问题 181036 Pebble Merging 191037 租用游艇问题 211038 Minimal m Sums 221040 Knapsack Problem 241041 最优装载 251042 Lecture Halls 261043 程序存储问题 291048 Optimal Services 301049 汽车加油问题 301059 子集树问题 321060 0-1 Knapsack 331061 排列树问题 361062 Problem D General Search 381020 Permutation with RepetitionDescription R= r1,r2, ,rn 是要进行排列的n 个元素。其中元素r1,r2, ,rn可能相同。试设计一个算法，列出R的所有不同排列。 编程任务：给定n 以及待排列的n 个元素。计算出这n 个元素的所有不同排列。Input 输入由多组测试数据组成。每组测试数据的第1 行是元素个数n，1 = n = 500。接下来的1 行是待排列的n 个元素。 Output 对应每组输入，将计算出的n 个元素的所有不同排列输出，每种排列单独一行。最后1 行中的数是排列总数。Sample Input 4aaccSample Output aacc acac acca caac caca ccaa 6 #include #include using namespace std ;int ans ;int ok(char str,int a ,int b ) if( b a) 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 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塔问题Description A、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 个字符c1 和c2 组成，表示将第k 个圆盘从塔座c1 移到塔座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(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 科研调查时得到了n个自然数，每个数均不超过1500000000。已知不相同的数不超过10000个，现在需要在其中查找某个自然数，如找到则输出并统计这个自然数出现的次数，如没找到则输出NO。Input 输入由多组测试数据组成。 每组测试数据输入包含n+1行； 第一行是两个整数n和x，n表示自然数的个数,x表示要查找的自然数，两者之间用空格隔开； 第2至n+1每行一个自然数。Output 对应每组输入，如果查找到x，则每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开；如果没有查找到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;ahigh=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+) scanf(%d,&ai); quicksort(a,0,n-1); /调用快排 for (i=0;in;i+) /统计不同数字的个数 if(ai=s)Sum+;if(Sum=0)printf(NO);else printf(%d %d,s,Sum);1023 整数划分问题Description 将正整数n表示成一系列正整数之和：n=n1+n2+nk，其中n1n2nk1，k1。 正整数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的不同划分个数。 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; 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 问题描述： 一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2，9。 编程任务： 给定表示书的总页码的10 进制整数n (1n109) 。编程计算书的全部页码中分别用到多少次数字0，1，2，9。Input 输入由多组测试数据组成。 每组测试数据输入只有1 行，给出表示书的总页码的整数n。Output 对应每组输入，输出共有10行，在第k行输出页码中用到数字k-1 的次数，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*(pown/10); for(i=0; i n; statNum(sn, n); for(i=0; i 10; i+) cout sniendl; return 0; 1025 Problem B:输油管道问题Description 问题描述： 某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x 坐标（东西向）和y 坐标（南北向）,应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置? 编程任务： 给定n 口油井的位置,编程计算各油井到主管道之间的输油管道最小长度总和。Input 输入由多组测试数据组成。 每组测试数据输入的第1 行是油井数n，1n10000。接下来n 行是油井的位置，每行2个整数x和y，-10000x，y10000。Output 对应每组输入，输出的第1 行中的数是油井到主管道之间的输油管道最小长度总和。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);/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)/计算该点到其他点的距离for(int i=0;iaSize;i+)total+=abs(ax-ai);return total;/分两部分计算各自的最优值f=sPath(a,x,(x+y)/2);b=sPath(a,(x+y)/2+1,y);return fb?f:b;/归并操作，返回这两部分中更优解1026 Problem C:Integer FactorizationDescription 问题描述： 大于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 (1n2000000000)。Output 对应每组输入，输出计算出的不同的分解式数。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); 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) int 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:邮局选址问题Description 问题描述： 在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的街区中。用x 坐标表示东西向，用y坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。街区中任意2 点(x1,y1)和(x2,y2)之间的距离可以用数值|x1-x2|+|y1-y2|度量。居民们希望在城市中选择建立邮局的最佳位置，使n个居民点到邮局的距离总和最小。 编程任务： 给定n 个居民点的位置,编程计算n 个居民点到邮局的距离总和的最小值。Input 输入由多组测试数据组成。 每组测试数据输入的第1 行是居民点数n，1n10000。接下来n 行是居民点的位置，每行2 个整数x 和y，-10000x，y10000。 Output 对应每组输入，输出的第1 行中的数是n 个居民点到邮局的距离总和的最小值。Sample Input 51 22 21 33 -23 3Sample Output 10#includeusing 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);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; /取第一个做标准数据元书的while(ij)while(ij & temp =arryj)j-;/右端扫描if(ij)arryi=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:矩阵连乘问题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行，即每组测试数据的输出占一行，它是计算出的矩阵最少连乘积次数.Sample Input 1310 100 5 50Sample Output 7500#include int main() int p101,i,j,k,r,t,n; int m101101; /为了跟讲解时保持一致数组从1开始 int s101101; /记录从第i到第j个矩阵连乘的断开位置 scanf(%d,&n); for(i=0;i=n;i+) scanf(%d,&pi); /读入pi的值(注意：p0到pn共n+1项) 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:最长公共子序列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行，即每组测试数据的输出占一行，它是计算出的最长公共子序列长度。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) + 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 enough 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); 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整数(可能为负数)组成的序列 a1,a2,an，求该序列形如ai+ai+1,+aj的子段和的最大值。当所有的整数均为负数时定义其最大子段和为0。 Input 输入包含多组测试数据。第一行为一个整数C，表示有C组测试数据，接下来有2*C行数据，每组测试数据占2行，每组测试数据第一行是1个整数n，表示有n个整数,接下来一行有n个整数,它们之间用空格隔开. Output 你的输出应该有C行，即每组测试数据的输出占一行，它是计算出的最大子段和.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; else 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 给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。 编程任务：对于给定的由n 行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。Input 输入数据是由多组测试数据组成。第1 行是数字三角形的行数n，1n100。接下来n行是数字三角形各行中的数字。所有数字在0至99之间。Output 对应每组测试数据，每行输出的是计算出的最大值。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 = 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 编辑距离问题Description 设A 和B 是2 个字符串。要用最少的字符操作将字符串A 转换为字符串B。这里所说的字符操作包括 (1)删除一个字符； (2)插入一个字符； (3)将一个字符改为另一个字符。 将字符串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)。Sample Input fxpimuxwrsSample Output 5#include #include using namespace std;int main() string A1, A2; cin A1 A2; int m = A1.length(); 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 MergingDescription 在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。 编程任务： 对于给定n堆石子,编程计算合并成一堆的最小得分和最大得分。Input 输入由多组测试数据组成。 每组测试数据输入的第1 行是正整数n，1n100，表示有n堆石子。第二行有n个数，分别表示每堆石子的个数。Output 对应每组输入，输出的第1 行中的数是最小得分；第2 行中的数是最大得分。Sample Input 44 4 5 9Sample Output 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;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(