算法设计实验题目汇总

1、ACM算法设计实验题目汇总1020Permutation with Repetition11036Pebble Merging191021双色 Hanoi 塔问题31037租用游艇问题211022 Search Number41038Minimal m Sums221023整数划分问题 51040Knapsack Problem241024Counting61041最优装载251025输油管道问题 81042Lecture Halls261026Integer Factorization91043程序存储问题291027邮局选址问题 111048Optimal Services301031矩阵

2、连乘问题 131049汽车加油问题301032最长公共子序列 141059子集树问题321033MAX SUM1610600-1 Knapsack331034 Number Triangles171061排列树问题361035编辑距离问题181062Problem DGeneral Search 381020 Permutation with RepetitionDescriptionR= r1,r2,rn 是要进行排列的n 个元素。其中元素 r1,r2,rn 可能相同。试设计一个算法，列出R 的所有不同排列。编程任务：给定n 以及待排列的 n个元素。计算出这 n 个元素的所有不同排列。Inp

3、ut输入由多组测试数据组成。每组测试数据的第1 行是元素个数 n， 1 <= n <= 500。接下来的 1 行是待排列的 n 个元素。Output对应每组输入，将计算出的n 个元素的所有不同排列输出，每种排列单独一行。最后1 行中的数是排列总数。Sample Input4aaccSample Outputaaccacacacca caac caca ccaa 6#include <stdio.h>#include <algorithm>usingnamespace std ;int ans ;int ok(char str,int a ,int b )if

4、( 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") ;elsefor( i = k ; i <= m ;i+)if( ok(str,k,i) )swap ( strk,stri );perm(str, k+1 , m )

5、;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 塔问题DescriptionA 、B 、C 是 3 个塔座。开始时，在塔座大到小地叠在一起。各圆盘从小到大编号为盘着红色，如图所示。现要求将塔座A置。在移动圆盘时

6、应遵守以下移动规则：规则 (1) ：每次只能移动1 个圆盘；A 上有一叠共n 个圆盘，这些圆盘自下而上，1， 2，n，奇数号圆盘着蓝色，偶数号圆上的这一叠圆盘移到塔座B 上，并仍按同样顺序叠由规则 (2) ：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则 (3) ：任何时刻都不允许将同色圆盘叠在一起；规则 (4) ：在满足移动规则(1)-(3) 的前提下，可将圆盘移至A ， B， C中任一塔座上。试设计一个算法， 用最少的移动次数将塔座 A 上的 n 个圆盘移到塔座 B 上，并仍按同样顺序叠置。编程任务：对于给定的正整数n，编程计算最优移动方案。Input输入由多组测试数据组成。每组测试

7、数据的第1 行是给定的正整数n。Output对应每组输入， 输出的每一行由一个正整数盘从塔座c1 移到塔座c2 上。k 和2个字符c1和c2组成，表示将第k 个圆Sample Input3Sample Output1 A B2 A C1 B C3 A B1 C A2 C B1 A B#include <iostream>using namespace std;int main() void hanoi(int,char,char,char); int m; cin >> m; hanoi(m,'A','B','C');re

8、turn 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科

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

10、042254100Sample Output100 2NO#include<stdio.h>#include<string.h>#define LEN 200000int aLEN,temp,mid;int sort(int *a,int low,int high) /一趟快排mid=alow;while (low<high)while (low<high && ahigh>=mid) high-;temp=alow;alow=ahigh;ahigh=temp;while (low<high && ahigh<

11、;=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;i<n;i

12、+)scanf("%d",&ai);quicksort(a,0,n-1); /for (i=0;i<n;i+) /调用快排统计不同数字的个数if(ai=s)Sum+;if(Sum=0)printf("NO");elseprintf("%d %d",s,Sum);1023整数划分问题Description将正整数n 表示成一系列正整数之和：n=n1+n2+nk，其中n1n2 nk1，k1。正整数 n 的这种表示称为正整数n 的划分。求正整数n 的不同划分个数。例如正整数6 有如下 11 种不同的划分：6；5+1；4+2，

