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

NOIP初赛练习之二(解答题)


NOIP 初赛练习之二(解答题)
前言:如何做解答题 解答题一般是根据要求写出表达式或画出图等, 涉及的知识点主要有数学方面的基本知 识、数据结构方面的如树和图等、逻辑推理等,难点主要在写出递推公式。写出公式之前要 先从起始值开始进行摸索,写出若干个结果之后再观察其中的规律,再写出公式,一般是 F (N)=??,省略号部分可能是 F(N-1) 、F(N-2)??等的数学

表达式。最后再验证公 式的正确性,时间允许的话可从数学等方面加以证明(当然不要写出证明过程,除非要求你 说明其正确性) 。 有时是图形的变换,如正方形、三角形、圆等的旋转,先前给出了几个点相应的坐标, 求旋转若干周后的各点坐标,这种情况一般用到求余的运算,当以 N 为一个周期时往往是 用对 N 求余(mod n)的运算;如果是正反两种情况可以使用(-1)的若干次方的形式来转 换两种状态,即用某一表达式乘以-1 的若干次方。 有时是有关组合数学的知识,如排列或组合,确定是(分步)乘法原理还是(分类)加法 原理。对于排列分次序,而组合不分各元素的次序: 组合:C(m, n)=n*(n-1)*….*(n-m+1)/m! 排列:P (m, n)= n*(n-1)*….*(n-m+1) 数据结构方面要对堆栈的先进后出原理、队列的先进先出原理、二叉树(结点)的遍历、 图的邻接矩阵表示法熟悉。 至于逻辑推理方面的要将各个条件(描述)一一列出,排除矛盾情况,列举出可能的情 况,写出符合条件的结果。

练习:
1.公式推导(10 分)1999 年初中组初赛题 根据 Nocomachns 定理, 任何一个正整数 n 的立方一定可以表示成 n 个连续的奇数的和。 如: 3 1= 1 23= 3+ 5 33= 7+ 9 +11 43=13 十 15+17+19 在这里,若将每一个式中的最小奇数称为 X,那么当给出 n 之后,请写出 X 与 n 之间 的关系表达式:___ 2、问题解答: (每题 7 分,共 14 分) 2000 初中组 (1).已知,按中序遍历二叉树的结果为:abc 问:有多少种不同形态的二叉树可以得到这一遍历结果,并画出这些二叉树。 (2).有 2×n 的一个长方形方格,用一个 1×2 的骨牌铺满方格。例如 n=3 时,为 2×3 方格。此时用一个 1×2 的骨牌铺满方格,共有 3 种铺法。 试对给出的任意一个 n (n>0) ,求出铺法总数的递推公式。 3.问题求解: (6+6=12 分) 2000 高中组 (1).已知,按中序遍历二叉树的结果为:abc 问:有多少种不同形态的二叉树可以得到这一遍历结果,并画出这些二叉树。 (2).设有一个共有 n 级的楼梯,某人每步可走 1 级,也可走 2 级,也可走 3 级,用递推 公式给出某人从底层开始走完全部楼梯的走法。 例如: 当 n=3 时, 共有 4 种走法, 即 1+1+1, 1+2,2+1,3。 4、问题求解(5+7=12 分) 2001 年初中组

(1) 在 a,b,c,d,e,f 六件物品中,按下面的条件能选出的物品是: (1)a,b 两样至少有一样 (2)a,d 不能同时取 (3)a,e,f 中必须有 2 样 (4)b,c 要么都选,要么都不选 (5)c,d 两样中选一样 (6)若 d 不选,则 e 也不选 (2) 平面上有三条平行直线,每条直线上分别有 7,5,6 个点,且不同直线上三个点都 不在同一条直线上。问用这些点为顶点,能组成多少个不同三角形? 5、问题求解(5+7=12 分) 2001 年高中组 (1). 已知一棵二叉树的结点名为大写英文字母,其中序与后序遍历的顺序分别为: CBGEAFHDIJ 与 CGEBHFJIDA 则该二叉树的先序遍历的顺序为:ABCEGDFHIJ (2)平面上有三条平行直线,每条直线上分别有 7,5,6 个点,且不同直线上三个点都 不在同一条直线上。问用这些点为顶点,能组成多少个不同四边形? 6. 问题求解 每题 5 分 (2003 年高中组) (1) 无向图 G 有 16 条边,有 3 个 4 度顶点、4 个 3 度顶点,其余顶点的度均小于 3,则 G 至少_______个顶点。 (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)≠ф ,问至少安排_____天才能考完这 6 门课程。 7. 问题求解(共 2 题,每题 5 分,共计 10 分,2004NOIP 初赛提高组) (1) 5 名儿童到游乐场去玩。他们可以骑旋转木马,坐滑行铁道,乘宇宙飞船。已知其 中 20 人这三种东西都玩过,55 人至少玩过其中的两种。若每样乘坐一次的费用是 5 元,游乐场总共收入 700,可知有 名儿童没有玩过其中任何一种。 (2) 知 a, b, c, d, e, f, g 七个人中,a 会讲英语;b 会讲英语和汉语;c 会讲英语、意大利 语和俄语;d 会讲汉语和日语;e 会讲意大利语和德语;f 会讲俄语、日语和法语;g 会讲德语和法语。能否将他们的座位安排在圆桌旁,使得每个人都能与他身边的人 交谈?如果可以,请以“a b”开头写出你的安排方案: 。 参考答案: 1、x=n*n-n+1 2、(1) 5 种,图略 (2) 对 给 出 的 任 意 一 个 n(n>0) , 用 F(n) 表 示 其 铺 法 的 总 数 的 递 推 公 式 为 : F(1)=1 F(2)=2 F(n)=F(n-2)+F(n-1) (n≥3) 3、(1) 5 种 图略 (2) f(1)=1 f(2)=2 f(3)=4 f(n)=f(n-1)+f(n-2)+f(n-3) (n>3) 4、 (1) a、b、c、f (2) 751 5、(1) ABCEGDFHIJ (2) 2250 C(7,2)*C(5,2)+C(7,2)*C(6,2)+C(5,2)*C(6,2)+C(7,2)*5*6+C(5,2)*7*6+C(6,2)*7*5 6、 (1) 11 (2) 4

