小猴子下落
有一颗二叉树，最大深度为D,且所有叶子的深度都相同。所有结点从左到右从上到下的编号为1,2,3，·····，2的D次方减1。在结点1处放一个小猴子，它会往下跑。每个内结点上都有一个开关，初始全部关闭，当每次有小猴子跑到一个开关上时，它的状态都会改变，当到达一个内结点时，如果开关关闭，小猴子往左走，否则往右走，直到走到叶子结点。
一些小猴子从结点1处开始往下跑，最后一个小猴儿会跑到哪里呢？
?4 23 40 0
127
? ?题意：
? ?从根数1开始往下落，初始状态全为0，每经过一次就改变一次状态，0则到左儿子处，1则到右儿子处，输出最后一次下落后所在位置。
? ?思路：
? ?二叉树的简单应用，帮助理解二叉树。模拟一下猴子下落过程即可。
AC:
?
#include<stdio.h>#include<string.h>#include<math.h>int a[1500000];int main(){int n,m;while(scanf("%d%d",&n,&m)!=EOF){int i,j;if(!n&&!m) break;memset(a,0,sizeof(a));//初始设为0，表全关for(i=1;i<=m;i++){j=1;while(j<pow(2,n-1)){if(a[j]==1) { a[j]=0; j=2*j+1;}//往右儿子走else { a[j]=1; j=2*j; }//往左儿子走}}printf("%d\n",j);}return 0;}?还有一种更简单的方法AC：
?
上面的方法虽然简单易懂，但是运算量太大了，所以可以直接模拟最后一只猴子的下落路线。
从序号的奇偶性来观察，从节点1开始，如果这个序号R是奇数的话，则往左走，也就是说它是在节点1往左走的第(R+1)/2只猴子，如果是偶数的话，则往右走，它是在节点1往右走的第R/2只猴子。
这样看来，只需要看猴子编号的奇偶性，就可以知道它最终落在哪里了，当它落在某一位置时，只需要知道它是第几个落在这个位置，就知道它往左走还是右走了。
比如：
有1号，2号，3号，4号，5号共5只猴子，一共有3层数，则：
1???2?3?4567第一层：1号是第1只猴子在第一层1这个位置上，则他会往左走到第二层2的位置上；2号是第2只猴子在第一层1这个位置上，则他会往右走到第二层3的位置上…………
第二层：1号是第1（（1+m）/2）只猴子在第二层2这个位置上，3号是第2（（1+m）/2）只……2号是第1（m/2）只猴子在第二层2这个位置上，4号是第2（m/2）只……
依次类推，把关注的对象从本身的序号变为第N只落在某一位置上来加以判断。
?
#include<stdio.h>int main(){int n,m;while(scanf("%d%d",&n,&m)!=EOF&&(n+m)){int i,pos=1;for(i=1;i<n;i++)//循环层数{if(m%2) {pos=pos*2;m=(m+1)/2;}//在这个位置是奇数，往左走，序号变化else {pos=pos*2+1;m=m/2;}//偶数，往右走，序号变化}printf("%d\n",pos);}return 0;}? ?总结：
?
? ?模拟也需要有技巧。