信息学初赛问题求解解题(共5页)

《信息学初赛问题求解解题(共5页)》由会员分享，可在线阅读，更多相关《信息学初赛问题求解解题(共5页)（5页珍藏版）》请在装配图网上搜索。

1、精选优质文档-倾情为你奉上信息学初赛问题求解部分（第14-18届）（第十四届）1书架上有4本不同的书A、B、C、D。其中A和B是红皮的，C和D是黑皮的。把这4本书摆在书架上，满足所有黑皮的书都排在一起的摆法有_种。满足A必须比C靠左，所有红皮的书要摆在一起，所有黑皮的书要摆放在一起，共有_种摆法。解: 1、分析（1）CDAB (2) CDBA (3)ACDB (4)BCDA (5)ABCD (6)BACD (7)DCAB (8)DCBA (9)ADCB (10)BDCA (11)ABDC (12)BADC 2、分析(1)ABCD （2）BACD (3)ABDC (4)BADC2有6个城市，任何

2、两个城市之间都有一条道路连接，6个城市两两之间的距离如下表所示，则城市1到城市6的最短距离为_ 7_。城市1城市2城市3城市4城市5城市6城市102311215城市22025312城市3320365城市4153079城市51236702城市615125920解：(1-2-5-6) 城市1到城市2，到城市5，到城市6是2+3+2=7.是距离最短的。（第十五届）1. 小陈现有2个任务A，B要完成，每个任务分别有若干步骤如下：A=a1-a2-a3，B=b1-b2-b3-b4-b5。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此

3、任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如a2-b2-a3-b3是合法的，而 a2-b3-a3-b2是不合法的。小陈从B任务的b1步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务A，其他的都忘了。使计算小陈饭前已做的可能的任务步骤序列共有 _ 种。解法一： 相当于以前的A到B路程的问题a3 0 1 4 10 20 35 a2 0 1 3 6 10 15 a1 0 1 2 3 4 5 0 1 1 1 1 1 b1 b2 b3 b4 b5 能明白吧。然后把a3那一行加起来1+4+10+20+35=70解法二： 排列组合+加法原理

4、B任务中的b1一定做，而且肯定是第一个做的。除了b1外， 第一类：完成A任务 只有1种。 第二类：完成A任务和b2 有C(4,1)=4种。 第三类：完成A任务和b2、b3 有C(5,2)=10种。 第四类：完成A任务和b2、b3、b4 有C(6,3)=20种。 第五类：完成A任务和b2、b3、b4、b5有C(7,4)=35种。 加起来1+4+10+20+35=70。2. 有如下的一段程序：1. a:=1;2. b:=a;3. d:=-a;4. e:=a+d;5. c:=2*d;6. f:=b+e-d;7. g:=a*f+c;现在要把这段程序分配到若干台（数量充足）用电缆连接的PC上做并行执行。

5、每台PC执行其中的某几个语句，并可随时通过电缆与其他PC通讯，交换一些中间结果。假设每台PC每单位时间可以执行一个语句，且通讯花费的时间不计。则这段程序最快可以在_单位时间内执行完毕。注意：任意中间结果只有在某台PC上已经得到，才可以被其他PC引用。例如若语句4和6被分别分配到两台PC上执行，则因为语句6需要引用语句4的计算结果，语句6必须在语句4之后执行。解: 第一时间1，第二时间2和3，第三时间4和5，第四时间6，第五时间7。（第十六届）1、LZW编码是一种自适应词典编码。在编码的过程中，开始时只有一部基础构造元素的编码词典，如果在编码的过程中遇到一个新的词条，则该词条及一个新的编码会被追

6、加到词典中，并用于后继信息的编码。举例说明，考虑一个待编码的信息串：“xyx yy yy xyx”。初始词典只有3个条目，第一个为x,编码为1；第二个为y，编码为2；第三个为空格，编码为3；于是串“xyx”的编码为1-2-1（其中-为编码分隔符），加上后面的一个空格就是1-2-1-3。但由于有了一个空格，我们就知道前面的“xyx”是一个单词，而由于该单词没有在词典中，我们就可以自适应的把这个词条添加到词典里，编码为4，然后按照新的词典对后继信息进行编码，以此类推。于是，最后得到编码：1-2-1-3-2-2-3-5-3-4。现在已知初始词典的3个条目如上述，则信息串“yyxy xx yyxy x

7、yx xx xyx”的编码是 解：2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6（或）2、队列快照是指在某一时刻队列中的元素组成的有序序列。现有3个正整数元素依次入队、出队。已知它们的和为8，则共有_种可能的不同的队列快照（不同队列的相同快照只计一次）。例如，5 1、4 2 2、都是可能的队列快照；而7不是可能的队列快照，因为剩下的2个正整数的和不可能是1。解：49（第十七届）1、每份考卷都有一个 8 位二进制序列号。当且仅当一个序列号含有偶数个 1 时，它才是有效的。例如，、 都是有效的序列号，而 不是。那么，有效的序列号共有_个解：这是个排列组合问题中的组合问题。 8个

