小猴子下落——个人c++解

曾经终败给现在 2022-06-08 07:10 180阅读 0赞

## 小猴子下落 ##

## 时间限制：3000 ms  |  内存限制：65535 KB ##

## 难度：3 ##

## 描述 ##

有一颗二叉树，最大深度为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<bits/stdc++.h>//小猴子下落，满二叉树
    using namespace std;
    int q[1500000];
    int main()
    {
        int i,d,x;
        while(1)
        {
            scanf("%d %d",&d,&i);
            memset(q,0,sizeof(q));//每组数据，数组归零代表关闭
            if(d==0&&i==0)break;
            for(int j=0;j<i;j++)//猴子依次下落
            {
                x=1;//节点从1开始
                for(int k=0;k<d-1;k++)//深度管理下落次数，下落次数为深度减一
                {
                    if(q[x]==0)//如果关闭
                    {
                        q[x]=1;//改变状态
                        x=2*x;//关闭向左下落，即到达左孩子，节点编号为2*x
                    }
                    else//如果开启
                    {
                        q[x]=0;//改变状态
                        x=2*x+1;//关闭向右下落，即到达右孩子，节点编号为2*x+1
                    }
                }
            }
            printf("%d\n",x);
        }
        return 0;
    }