当前位置:首页 >> 学科竞赛 >>

信息学奥赛普及组1-18届问题求解题解析


历届“问题求解”解析(2013 竞赛辅导)
问题求解是信息学竞赛初赛中常见题型,它共两题,每题 5 分,共 10 分,十六届增加了比重,有三题, 占 15 分。诸如寻找假币、博弈原理、抽屉原理、容斥问题、排列组合、逻辑推理、递推关系等问题出现在 问题求解中。 (相关问题的具体讲解根据需要考虑发讲义) 第一届(逻辑推理问题) 1. 有标号为 A、B、C、D 和 1、2、3

、4 的 8 个球,每两个球装一盒,分装 4 盒。标号为字母的球与标号 为数字的球有着某种一一对应的关系(称为匹配) ,并已知如下条件: ① 匹配的两个球不能在一个盒子内。 A B C D ② 2 号匹配的球与 1 号球在一个盒子里。 4 3 1 2 ③ A 号和 2 号球在一个盒子里。 ④ B 匹配的球和 C 号球在一个盒子里。 ⑤ 3 号匹配的球与 A 号匹配的球在一个盒子里。 ⑥ 4 号是 A 或 B 号球的匹配球。 ⑦ D 号与 1 号或 2 号球匹配。 请写出这四对球匹配的情况。 第四届(递推、树、图) 1. 已知一个数列 U1,U2,U3,?,UN,? 往往可以找到一个最小的 K 值和 K 个数 a1,a2,?,an 使得数列 从某项开始都满足: UN+K=a1UN+K-1+a2UN+K-2+??+akUN (A) 例如对斐波拉契数列 1,1,2,3,5,?可以发现:当 K=2,a1 =1,a2 =1 时,从第 3 项起(即 N>=1) 都满足 U n+2 =Un+1+Un 。试对数列 13,23,33,?,n3,?求 K 和 a1,a2, ?,aK 使得(A)式成立。 当 K= 4,a1,a2,…,ak 为 a1=4, a2=6, a3=4,a4=-1 对数列 132333,…,n3,…(A)成立。 2.给出一棵二叉树的中序遍历:DBGEACHFI 与后序遍历:DGEBHIFCA 画出此二叉树。 3.用邻接矩阵表示下面的无向图: 表示该无向图的邻接矩阵为 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0 A B D G E H C F I

第五届(递推) 将 Ln 定义为求在一个平面中用 n 条直线所能确定的最大区域数目。例如:当 n=1 时,L1=2,进一步考虑,用 n 条折成角的直线(角度任意) ,放在平面上,能确定的最大区域数目 Zn 是多少?例如:当 n=1 时,Z1=2 (如下图所示) 当给出 n 后,请写出以下的表达式:Ln = ______________ 2、Zn = _______________ 答案为:Ln=n(n+1)/2+1(n≥0) Zn=L2n-2n=2n2-n+1 解析:本题实质是求直线或折线将一个平面分成的最大区域数,从两个方面考虑: (1)求在一个平面中用 n 条直线所能确定的最大区域数; n=1,L1=2, F(1)=2 n=2,L2=4, F(2)=F(1)+2 n=3,L3=7, F(3)=F(2)+3 n=4,L4=11, F(4)=F(3)+4 ?? 所以, F(n)=F(n-1)+n 把上面的 n 个等式左右相加,化简得出:F(n)=2+2+3+4+??+n 即:L(n)=n*(n+1)/2+1
1

