NOIP初赛知识点复习总结资料讲解.ppt

英 汉 意 俄 日 德 法 a O b O O c O O O d O O e O O f O O O g O O 2. 取火柴游戏的规则如下：一堆火柴有N 根，A、B两人轮流取出。每人每次可以取 1 根或2 根，最先没有火柴可取的人为败 方，另一方为胜方。如果先取者有必胜策 略则记为1，先取者没有必胜策略记为0。 当N 分别为100，200，300，400，500 时，先取者有无必胜策略的标记顺序为 （回答应为一个由0 或1 组成的字符串）。 11011，简单的博弈论，小学奥数题 （取石子游戏） 现有 5 堆石子,石子数依 次为 3，5，7，19，50，甲乙两人轮流从 任一堆中任取（每次只能取自一堆，不能 不取）, 取最后一颗石子的一方获胜。甲 先取，问甲有没有获胜策略（即无论 乙怎 样取，甲只要不失误，都能获胜）？ T=3^5^7^19^50=32，取掉32后T=0，面对 T=0的状态时，先取者必败 普及组的题目。 第一次在第五堆里面取32枚石子。 1．将 2006 个人分成若干不相交的子集， 每个子集至少有 3 个人，并且： （1）在每个子集中，没有人认识该子集 的所有人。 （2）同一子集的任何 3 个人中，至少 有 2 个人互不认识。 （3）对同一子集中任何 2 个不相识的 人，在该子集中恰好只有 1 个人认识这两 个人。 则满足上述条件的子集最多能有 _______个？ 401，主要方法是根据(1)，(2)，(3)进行假设， 发现至少需要5个人才能同时满足(1)，(2)，(3)， 于是……2006/5，一个6人，其余5人 2．将边长为 n 的正三角形每 边 n 等分，过每个分点分别 做另外两边的平行线，得到若 干个正三角形， 我们称为小 三角形。正三角形的一条通路 是一条连续的折线，起点是最 上面的一个小三角形，终点是 最 下面一行位于中间的小三 角形。在通路中，只允许由一 个小三角形走到另一个与其有 公共边的且位于同 一行或下 一行的小三角形，并且每个小 三角形不能经过两次或两次以 上（图中是 n=5 时一条通路 的例 子）。设 n=10，则该正 三角形的不同的通路的总数为 _______。 362880 严格证明挺复杂，找规律 可以知道总数为(n-1)! 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)=_____。 289 S(n,r)=S(n-1,r-1)+r*S(n-1,r) 边界条件自己找。 难题，递推类问题 下面介绍一个简单的递推问题，好让大家 初步认识递推。 小明上楼，一步可以上一级，也可以上两 级，请问上n级有多少种上法？例如，上2 级可以有1+1，也可以一次上2级。上3级 可以是1+1+1，2+1,1+2三种。 设f(n)表示上n级需要的步数，显然只能够从n-1级或n- 2级上到第n级，所以方法总数适用加法原理， f(n)=f(n-1)+f(n-2)，斐波那契数列！ 其中f(1)=1，f(2)=2，后面的都可以根据这两个初 始条件推出来 2．N个人在操场里围成一圈，将这N个人 按顺时针方向从1到N编号，然后从第一个 人起，每隔一个人让下一个人离开操场， 显然，第一轮过后，具有偶数编号的人都 离开了操场。依次做下去，直到操场只剩 下一个人，记这个人的编号为J(N)，例 如，J(5)=3，J(10)=5，等等。 则J(400)= _______。 （提示：对J(N)=2m+r进行分析，其中 0≤r2m）。 289，找规律，数学好的智商分数的比较占优势 N 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 J(n) 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1 3 m 2 0 2 1 2 1 2 2 2 2 2 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 4 2 4 2 r 0 0 1 0 1 2 3 0 1 2 3 4 5 6 7 0 1 2r+1 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1 3 非常容易看出：J(N)=J(2m+r)=2r+1 J(400)=J(28+144)=2*144+1=289 问题求解总结 1、要耐心地寻找规律 2、要冷静的分析问题 3、不到万不得已决不