ACM算法设计实验题目汇总

1、. 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 Min

2、imal 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可能相同。试设计一个算法，列

3、出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 <stdio.h>#include <algorithm>using

4、 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 ;

5、 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

6、塔问题Description A、B、C 是3个塔座。开始时，在塔座A 上有一叠共n 个圆盘，这些圆盘自下而上， 由大到小地叠在一起。各圆盘从小到大编号为1，2，n，奇数号圆盘着蓝色，偶数号圆盘着红色，如图所示。现要求将塔座A 上的这一叠圆盘移到塔座B 上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则： 规则(1)：每次只能移动1个圆盘； 规则(2)：任何时刻都不允许将较大的圆盘压在较小的圆盘之上； 规则(3)：任何时刻都不允许将同色圆盘叠在一起； 规则(4)：在满足移动规则(1)-(3)的前提下，可将圆盘移至A，B，C 中任一塔座上。 试设计一个算法，用最少的移动次数将塔座A 上的n个

7、圆盘移到塔座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 <iostream> using namespace std;int main() void hanoi(int,char,

8、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 << " "&

9、lt;< x << " " << y <<endl;1022 Search NumberDescription 科研调查时得到了n个自然数，每个数均不超过1500000000。已知不相同的数不超过10000个，现在需要在其中查找某个自然数，如找到则输出并统计这个自然数出现的次数，如没找到则输出NO。Input 输入由多组测试数据组成。 每组测试数据输入包含n+1行； 第一行是两个整数n和x，n表示自然数的个数,x表示要查找的自然数，两者之间用空格隔开； 第2至n+1每行一个自然数。Output 对应每组输入，如果查找到x，则每行输出

10、两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开；如果没有查找到x，则每行输出NO.Sample Input 8 1002424510021008 3242451002100Sample Output 100 2NO#include<stdio.h> #include<string.h> #define LEN 200000 int aLEN,temp,mid; int sort(int *a,int low,int high) /一趟快排 mid=alow; while (low<high) while (low<high &&

11、ahigh>=mid) high-; temp=alow;alow=ahigh;ahigh=temp; while (low<high && 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

12、 main() int i,n,s;int Sum=0;scanf("%d",&n); scanf("%d",&s); for (i=0;i<n;i+) scanf("%d",&ai); quicksort(a,0,n-1); /调用快排 for (i=0;i<n;i+) /统计不同数字的个数 if(ai=s)Sum+;if(Sum=0)printf("NO");else printf("%d %d",s,Sum);1023 整数划分问题Description

13、 将正整数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 <std

14、io.h> 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, n); if(n = m) return (split(n, m - 1) + 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;i<k;

15、i+) scanf("%d",&ai); for(i=0;i<k;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) 。编程计算书

16、的全部页码中分别用到多少次数字0，1，2，9。Input 输入由多组测试数据组成。 每组测试数据输入只有1 行，给出表示书的总页码的整数n。Output 对应每组输入，输出共有10行，在第k行输出页码中用到数字k-1 的次数，k=1，2，10。Sample Input 11Sample Output 1411111111程序代码：#include <iostream.h> void statNum(long int sn10, int n) int i, c, k, s, pown; for( i = 0; i < 10; i+) sni = 0; for(k=s=0, po

17、wn=1; n > 0; k+, n /=10, pown *=10) c = n%10; for(i=0; i < 10; i+) sni += c*k*(pown/10); for(i=0; i < c; i+) sni += pown; snc += 1 + s; sn0 -= pown; s += c*pown; int main() int i,n; long int sn10; cin>>n; statNum(sn, n); for(i=0; i < 10; i+) cout <<sni<<endl; return 0;

18、1025 Problem B:输油管道问题Description 问题描述： 某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x 坐标（东西向）和y 坐标（南北向）,应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置? 编程任务： 给定n 口油井的位置,编程计算各油井到主管道之间的输油管道最小长度总和。Input 输入由多组测试数据组成。 每组测试数据输入的第1 行是油井数n，1n10000。接下来n 行是油井的位置，每行2个整数x和y，-

19、10000x，y10000。Output 对应每组输入，输出的第1 行中的数是油井到主管道之间的输油管道最小长度总和。Sample Input 51 22 21 33 -23 3Sample Output 6 #include<iostream>using 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&quo

20、t;,"w",stdout);cin>>aSize;int *x=new intaSize;int *y=new intaSize;for(int i=0;i<aSize;i+)cin>>xi;cin>>yi;int p=0;p=sPath(y,0,aSize-1);cout<<p;return 0;int sPath(int a,int x,int y)int f,b,total=0;if(x=y)/计算该点到其他点的距离for(int i=0;i<aSize;i+)total+=abs(ax-ai);retur

21、n total;/分两部分计算各自的最优值f=sPath(a,x,(x+y)/2);b=sPath(a,(x+y)/2+1,y);return f<b?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共有多少种不

22、同的分解式。Input 输入由多组测试数据组成。 每组测试数据输入第一行有1 个正整数n (1n2000000000)。Output 对应每组输入，输出计算出的不同的分解式数。Sample Input 12Sample Output 8#include<stdio.h> #include<math.h> 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(i&