(2)求在一个平面中用 n 条折线所能确定的最大区域数; n=1,Z1=2, F(1)=0+2 n=2,Z2=7, F(2)=1*(2*2-1)+4 n=3,Z3=16, F(3)=2*(2*3-1)+6 n=4,Z4=29, F(4)=3*(2*4-1)+8 ?? 所以, F(n)=(n-1)*(2*n-1)+2*n 即:Z(n)=(n-1)*(2*n-1)+2*n 几何+归纳+组合数学! 第六届(树与递推) 1. 已知,按中序遍历二叉树的结果为:abc 问:有多少种不同形态的二叉树可以得到这一遍历结果,并画出这些二叉树。 有 5 种不同形态的二叉树可以得到这一遍历结果; 可画出的这些二叉树为: ① a ② b ③ a ④ c ⑤ c \ / \ \ / / b a c c a b \ / \ / c b b a 2. 设有一个共有 n 级的楼梯,某人每步可走 1 级,也可走 2 级,也可走 3 级,用递推公式给出某人从底 层开始走完全部楼梯的走法。例如:当 n=3 时,共有 4 种走法,即 1+1+1,1+2,2+1,3。 答案:F(n)=f(n-1)+f(n-2)+f(n-3) n>=4; F(1)=1; f(2)=2; f(3)=4; 解析:两种方法,一是“猜”+“凑” ,从具体的 n=1,2,3??算起,只能算比较简单的,容易错;二是用组 合数学和归纳法进行推导,一般先假设 F (n)= a*F(n-1)+b*F (n-2)+c*F (n-3)+??, 然后算 a,b,c?? 直到某个系数=0 就结束,再代入式子中。 F(1)=1 F(2)=2 F(3)=4 F(N)=F(N-3)+F(N-2)+F(N-1) (N≥4) 推导:对于 n 级楼梯,可以有下面几种走法: 1. 最后走一级,则有 f(n-1)种 2. 最后走两级,则有 f(n-2)种 3. 最后走三级,则有 f(n-3)种 第七届(树与排列组合) 1. 已 知 一 棵 二 叉 树 的 结 点 名 为 大 写 英 文 字 母 , 其 中 序 与 后 序 遍 历 的 顺 序 分 别 为 : CBGEAFHDIJ 与 CGEBHFJIDA 则该二叉树的先序遍历的顺序为: ABCEGDFHIJ 2.平面上有三条平行直线,每条直线上分别有 7,5,6 个点,且不同直线上三个点都不在同一条直线上。问 用这些点为顶点,能组成多少个不同四边形? C(7,2)*(5+6)+C(5,2)*(7+6)+C(6,2)*(7+5)+7*6*5 =21*11+10*13+15*12+210=231+130+180+210=751 第八届(排列与递推) 1. 在书架上放有编号为 1 ,2 ,.,n 的 n 本书。现将 n 本书全部取下然后再放回去,当放回去时要求每 .. 本书都不能放在原来的位置上。例如:n = 3 时: 原来位置为:1 2 3 放回去时只能为:3 1 2 或 2 3 1 这两种 问题:求当 n = 5 时满足以上条件的放法共有多少种?(不用列出每种放法) 解法一:c(5,0)*5!-c(5,1)*4!+c(5,2)*3!-c(5,3)*2!+c(5,4)*1!-c(5,5)*0!=60-20+5-1=44

1? ? 1 1 n!?1 ? ? ? ? ? (?1) n ? 1! 2! n! ? 。 解法二:n 封装入 n 个信封时全部装错的装法总数为 ?
2

通常称为伯努利一欧拉错装信封问题,又称为乱序排列,即把 n 个元素的排列 a1,a2,L,an 重新排列, 使每个元素都不在原来的位置上的排列问题。因此只要你代入公式就行 2. 设有一棵 k 叉树,其中只有度为 0 和 k 两种结点,设 n 0 ,n k ,分别表示度为 0 和度为 k 的结点个数, 试求出 n 0 和 n k 之间的关系(n 0 = 数学表达式,数学表达式仅含 n k 、k 和数字) 。n0 和 nk 之间的关系 为:n0=(k-1) nk+1。 第九届(图与集合) 1.无向图 G 有 16 条边,有 3 个 4 度顶点、4 个 3 度顶点,其余顶点的度均小于 3,则 G 至少 11 个 顶点。 2. 某年级学生共选修 6 门课程,期末考试前,必须提前将这 6 门课程考完,每人每天只在下午至多考一门 课程,设 6 门课程为 C1,C2,C3,C4,C5,C6,S(Ci)为学习 Ci 的学生集合。已知 S(Ci)∩S(C6)≠ф ,i=1, 2,...,5,S(Ci)∩S(Ci+1)≠ф ,i=1,2,3,4,S(C5)∩S(C1)≠ф ,问至少安排_4__天才能考完这 6 门课程。 第十届(递推) 1. 75 名儿童到游乐场去玩。他们可以骑旋转木马,坐滑行铁道,乘宇宙飞船。已知其中 20 人这三种东西都 玩过,55 人至少玩过其中的两种。若每样乘坐一次的费用是 5 元,游乐场总共收入 700,可知有 名儿 童没有玩过其中任何一种。 设 a1,a2,a3 分别是仅仅玩过一种游戏的人数, 仅仅玩过 2 种游戏的人数, 仅仅玩过三种的人数。 因此有 a2+a3 = 55, a3=20, a1+2*a2+3*a3= 700/5;==>a1= 10 所以结果就是 75-a1-a2-a3=10 名 2. 已知 a, b, c, d, e, f, g 七个人中,a 会讲英语;b 会讲英语和汉语;c 会讲英语、意大利语和俄语;d 会讲汉 语和日语;e 会讲意大利语和德语;f 会讲俄语、日语和法语;g 会讲德语和法语。能否将他们的座位安排在 圆桌旁,使得每个人都能与他身边的人交谈?如果可以,请以“a b”开头写出你的安排方案: abdfgec 第十一届(排序与最火柴) 1. 将数组{32, 74, 25, 53, 28, 43, 86, 47}中的元素按从小到大的顺序排列,每次可以交换任 意两个元素,最少需要交换次。 思路一:用直接选择排序实现:

