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

ACM算法设计实验题目汇总 1020 Permutation with Repetition 1 1021 双色Hanoi塔问题Search Number 4 1023 整数划分问题Counting 6 1025 输油管道问题Integer Factorization 9 1027 邮局选址问题矩阵连乘问题最长公共子序列MAX SUM 16 1034 Number Triangles 17 1035 编辑距离问题Pebble Merging 19 1037 租用游艇问题Minimal m Sums 22 1040 Knapsack Problem 24 1041 最优装载Lecture Halls 26 1043 程序存储问题Optimal Services 30 1049 汽车加油问题1059 子集树问题1060 0-1 Knapsack 33 1061 排列树问题1062 Problem D General Search 381020 Permutation with Repetition Description 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 4 aacc Sample Output aacc acac acca caac caca ccaa 6 #include stdio.h #include algorithm using namespace std ; int ans ; int ok(char str[],int a ,int b ) {if( b a) for(int i = a ; i b ; i++) if( str[i] == str[b] ) 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,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] ) ;} }} int main(int argc, char* argv[]) {char str[1000]; int n ; while( scanf(%d,n) != EOF ) {ans = 0 ; scanf(%s,str ) ; perm(str,0,n-1) ; printf(%d\n,ans );} return 0;} 1021 双色Hanoi塔问题Description A、B、C 是3个塔座。开始时，在塔座A 上有一叠共n 个圆盘，这些圆盘自下而上， 由大到小地叠在一起。各圆盘从小到大编号为1，2，……，n，奇数号圆盘着蓝色，偶数号圆盘着红色，如图所示。现要求将塔座A 上的这一叠圆盘移到塔座B 上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则： 规则(1)：