7、 (1)75-55-(700/5-20*3-35*2)=10 (2) a b d f g e c

阅读材料: 递推公式的推导
历年的信息学 (计算机) 奥林匹克分区联赛初赛的试题中均有根据要求写出递推公式(数 学上又叫通项公式)的题目。如 2000 年高中组的题目是:一个人上楼梯,一步可以跨一阶、 可以跨两阶、也可以跨三阶,假设有N阶楼梯,此人有多少种走法? 许多同学在推导公式时往往采用尝试法,从N=1,2,3?的情况依次算出有多少种 情况,然后观察出其中的规律,最后写出递推公式。如此上楼梯的走法可以转化为一个数字 的有序拆分: N=1 1=1 (只能一步跨一阶楼梯)共有1种走法,即 F(1)=1; N=2 2=1+1 (一步一阶) =2 (一步两阶) 共有2种走法,即 F(2)=2; N=3 3=1+1+1 (每一步一阶) =1+2 (第一步一阶,第二步两阶) =2+1 (第一步两阶,第二步一阶) =3 (一步三阶) 共有 4 种走法,即 F(3)=4; N=4 4=1+1+1+1 =1+1+2 =1+2+1 =1+3 以上 4 种走法除了第一步为一阶,后面的组合与 N=3 同 =2+1+1 =2+2 以上 2 种走法除了第一步为两阶,后面的组合与 N=2 同 =3+1 此走法除了第一步为三阶,后面的组合与 N=1 同 共有 7 种走法,即 F(4)=F(3)+F(2)+F(1)=7; N=5 5=1+1+1+1+1 =1+1+1+2 =1+1+2+1 =1+1+3 =1+2+1+1 =1+2+2 =1+3+1 以上 7 种走法除了第一步为一阶,后面的组合与 N=4 同 =2+1+1+1 =2+1+2 =2+2+1 =2+3 以上 4 种走法除了第一步为两阶,后面的组合与 N=3 同 =3+1+1 =3+2 以上 2 种走法除了第一步为三阶,后面的组合与 N=2 同 共有 13 种走法,即 F(5)=F(4)+F(3)+F(2)=13; ?? 由此推导出递推公式为: F(N)=F(N-1)+F(N-2)+F(N-3) (N>3) F(1)=1,F(2)=2,F(3)=4 这种推导方法主要靠排列准确、观察仔细,从而才能正确地写出递推公式。许多情况下

