《ACM算法设计实验题目汇总》由会员分享，可在线阅读，更多相关《ACM算法设计实验题目汇总（32页珍藏版）》请在金锄头文库上搜索。
1、ACM算法设计实验题目汇总1020 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
2、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的所有
3、不同排列。 编程任务：给定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
4、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,st
5、ri ) ; 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 上
6、，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则： 规则(1)：每次只能移动1个圆盘； 规则(2)：任何时刻都不允许将较大的圆盘压在较小的圆盘之上； 规则(3)：任何时刻都不允许将同色圆盘叠在一起； 规则(4)：在满足移动规则(1)-(3)的前提下，可将圆盘移至A，B，C 中任一塔座上。 试设计一个算法，用最少的移动次数将塔座A 上的n个圆盘移到塔座B 上，并仍按同样顺序叠置。 编程任务： 对于给定的正整数n，编程计算最优移动方案。Input 输入由多组测试数据组成。每组测试数据的第1 行是给定的正整数n。Output 对应每组输入，输出的每一行由一个正整数k和2 个字符c1 和c2 组成
7、，表示将第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 han
8、oi(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至
9、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=
10、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(%
11、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);elseprintf(%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