8、二进制各不干涉，且只有2中选择即0或1，满足题意的序列号序列号中有0个1的有1个，序列号中有2个1的有28个，4个1的有70个，6个1的有28个，8个1的有1个。得到：1+28+70+28+1=1282、定义字符串的基本操作为：删除一个字符、插入一个字符和将一个字符修改成另一个字符这三种操作。将字符串 A 变成字符串 B 的最少操作步数，称为字符串 A 到字符串 B 的编辑距离。字符串ABCDEFG到字符串BADECG的编辑距离为_。解：编辑距离为3ABCDEFG 删除A 得出 BCDEFG (A) BCDEFG 将C替换成A 得出 BADEFG (CA) BADEFG 将F替换成C 得出BA

9、DECG (FC)（第十八届）1、如果平面上任取n个整点（横纵坐标都是整数），其中一定存在两个点，它们连线的中点也是整点，那么n至少是_。 解：5想象横纵交错的网格纸，就像棋盘那样的，每个横纵线交点就是一个整点。如下图：任意三个点如果共线，即处在水平，竖直，或者对角线上，则其中定存在两个点满足连线中点是整点。如果n=2，取两个连续的整点，那么连线中点不是整点。如果n=3，取水平两个连续的点，垂直也两个连续的点，组成三角形。那么连线中点不是整点。如果n=4，取四个整点组成一个正方形，则连线中点不是整点。而取5个点的话，必然有两个点的连线中点是整点。2、在NOI期间，主办单位为了欢迎来自各国的选手

10、，举行了盛大的晚宴。在第十八桌，有5名大陆选手和5名港澳选手共同进膳。为了增进交流，他们决定相隔就坐，即每个大陆选手左右旁都是港澳选手，每个港澳选手左右旁都是大陆选手。那么，这一桌一共有_种不同的就坐方案。注：如果在两个方案中，每个选手左右相邻的选手相同，则视为同一种方案。解1：2880相当于1个圆，十个人。先随便找个座，让人去坐，有10个可能，然后顺时针走，下一个座就有5种可能，再下一个就4个，再下一个还是4个，以此类推，就是10*5*4*4*3*3*2*2*1*1。这其中有重复的，同一种坐法，可以绕着桌子走一圈，就是上一个人坐到下一个人的位置，串一下，这样所有坐法就算重复了10次，再除以1

11、0就行了。就是5*4*4*3*3*2*2*1*1。解2：2880首先安排5个大陆选手相隔就坐，他们的位置是任意的，有P（5，5）种坐法，然后再安排五个港澳选手，是共同进膳应该只有5个空，5个人坐5个空，也可以随意坐，也有P（5，5）种坐法，然后相乘。可到这里并不是就结束了，因为这里面包含了重复的，可是重复的情况非常极端，“每个选手左边相邻的选手均相同”，每一种方案，每个人都往左或者往右移动一个位子，两个位子，三个位子跟原先的还是一样的方案，也就是说每十种方案里一共有5种是重复的。所以要去除重复，除以5。所以应该是P（5，5）*P（5，5）/5。附：排列组合原理一、加法原理与乘法原理1、加法原理

12、： 做一件事情，完成它可以有n类办法，在第一类办法中有m1 种不同的方法，在第二类办法中有 m2种不同的方法，在第n类办法中有mn种不同的方法。那么完成这件事共有 N=m1+m2+.+mn 种不同的方法。2、乘法原理： 做一件事情，完成它需要分成n个步骤，做第一步有m1 种不同的方法，做第二步有 m2种不同的方法，做第n步有 种mn不同的方法，那么完成这件事有 N=m1*m2*.*mn 种不同的方法。3.两个原理的区别：一个与分类有关，一个与分步有关；加法原理是“分类完成”，乘法原理是“分步完成”。二、排列与组合的概念与计算公式1、排列及计算公式从n个不同元素中，任取m(1mn)个元素按照一定

13、的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(mn)个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号 p(n,m)表示。当mn时称为选排列，其排列数记做p(n,m)；m=n时称做全排列，记为p(n,n)，显然p(n,n)=n!。p(n,m)=n(n-1)(n-2)(n-m+1)= n!/(n-m)!规定0!=1。根据排列的定义，两个排列相同，当且仅当两个排列的元素完全相同，且元素的排列顺序也相同。2、组合及计算公式从n个不同元素中，任取m(mn)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(mn)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。用符号c(n,m) 表示。专心-专注-专业