小球下落

   有一棵二叉树，最大深度为D，且所有的叶子深度都相同。所有结点从上到下从左到右编号为1，2，3，…，2eD-1。在结点1处放一个小球，它会往下落。每个结点上都有一个开关，初始全部关闭，当每次有小球落到一个开关上时，它的状态都会改变。当小球到达一个内结点时，如果该结点的开关关闭，则往上走，否则往下走，直到走到叶子结点，如下图所示。
    一些小球从结点1处依次开始下落，最后一个小球将会落到哪里呢？输入叶子深度D和小球个数I，输出第I个小球最后所在的叶子编号。假设I不超过整棵树的叶子数；D<=20。输出最多包含1000组数据。
样例输入：
4 2
3 4
10 1
2 2
8 128
16 12345
样例输出：
12
7
512
3
255
36358

解法一：

#include<iostream>
#include<cstdio>
#include<cstring>
const int maxn=20;
int s[1<<maxn];//最大节点数为sqrt(2,maxn)-1;

int main(){
    int D,I;
    while(scanf("%d%d",&D,&I)==2){
        memset(s,0,sizeof(s));//将树中的全部节点关闭
        int k,n=(1<<D)-1;//n是最大节点编号
        for( int i=0; i<I; i++ ){
            k=1;
            for( ; ; ){
                s[k]=!s[k];//当前节点状态变化
                k=s[k]?k*2:k*2+1;
                if(k>n) break;//出界
            }
        }
        printf("%d
",k/2);
    }
    return 0;
}

分析：
1.对于一个结点k，它的左儿子，右儿子的编号分别是2k和2k+1。
2.尽管每次小球都是严格下落D-1次，但上述代码中采用“if(k>n) break”的方法判断“出界”更具一般性。
3.该程序运算量太大：由于I可以高达2^(D-1)，每个测试数据下落总层数可能会高达2¹⁹*19（即I*19）=9961472,而一共可能有1000组数据。

如果使用题目中给的编号I,则当I是奇数时，他是往左走的第（I+1）个小球；当I是偶数时，他是往右走的第I/2个小球。这样，可以直接模拟最后一个小球的路线。

解法二：

#include <stdio.h>
#include <string.h>
#define MAXN 20
int s[1<<MAXN];                        //将1左移20位，即得最大结点个数为2eMAXN-1
int main(void)
{
    int D, I;                        //定义小球的个数,即最后一个小球编号为I
    //直接模拟最后一个小球的路线
    while(scanf("%d%d", &D, &I) == 2)
    {
        memset(s, 0, sizeof(s));            //开关（默认0为关闭状态），memset函数包含头文件string.h
        int k;                        //n是最大结点编号
        for(int i = 0; i < I; i++)  //连续让n个小球下落
        {
            k = 1;
            for(int i = 0; i < D-1; i++)        //连续进行D-1次下落
            if(I%2) { k = k*2; I = (I+1)/2; }    //当I为奇数时，它是往左走的第（I+1）/2个小球
            else    { k = k*2+1; I /= 2; }        //当I为偶数时，它是往右走的第I/2个小球
        }
        printf("%d
", k);            //输出最后一个小球I的叶子编号
    }
    return 0;
}