NOIP初赛试题提高组C语言

ＮＯＩＰ初赛试题（提高组Ｃ语言） 第十届（2004） 三．问题求解（ 共 2 题，每题 5 分，共计 10 分 ） 1.75 名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中 20 人这三种东西都玩过， 55 人至少玩过其中的两种。若每样乘坐一次的费用是 5 元，游乐场总共收入 700 ，可知有 名儿童没有玩过其中任何一种。 分析与解：已知总人数为75，总金额是700，玩3项的人数是20，花费的金额是5*3*20=300，玩2项的人数是55-20=35，花费的金额是5*2*35=350，剩余金额是700-300-350=50，只能玩50/5=10项次，即玩1项的人数是10，所以玩0项的人数是：75-20-35-10=10 人数 金额 总共 75 700 玩3项 玩2项 玩1项 玩0项 20 300 35 350 ？ 0 2.已知 a, b, c, d, e, f, g 七个人中， a 会讲英语； b 会讲英语和汉语； c 会讲英语、意大利语和俄语； d 会讲汉语和日语； e 会讲意大利语和德语； f 会讲俄语、日语和法语； g 会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？如果可以，请以“ a b ”开头写出你的安排方案： 。

a-b-d-f

.

c-e-g-f g-e-c-f

答： a b d f g e c

第十一届（2005）

三．问题求解（请在空格处填上答案，每空5分，共计10分） 1．将数组{32, 74, 25, 53, 28, 43, 86, 47}中的元素按从小到大的顺序排列，每次可以交换任意两个元素，最少需要交换 次。 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，43，74，53，86，47 ④ 25，28，32，43，47，53，86，74 ⑤ 25，28，32，43，47，53，74，86 2．取火柴游戏的规则如下：一堆火柴有N根，A、B两人轮流取出。每人每次可以取1根或2根，最先没有火柴可取的人为败方，另一方为胜方。如果先取者有必胜策略则记为1，先取者没有必胜策略记为0。当N分别为100，200，300，400，500时，先取者有无必胜策略的标记顺序为 （回答应为一个由0和/或1组成的字符串）。 分析与解：当火柴的根数为3或3的整数倍时，先取者没有必胜的策略；而当火柴的根数不为3的整数倍时，先取者有必胜的策略：取后使得剩余火柴的根数为3的整数倍。 所以答案为11011 相似的游戏：A、B两人轮流往同一储蓄罐存钱并记录每次存入的金额，每人每次可存入的金额为1元至5元间的任一整数（包括1和5），谁某次存完钱后使得储蓄罐里的总金额大于等于100即获胜利（获得储蓄罐里所有的存钱的奖励）。若让你参加该游戏并为第一个存钱者，你有必胜的策略吗？

第十二届（2006）

三．问题求解（共 2 题，每题 5 分，共计 10 分）

1．将 2006 个人分成若干不相交的子集，每个子集至少有 3 个人，并且： （1）在每个子集中，没有人认识该子集的所有人。

（2）同一子集的任何 3 个人中，至少有 2 个人互不认识。

（3）对同一子集中任何 2 个不相识的人，在该子集中恰好只有 1 个人认识这两个人。 则满足上述条件的子集最多能有___________个？

分析：要使子集数最多，每一子集的人数应最少。每一子集的人数为3，不符合要求，为4也不符合要求，为5可符合要求。

2．将边长为 n 的正三角形每边 n 等分，过每个分点分别做另外两边的平行线，得到若干个正三角形， 我们称为小三角形。正三角形的一条通路是一条连续的折线，起点是最上面的一个小三角形，终点是最下面一行位于中间的小三角形。在通路中，只允许由一个小三角形走到另一个与其有公共边的且位于同一行或下一行的小三角形，并且每个小三角形不能经过两次或两次以上（图中是 n=5 时一条通路的例子）。设 n=10，则该正三角形的不同的通路的总数为_____________。

分析与解：如果n=2，存在的不同的通路总数为1 如果n=3，存在的不同的通路总数为2=1*2=2！ 如果n=4，存在的不同的通路总数为6=1*2*3=3！ 如果n=5，存在的不同的通路总数为24=1*2*3*4=4！ ??

如果n=10，存在的不同的通路总数为9！

第十三届（2007）