写出的排列组合不是少几种就是多一到几种, 很难写出正确的递推公式, 特别是排列组合的 种类较多时,人工的机械地排列组合就更难实现了,如N封信装在N个信封全装错的问题。 另外,通过观察写出的递推公式还不能证明是正确的,要证明其正确性,还要借助于数学归 纳法。其实我们可以直接用数学归纳法的思想来推导递推公式,还是来看楼梯的走法: 假设上 N 阶楼梯的过程已经进行到最后一步,因为每一步可以有三种走法,因此最后 一步也无非是跨一阶、 跨二阶或跨三阶。 如果最后一步跨一阶, 前面的 N-1 阶的走法有 F(N-1) 种;如果最后一步跨两阶,前面的 N-2 阶走法有 F(N-2)种;如果最后一步跨3阶,前面的 N-3 阶有 F(N-3)种。根据有关原则可以知道最后总的走法数目应是这三种走法的和。从而可 以推导出 F(N)=F(N-1)+F(N-2)+F(N-3)。 在这种构造推导公式时要考虑到是否全面, 如N封信装在N个信封全装错的问题: N封 写给N个人的信,有N个信封已经写好了地址,本来这 N 封信和 N 个信封是一一对应的, 假设N封信全都装错信封,有多少种不同的装法? 在构造时一般都能做出以下步骤的推导: 假设 N-1 封信全装错在 N-1 个信封里(N>2),有 F(N-1)种。现有第 N 封信和第 N 个 信封,对于 F(N-1)的某一种全装错的装法而言,把第 N 封信依次装在第一个信封、第二 个信封??第 N-1 个信封,而把原来第一个信封、第二个信封??第 N-1 个信封里的信装 在第 N 个信封里,这样的 N-1 种装法都符合要求。原 F(N-1)种都用此法,共有(N-1) *F(N-1)种,由此推出 F(N)=(N-1) ! 。 以上的构造并没有包括所有的情况,假设原 N-1 封信有 1 封信是装对的,而其它的 N-2 封是全装错的,此时把第 N 封信装在原装对的信封里, 而原信封里的信装在第 N 个信封里, 这样 N 封信全装错了信封。当第一封信装对信封,其它的 N-2 封信全装错共有 F(N-2)种 装法,当第二封信装对信封,其它的 N-2 封信全装错也有 F(N-2)种装法??,这种情况 总共有(N-1)*F(N-2)种装法。 所以 N 封信全装错信封的方法的个数的递推公式为: F(N)=(N-1)*F(N-1)+(N-1)*F(N-2) (N>2) F(1)=0, F(2)=2 因此,要在相对较短的时间里推导出相应的公式,用观察尝试法写出公式虽然简单,但 往往容易多写或少写几种情况, 从而写出错误的公式。 使用构造法, 即由 F (N-1) 、 F (N-2) ?? 的情况推导出 F(N) ,才是最终的目的。最后提醒别忘了写上初始值: F(1)=??;F(2)=??;??。 这是递推的起点。 有些问题虽然写不出递推公式, 但是实际操作的过程中有递推的思想, 可以通过文字描 述出其递推的过程。 思考题: 1、有 N 个黑棋子和 N 个白棋子如下图排列(N>=4) : ●●●●??●○○○○??○ 现在让你移动棋子, 每次只能移动相邻的两个棋子放到空白位置 (最左边或最右边 没棋子的地方也认为是空白位置) 。最终移成如下黑白相间的状态: ●○●○●○●○??●○ 写出移动方案。 (提示:先想出 N=4 时的移动方案,N>4 的情况都可以由 N-1 的推 导出。 2、将一个正方形分成 n 个小正方形(n>5)。


相关文章:
NOIP初赛练习之二(解答题)
NOIP 初赛练习之二(解答题) 前言:如何做解答题 解答题一般是根据要求写出表达式或画出图等, 涉及的知识点主要有数学方面的基本知 识、数据结构方面的如树和图等...
NOIP初赛练习题(分类)
(03 高中组题)D BDE AD AB AC E B BCD D BE NOIP 初赛练习之二(解答题) 前言:如何做解答题 解答题一般是根据要求写出表达式或画出图等, 涉及的知识点...
NOIP2010第十六届初赛试题及答案
NOIP2010第十六届初赛试题答案_学科竞赛_初中教育_教育专区。2010 NOIP Pascal...三. 阅读程序写结果(共 4 题,每题 8 分,其中第 4 题(1)、(2)各 4 ...
NOIP2015普及组初赛试题及答案(Pascal)
NOIP2015普及组初赛试题答案(Pascal)_学科竞赛_初中教育_教育专区。第二十一...阅读程序,并写出程序的正确运行结果:(每题 8 分,共 32 分) (1) 程序的...
noip2001初赛试题及答案
noip2001初赛试题答案_IT认证_资格考试/认证_教育...二、问题解答(5+7 分,两题共 12 分) 1.答:...吃哪些食物不发胖 在家全套瑜伽练习教程88份文档 2014...
NOIP2015提高组day1第二题解题报告
NOIP2015 提高组复赛 Day1 第二题解题报告 By 某蒟蒻 zrw 1. 题目大概描述(因为写的时候题目还没放出来)几个小盆友们在传递自己的信息(生日) ,并且每个小盆...
NOIP初赛练习题
NOIP练习题NOIP练习题隐藏>> NOIP 初赛练习题 下列设备哪一项不是计算机输入设备( ) A)鼠标 答案:C 在外部设备中,绘图仪属于( A.输入设备 答案:A (0.5)10...
Noip2010提高组初赛试题及详细解析(C语言)
Noip2010提高组初赛试题及详细解析(C语言)_建筑/土木_工程科技_专业资料。第十六...二.不定项选择题(共 10 题,每题 1.5 分,共计 15 分。每题有一个或多...
NOIP02提高组初赛试题附解答
NOIP02提高组初赛试题解答_IT/计算机_专业资料。noip 01-03提高初赛题目 解答...选择一个正确答案代码(A/B/C/时,填入每题的括号内(每题 1.5 分,多选无分...
NOIP初赛模拟试题及答案
NOIP初赛模拟试题及答案_计算机硬件及网络_IT/计算机_专业资料。信息学奥林匹克联赛...第一题3 每空2 第二题前1 每空2 每空5 28分 四、完善程序 (第一题3...
更多相关标签: