题目描述
有一颗二叉树, 最大深度为 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
- // 直观想法, 用二叉树, 深搜方法模拟每一个小猴子跑一遍
- #include<iostream>
- #include<vector>
- using namespace std;
- struct node{
- int num;
- int light;
- node* left;
- node* right;
- };
- int dfs(node* root,node* now){
- now->light= - now->light;
- if(now->left==NULL){
- return now->num;
- }
- if(now->light==1) dfs(root,now->left);
- else dfs(root,now->right);
- }
- int main(){
- int d,i;
- while(cin>>d>>i){
- int size=(1<<d)-1;
- node tree[size];
- for(int i=0;i<size;i++){
- tree[i].num=i+1;
- tree[i].light=-1;
- if(i<((1<<d-1)-1)){
- tree[i].left=&tree[2*i+1];
- tree[i].right=&tree[2*i+2];
- }
- else tree[i].left=tree[i].right=NULL;
- }
- int tem;
- for(int j=0;j<i;j++){
- tem = dfs(tree,tree);
- }
- if(!d | !i) {
- cout<<endl;
- continue;
- }
- cout<<tem<<endl;
- }
- return 0;
- }
- // 观察到每一个节点是按到达该层的猴子奇偶来判断向左或右的, 类似二分法.
- int main(){
- int d,i;
- while(cin>>d>>i){
- if(d==0&&i==0) break;
- int answer=1;
- for(int j=1;j<d;j++){
- if(i%2){
- answer*=2;
- i=i/2+1;
- }
- else{
- answer=answer*2+1;
- i=i/2;
- }
- }
- cout<<answer<<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3186435.html