三．问题求解（共2 题，每题5 分，共计10 分）

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)= _____________。 分析与解：

方法一：4个盒子放7个球的情况依每个盒子所放球的个数不同可分为以下情形： ①4，1，1，1；共有C（7，4）=7*6*5*4/（4*3*2*1）=35种 ②3，2，1，1；共有C（7，3）*C（4，2）=35*6=210种

③2，2，2，1。共有C（7，2）*C（5，2）*C（3，2）/A（3，3）=21*10*3/6=105种 共计：35+210+105=350种

方法二：S(n,r)=S(n-1,r)×r + S(n-1,r-1)

因为，多一个球的放法：若空盒没有增多，则往r个盒子的任何一个盒子放入该球都是一种放法。所以共有S(n-1,r)×r 种放法，若空盒有增加1个，则增加的球只能放在该盒，放法有S(n-1,r-1)种。 另：S(n,n)=1；S(n,1)=1，依S(n,r)=S(n-1,r)×r + S(n-1,r-1)填下表： r n 1 2 3 4 1 1 2 1 1 3 1 1 4 1 1 5 1 6 1 7 1

2．N 个人在操场里围成一圈，将这N 个人按顺时针方向从1 到N 编号，然后，从第一个人起，每 隔一个人让下一个人离开操场，显然，第一轮过后，具有偶数编号的人都离开了操场。依次做下去，直到操场只剩下一个人，记这个人的编号为J(N) ，例如，J(5)=3 ，J(10)=5 ，等等。则J(400)=______________。

（提示：对N=2m+r 进行分析，其中0≤r<2m ）。

（答案：1、350；2、289）

第十四届（2008）

三．问题求解（ 共 2 题，每题 5 分，共计 10 分 ）

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本，其中每两本的编号都不相邻的选法一共有______种。

分析与解：若只有1-7号7本书，符合要求的取法只有1种，即取1357，取完后剩3本书，3本书间有2个空位，加上头尾2个空位，共4个空位。现把书放回去，满足要求的放法应只有1种，即为4个空位放4本书的组合数C（4，4）=1；

若有1-8号8本书，符合要求的取法有5种，即取1357、2468、1358、1468和1368，取完后剩4本书，4本书间有3个空位，加上头尾2个空位，共5个空位。现把各种取法的书放回去，满足要求的放法应该也为5种，即为5个空位放4本书的组合数C（5，4）=5；

所以，21本书，取走4本后剩余17本，17本书间有16个空位，加上头尾2个空位，共18个空位。往18个空位放4本书的组合数是C（18，4）=3060种。

m(4)=f(4)+g(4)=2+6=8 f(4)=g(1)*g(2)=1*2=2 g(4)=m(1)*m(2)=2*3=6 m(2)=f(2)+g(2)=3 f(2)=g(1)=1 g(2)=m(1)=2 m(1)=2 f(1)=1 g(1)=1

第十九届（2013）

1．某系统自称使用了一种防窃听的方式验证用户密码。密码是 n 个数 s1, s2, ?, sn，均为 0或 1。该系统每次随机生成 n 个数 a1, a2, ?, an，均为 0 或 1，请用户回答(s1a1 + s2a2 + ?+ snan)除以 2 的余数。如果多次的回答总是正确，即认为掌握密码。该系统认为，即使问答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。

然而，事与愿违。例如，当 n = 4 时，有人窃听了以下 5 次问答：

系统生成的 n 个数 问答编号 掌握密码的用户的回答 a1 1 2 3 4 5 1 0 0 1 1 a2 1 0 1 1 0 a3 0 1 1 1 0 a4 0 1 0 0 0 1 0 0 0 0 就破解出了密码 s1 = ，s2 = ，s3 = ，s4 = 。 (0 1 1 1)

2．现有一只青蛙，初始时在 n 号荷叶上。当它某一时刻在 k 号荷叶上时，下一时刻将等概率地随机跳到 1, 2, ?, k 号荷叶之一上，直至跳到 1 号荷叶为止。当 n = 2 时，平均一共跳 2 次；当 n = 3 时，平均一共跳 2.5 次。则当 n = 5 时，平均一共跳

次。

（答案：1、0 1 1 1；2、37/12）

