有一颗二叉树，最大深度为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 来源 [张洁烽]原创 上传者张洁烽
只要判断该猴子是第几只从该节点通过的，偶数向右（之前有奇数只通过），奇数想左，开关是一开一关的，所以猴子通过时候肯定是一左一右，若I为偶数则I＝I／２，奇数则I＝（Ｉ＋１）／２；
#include<stdio.h> #include<math.h> int main() { int D,I,i,j,t; while(scanf("%d %d",&D,&I)!=EOF&&D!=0&&I!=0) { int t=1; for(j=1;j<D;++j) { if(I%2==0)//1为开，0为关，关往左，开往右 { t=2*t+1; I=I/2; } else { t=t*2; I=(I+1)/2; } } printf("%d\n",t); } return 0; }
此方法比用数组记录开关状态节省内存
