ACM程序设计竞赛例题1

1、备战 ACM资料习题1 0-1 背包问题在 0 / 1 背包问题中，需对容量为 c 的背包进行装载。从 n 个物品中选取装入 背包的物品，每件物品 i 的重量为 wi ，价值为 pi 。对于可行的背包装载，背 包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。程序如下：#include void readdata();void search(int);void checkmax();void printresult();int c=35, n=10; );printf(n);printf(n);6 素数环问题把从 1到 20这20个数摆成一个环，要求相邻的两个数的和是一个素

2、数。分析：用回溯算法，考察所有可能的排列。程序如下：#include #include void search(int);void init();表示空格； X表示墙。程序如下：#include #include void search(int,int);int canplace(int,int);void readdata(); Floodfill给一个 2020 的迷宫和一个起点坐标，用广度优先搜索填充所有的可到达的格 子。提示：参考第 2 题。2. 电子老鼠闯迷宫如下图 1212 方格图，找出一条自入口( 2， 9)到出口( 11，8)的最短路 本题给出完整的程序和一组测试数据。状态：老

3、鼠所在的行、列。程序如下： #includevoid readdata();aij=0; 注：测试数据可在运行时粘贴上去(点击窗口最左上角按钮，在菜单中选则“编 辑”/ “粘贴”即可)。想一想： 此程序都存在哪些问题， 如果 openlen 太小程序会不会出错， 加入代码 使程序能自动报出此类错误。3. 跳马给一个 200200 的棋盘，问国际象棋的马从给定的起点到给定的终点最少需要 几步。Sample Input 0 0 1 1 Sample output 4状态：马所在的行、列。程序如下：独轮车#include void readdata(); 独轮车的轮子上有 5 种颜色，每走一格颜色变

4、化一次， 独轮车只能往前推， 也可 以在原地旋转，每走一格，需要一个单位的时间，每转 90 度需要一个单位的时 间，转 180度需要两个单位的时间。现给定一个 2020 的迷宫、一个起点、一 个终点和到达终点的颜色，问独轮车最少需要多少时间到达。状态：独轮车所在的行、列、当前颜色、方向。 另外为了方便在结点中加上到达该点的最小步数。程序如下：#includestruct colornodeint row;表示空格aij=0;.XXXX XX1 1 1 4 8 11 最长公共子序列一个给定序列的子序列是在该序列中删去若干元素后得到的序列。 确切地说， 若 给定序列 X= ，则另一序列 Z= 是

5、X的子序列是 指存在一个严格递增的下标序列 ，使得对于所有 j=1,2, ,k 有答如下：a) 最长公共子序列的结构若用穷举搜索法，耗时太长，算法需要指数时间。易证最长公共子序列问题也有最优子结构性质设序列 X=和 Y=的一个最长公共子序列 Z= ，则：i. 若 xm=yn，则 zk=xm=yn且 Zk-1 是 Xm-1和 Yn-1 的最长公共子序列；ii. 若 xmyn且 zkxm ，则 Z是Xm-1和 Y的最长公共子序列；iii. 若 xmyn 且 zkyn ，则 Z是 X和 Yn-1 的最长公共子序列。其中 Xm-1=，Yn-1= ，Zk-1= 。最长公共子序列问题具有最优子结构性质。b

6、) 子问题的递归结构由最长公共子序列问题的最优子结构性质可知，要找出 X= 和 Y= 的最长公共子序列，可按以下方式递归地进行：当 xm=yn 时，找出 Xm-1和 Yn-1 的最长公共子序列，然后在其尾部加上 xm(=yn) 即可得 X 和 Y 的一个最长公共子序列。当 xm yn 时，必须解两个子问题，即找出 Xm-1 和 Y的一个最长公共子序列及 X和 Yn-1 的一个最长公共子序列。这两个公共子 序列中较长者即为 X和 Y的一个最长公共子序列。由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。 例如，在计算 X和 Y的最长公共子序列时， 可能要计算出 X和 Yn-1 及Xm-1

