NOIP问题求解集合.doc

WORD格式分享 精品资料整理 NOIP1998 普及 二、问题求解：（20%） 1．已知一个数列U1，U2，U3，…，UN，… 往往可以找到一个最小的K值和K个数a1，a2， …，ak使得数列从某项开始都满足： 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 。试对数列12，22，32，…，n2,…求K和a1,a2, …,aK使得（A）式成立。 {7%} 2．某班有50名学生，每位学生发一张调查卡，上写a，b，c三本书的书名，将读过的书打?，结果统计数字如下： 只读a者8人；只读b者4人；只读c者3人；全部读过的有2人；读过a，b两本书的有4人；读过a，c两本书的有2人；读过b，c两本书的有3人；{6%} （1）读过a的人数是 （2）一本书也没有读过的人数是 3．任给自然数n，k， 1≤K≤9 ，按如下计算步骤求序列XJXJ-1……X0的步骤：{8%} j=0 如果N=K 则转第3步，否则转第7步 Xj = N MOD K {div表示整数除法，结果取整数； N =N DIV K mod表示整除取余数} j=j+1 回第2步 Xj = N 结束 试求当： N=1998， K=3时，XJXJ-1……X0 之值。 NOIP1998 提高 二、问题求解：(21%) 1、已知一个数列U1，U2，U3，…Un，…往往可以找到一个最小的k值和k个数a1，a2，…，ak，使得数列从某项开始都满足： un+k=a1un+k－1+a2un+k－2+…+akun (A) 例如对斐波拉契数列1，1，2，3，5，…可以发现：当k=2，a1=1，a2=1时，从第3项起(即n≥1)都满足un+2=un+1+un。 试对数列13，23，33，…，n3，…求k和a1，a2，…，ak使得(A)成立。 (8%) 2、给出一棵二叉树的中序遍历：DBGEACHFI与后序遍历：DGEBHIFCA画出此二叉树。 (8%) 3、用邻接矩阵表示下面的无向图： NOIP1999 普及 二、回答问题（10分） 在磁盘的目录结构中，我们将与某个子目录有关联的目录数称为度。例如下图 该图表达了A盘的目录结构：D1，Dll，…，D2均表示子目录的名字。在这里，根目录的度为2，D1子目录的度为3，D11子目录的度为4，D12，D2，D111，D112，D113的度均为1。不考虑子目录的名字，则可简单的图示为如下所示的树结构： 若知道一个磁盘的目录结构中，度为2的子目录有2个，度为3的子目录有1个，度为4的子目录有3个。 试问：度为1的子目录有几个？ 三、公式推导（10分） 根据Nocomachns定理，任何一个正整数n的立方一定可以表示成n个连续的奇数的和。 例如： 13＝ 1 23＝ 3＋ 5 33＝ 7＋ 9 ＋11 43= 13+15+17+19 在这里，若将每一个式中的最小奇数称为X，那么当给出n之后，请写出X与n之间的关系表达式： NOIP1999 提高 二、回答问题（10分） 将Ln定义为求在一个平面中用n条直线所能确定的最大区域数目。例如：当n=1时，L1=2,进一步考虑，用n条折成角的直线（角度任意），放在平面上，能确定的最大区域数目Zn是多少？例如：当n=1时，Z1=2（如