有一颗二叉树，最大深度为 DD，且所有叶子的深度都相同。所有结点从左到右从上到下的编号为 1,2,3,\cdots1,2,3,?，22 的 DD 次方减 11。在结点 11 处放一个小猴子，它会往下跑。每个内结点上都有一个开关，初始全部关闭，当每次有小猴子跑到一个开关上时，它的状态都会改变，当到达一个内结点时，如果开关关闭，小猴子往左走，否则往右走，直到走到叶子结点。
一些小猴子从结点 11 处开始往下跑，最后一个小猴儿会跑到哪里呢？
输入二叉树叶子的深度 DD，和小猴子数目 II，假设 II 不超过整棵树的叶子个数，D \le 20D≤20，最终以 00 00 结尾。
输出第 II 个小猴子所在的叶子编号。
4 2 3 4 0 0
12 7
算法：递推
思路：如果当前节点的猴子数量是奇数，那么猴子往左边走，否则猴子往右边走；
猴子每往下面走一层，递推出每层猴子的数量，整个大循环递推层数
往左走k = 2*k,往右走k=2*k+1
#include <iostream> #include <cstring> #include <algorithm> #include <cstring> using namespace std ; int main(){ int n, d ; while(cin >> d >> n , d||n){ int ans = 1 ; for(int i=1;i<d;i++){ if(n%2){ ans *= 2 ; n = (n+1)/2 ; }else{ ans = ans * 2 + 1 ; n /= 2 ; } } cout << ans << endl ; } return 0 ; }
...
原文：https://www.cnblogs.com/gulangyuzzz/p/12465073.html