noi全国青少年信息学奥林匹克竞赛习题.ppt

《noi全国青少年信息学奥林匹克竞赛习题.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、设有一个N*M方格的棋盘（l＜＝N＜＝100，1＜＝M＜＝100）。(30％)求出该棋盘中包含有多少个正方形、多少个长方形（不包括正方形）。例如：当N=2，M＝3时：正方形的个数有8个：即边长为1的正方形有6个；边长为2的正方形有2个。长方形的个数有10个：即2*1的长方形有4个：1*2的长方形有3个：3*1的长方形有2个：3*2的长方形有1个：程序要求：输入：N，M输出：正方形的个数与长方形的个数如上例：输入：23输出：8，10二、把1，2，…9共9个数排成下列形状的三角形：（30％）abcdefghi

2、abcdefghi其中：a～i分别表示1，2，...9中的一个数字，并要求同时满足下列条件：(1)a

3、为N＝3，M=3的街道图：BA图二从A出发到达B共有6条可供行走的路径：1.A-A1-A2-A5-B2.A-A1-A4-A5-B3.A-A1-A4-A7-B4.A-A3-A4-A5-B5.A-A3-A4-A7-B6.A-A3-A6-A7-B若在N＊M的街道中，设置一个矩形障碍区域（包括围住该区域的的街道）不让行人通行，如图一中用“＊”表示的部分。此矩形障碍区域用2对顶点坐标给出,图一中的2对顶点坐标为:(2，2),(8，4),此时从A出发到达B的路径仅有两条。程序要求任务一：给出N，M后，求出所有从A出

4、发到达B的路径的条数。任务二：给出N，M，同时再给出此街道中的矩形障碍区域的2对顶点坐标(X1,y1),（X2，Y2），然后求出此种情况下所有从A出发到达B的路径的条数。一、问题描述：   设有下列的算式：求出中的数字，并打印出完整的算式来。三、问题描述：   若将一个正整数化为二进制，在此二进制数中，我们将数字1的个数多于数字0的个数的这类二进制数称为A类数，否则就称其为B类数。   例如：(13)10=(1101)2，其中1的个数为3，0的个数为1，则称此类数为A类数。(10)10=(1010)2，其中1的

5、个数为2，0的个数也为2，称此类数为B类数。(24)10=(11000)2，其中1的个数为2，0的个数为3，则称此类数为B类数。   程序要求：求出1-1000之中(包括1与1000)，全部A、B两类数的个数。四、问题描述：   编码问题：设有一个数组A：ARRAY[0..N-1]OFINTEGER；数组中存放的元素为0到N-1之间的整数，且A[i]<>A[j](当i<>j时)。   例如：N=6时，A=(4,3,0,5,1,2)此时，数组A的编码定义如下：A[0]的编码为0A[i]的编码为：在a[0],A[1]

6、,…A[i-1]中比A[i]的值小的个数(i=1,2,…,N-1)所以上面数组A的编码为：B=(0,0,0,3,1,2)程序要求解决以下问题：   ①给出数组A后，求出其编码；   ②给出数组A的编码后，求出A中的原数据。五、问题描述：   灯的排列问题：设在一排上有N个格子(N<=20)，在格子中放置有不同颜色的灯，每种灯的个数记为N1,N2,…Np(p表示不同颜色灯的个数)。   放灯时要遵守下列规则：   ①同一种颜色的灯不能分开；   ②不同颜色的灯之间至少要有一个空位置。   例如：N=8(格子

7、数)         R=2(红灯数)         B=3(蓝灯数)放置的方法有：R-B顺序RRBBBRRBBBRRBBBRRBBBRRBBBRRBBBB-R顺序放置的方式为12种。数据输入的方式为：N   P1(颜色，为第一个字母)N1(灯的数量)   P2                    N2     ……   Q(结束标记，Q本身不是灯的颜色)程序要求：求出一种顺序的排列方案及排列总数。BBBRRBBBRRBBBRRBBBRRBBBRRBBBRR