25,74,32,53,28,43,86,47 25,28,32,53,74,43,86,47 25,28,32,53,74,43,86,47 25,28,32,43,74,53,86,47 25,28,32,43,47,53,86,74 25,28,32,43,47,53,86,74 25,28,32,43,47,53,74,86

第一次:32<-->25 第二次: 28<-->74 第三次:43<-->553 第五次:47-->74 第五次:74<-->86

思路二:首先排序 给每个数字标上序号 {32,74,25,53,28,43,86,47} {3 ,7 ,1 ,6 ,2 ,4 ,8 ,5 }再和标准序列 {1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 }比较 找出其中所有的"环" ,这里的"环"就是指它们互相交换之后能成为标准序列的最小集合 比如 这里{1,3}是一个"环", {7,2,5,8}是一个"环"。 具体找法很简单 首先确定一个不在已找出"环"中的数字。 例如第一次从 3 开始,3 对应标准序列的 1 再 找 1 对应的标准序列 3 3 回到了开始的数字 那么这个环就是{1, 3}第二次从 7 开始, 7->2 2->5 5->8 8->7 所以第二个环是{7,2,5,8} 第三个环是{6,4} 这样所有的数字都在环中了 交换的次数=(环中 数字总数-环数)=8-3=5 2. 一堆火柴有 N 根,A、B 两人轮流取出。每人每次可以取 1 根或 2 根,最先没有火柴可取的人为败方,
3

另一方为胜方。如果先取者有必胜策略则记为 1,先取者没有必胜策略记为 0。当 N 分别为 100,200, 300,400,500 时,先取者有无必胜策略的标记顺序为(回答应为一个由 0 和/或 1 组成的字符串) 。 答案:11011 规律:每次可以取 1..m 根火柴(n 为正整数,且 1<=m<N) 则 N=k(m+1) 后手胜,N!=k(m+1)先手胜(k 为 正整数),N=3k 后手胜和 N!=3k 先手胜(k 为正整数) 补:(取石子游戏)现有 5 堆石子,石子数依次为 3,5,7,19,50,甲乙两人轮流从任一堆中任取(每次只能取自 一堆,不能不取),取最后一颗石子的一方获胜.甲先取,问甲有没有获胜策略(即无论乙怎样取,甲只要不失误, 都能获胜) 如果有,甲第一步应该在哪一堆里取多少 请写出你的结果。 规律:将所有的堆的石子数化为二进制后,如果所有数位上的 1 的个数都是偶数(相加不考虑进位,为零) 那么先取者必败;如果有些位上的 1 的个数是奇数,先取者能够将所有数位上的 1 的个数都变为偶数的话, 那么先取者必胜。 (也可以用 or 不考虑进位来解决)

