学步园

有一颗二叉树，最大深度为D,且所有叶子的深度都相同。所有结点从左到右从上到下的编号为1,2,3，·····，2的D次方减1。在结点1处放一个小猴子，它会往下跑。每个内结点上都有一个开关，初始全部关闭，当每次有小猴子跑到一个开关上时，它的状态都会改变，当到达一个内结点时，如果开关关闭，小猴子往左走，否则往右走，直到走到叶子结点。

一些小猴子从结点1处开始往下跑，最后一个小猴儿会跑到哪里呢？

输入

输入二叉树叶子的深度D,和小猴子数目I，假设I不超过整棵树的叶子个数，D<=20.最终以 0 0 结尾

输出

输出第I个小猴子所在的叶子编号。

样例输入

4 2
3 4
0 0

样例输出

12
7

给定一棵包含2^d个节点的完全二叉树，如果把节点从上到下从左到右编号为1,2,3,4......
则节点k的左右子节点分别是2k和2k+1。形如：

解法一：不难写出如下模拟程序：

#include<cstdio>
#include<cstring>
const int max = 20;
int s[1<<20]; //最大节点个数为2^20-1 
int main()
{
	int D,I,i,k,n;
	while(scanf("%d %d",&D,&I)&&(D||I))//d深度，i小球个数 
	{
		n = (1<<D)-1;  //等同于 n = 2^D-1 
		memset(s,0,sizeof(s));
		for(i=0; i<I; i++)
		{
			k=1;
			while(1)
			{
				s[k] = !s[k];
				k = s[k]?k*2:k*2+1;
				if(k>n)
					break;
			}
		}
		printf("%d\n",k/2);
	}
}
注释：a<<20将a的二进制代码左移20位，即a*2*2*...*2（a乘20个二）。

解法二：
每个小猴都会落在根节点上，因此前两个小猴必然是一个在左子数，一个在右子树。
一般地，只需看小猴编号的奇偶性，就能知道它是最终在哪颗子数中。例如，对于那些
落入根节点左子数的小猴来说，只需知道该小猴是第几个落在根的左子数里的，就可以
知道它下一步往左还是往右了。依次类推，直到小猴落在叶子上。
如果使用题目给出的编号I，则当I是奇数时，它是往左走的第（I+1)/2个小猴，当I时偶数时，
它是往右走的第I/2个小猴。这样，可以直接模拟最后一个小猴的路线。 

#include<cstdio>
int main(){
	int D,I,i,k;
	while(scanf("%d %d",&D,&I)&&(D||I))
	{
		for(i=1,k=1; i<=D-1 ; i++)
		{
			if(I&1)  {I = (I+1)/2; k = k*2;}//I是奇数 
			else{I = I/2; k = k*2+1;}
		}
		printf("%d\n",k);
	}
}
注释：I&1将I的二进制与1进行&运算，I是偶数为0，奇数为1. 

这样，程序的运算量就与小猴编号无关了，而且节省了一个巨大的数组。 

————来自《算法竞赛入门经典》p149