有一颗二叉树，最大深度为D,且所有叶子的深度都相同。所有结点从左到右从上到下的编号为1,2,3，·····，2的D次方减1。在结点1处放一个小猴子，它会往下跑。每个内结点上都有一个开关，初始全部关闭，当每次有小猴子跑到一个开关上时，它的状态都会改变，当到达一个内结点时，如果开关关闭，小猴子往左走，否则往右走，直到走到叶子结点。

一些小猴子从结点1处开始往下跑，最后一个小猴儿会跑到哪里呢？

输入
输入二叉树叶子的深度D,和小猴子数目I，假设I不超过整棵树的叶子个数，D<=20.最终以 0 0 结尾
输出
输出第I个小猴子所在的叶子编号。



#include <stdio.h>
#include <math.h>
#include <string.h>
int main()
{
    int m,n,i;
    int max=pow(20,2)-1;
    int a[max];
    scanf("%d%d",&m,&n);
    while(m!=0&&n!=0)
    {
        memset(a,0,sizeof(int)*m);                //先把数组置位0，
        for(i=1;i<=n;)
        {
            while((2*i<m)||((2*i+1)<m))            //当没走到叶子结点时
            {
                 if(a[i]==0)                        //如果a[i]没走过，
                {
                    a[i]=1;                        //a[i]置位1，说明a[i]已走过
                    i=2*i;                        //走向做孩子。
                }
                else if(a[i]==1)                //如果走过
                {
                    i=2*i+1;                    //走向右孩子
                    a[i]=1;                        //a[i]置位1，说明a[i]已走过
                }
            }
            printf("%d\n",i);                    //输出最后的位置。
            scanf("%d%d",&m,&n);
        }
    }
    return 0;
}

不知道哪考虑错了，请各位指教。
可能是逻辑错了。        

我还是那句哈~

我说说自己的思路~

应该一个循环就可以啦~
先把i取余于叶子节点数目~
再把区间分治成两半~
判断第i个猴子在左半区间还是右半区间~
i%2==1则在左半区间,i%2==0则在右半区间~
把i/=2然后再用递归思想求子区间的左半区间还是右半区间~直到(i/=2)==0为止
随意思考到的,不知道是不是这样子~

还有直接的话2的20次方乘以深度20有可能会超时哦~

[此贴子已经被作者于2017-12-11 17:22编辑过]

这个没有细测,不过思路应该没有问题~试试看~

#include<stdio.h>
#include<math.h>

#define N 20

unsigned  fun(unsigned ,unsigned );

int main( void )
{
    unsigned n;
    unsigned m;
    
    if (scanf("%u%u",&n,&m)!=2&&n>N)
        return 1;
        
    printf("%u\n",fun(n,m));
    
    return 0;
}

unsigned fun(unsigned n ,unsigned m)
{
    
    unsigned i;
    unsigned s=0;
    
     m=(m-1)%(1<<--n);
     
     i=1<<(unsigned )(log(m)/log(2));

     for (--n;i!=0;i>>=1)
         s=((!!(i&m))<<n)|(s>>1);
     
    return s+1;
}

PS：叶子节点编号我没按题意,如果要对号入座的话最后结果加个原来的(1<<(n-1))-1就可以了~

[此贴子已经被作者于2017-12-11 20:56编辑过]

2楼分治法是比较好的办法。
我仔细分析后发现2楼有个小问题。
对于第一个节点，没有问题通过奇数偶数来判断位置，
但是如果对于奇数来说，左边应该递归的为i/2+1,就3层来说，如果猴子为3，其实左边子数是走了两次。而右边子树走了一次。

多谢提醒,其实这个问题是相对的,看了不是之前以下标为1的问题,而是我求得的是叶子编号最左边的开始下标为1的结果,加上上一层总结点数就符合题意了~

[此贴子已经被作者于2017-12-12 05:06编辑过]

好的 谢谢。

谢谢、

http://blog.

8楼那个看过可以的~这个可以用~

PS:其实修改前本来就已经可以了,不过既然用到用了位运算就尽可能地让它发挥作用比较好,并且题意说明i不会大于叶子数目,则不用考虑取余问题了,这样就可以完全实现位运算~

#include<stdio.h>

#define N 20

unsigned  fun(unsigned ,unsigned );

int main( void )
{
    unsigned n;
    unsigned m;

    while (scanf("%u%u",&n,&m)==2&&n!=0&&m!=0&&n<=N)
    printf("%u\n",fun(n,m));
    
    return 0;
}

unsigned fun(unsigned n ,unsigned m)
{
    unsigned s=0;
    unsigned i=1<<--n;
     
    for (m=--m<<1|1;i;i>>=1)
         s=!!(i&m)<<n|s>>1;
     
    return s;
}

[此贴子已经被作者于2017-12-12 22:31编辑过]

不太会用位运算，在什么地方用它比较合适呢？