例: 本题: 可见,只有最高位的 1 是奇数个,其他位上都是偶数个。 所以只需要将最高位的 1 取走即可必胜。 二进制的 100000 就是 10 进制的 32,所以要将 50 个石子的那堆 取 32 个,取掉就变成偶数个数目。于是先取者必胜。以后无论对方怎么取,始终保证每一位上的 1 的个数 是偶数即可(一种简单的方法是,他在一堆中取几个,你在另一堆中也取几个就可以)。 第十二届(递推) 1.将 2006个人分成若干不相交的子集,每个子集至少有 3个人,并且: (1)在每个子集中,没有人认识该子集的所有人。 (2)同一子集的任何 3个人中,至少有 2个人互不认识。 (3)对同一子集中任何 2个不相识的人,在该子集中恰好只有 1个人认识这两个人。 则满足上述条件的子集最多能 有 个? 显然集合的人数为 3 人以上。4 人构造不出满足条件的情况,下面构造 5 人的情况:(存在边,表示两个人相互认识) 故集合个数为 2006 div 5=401 2.将边长为 n的正三角形每边 n等分,过每个分点分别做另外两边的平行线,得到若干个正三角形, 我们称为小三角 形。正三角形的一条通路是一条连续的折线,起点是最上面的一个小三角形,终点是最 下面一行位于中间的小三角形。 在通路中, 只允许由一个小三角形走到另一个与其有公共边的且位于同 一行或下一行的小三角形, 并且每个小三角形不 能经过两次或两次以上(图中是 n=5 时一条通路的例 子)设 n=10,则该正三角形的不同的通路的总数为_ 。 9! =362880 _。 解析:好的解题习惯是,通过人脑对小规模数据的求解,分析出问题的规律,从而得到解决问题的方法。 本题 n=10,而最后一层固定为中间的小三形,所以对结果有影响的,就 9 层。我们可以假设,对结果 有影响的层数: 如果只有一层,结果是什么(1) 如果有两层呢(1×2) 三层?(1×2×3) ?? 自然得出答案

4

第十三届(排列组合与报数) 1.给定 n 个有标号的球,标号依次为 1,2,?,n。将这 n 个球放入 r 个相同的盒子里,不允许有空盒,其 不同放置方法的总数记为 S(n,r)。 例如, S(4,2)=7, 7 种不同的放置方法依次为{(1) , (234)} , {(2) , (134)} , {(3) , 这 (124)} , {(4) , (123)} , {(12) , (34)} , {(13) , (24)} , {(14) , (23)}。当 n=7,r=4 时,S(7,4)=标准答案:350 解法一: 此题应用递归思想做,很容易知道 S(n,1)=1,为了利用这点,先分析 S(n-1,r)与 S(n-1,r-1)的情况,而 S(n.r)=S(n-1,r)*r+(n-1,r-1)其具体分析如下: 假设已知 n-1 个球放置的情况数,如今要多加入一个球,有两种新情况:一是放入原有球的箱子,即情况数 为 S(n-1,r)*r(每种情况中放入任意一箱子都是新情况,所以乘以箱子数 r)二是取出所有球,让新加入的 球独占一个箱子,则余下 r-1 个箱子可放球,有 n-1 个球可用来放,即情况数为 S(n-1,r-1)。 综上,得出 S(n.r)=S(n-1,r)*r+(n-1,r-1) 解法二: 7 个球放入 4 个箱子无非是 2+2+2+1 或者 3+2+1+1 或者 4+1+1+1 三种情况。所以分别求解再加起 来:C(7,1)*C(6,2)*C(4,2)*C(2,2)/P(3,3)+C(7*3)*C(4,2)+C(7,4)。 2.N 个人在操场里围成一圈,将这 N 个人按顺时针方向从 1 到 N 编号,然后从第一个人起,每隔一个人让 下一个人离开操场,显然,第一轮过后,具有偶数编号的人都离开了操场。依次做下去,直到操场只剩下一 个人,记这个人的编号为 J(N),例如,J(5)=3,J(10)=5,等等。 则 J(400)= 。 (提示:对 N=2m+r 进行分析,其中 0≤r<2m) 。 把 N 写成 2 的 K 次方加 X 的形式 则 J[N]=2X+1 400=2 的 8 次方加 144 所以是第 2*144+1=289 个人 第十四届 1. 有 6 个城市,任何两个城市之间有一条道路连接,6 个城市之间两两之间的距离如下表表示,则城市 1 到城市 6 的最短距离为___7_____。 城市 1 城市 1 城市 2 城市 3 城市 4 城市 5 城市 6 0 2 3 1 12 15 城市 2 2 0 2 5 3 12 城市 3 3 2 0 3 6 5 城市 4 1 5 3 0 7 9 城市 5 12 3 6 7 0 2 城市 6 15 12 5 9 2 0

