NYOJ--小猴子下落

灰太狼 2022-08-26 14:09 137阅读 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

解析：二叉树的基础题，总感觉这道题没说清楚，所有叶子的深度都相同并不意味着是完全二叉树吧，但我看了这道题的讨论后感觉出题人是这个意思，完全二叉树，不然最后小猴子怎么跑也没解释，剩下的就是二叉树节点与其左孩子右孩子之间的关系了，当前节点的编号设为i则其左孩子的编号为2×i，右孩子的编号为2×i+1，然后设置一个标记数组来标记小猴子是否走过这里控制开关的的开和关就好了，另外不要忘了每组数据都要事先重置这个标记数组，我是用memset(数组指针,要重置的值,大小)，第三个参数如果写成sizeof(data)是错误的，应该写成sizeof(int)\*数组元素的个数,详细的可百度一下哈！好像这道题可以总结出公式，逐步二分会更简单，这样就不用分配标记数组了哈！

下面贴一下基础的代码

#include <iostream>
    #include <memory.h>
    using std::endl;
    using std::cin;
    using std::cout;
    int main()
    {
    	int D,I;
    	int isVisited[1000000];
    	while(1)
    	{
    		//保存最终的结果
    		int res;
    		cin >> D >> I;
    		if(D==0)
    			break;
    		int sum=1;
    		for(int i=1;i<D;++i)
    		{
    			sum*=2;
    		}
    		//每组数据都必须初始化data数组
    		//memset中不能用sizeof(data),这样会报错
    		memset(isVisited,0,sum*sizeof(int));
    		for(int i=1;i<=I;++i)
    		{
    			int temp=1;
    			while(1)
    			{
    				if(isVisited[temp]==0)
    				{//向左走，指向左孩子
    					isVisited[temp]=1;
    					temp=2*temp;
    				}else{
    					//向右走，指向右孩子
    					isVisited[temp]=0;
    					temp=2*temp+1;
    				}
    				if(temp>=sum)
    				{
    					res = temp;;
    					break;
    				}
    			}
    		}
    		cout << res << endl;
    	}
    	return 0;
    }

内存消耗较小的方法是，不用设置标记数组去判断，只需要知道第n个猴子到达当前节点的次数的奇偶性即可判断出最后一只猴子向它的左孩子走还是右孩子走，比如测试用例当前D=4，I=4；因为I%2==0经过第一个节点的时候是第四次到达该节点，说明到达该节点时此时开关是开的，所以向右孩子走，经过该节点的次数是偶数则按照题意就是向右走，奇数则是向左走。总结就是偶数右孩子，奇数左孩子

第一个的节点很容易判断，那么后面的节点我们该怎么判断呢？其实想想也很容易，当从第一个节点向左走到达新的节点时，此时该猴子经过该节点的次数应该是I/2，因为开关是交替的，就像二分法一样，猴子都是左右左右交替走的，也就是一半向左走一半向右走，所以应该是猴子的个数/2，越向下走D越大，I也就越小，当向右走的时候I为奇数此时I=(I+1)/2。总结就是深度没增加一层，次数就减半。

那么上面的判断条件和走向弄清楚了，什么时候该停止类？很明显，当猴子到达深度为D-1时，我们就可以判断出下一步猴子将会跳的方向，即叶子节点的编号，记录下来输出就OK了哈！

说的好罗嗦，直接贴代码

#include <iostream>
    using std::endl;
    using std::cin;
    using std::cout;
    int main()
    {
    	int D , I;
    	while(cin >> D >> I)
    	{
    		if(D==0&&I==0)
    			break;
    		int res=1;
    		for(int i=1;i<D;++i)
    		{
    			if(I%2==0)
    			{//偶数右走
    				res=res*2+1;
    				I/=2;
    			}else{
    				//奇数
    				res=res*2;
    				I=(I+1)/2;
    			}
    		}
    		cout << res << endl;
    	}
    }