23、lt;j) do while(tag.num<keyj.num && i<j) j-; if(i<j) keyi=keyj; i+; while(tag.num>=keyi.num && i<j) i+; if(i<j) keyj=keyi; j-; while(i<j); 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(l<

24、=r) m=(l+r)>>1; if(dm.num<left) 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) dma

25、x.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|度量。居民们希望在城市中选择建立邮局的最佳位

26、置，使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#include<iostream>using namespace std;void QuickSort(i

27、nt 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;i<n;i+)for(j=0;j<2;j+)scanf("%d",&arryij);for(i=0;i<n;i+)x1i=arryi0;y1i=arryi1; QuickSort( x1,l, h);QuickSort( y1,l, h);x=

28、x1(n -1)/2;y=y1(n -1)/2;for(i=0;i<n;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;cout<<sum1+sum2<<endl;return 0;void QuickSort(int arry,int l,int h)int i=l, j=h; /低LOW ，高HIGHint temp = arryl; /取第一个做标准数据元书的while(i<j)while(i<j

29、&& temp <=arryj)j-;/右端扫描if(i<j)arryi=arryj;i+;while(i<j && arryi < temp)i+;if(i<j)arryj=arryi;j-;arryi=temp;if(l<i)QuickSort( arry, l,i-1);if(i<h)QuickSort( arry, j+1,h);1031 Problem A:矩阵连乘问题Description 给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1,2 ,n-1。如何确定计算矩阵连乘积的计算次序，使得依

30、此次序计算矩阵连乘积需要的数乘次数最少。 Input 输入包含多组测试数据。第一行为一个整数C，表示有C组测试数据，接下来有2*C行数据，每组测试数据占2行，每组测试数据第一行是1个整数n，表示有n个矩阵连乘,接下来一行有n+1个数,表示是n个矩阵的行及第n个矩阵的列,它们之间用空格隔开. Output 你的输出应该有C行，即每组测试数据的输出占一行，它是计算出的矩阵最少连乘积次数.Sample Input 1310 100 5 50Sample Output 7500#include<stdio.h> int main() int p101,i,j,k,r,t,n; int m1

31、01101; /为了跟讲解时保持一致数组从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;r<n;r+) /r为i、j相差的值 for(i=1;i<n;i+) /i为行 j=i+r; /j为列 mij=mi+1j+pi-1*pi*pj; /给mij赋初值 sij=

32、i; for(k=i+1;k<j;k+) t=mik+mk+1j+pi-1*pk*pj; if(t<mij) 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

33、，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#inc

34、lude <stdio.h>#include <string.h>#include <stdlib.h>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*) mall

35、oc(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; fo

36、r (i = 0; i < n; i +) a0i = 0; for (i = 1; i < m; i +) for (j = 1; j < n; j +) if (xi - 1 = yj - 1) aij = ai - 1j - 1 + 1; bij = 1; else if (ai - 1j >= 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(

37、"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

38、 - 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

39、-2Sample Output 20#include <stdio.h>int maxsum(int n,int *a) int sum=0,b=0,i,j; for(i=1;i<=n;i+) if(b>0) b+=ai; else b=ai; if(b>sum) 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("

40、%d",&ai); max=maxsum(n,a); printf("%dn",max); 1034 Problem D:Number TrianglesDescription 给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。 编程任务：对于给定的由n 行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。Input 输入数据是由多组测试数据组成。第1 行是数字三角形的行数n，1n100。接下来n行是数字三角形各行中的数字。所有数字在0至99之间。Output

41、 对应每组测试数据，每行输出的是计算出的最大值。Sample Input 573 88 1 02 7 4 44 5 2 6 5Sample Output 30#include <stdio.h>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 <= i; j+ ) s

42、canf("%d",&intaij ) ; for( i = n - 1 ; i > 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)

43、将一个字符改为另一个字符。 将字符串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 <iostream>#include <str

44、ing>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 <= n; j+) int x = y; y = dj; int z = j > 1 ?

45、 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堆石子合并成一堆的最小得分和最大得

46、分。 编程任务： 对于给定n堆石子,编程计算合并成一堆的最小得分和最大得分。Input 输入由多组测试数据组成。 每组测试数据输入的第1 行是正整数n，1n100，表示有n堆石子。第二行有n个数，分别表示每堆石子的个数。Output 对应每组输入，输出的第1 行中的数是最小得分；第2 行中的数是最大得分。Sample Input 44 4 5 9Sample Output Hint 43 54#include<stdio.h>#include<memory.h>int n;int a101,s101101,t101101;int i,j,k,temp,max,min;i

47、nt 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;k<=i+j-1;k+) if(k>n) 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;k<=j-1;k+) if(i+k>n) temp=(i+k)%n; else temp=i+k; max=sik+stempj-k+tij; if(sij<max) sij=max; max=0; for(i=1;i<=n;i+) if(max<sin) max=sin; memset(s,0,sizeof(s); for(