填空题复习资料

1、数列、递推类问题求解题目1：走楼梯问题设有一个共有n级的楼梯，某人每步可走1级，也可走2级，也可走3级，用递推公式给出某人从底层开始走完全部楼梯的走法。例如：当n=3时，共有4种走法，即1+1+1，1+2，2+1，3。答：用递推公式给出的某人从底层开始走完全部楼梯的走法为(用F(N)记录不同案数：F(1)=1F(2)=2F(3)=4F(N)=F(N-3)+F(N-2)+F(N-1)(N4)题目2：走楼梯问题（变种）有2n的一个长方形方格，用一个12的骨牌铺满方格。例如n=3时，为23方格。此时用一个12的骨牌铺满方格，共有3种铺法： 试对给出的任意一个n(n0)，求出铺法总数的递推公式。 答：

2、此题与走楼梯完成一致，即：对给出的任意一个n(n0)，用F(n)表示其铺法的总数的递推公式为：F(1)=1F(2)=2F(n)=F(n-2)+F(n-1)(n3)题目3：球入盒方案数将n个不同颜色的球放入k个无标号的盒子中（nk，且盒子不允许为空）的方案数为S（n,k），例如：n=4，k=3时，S（n,k）=6。当n=6，k=3时，S（n,k）=。答：将n个不同颜色的球放入k个无标号的盒子中（nk，且盒子不允许为空）的方案数为S（n,k），它可以分成二种情况：第n个球单独成堆，此时有S（n-1,k-1）种方案；第n个球不单独成堆，而是和其他若干个球合成一堆，此时我们先将前(n-1)个球分成k堆

3、，然后将第n个球插入某一堆中。对于每一种将前(n-1)个球分成k堆的方案，我们都有k种插入方法，所以此时有k*S(n-1,k)种方案。综上所述，S(n,k)的递推公式是：S(1,1)=1S(n,k)=0 (n=k)结果：90题目4：错位排列问题某校有学号分别为1，2，3，m。m中的n个学生要去音乐厅听音乐，音乐老师手里有座位号分别为1，2，3，n的票要分给学生，希望每个学生的座位号与自己的学号都不相同，请问老师有多少种不同的方案来分配这些票？例如，当n=2时，只有1种方案，n=3时，有2种方案，现对任意的n1，记F（n）为不同的方案数，请写出F（n）的递归关系式。分析：该问题为著名的错位排列问

4、题，其对应的递归公式为：f(n)=(n-1)*(f(n-1)+f(n-2) (n2)f(2)=1f(1)=0。题目5：Nocomachns定理的最小奇数问题根据Nocomachns定理，任何一个正整数n的立方一定可以表示成n个连续的奇数的和。 例如：13 1 23 3 5 33 7 9 11 43=13+15+17+19 在这里，若将每一个式中的最小奇数称为X，那么当给出n之后，请写出X与n之间的关系表达式：_答案：关系表达式:X=N*N-N+1题目6：直线分平面 n条直线最多能把平面分成几部分？分析：一条直线把平面分成两部分；两条直线时，增加的一条直线被另一条直线截成两段，每一段把原来的两部

5、分平面又分成两部分，这样就增加了两个部分出来，共有了4个部分，可以看作是在由算式2+2得到；当有三条直线时，第三条直线被原来的2条直线截成3段，这3段再把所在部分又一分为二，所以又增加3个部分，此时共有7个部分，可以看作由算式2+2+3得到；依次类推，4条直线时，可由算式2+2+3+4得到最多分成11个部分，所以6条直线时，可把平面最多分成2+2+3+4+5+6=22个部分，10条直线时，可把平面最多分成：2+2+3+4+5+10=56个部分。如果有n条直线，则可把平面最多分成为：2+2+3+4+5+6+n个部分，也就是：1+1+2+3+4+5+6+n个部分，而1+2+3+4+5+6+n是一个

6、等差数列，它的和为：Sn=n*(1+n)/2所以平面被分成部分数应该是: 1+n(n+1)/2 与之有关的数列方面的知识点:数列几个重要公式及有关推导：一、 等差数列的通项公式：an=a1+(n-1)d (d为公差)二、 等比数列的通项公式：an=a1qn-1(q为公比)三、 等差数列前n项和公式： Sn=n(a1+an)/2或：Sn=na1+ n(n-1)d/2四、 等比数列前n项和公式：Sn=a1(1-qn)/(1-q)或：Sn=(a1-an q)/(1-q) 其中q 不等于1（当q=1时为常数数列）。五、等差数列前n项和公式的推导：一般地，设有等差数列a1,a2,a3,an,它的前n项的

7、和是Sn，即：Sn=a1+a2+a3+an根据等差数列an的通项公式，上式可改写成：Sn=a1+（a1+d）+（a1+2d）+a1+(n-1)d Sn= an +（an - d）+（an -2d）+ an -(n-1)d + 2Sn=( a1+ an)+ ( a1+ an) + ( a1+ an) 上式中共有n个( a1+ an)相加，所以可得：2Sn=n( a1+ an)，即：Sn=n( a1+ an)/2六、等比数列前n项和公式的推导：设有等比数列a1,a2,a3,an,它的前n项的和是Sn，即：Sn=a1+a2+a3+an根据等比数列an的通项公式，上式可改写成：Sn=a1+a1q+a1

8、q2+a1qn-1 将式两端同乘以qqSn=a1q+a1q2+a1q3+a1qn -得：Sn(1-q)=a1-a1qn=a1(1-qn)所以：Sn= a1(1-qn)/ (1-q)例2一个长方形把平面分成两部分，那么3个长方形最多把平面分成多少部分？解答：见右图,最多26个。上面是画出实图，有点难度，这方法较笨拙，要是问10个长方形怎么办？显然得找出规律，可结合画图的过程，参考如下思路，一个长方形可分内外两部分，第2个长方形有四条边，每条边都可以挂一下原长方形的每个角，这样就产生8个交点，这8个交点自然把第2个长方形这样一个封闭图形分成8段（有直有弯），每段穿过一个部分一分为2，新增8个，所以

9、2+8=10，第3个长方形的每条边现在可以挂到原有2个长方形的8个角，最多可产生16个交点，同理这16个交点把第三个长方形本身分成16段，每段穿过一个部分，又新增加16个，共2+8+16=26个。N个四边形分部分数可总结出一个规律：部分数=2+n(n-1)4公式里的4就对应着，4边形的4，其实圆可当成封闭的1边形，那么n个圆分的部分数可仿写为：部分数S=2+ n(n-1)1同理n个三角形分平面的部分数公式为：A=2+ n(n-1)3同理n个5边形分平面的部分数公式为：A=2+ n(n-1)5上面的能看明白，记住，以后做类似题就方便多了.再来一道详解，巩固一下：例3：10个三角形最多将平面分成几

10、个部分？解：可这样想，设n个三角形最多将平面分成an个部分。n=1时，a1=2；n=2时，第二个三角形的每一条边与第一个三角形最多有2个交点，三条边与第一个三角形最多有23=6（个）交点。这6个交点将第二个三角形的周边分成了6段，这6段中的每一段都将原来的每一个部分分成2个部分，从而平面也增加了6个部分，即a2223。n3时，第三个三角形与前面两个三角形最多有4312（个）交点，从而平面也增加了12个部分，即：a3=22343。一般地，第n个三角形与前面（n-1）个三角形最多有2（n-1）3个交点，从而平面也增加2（n1）3个部分，故an=223432（n-1）32242（n-1）323n（n

11、-1）3n2-3n2。特别地，当n10时，a1031023102=272，即10个三角形最多把平面分成272个部分。 套用例2下的公式：2+10（10-1）3=272，与上面结果相同，只是公式的表达形式不全相同。例4：在平面上画5个圆和1条直线，最多可把平面分成多少部分？解答：关于圆分平面，我们在第一题中已经给出了一个计算公式（推导方法与第一题相同）。由此我们知道5个圆最多分平面5（5-1）+2=22部分。现在再增加一条直线，那么一条直线最多有5个圆有10个交点，所以最多增加10部分，也即5个圆和1条直线最多可把平面分成22+10=32部分。数字游戏的问题求解1、由a，b，c三个不同的数字组成

12、一个N位数，要求不出现两个a相邻，也不出现两个b相邻，这样的N位数的个数为AN，用AN-1和AN-2表示AN的关系式为：AN= 。 答：N=1时，这时a,b,c 3个数组成一位数有a,b,c共3个； N=2时，由于要求不出现两个a相邻，也不出现两个b相邻，所以有： ab ac ba bc ca cb cc 共7个二位数； N=3时，由于要求不出现两个a相邻，也不出现两个b相邻，所以有： aba abc aca acb acc bab bac bca bcb bcc cab cac cba cbc cca ccb ccc 共17个三位数； 分析以上数据可得：AN= 2AN-1 +AN-2 (N=

13、2)，且A0 =1，A1 =32、有位小同学喜欢在方阵中填数字，规则是按下图标示例从右上角开始，按斜线填数字，碰到边界就重新。显然，数字1在坐标（1，5）位置，数字25在坐标（5，1）位置。后来这位小朋友想知道，对于N阶的方阵，随机取一个位置（x,y），并规定xy，问这个位置上应该填的数字是多少？5阶方阵的示例图如下：117 4 2 11612 8 5 32017 13 9 62321 18 14 1025 24 22 19 15答：首先，填数的规律从右上角开始，沿着主对角线的方向依次进行下去。容易从下面的图例中看出：对于一个格子(x,y)，其中x=y, n-y+x就是这个格子所在钭线的编号。

14、而编号为I的钭线上显然能够填入I个数字。求一个格子中的数字，可以分为二步：(1) 求这个格子所在的钭线之前的所有钭线填了多少个数，显然是：1+2+(n-y+x-1)=(n-y+x)*(n-y+x-1)/2(2) 这个格子是这条钭线上的第几个，显然是x。结果：(n-y+x)*(n-y+x-1)/2+x4、Kathy函数是这样定义的：f（1）=1f（3）=3f（2n）=f（n）f（4n+1）=2f（2n+1）-f（n）f（4n+3）=3f（2n+1）-2f（n）对于一个给定的数m=30，求出所有的满足f（n）=n（nm）的自然数n的个数。分析：根据Kathy函数的定义，我们可以从简单情况分析入手，

15、当f（n）=n时，将函数值转化为二进制数，有f(1)=1=(1)2f(2)=f(1)=1f(3)=3=(11)2f(4)=f(2)=1f(5)=2f(3)-f(1)=2*3-1=5=(101)2f(6)=f(3)=3f(7)=3f(3)-2f(1)=3*3-2*1=7=(111)2f(8)=f(4)=1f(9)=2f(5)-f(2)=2*5-1=9=(1001)2由此，我们可以猜测，当f(n)=n时，其函数值n转化为二进制后得到的二进制串为回文串（从左到右读和从右到左读时两串为同一个串）。事实上，利用数学方法可以证明，当n转化为二进制数，若得到的二进制串为回文串时，满足f(n)=n。问题就转化

16、为求整数1到30之间有多少个整数转化为二进制串后，该二进制串为回文串，则有多少个整数满足f(n)=n。答案：9。5、设1个1.100,1.100的二维数组A，每个元素I，J存储时占2个字节，将A数组按行优先的顺序存入从SA开始的连续存储单元中，则元素A66，65存储的结束地址是 。答： SA+13129 分析：从A1，1到A66，65共占用了(66-1)*100+65*2=13130个字节，因为是从SA开始的，所以SA本身被A1，1占用，所以结果=SA+13130-1=SA+131296、设数组X10.40，20.50以行优先的方式存储，每个元素占4个字节，且已知X10，20的地址为1000，

17、则X30，30的地址是 。答： 2280 分析：loc(30,30)=loc(x10,20+(50-20+1)*(30-10)+(30-20)*4=1000+(31*10+10)*4=22807、设有100个顶点，利用二分法查找时，最大的比较次数是 。答： 7分析：二分法查找，最大比较次数为log2N8、某校足球队有球衣30件，篮球队有球衣15件，排球队有球衣18件，三队队员总数为50人，其中有3人同时参加3个队，那么同时只参加两个队的队员有多少？分析：设同时只参加两个队的队员（只同时拥有两个队球衣的人）有x人，由于50个人，每人至少有一件球衣，共要50件球衣，只参加两个队的队员有x人，又需要

18、增加x件球衣，且有3人同时参加3个队（即有3个人，同时有3件球衣），又要多3*2件球衣，因此50+x+6=30+15+18，所以x=7，即同时只参加两个队的队员有7人。答案：7。9、下列形状的三角形中，字母ai分别表示数字1，2，39 a b c d e f g h i字母ai同时满足下列条件：（1） afi（2） bd，gh，ce（3） a+b+d+f=f+g+h+i=i+e+c+a=19试求出满足条件的三角形的个数。分析：因为字母ai分别表示数字1，2，39，且a+b+d+f=f+g+h+i=i+e+c+a=19，所以a+b+d+f+f+g+h+i+i+e+c+a=57，即a+b+c+d+

19、e+f+g+h+i+a+f+i=57，而a+b+c+d+e+f +g+h+i=45，综合上述两式得a+f+i=12，即这个数字三角形3个顶点的数和为12，只要经过全面仔细的计算，采用穷举法即可得到如下4个三角形，他们满足所有条件：（根据afi和a+f+i=12可知，a4） 1 1 2 2 6 2 5 3 5 4 6 1 8 9 9 8 9 6 8 9 4 3 5 7 4 2 6 7 3 1 8 7 3 4 5 7答案：4。10、给定一个正整数N=8934632179，现决定依次删除其中6个数位以上的数字（每次删除一个数位上的数字），每次删除后按原来的次序组成一个新数，每次得到的新数M的值均是当

20、前状态下的最小数，则第4次应该删除的数字是 。答： 4分析：此题可以推出一个贪心标准，每次从最高位起寻找递减区间，若存在递减区间，则删除递减区间的最高位数字，若不存在递减区间，则删除最末位数字。根据这一贪心标准，要删除6个数位上的数字，使得每次删除后组成的新数最小，应依次删除数字：9，8，6，4，3，3。11、编号为1到13的纸牌顺时针排成一圈，有人从编号为1的牌从数字1开始顺时针数下去，1，2，3，20，21，一圈又一圈。问：当数到数字N时，所在的纸牌的编号为多少？ 答：由于编号为1到13的纸牌顺时针排成一圈，因此当数到数字N时，所在纸牌相距编号为1的牌有(N-1)mod 13个位置，其编号

21、为1+(N-1)mod 13。所以答案为：1+(N-1)mod 1312、75名儿童去游乐场玩。他们可以骑旋转木马，坐滑行轨道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中两种。若每玩一样的费用为5元，游乐场总共收入700，可知有_名儿童没有玩过其中任何一种。0*t+1*x+2*y+3*z=400/5 t+x+y+z=75 z=20 y=55-20=35 分析：设有t人没有玩过任何一种，有x人玩过一种，y个人玩过2种，z个人玩过3种，则根据已知条件可得：将代入后可得：x=10，所以t=75-20-35-10=10。答案：10。13、用1个或多个互不相同的正整数之和表示1511

22、之间的所有整数，问：至少要多少个不同的正整数 这些正整数是 答：第一种方法： 新选整数表示整数的增加范围目前可表示的整数范围11122,31,2，344,5，6,71,2，3,4，5,6，788,9,151,2,151616,17,311,2,313232,33,631,2,636464,65,1271,2,127128128,129,2551,2,255256256,257,5111,2,511 从图中可以看出需要9个整数，它们分别是：1,2,4,8,16,32,64,128,256。方法二： 因为n个二进制位可表示2n-1个从1开始的不同的整数，511=29-1，所以需要9个整数，它们分别

23、是：1,2,4,8,16,32,64,128,25614、设有质量为1、3、9、27、81、3ng.的砝码各一枚，如果砝码允许放在天平的两边，则用它们来称物体的质量，最多可称出1g到3n+3n/2g之间的所有质量，如n=4时，可称出18到121g之间的所有质量；当物体质量为M=14时，有14+9+3+1=27，即天平一端放M=14g的物体和9g、3g、1g的砝码，另一端放27g的砝码，即可称出M的质量。当M=518g时，请你写出称出该物体的质量的方法，并用上述所示的等式来表示。518+243+3+1= 729+27+915、一个家具公司生产桌子和椅子。现有113个单位的木材。每张桌子要使用20

24、个单位的木材，售价是30元；每张椅子要用16个单位的木材，售价是20元。使用已有的木材生产桌椅（不一定要用光木材）做多可以买_元钱。分析，设：做x张桌子和y 张椅子可以卖到最高的价钱。则，根据已知条件可得：20*x+16*y113。因为每张桌子售价30， 每张椅子售价20，所以要卖到最高的价钱，必须使x的值尽可能的大。所以结合不等式求解，x的最大值是4，此时y 的值最大是2。此时可以卖到30*4+20*2=160元。答案：160。16、编号为1到13的纸牌顺时针排成一圈，有人从编号为1的牌从数字1开始顺时针数下去，1、2、3、20、21、，一圈又一圈。问：当数到数字N时，所在纸牌的编号为多少?

25、 1+(N-1) mod 13排列组合类问题求解题1：放书问题在书架上放有编号为1,2,.n的n本书。现将n本书全部取下然后再放回去,当放回去时要求每本书都不能放在原来的位置上。例如:n=3时：原来位置为:123放回去时只能为:312或231这两种。问题：求当n=5时满足以上条件的放法共有多少种?(不用列出每种放法)答：44 本题是典型的错位排列问题f(5)=5!*(1-1/1!+1/2!-1/3!+1/4!-1/5!)=120*(11/30)=44题目2：红、黄球排列问题将N个红球和M个黄球排成一行。例如:N=2,M=3可得到以下6种排法:红红黄黄黄红黄红黄黄红黄黄红黄黄红红黄黄黄红黄红黄黄

26、黄黄红红问题:当N=4,M=3时有多少种不同排法?(不用列出每种排法)答：35 C73=7*6*5/3!=35题目3：三角形个数问题平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同三角形？答：751 C72C51 + C72C61 + C71C52 + C71C62 + C52C61 + C62C51 + C71C61C51=751题目4：四边形个数问题平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形？答：2250C52C62 + C71C52C61+ C71C62C51 + C72C52 + C72C62 + C72C61C51=2250题目5：三角形内四边形个数问题把三角形各边分成n等份，过每一分点分别作各边的平行线，得到一些由三角形的边和这些平行线所组成的平行四边