2.书架上有 21 本书,编号从 1 到 21 从中选 4 本,其中每两本的编号都不相邻的选法一共有 ___________________种。 标准答案是 3060 种。3060=C(18,4)。这个答案可以怎么推到呢? 一种方法是,先把选到的 4 本书提出来不考虑,也先不考虑选法的数量(一会我们可以看出这一点) 。 剩下的 17 本书的前后我们一共要插入 4 本书,也就是说有 18 个位置等待插书。一共要插入 4 本书,也不能 有两本书插入同一个位置,所以最后的插法个数为 C(18,4),很显然,因为这 21 本书是有序的,所以一开始 我们假设抽出的 4 本书不用考虑有多少情况,因为每种情况和一种选法对应了。 第十五届 1. 拓扑排序是指将有向无环图 G 中的所有顶点排成一个线性序列,使得图中任意一对顶点 u 和 v,若<u, v>∈E(G),则 u 在线性序列中出现在 v 之前,这样的线性序列成为拓扑序列。如下的有向无环图,对其顶 点做拓扑排序,则所有可能的拓扑序列的个数为______。 【分析】432
5

用排列组合即可,先确定 12346 的顺序,然后将 7 插入内部有两个位置可选,然后将 5 插入时候,可以 有 6 个位置选择。最后,放 89 的时候,考虑两种情况,89 在一起,有 8 个位置选;89 不在一起,8 个位置 选 2 个。 C(2,1)× C(6,1)× [C(8,1)+C(8,2)]=2× (8+28)=432 6×

2、某个国家的钱币面值有 1,7,7^2,7^3 共计四种,如果要用现金付清 10015 元的货物,假设买卖 双方各种钱币的数量无限且允许找零,那么交易过程中至少需要流通______张钱币。 【分析】35 10015 化成 7 进制数是 41125,正常是 4×7+1=29 张 7^3 面额的,1 张 7^2 面额,2 张 7 面额的,5 张 1 面额的。 因为可以无限且找零,并要求最少流通数量。这样就把 7 进制上大于等于 4 的数 a,用找零 7-a 的方法代替,这样就能达到最少。 这里 29、1、2、5 中只有 5 是大于 4 的,所以用一张大额的,并 7-5 找 零的方法计算。这样,总数 29+1+2+(1+7-5)=35 张。 第十六届 1.LZW 编码是一种自适应词典编码。在编码的过程中,开始时只有一部基础构造元素的编码词典,如果在 编码的过程中遇到一个新的词条,则该词条及一个新的编码会被追加到词典中,并用于后继信息的编码。 举例说明,考虑一个待编码的信息串:“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 个条目如上述,接收端收到的 编码信息为 2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6,则解码后的信息串是”____________”。 【分析】:x-- 1 y--2 - 3 2-2-1-2-3 yyxy ---4 xx—5 xyx—6 yyxy xx yyxy xyx xx xyx 2.无向图 G 有 7 个顶点,若不存在由奇数条边构成的简单回路,则它至多有__________条边。

6