13、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，表示有第 2 至 n+1 每行一个正整数。n 个测试用例；Output对应每组输入，输出正整数Sample Input256Sample Output7n 的不同划分个数。11#include <stdio.h>int split(int n, int m)if(n < 1 | m < 1) return 0;if(n = 1 | m = 1) return 1;if(n < m) ret

14、urn 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;i+)scanf("%d",&ai);for(i=0;i<k;i+)printf("%dn",split(ai,ai);1024Problem A:CountingDescripti

15、on问题描述：一本书的页码从自然数1 开始顺序编码直到自然数 n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第 6 页用数字 6 表示，而不是 06或 006等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1， 2， ， 9。编程任务：给定表示书的总页码的10 进制整数 n (1 n 109) 。编程计算书的全部页码中分别用到多少次数字0， 1， 2， ， 9。Input输入由多组测试数据组成。每组测试数据输入只有1 行，给出表示书的总页码的整数n。Output对应每组输入，输出共有10 行，在第 k 行输出页码中用到数字k-1 的次数

16、， k=1， 2， ，10。Sample Input11Sample Output1114111111程序代码：#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, pown=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+)sn

17、i += 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;1025 Problem B:输油管道问题Description问题描述： 某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北 )与主管道相连。如果给定n口油井的位置 ,即它们的x 坐标

18、（东西向）和y 坐标（南北向）,应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置?编程任务： 给定 n 口油井的位置,编程计算各油井到主管道之间的输油管道最小长度总和。Input输入由多组测试数据组成。每组测试数据输入的第1 行是油井数 n，1n 10000。接下来 n行是油井的位置，每行2 个整数 x 和 y， -10000 x，y 10000。Output对应每组输入，输出的第1 行中的数是油井到主管道之间的输油管道最小长度总和。Sample Input51222133-233Sample Output6#include<iostream>usin

19、g 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);cin>>aSize;int *x=new intaSize;int *y=new intaSize;for(int i=0;i<aSize;i+)cin>>xi;cin>&g

20、t;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);return total;/分两部分计算各自的最优值f=sPath(a,x,(x+y)/2);b=sPath(a,(x+y)/2+1,y);return f<b?f:b;/ 归并操作，返回这两部分中更优解1026Problem C:Integer Factoriza

21、tionDescription问题描述： 大于 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(1 n 2000000000) 。Output对应每组输入，输出计算出的不同的分解式数。Sample Input12Sample Output8#include<

22、stdio.h>#include<math.h>struct DPint 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<j)dowhile(tag.num<keyj.num && i<j) j-;if(i<j)keyi=keyj;i+;while(tag.num>=keyi.num && i<j) i+;if(i<j

23、)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<=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

24、.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 个居

25、民点散乱地分布在不同的街区中。 用 x 坐标表示东西向， 用 y 坐标表示南北向。 各居民点的位置可以由坐标 (x,y) 表示。街区中任意 2 点 (x1,y1) 和 (x2,y2) 之间的距离可以用数值 |x1-x2|+|y1-y2| 度量。 居民们希望在城市中选择建立邮局的最佳位置， 使 n 个居民点到邮局的距离总和最小。 编程任务： 给定 n 个居民点的位置 ,编程计算 n 个居民点到邮局的距离总和的最小值。Input输入由多组测试数据组成。每组测试数据输入的第来 n 行是居民点的位置，每行 2 个整数 x 和1 行是居民点数 n， 1 n 10000。接下y， -10000 x，y 1

26、0000。Output对应每组输入，输出的第1 行中的数是Sample Input51 22 2n 个居民点到邮局的距离总和的最小值。1 33 -23 3Sample Output10#include<iostream> using 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;f

27、or(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=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<<

28、;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 && 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)

29、QuickSort( arry, l,i-1);if(i<h)QuickSort( arry, j+1,h);1031Problem 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 个矩

30、阵的行及第n 个矩阵的列 , 它们之间用空格隔开 .Output你的输出应该有C 行，即每组测试数据的输出占一行，它是计算出的矩阵最少连乘积次数.Sample Input1310 100 5 50Sample Output7500#include<stdio.h>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&qu

