小球下落
有一棵二叉树,最大的深度为D,所有叶子的深度都相同,所有节点从上到下从左到右的编号为 1,2,3,4....2^(D-1)
在节点1处放一个小球,它会往下落,每个内节点上都有一个开关,初始化的时候都是关着的,当每次有小球落到一个开关的时候,它的状态就会变化
当小球到达一个内节点的时候,如果开关是关闭的,就往左走,否则就往右走,直到走到叶子节点。
输入 D I
D表示二叉树的深度,在输入I表示第几个小球
（D <= 20 输入最多包含1000组数据）；
输出
第I个小球最后落入的叶子节点数目。
分析： 本质 -> 二叉树
知识：
结点的度：一个结点拥有子树的数目称为结点的度
树的度：树中所有结点的度的最大值
叶子结点：也称为终端结点，没有子树的结点或者度为零的结点
二叉树的性质：
性质1：二叉树的第i层上至多有2i-1（i≥1）个节点
性质2：深度为h的二叉树中至多含有2h-1个节点
性质3：若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1
性质4：具有n个节点的完全二叉树深为log2x+1（其中x表示不大于n的最大整数）
性质5：若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：
当i=1时，该节点为根，它无双亲节点
当i>1时，该节点的双亲节点的编号为i/2
若2i≤n，则有编号为2i的左节点，否则没有左节点
若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点
重点：
对于一个结点，其左右结点分别为 2k 和 2k+1，其父结点为 k/2
多运用位运算 1 << maxd
书中参考代码：
1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 const int maxn = 20; 5 int s[1<<maxn]; 6 int main(){ 7 int D,I,k; 8 while(scanf("%d %d",&D,&I)==2){ 9 memset(s,0,sizeof(s)); 10 int n=(1<<D)-1; // n为最大结点编号 11 for(int i=0;i<I;i++){ // I个小球下落 12 k=1; 13 while(1){ 14 s[k] = !s[k]; 15 k = s[k] ? k*2 : k*2+1; 16 if(k > n) break; 17 } 18 } 19 printf("%d\n",k/2); 20 } 21 }