解：记青蛙从n号荷叶平均一共跳f(n)次会到1号荷叶上，则f(2)=2，f(3)=2.5，求f(5)。 f(2)=(1/2)*1+(1/2)*(1+f(2))?f(2)=2

f(3)=(1/3)*1+(1/3)*(1+f(2))+ (1/3)*(1+f(3))?f(3)=2.5 同理可得：

f(4)=(1/4)*1+(1/4)*(1+f(2))+ (1/4)* (1+f(3)) +(1/4)* (1+f(4))?f(4)=17/6 f(5)=(1/5)*1+(1/5)*(1+f(2))+ (1/5)* (1+f(3)) +(1/5)* (1+f(4)) +(1/5)* (1+f(5)) 解得：f(5)=37/12

2014（20届） 1．有数字1，1，2，4，8，8所组成的不同的四位数的个数是 。 2．如图所示，图中每条边上的数字表示该边的长度，则从A到E的最短距离是 。

（答案：1、102；2、15）

2015（21届）

1．在1和2015之间（包括1和2015在内）不能被4、5、6三个数任意一个数整除的数有 个。

2．结点数为5的不同形态的二叉树一共有 种。（结点数为2的二叉树一共有2种：一种是根结点和左儿子，另一种是根结点和右儿子。） （答案：1、1075；2、42）

2016提高组（22届） 1．一个1×8的方格图形（不可旋转）用黑、白两种颜色填涂每个方格。如果每个方格只能填涂一种颜色，且不允许两个黑格相邻，共有 种填涂方案。 2．某中学在安排期末考试时发现，有7个学生要参加7门课程的考试，下表列出了哪些学生参加哪些考试（用√表示要参加相应的考试）。问最少要安排 个不同的考试时间段才能避免冲突？ 考试 通用技术 物理 化学 生物 历史 地理 政治 学生1 √ √ √ 学生2 √ √ √ 学生3 √ √ √ 学生4 √ √ 学生5 √ √ 学生6 √ √ √ （答案：1、55；2、3）

2017提高组（23届）

1．如图所示，共有13个格子。对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变(由1变0，或由0变1)。现在要使得所有的格子中的数字都变为0，至少需要3次操作。

2.如图所示，A到B是连通的。假设删除一条细的边的代价是1，删除一条粗的边的代价是2，要让A、B不连通，最小代价是4(2分)，最小代价的不同方案数是9(3分)。（只要有一条删除的边不同，就是不同的方案）

（答案：1．3；2．4、9）

1．某系统自称使用了一种防窃听的方式验证用户密码。密码是n个数s1,s2,…，sn,均为0或1。该系统每次随机生成n个数a1,a2,…,an，均为0或1，请用户回答(s1a1+s2a2+…+snan)除以2的余数。如果多次的回答总是正确，即认为掌握密码。该系统认为，即使问答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。

然而，事与愿违。例如，当n=4时，有人窃听了以下5次问答：

就破解出密码s1= ，s2= ，s3= ，s4= 。

分析： (s1*1+s2*1+s3*0+s4*0) mod 2=1 (s1*0+s2*0+s3*1+s4*1) mod 2=0 (s1*0+s2*1+s3*1+s4*0) mod 2=0 (s1*1+s2*1+s3*1+s4*0) mod 2=0 (s1*1+s2*0+s3*0+s4*0) mod 2=0

解得：s1= 0 ，s2= 1 ，s3= 1 ，s4= 1 。

2．现有一只青蛙，初始时在n号荷叶上，当它某一时刻在K号荷叶上时，下一时刻将等概率地随机跳到1，2，…，k号荷叶之一上，直至跳到1号荷叶为止。当n=2时，平均一共跳2次；当n=3时，平均一共跳2.5次。则当n=5时，平均一共跳 次。

分析与解：记青蛙从n号荷叶跳到1号荷叶上平均一共跳fn次，则： f1=1

f2=1*(1/2)+(1+f2)*(1/2)

f3=1*(1/3)+(1+f2)*(1/3)+(1+f3)*(1/3) ……

fn=1*(1/n)+(1+f2)*(1/n)+…+(1+fn)*(1/n) 即fn=(1+1+f2+…+1+fn)*(1/n)=(f1+f2+…+fn)/n

fn=1+(f1+f2+…+fn-1)/(n-1)

本文来源：https://www.bwwdw.com/article/caad.html