31、ot;,&pi); /读入 pi 的值 ( 注意： p0 到 pn 共 n+1 项)for(i=1;i<=n;i+) /初始化 mii=0mii=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=i;for(k=i+1;k<j;k+)Output你的输出应该有输入包含多组测试数据。第一行为一个整数 C，表示有 C 组测试数据，接下来有每组测试数据占 1 行，它由 2 个给定序列的字符串组成，两个字符串之间用空格隔开t=m

32、ik+mk+1j+pi-1*pk*pj;if(t<mij)mij=t; /mij取最小值sij=k;printf("%d",m1n);1032Problem 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 的一个最长公共子序列。InputC 行数据，.C 行，即每组测试数据的输出占一行，它是计算出的最长公共子序列长度。Sample Input1ABCBDBA BDCABASample Output4#include <stdio.h>#include <string.h>#include <stdlib.h>void

34、 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(

35、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 < n; j +)if

36、 (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("n");for (i = 0; i < m; i +) free(ai);free(bi);free(a);free(b);return 0;void prt_lc

37、s(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);elseprt_lcs(i, j - 1, x, b);1033Problem B:MAX SUMDescription给定由 n 整数 ( 可能为负数 ) 组成的序列 a1,a2, ,an ，求该序列形如ai+ai+1,+aj 的子段和的最大

38、值。当所有的整数均为负数时定义其最大子段和为0。Input输入包含多组测试数据。 第一行为一个整数C，表示有 C 组测试数据， 接下来有2*C 行数据，每组测试数据占2 行，每组测试数据第一行是1 个整数 n，表示有 n 个整数 , 接下来一行有 n个整数 , 它们之间用空格隔开 .Output你的输出应该有C 行，即每组测试数据的输出占一行，它是计算出的最大子段和.Sample Input16-2 11 -4 13 -5 -2Sample Output20#include <stdio.h>int maxsum(int n,int *a)int sum=0,b=0,i,j;for

39、(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("%d",&ai);max=maxsum(n,a);printf("%dn",max);1034Problem D:Number TrianglesDescript

40、ion给定一个由n 行数字组成的数字三角形如下图所示。至底的一条路径，使该路径经过的数字总和最大。试设计一个算法， 计算出从三角形的顶编程任务：对于给定的由 n 行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。Input输入数据是由多组测试数据组成。第1 行是数字三角形的行数n，1n100。接下来n 行是数字三角形各行中的数字。所有数字在0 至 99之间。Output对应每组测试数据，每行输出的是计算出的最大值。Sample Input573 88 1 0274445265Sample Output30#include <stdio.h>int main

41、()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+ ) scanf("%d",&intaij ) ; for( i = n - 1 ; i > 0 ; i - )for( j = i ; j > 0 ; j - )intaij+=intai

42、+1j+1>intai+1j?intai+1j+1:intai+1j;printf("%dn",inta11 ) ;return0 ;1035 编辑距离问题Description设 A 和 B 是 2 个字符串。要用最少的字符操作将字符串A 转换为字符串B。这里所说的字符操作包括(1) 删除一个字符；(2) 插入一个字符；(3) 将一个字符改为另一个字符。将字符串A 变换为字符串B 所用的最少字符操作数称为字符串A 到 B 的编辑距离，记为d(A,B) 。试设计一个有效算法，对任给的2 个字符串A 和 B，计算出它们的编辑距离d(A,B)。编程任务：对于给定的字符串A

43、 和字符串B，编程计算其编辑距离d(A,B)。Input输入由多组测试数据组成。每组测试数据输入的第1 行是字符串A，第2 行是字符串B。Output对应每组输入，输出的每行中的数是编辑距离d(A,B)。Sample InputfxpimuxwrsSample Output5#include <iostream>#include <string>using namespace std;int main()string A1, A2;cin >> A1 >> A2;int m = A1.length();int n = A2.length();in

44、t *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 ? 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;1036Pebble MergingDescription在一个圆形操场的四周摆放着 n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的 2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将 n 堆石子合并成一堆的最小得分和最大得分。编程任务：对于给定n 堆石子 , 编程计算合并成一堆的最小得分和最大得分。Input输入由多组测试数据组成。每组测试数据输入的第 1 行是正整数 n，1n100，表示有 n 堆石子。第二行