ACM程序设计竞赛例题1

1、ACM程序设计竞赛例题1ACM程序设计竞赛例题1ACM程序设计竞赛例题1ACM程序设计竞赛例题1编制仅供参考审核批准生效日期地址： 电话：传真: 邮编:备战ACM资料习题10-1背包问题在0 / 1背包问题中，需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。 程序如下：#include void readdata();void search(int);void checkmax();void printresult();int c=35, n=1

2、0; );printf(n);printf(n);6素数环问题把从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。分析：用回溯算法，考察所有可能的排列。程序如下：#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

3、方格图，找出一条自入口（2，9）到出口（11，8）的最短路本题给出完整的程序和一组测试数据。状态：老鼠所在的行、列。程序如下：#includevoid readdata(); aij=0; .注：测试数据可在运行时粘贴上去（点击窗口最左上角按钮，在菜单中选则“编辑”/“粘贴”即可）。想一想：此程序都存在哪些问题，如果openlen太小程序会不会出错，加入代码使程序能自动报出此类错误。3.跳马给一个200200的棋盘，问国际象棋的马从给定的起点到给定的终点最少需要几步。Sample Input 0 0 1 1 Sample output 4状态：马所在的行、列。程序如下：#includevoid

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

5、切地说，若给定序列X=，则另一序列Z=是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的一个最长公共子序列。当xmyn时，必须解两个子问题，即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算X和Y的最长公共子序列时，可能要计算出X和Yn-1及Xm-1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题，即计算Xm-1和Yn-1的最长

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

8、构造最长公共子序列时要用到。最后，X和Y的最长公共子序列的长度记录于cm,n中。程序如下：#include#includeint 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。现在要把一些课桌从某些教室搬到另外一些教室，每张桌子都是从编号较小的教室搬到编号较大的教室，每一趟，都是从左到右走，搬完一张课桌后，可以继续从当前位置或往右走搬另一张桌子。输入数据：先输入n、m，然后紧接着m行输入这m

9、张要搬课桌的起始教室和目标教室。输出数据：最少需要跑几趟。Sample Input10 51 33 94 66 107 8Sample Output3分析：贪心算法，把课桌按起点从小到大排序，每次都是搬离当前位置最近的课桌。程序如下：#includeint main()structint start;int end;a100;int i,j;int n,m,min,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条封闭曲线画在

10、平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。#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难题：有排成一行的个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色编程全部的满足要求的涂法.#includeint f(int n)if(n=1) return 3;

11、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、10、20、50、100，用来凑 15元，可以用5个2元、1个5元，或者3个5元，或者1个5元、1个10元，等等。显然，最少需要2个钱币才能凑成15元。你的任务就是，给定若干个互不相同的钱币面值，编程计算，最少需要多少个钱币才能凑成某个给出的钱数。【要求】【数据输入】输入可以有

12、多个测试用例。每个测试用例的第一行是待凑的钱数值M（1 = M = 2000，整数），接着的一行中，第一个整数K（1 = K = 10）表示币种个数，随后是K个互不相同的钱币面值Ki(1 = Ki = 1000)。输入M=0时结束。【数据输出】每个测试用例输出一行，即凑成钱数值M最少需要的钱币个数。如果凑钱失败，输出“Impossible”。你可以假设，每种待凑钱币的数量是无限多的。【样例输入】156 2 5 10 20 50 10011 20【样例输出】2Impossible/* 2010年5月19日 */#include#includeusing namespace std;int m10

13、00;int M;int p;int check() .70，71，72，73.）【要求】【数据输入】一个整数N。(N不大于30000)【数据输出】从小到大排列的不大于N的与7有关的数字，每行一个。【样例输入】20【样例输出】71417#includeusingnamespacestd;boolHasSeven(inti)intflag(0);while(i)if(i%10=7)flag+;i/=10;if(flag)return1;elsereturn0;intmain()intN;coutN;for(inti=1;i!=N;i+)if(i%7=0|HasSeven(i)coutiendl;

14、连续邮资问题【问题描述】G国发行了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮票。连续邮资问题要求对于给定的n和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家至少养猪的数

15、目。【样例输入】33 15 17 2【样例输出】16#includeusing 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#include#include#include#defineMAX_POINT50/*n=50*/#defineSquare(x)(

16、x)*(x)#defineN_DIMENSION3/*定义维数*/typedefintCoordinateN_DIMENSION;/*定义坐标*/CoordinatepointMAX_POINT;/*初始坐标*/CoordinatepathMAX_POINT;/*坐标路径*/intflagMAX_POINT;/*路径标记*/intpointNum;/*坐标点数*/doublesumDistance;/*路径距离*/doubleminDistance=LONG_MAX;/*最小路径*/voidReadSampleInput()FILE*fpSampleInput=NULL;inti,j;fpSa

17、mpleInput=fopen(,rb);if(NULL=fpSampleInput)printf(Error:Opensampleinputfilefailed!n);exit(-1);fscanf(fpSampleInput,%d,&pointNum);for(i=0;ipointNum;i+) for(j=0;jN_DIMENSION;j+)fscanf(fpSampleInput,%d,&pointij);fclose(fpSampleInput);voidCopyCoordinate(Coordinatea,Coordinateb)inti;for(i=0;iN_DIMENSION;

18、i+)ai=bi;doubleCalPointDistance(Coordinatea,Coordinateb)inti;intdistance=0;for(i=0;iN_DIMENSION;i+)distance+=Square(ai-bi);returnsqrt(distance);/*核心函数：使用回溯算法遍历所有可能的路径*/voidCalMinDistance(intpointCnt)inti=0;doubledistance=;if(pointCnt=pointNum)/*已经访问完每一点*/if(sumDistanceminDistance)minDistance=sumDist

19、ance;return;if(0=pointCnt)/*从第一点开始访问*/CopyCoordinate(path0,point0);pointCnt+=1;for(i=1;iminDistance)flagi=0;sumDistance-=distance;return;CalMinDistance(pointCnt+1);/*继续计算下一点*/flagi=0;/*回溯*/sumDistance-=distance;voidWriteSampleInput(doublenumber)FILE*fpSampleOutput=NULL;fpSampleOutput=fopen(,wb);if(N

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