3.记 T 为一队列,初始时为空,现有 n 个总和不超过 32 的正整数依次入列。如果无论这些数具体为何值, 都能找到一种出队的方式,使得存在某个时刻队列 T 中的数之和恰好为 9,那么 n 的最小值是___________。 答案:18 【分析】 证明:设这些数依次为 a1, a2, a3, ?, an,且记 Si 为前 i 项和,规定 S0=0。很明显 Si 单调递增,且对 任意 i 有 0<=Si<=32。 我们可以以 Si 为顶点构造一张图,两点 Si,Sj 间连边当且仅当|Si-Sj|=9(图中数字为 Si 的编号,即 i): 0–9–18–27 1–10–19–28 2–11–20–29 3–12–21–30 4–13–22–31 5–14–23–32 6–15–24 7–16–25 8–17–26 我们从这个图中选择一些顶点,将它们的编号排序作为一个可能的序列,比如选择 0, 1, 10, 2, 13, 16, 排序后得 0, 1, 2, 10, 13, 16,作差得 ai 依次为 1,1,8,3,3 显然有 a2+a3=9 即满足条件 可以发现,若我们选择了图中的两个顶点,且它们之间连边,那么就存在一个和为 9 的子序列 那么,倘若对于某个 n,我们能从图中选择 n 个顶点,使得任意两点间没有边,那么这个 n 就是不满足条件 的 事实上,我们最多可以选择 18 个顶点,使得它们之间没有边相连: 第 0 行~第 5 行每行可以选第一、三个顶点或第二、四个顶点 最多共选 10 个 第 6 行~第 8 行每行可以选第一、三个顶点 最多选 8 个 注意到 S0=0 是必须选的,那么也就是说不满足条件的 n 的最大值是 17 由鸽巢原理,若我们选择 18 个顶点,必有 2 个顶点之间有边连接,即必存在一个子序列的和为 9 所以答案就是 18。 十七届 第 1.平面图可以在画在平面上,且它的边仅在顶点上才能相交的简单无向图。4 个顶点的平面图至少有 6 条边,如右图所示。那么,5 个顶点的平面图至少有________条边。

平面图中点数 n 与边数 m 之间的关系是:m<=3n-6,当 n=5 时,m 的最大值为 9。 2.定义一种字符串操作,一次可以将其中一个元素移到任意位置。举例说明,对于字符串“BCA”可以将 A 移到 B 之前, 变字符串 “ABC” 如果要将字符串 。 “DACHEBGIF” 变成 “ABCDEFGHI” 最少需要________ 次操作。
7

求出给定的长度为 n 的字符串的最长上升序列的长度 m,最小的操作次数为 n-m

(第十八届)
1、如果平面上任取n个整点(横纵坐标都是整数),其中一定存在两个点,它们连线的中点也 是整点,那么n至少是__________。 解:5 想象横纵交错的网格纸,就像棋盘那样的,每个横纵线交点就是一个整点。如下图: 任意三个点如果共线,即处在水平,竖直,或者对角线上,则其中定存在两个点满足连线中点

是整点。 如果n=2,取两个连续的整点,那么连线中点不是整点。 如果n=3,取水平两个连续的点,垂直也两个连续的点,组成三角形。那么连线中点不是整点。 如果n=4,取四个整点组成一个正方形,则连线中点不是整点。 而取5个点的话,必然有两个点的连线中点是整点。 2、在NOI期间,主办单位为了欢迎来自各国的选手,举行了盛大的晚宴。在第十八桌,有5名 大陆选手和5名港澳选手共同进膳。为了增进交流,他们决定相隔就坐,即每个大陆选手左右 旁都是港澳选手,每个港澳选手左右旁都是大陆选手。那么,这一桌一共有_______种不同的 就坐方案。注:如果在两个方案中,每个选手左右相邻的选手相同,则视为同一种方案。 解 1:2880 相当于 1 个圆,十个人。先随便找个座,让人去坐,有 10 个可能,然后顺时针走,下一 个座就有 5 种可能,再下一个就 4 个,再下一个还是 4 个,以此类推,就是 10*5*4*4*3*3*2*2*1*1。这其中有重复的,同一种坐法,可以绕着桌子走一圈,就是上一个人 坐到下一个人的位置,串一下,这样所有坐法就算重复了 10 次,再除以 10 就行了。就是 5*4*4*3*3*2*2*1*1。 解 2:2880 首先安排 5 个大陆选手相隔就坐,他们的位置是任意的,有 P(5,5)种坐法,然后再安 排五个港澳选手,是共同进膳应该只有 5 个空,5 个人坐 5 个空,也可以随意坐,也有 P(5, 5)种坐法,然后相乘。 可到这里并不是就结束了,因为这里面包含了重复的,可是重复的情况非常极端,“每个选手 左边相邻的选手均相同”,每一种方案,每个人都往左或者往右移动一个位子,两个位子,三
8

个位子……跟原先的还是一样的方案,也就是说每十种方案里一共有 5 种是重复的。所以要去 除重复,除以 5。 所以应该是 P(5,5)*P(5,5)/5。

