大学ACM考试题目及作业答案整理.docx

ACM作业与答案整理1、平面分割方法：设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。#include iostream.hint 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)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色．编程全部的满足要求的涂法.#includeiostream.hint 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;}}3、北大ACM(1942)Paths on a GridTime Limit: 1000MSMemory Limit: 30000KDescriptionImagine you are attending your math lesson at school. Once again, you are bored because your teacher tells things that you already mastered years ago (this time hes explaining that (a+b)2=a2+2ab+b2). So you decide to waste your time with drawing modern art instead. Fortunately you have a piece of squared paper and you choose a rectangle of size n*m on the paper. Lets call this rectangle together with the lines it contains a grid. Starting at the lower left corner of the grid, you move your pencil to the upper right corner, taking care that it stays on the lines and moves only to the right or up. The result is shown on the left: Really a masterpiece, isnt it? Repeating the procedure one more time, you arrive with the picture shown on the right. Now you wonder: how many different works of art can you produce? InputThe input contains several testcases. Each is specified by two unsigned 32-bit integers n and m, denoting the size of the rectangle. As you can observe, the number of lines of the corresponding grid is one more in each dimension. Input is terminated by n=m=0. OutputFor each test case output on a line the number of different art works that can be generated using the procedure described above. That is, how many paths are there on a grid where each step of the path consists of moving one unit to the right or one unit up? You may safely assume that this number fits into a 32-bit unsigned integer. Sample Input5 41 10 0Sample Output1262#in