落球问题

　　这不是一道什么竞赛题目，就是刘汝佳老师在算法竞赛入门经典中给的关于二叉树的例子。自己写了一下，附到博客园上面来供自己回忆；

第一种解法是设了一个ok判断球是往左还是往右，但是要开一个2^20的数组，用来记录每个位置的0/1开关情况。这个代码很简单，在书的100页有详细的讲解。

#include<stdio.h>
#include<string.h>
#define max 20
int str[1<<max];
int ok;
int main()
{
    int a,b;
    while(scanf("%d%d",&a,&b) == 2)
    {
        memset(str,0,sizeof(str));
        int k=0,n;
        n=(1<<a)-1;
        for(;k<b;k++)
        {
            ok=1;
            for(;;)
            {
                str[ok] = !str[ok];
                ok=str[ok]?2*ok:2*ok+1;
                if(ok>n) break;
            }
        }
        printf("%d\n",ok/2);
    }
    return 0;
}

然后看刘老师讲了一种优化解法：利用那个数字的奇偶性来判断在第几个节点落在跟的左子树里。从而判断位置，不太好说，自己得好好想想。

#include<stdio.h>
#include<string.h>
int main()
{
    int line,ball;
    int ok,i,j;
    while(scanf("%d%d",&line,&ball) == 2)
    {    
        ok=1;
        for(i=0;i<line-1;i++)
        {
            if(ball%2)
            {
                ok=2*ok;
                ball=(ball+1)/2;
            }
            else
            {
                ok=2*ok+1;
                ball/=2;
            }
        }
        printf("%d",ok);
    }
}