附:排列组合原理
一、加法原理与乘法原理 1、加法原理: 做一件事情,完成它可以有 n 类办法,在第一类办法中有 m1 种不同的方法,在第二类办 法中有 m2 种不同的方法,??,在第 n 类办法中有 mn 种不同的方法。那么完成这件事共有 N=m1+m2+...+mn 种不同的方法。 2、乘法原理: 做一件事情,完成它需要分成 n 个步骤,做第一步有 m1 种不同的方法,做第二步有 m2 种不同的方法, ??, 做第 n 步有 种 mn 不同的方法, 那么完成这件事有 N=m1*m2*...*mn 种 不同的方法。 3.两个原理的区别:一个与分类有关,一个与分步有关;加法原理是“分类完成”,乘法 原理是“分步完成”。 二、排列与组合的概念与计算公式 1、排列及计算公式 从 n 个不同元素中,任取 m(1≤m≤n)个元素按照一定的顺序排成一列,叫做从 n 个不同元 素中取出 m 个元素的一个排列;从 n 个不同元素中取出 m(m≤n)个元素的所有排列的个数,叫 做从 n 个不同元素中取出 m 个元素的排列数,用符号 p(n,m)表示。当 m<n 时称为选排列,其 排列数记做 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(m≤n)个元素并成一组,叫做从 n 个不同元素中取出 m 个元素 的一个组合;从 n 个不同元素中取出 m(m≤n)个元素的所有组合的个数,叫做从 n 个不同元素 中取出 m 个元素的组合数。用符号 c(n,m) 表示。

9


相关文章:
信息学奥赛普及组1-18届问题求解题解析
信息学奥赛普及组1-18届问题求解题解析_学科竞赛_高中教育_教育专区。信息学奥赛普及组1-18届问题求解题解析 2013年辅导历届“问题求解”解析(2013 竞赛辅导)问题...
信息学奥赛问题求解(带答案)
信息学奥赛问题求解(带答案)_学科竞赛_初中教育_教育专区。1.已知,按中序遍历...第八届信息学奥赛普及组... 暂无评价 7页 免费 noip第十五届(2009年)信....
高中信息学竞赛各种问题求解试题及答案
高中信息学竞赛各种问题求解试题答案1 题(5...题(14 分)以下程序是将组整数按从小到大的顺序...(A、13 B、-7 C、11 D、0 信息学奥赛 pascal...
信息学奥赛普及组初赛模拟试题
信息学奥赛普及组初赛模拟试题() 发布: 郭琪 时间: 2011/7/6 13:56:18 ...后 10 题为不定 项选择题(即每题有 1 至 5 个正确答案,只有全部选对才...
信息学竞赛中问题求解常见题分析(综合打印)
信息学竞赛中问题求解常见题分析( 信息学竞赛中问题...1. 四种典型的递推关系 Ⅰ.Fibonacci 数列型 在...信息学竞赛普及组初赛模... 暂无评价 9页 免费 ...
信息学竞赛中问题求解常见题分析
信息学竞赛中问题求解常见题分析_IT/计算机_专业资料。中学生信息学竞赛小贴士!信息学竞赛中问题求解常见题分析 排列组合问题 知识点: 、知识点: 1. 分类计数...
第十四届信息学奥赛初赛试题 普及组(P)
第八届信息学奥赛普及组... 第十届信息学奥赛普及...●● 全部试题答案均要求写在答卷纸上,写在试卷纸...A.20 B.1 C.220 D.202 二、问题求解(共 2 ...
信息学奥数1-17届问题求解题解析
信息学奥数1-17届问题求解题解析_学科竞赛_小学教育_教育专区。历届“问题求解”解析(2011 竞赛辅导)问题求解是信息学竞赛初赛中常见题型,它共两题,每题 5 分,...
第八届信息学奥赛普及组试题
第八届信息学奥赛普及组试题 隐藏>> 一.选择一个正确答案代码(A/B/C/D,填入...12345678 4 6 1 -1 7 3 2 A) 6 B) O C) 5 D) 3 二.问题求解: ...
更多相关标签:
初中信息学奥赛普及组 | 2015信息学奥赛普及组 | 信息学奥赛 | 信息学奥赛noip官网 | 信息学奥赛一本通 | 信息学奥赛一本通 pdf | 小学信息学奥赛 | 中学生信息学奥赛试题 |