7、和 Y的最长公共子 序列。而这两个子问题都包含一个公共子问题， 即计算 Xm-1和 Yn-1 的最长公共 子序列。我们来建立子问题的最优值的递归关系。用 ci,j 记录序列 Xi 和 Yj 的最长公 共子序列的长度。其中 Xi= ，Yj= 。当 i=0 或 j=0 时，空序列是 Xi 和 Yj 的最长公共子序列，故 ci,j=0 。建立递归关系 如下：c) 计算最优值由于在所考虑的子问题空间中，总共只有 (m*n) 个不同的子问题，因此，用动 态规划算法自底向上地计算最优值能提高算法的效率。计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y以) 序列 X= 和 Y= 作为输入。输

8、出两个数组 c0.m ,0.n 和 b1.m ,1.n 。其中 ci,j 存储 Xi 与 Yj 的最长公共子序列的长度， bi,j 记 录指示 ci,j 的值是由哪一个子问题的解达到的，这在构造最长公共子序列时 要用到。最后， X和 Y 的最长公共子序列的长度记录于 cm,n 中。程序如下：#include#include int lcs_length(char x, char y);int main()char x100,y100;int len;while(1)scanf(%s%s,x,y);if(x0=0) 搬桌子问题某教学大楼一层有 n 个教室，从左到右依次编号为 1、2、n。现在要把

9、一些 课桌从某些教室搬到另外一些教室， 每张桌子都是从编号较小的教室搬到编号较 大的教室，每一趟，都是从左到右走，搬完一张课桌后，可以继续从当前位置或 往右走搬另一张桌子。输入数据：先输入 n、m，然后紧接着 m行输入这 m张要 搬课桌的起始教室和目标教室。输出数据：最少需要跑几趟。Sample Input10 51 33 94 66 107 8Sample Output3分析：贪心算法， 把课桌按起点从小到大排序， 每次都是搬离当前位置最近的课 桌。程序如下：#include int main()structint start;int end;a100;int i,j;int n,m,min

10、,num,temp,used100=0;scanf(%d%d,&m,&n);for(i=0;i=temp)temp=ai.end;usedi=1;num+;min+;printf(%d,min);1、平面分割方法：设有 n 条封闭曲线画在平面上，而任何两条封闭曲线恰好相 交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割 成的区域个数。#include int f(int n)if(n=1) return 2;else return f(n-1)+2*(n-1);void main()int n;while(1)cinn;coutf(n)endl;2、LELE的 RPG难题：

11、有排成一行的个方格， 用红(Red) 、粉(Pink) 、绿(Green) 三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也 不同色编程全部的满足要求的涂法 .#includeint f(int n)if(n=1) return 3;else if(n=2) return 6; else return f(n-1)+f(n-2)*2; void main() int n;while(1)cinn; coutf(n)endl;最少钱币数：【问题描述】这是一个古老而又经典的问题。 用给定的几种钱币凑成某个钱数， 一般而言有多 种方式。例如：给定了 6 种钱币面值为 2、5、 1

12、0、20、50、100，用来凑 15 元， 可以用 5个2元、1个5元，或者 3个 5元，或者 1个 5元、1个10元，等等。 显然，最少需要 2 个钱币才能凑成 15 元。你的任务就是， 给定若干个互不相同的钱币面值， 编程计算， 最少需要多少个钱 币才能凑成某个给出的钱数。【要求】【数据输入 】输入可以有多个测试用例。 每个测试用例的第一行是待凑的钱数值 M(1 = M = 2000 ，整数)，接着的一行中，第一个整数 K(1 = K = 10 )表 示币种个数，随后是 K个互不相同的钱币面值 Ki(1 = Ki = 1000) 。输入 M=0 时结束。【数据输出 】每个测试用例输出一行，

13、 即凑成钱数值 M最少需要的钱币个数。 如 果凑钱失败，输出“ Impossible ”。你可以假设，每种待凑钱币的数量是无限多 的。样例输入】156 2 5 10 20 50 10011 20【样例输出】2Impossible/* 2010 年 5 月 19 日 */#include #include using namespace std;int m1000;int M;int p;int check() .70 ，71，72， 73. )要求】数据输入 】一个整数 N。（N 不大于 30000）数据输出】从小到大排列的不大于 N的与 7有关的数字，每行一个样例输入】20【样例输出】714

14、17# includeusing namespace std;bool HasSeven(int i)int flag(0);while(i)if( i%10 = 7) flag+;i /= 10;if(flag) return 1;elsereturn 0;连续邮资问题【问题描述】int main()int N;cout N;for(int i =1; i !=N;i+)if(i % 7 =0 |HasSeven(i)cout i endl;( smaller than 30000): G国发行了 n 种不同面值的邮票，并且规定每张信封上最多只允许贴 m张邮票。连续邮资问题要求对于给定的 n

