历届“问题求解”解析（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．用邻接矩阵表示下面的无向图：
表示该无向图的邻接矩阵为 A 0 1 0 0 0 0 0 1 0 1 1 0 0 0 B C 0 1 0 1 0 0 0 0 1 1 0 1 1 1 D E F 0 0 0 1 0 0 1 0 0 0 1 0 0 1 G H I 0 0 0 1 1 1 0
第五届（递推）
将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??11n!?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 第一次：32<-->25 25,28,32,53,74,43,86,47 第二次: 28<-->74 25,28,32,53,74,43,86,47
25,28,32,43,74,53,86,47 第三次：43<-->553 25,28,32,43,47,53,86,74 第五次：47-->74 25,28,32,43,47,53,86,74 25,28,32,43,47,53,74,86 第五次：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 补：(取石子游戏)现有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 城市2 城市3 城市4 城市5 城市6 城市1 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，若 5 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库信息学奥赛普及组1-18届问题求解题解析在线全文阅读。
相关推荐：