NOIP 2015 普及组 基础题5
21 重新排列 1234使得每一个数字都不在原来的位置上，一共有( )种排法
22 一棵结点数为 2015的二叉树最多有( )个叶子结点
2 相关知识点
1) 错位排列
考虑一个有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。 n个元素的错排数记为D(n)
错排问题最早被尼古拉·伯努利和欧拉研究，因此历史上也称为伯努利-欧拉的装错信封的问题。
这个问题有许多具体的版本，如在写信时将n封信装到n个不同的信封里，有多少种全部装错信封的情况？
又比如四人各写一张贺年卡互相赠送，有多少种赠送方法？自己写的贺年卡不能送给自己，也是典型的错排问题
例题
有99封信，装到99个信箱中，正确的装法是，每封信装到正确的信箱中，即1号信装1号信箱，2号信装2号信箱
每封信都恰好装错的装法一个有多少种？
解析
D[i]表示i封信进行错排
此题需要计算D[99]
通过枚举可知，D[1]=0,D[2]=1,D[3]=2
此题可分2步
第1步
1 把信放入信箱，第1个信箱可以放2~99总共n-1封，即98封信，具体如下
第2步
2 要求装错，1号信不能放入1号信封，除1号信，其他都可以放入1号信封
考虑3号放入1号信封，此时分两种情况
1号信放入3号信和1号信不放入3号信箱2种情况
1号信放入3号信封时
1号信和3号信分别3号信封和1号信封，剩余2，4，5...99封信和2，4，5...99个信箱进行错排
满足97封信进行错排即D[n-2]=D[97]
1号信不放3号信封时
此时3号信已经放入1号信封，不需要考虑3号信和1号信封
把1号替换到3号信，此时1号信不能放入3号信封，观察信2，1，4，5...99和信封2，3，4，5...99，满足错排
98封信进行错排，这种情况错排D[n-1]=D[98]
根据乘法原理，所以错排的递推公式为
D[n] = (n-1) * (D[n-1] +D[n-1])
D[99]=98 * (D[98] + D[97] )
由前面枚举可知
D[1]=0,D[2]=1,D[3]=2
推出以下错排
D[4]=(4-1) * (D[4-1] + D[4-2])=3*(D[3]+D[2])=3 * (2+1)= 9
D[5]=(5-1) * (D[5-1] + D[5-2])=4*(D[4]+D[3])=4 * (9+2)= 44
2) 树的相关概念
根节点
在一颗树形结构中，最顶层的那个节点就是根节点了，所有的子节点都源自它发散开来。
父节点
树的父子关系和现实中很相似，若一个节点含有子节点，则这个节点称为其子节点的父节点。
叶子节点
直观来看叶子节点都位于树的最底层，就是没有分叉的节点，严格的定义是度为 0 的节点叫叶子节点。
非叶节点
在树中的所有节点，除去叶子节点都为非叶节点
二叉树
每个结点至多拥有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒
例如下面是一棵二叉树
完全二叉树
除了最下层，其他每层都饱满，去除最后一层是一棵满二叉树，最下层的结点都集中在该层最左边的若干位置上
完全二叉树最后1层叶子节点的数量
包括最后1层所有节点和倒数第2层的叶子节点数量
上图如果3没有子节点，也为叶子节点
3 思路分析
21 重新排列 1234使得每一个数字都不在原来的位置上，一共有( 9 )种排法
分析
根据错排公式
D[n] = (n-1) * (D[n-1] +D[n-1])
由前面枚举可知
D[1]=0,D[2]=1,D[3]=2
推出以下错排
D[4]=(4-1) * (D[4-1] + D[4-2])=3*(D[3]+D[2])=3 * (2+1)= 9
22 一棵结点数为 2015的二叉树最多有( 1008 )个叶子结点
分析
二叉树是每个节点最多有两个子节点的树结构。通常，我们称子节点为左子节点和右子节点。
为了最大化叶子节点的数量，我们应该尽量让每个非叶子节点只有两个子节点（即完全二叉树）
根节点高度为1，则高度为n的满二叉树所有节点树为2^n-1
2015个节点在高度10和11之间
2^10-1=1023
2^11-1=2047
完全二叉树最后一层都为叶子节点2015-1023=992个
倒数第2层有些没有子节点，也是叶子节点2047-2015=32,对应上一层会少一半32/2=16
所以总的叶子节点数量为992+16=1008