15、 和 m的值，给出邮票面值的最佳设计， 使得可在1张信封上贴出从邮资 1 开始，增量为 1的最大连续邮资区间。例如，当 n=5和 m=4时，面值为(1,3,11,15,32) 的 5种邮票可以贴出邮资的最大连续邮资区间是 1 到 70。编程任务 : 对于给定的正整数 m 和 n，计算出邮票面值的最佳设计。【要求】【数据输入 】输入数据每一行给出 2 个正整数 m和 n 的值( 1=n，m=9)，最后 以 0 0 表示文件结束。【 数据输出 】对于输以假定 (ai, aj) = 1. 输出包含一个正整数，即为 Andy 家至少养猪的数目【样例输入】33 15 17 2【样例输出】16#inclu

16、de using namespace std;class Stampfriend int MaxStamp(int ,int ,int );private:int Bound(int i);void Backtrack(int i,int r);int n; 第 1 行 n, 然后 n 行 3 个整数坐标【数据输出】每组一行 ,代表最小权和 【样例输入】30 0 01 1 01 -1 0 【样例输出】#include标 */#includeCoordinate pathMAX_POINT;#include/*#include坐标路径 */int flagMAX_POINT;#defineMAX

17、_POINT 50/*/* 路径标记 */n =50*/int pointNum;#define Square(x) (x)*(x)/* 坐标点数 */#define N_DIMENSION 3doublesumDistance;/* 定义维数*/typedef intCoordinateN_DIMEN/*路径距离 */SION;/* 定义坐标 */doubleminDistance =LONGMAX/*最CoordinatepointMAX_POINT;小路径*/* 初 始坐 ai = bi;FILE*fpSampleInput= NULL;int i, j;doubleCalPointDi

18、stance( Coordinatea,Coordinate b )fpSampleInput = fopen( ,rb);inti;if (NULL = fpSamintdistance = 0;pleInput)for( i = 0; i N_DIMENSION; i+ )printf(Error:distance += SqOpen sampleinput file faiuare(ai- bi );led !n);return sqrt( distanceexit( -1 ););void ReadSampleInput()N_DIMENSION; i+ )fscanf( fpSamp

19、leInput%d, &pointNum );for( i =0; i pointNum;i+ )for( j =0; j N_DIMENSION; j+ )fscanf( fpSampleInput, %d, &point ij );fclose( fpSampleInput);void CopyCoordinate( Coordinat e a, Coordinate b ) /* 核心函数：使用回溯算法遍历所 有可能的路径*/ void CalMinDistance( int poin tCnt )int i = 0;double distance = ;if ( pointCnt =

20、poi ntNum ) /* 已 经 访 问 完 每 一 点 */if ( sumDistan ce minDistance )flagi = 0;sumDistance -= distance;for pointNum;( i+1; i return= 1 ) 点 */*if ( flagi 跳过已经标记的continue;stance( pointCnt+1*/ 继续计算下一点);CalMinDi/*flagi0;elsedinate( i ); 中 */CopyCoorpointpathpointCnt,/* 将 点 拷 贝 到 路 径flagi/* 回溯distance;*/sumDi

21、stance1;/* 标记该点 */* 计 算 点距离 */distance= CalPointDistance( pathpoi ntCnt-1, pathpointCnt );sumDistance += distance;/* 如 果 总距离已经超过当前最小距离，则回 溯 */void WriteSampleInput( double number )FILE *fpSampleOutput = NULL;fpSampleOutput = fopen( ,wb);if (NULL = fpSampleOutput)printf(Error:Open sample outputfilefa

22、iled !n);exit( -1 );intmain()ReadSampleInput();fprintf(fpSampleOutputCalMinDistance( 0 );, %.1lf, number );WriteSampleInput( minDistance );fclose(fpSampleOutput);return 0;对于 1 背包问题，如果该题一般化，那就是没有没有那个大米袋数，每种为 1 袋，对于这个问题可以得到以下结论设 numj 为用 j 元金额买下 前 i 种大米的最大质量，则题目要就的就是 nummn ；下面分 3 种情况讨论当 i ， j ，一个为 0 时，很明显， num0 = 0, num0j = 0如果