NYOJ-63 小猴子下落（二叉树及优化算法详解）

时间：2021-12-09 14:51:21

 

小猴子下落

时间限制：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<iostream>

 #include<queue>

 #include<cmath>

 using namespace std;

 struct node

 {

     int data;

     int flag;

     node *lchild,*rchild;

     node();

 };

 node::node()

 {

     flag=-;

     rchild=lchild=NULL;

 }

 void createTree(int d,node *&root)

 {

     queue<node *> q;

     while(!q.empty())

         q.pop();

     root=new node;

     static int count=;

     root->data=++count;

     q.push(root);

     node *t=root;

     while(count!=pow(,d)-)

     {

         t=q.front();

         q.pop();

         t->lchild=new node;

         t->lchild->data=++count;

         q.push(t->lchild);

         t->rchild=new node;

         t->rchild->data=++count;

         q.push(t->rchild);

     }

     t=NULL;

     count=;

 }

 /*

 void LevelOrder(node *root)

 {    //队列实现

     queue<node *> q;

     node *t=root;

     if(t!=NULL) q.push(t);                //根非空，入队

     while(!q.empty())                //队不空

     {

         t=q.front();

         q.pop();                    //出队

         cout<<t->data<<" ";

         if(t->lchild)

             q.push(t->lchild);  //遍历左孩子

         if(t->rchild)

             q.push(t->rchild); //遍历右孩子

     }

 }

 */

 void Go(int &t,node *&root)

 {

     if(root->lchild&&root->rchild){

     if(root->flag==-)

     {

         Go(t,root->lchild);

         root->flag=;

     }

     else

     {

         Go(t,root->rchild);

         root->flag=-;

     }

     }

     else

         t=root->data;

 }

 int main()

 {

     int d,num;

     while(cin>>d>>num,d&&num){

     node *root=NULL;

     createTree(d,root);

     int t;

     for(int i=;i<num;i++)

         Go(t,root);

     cout<<t<<endl;

     }

 return ;

 }

tree

但是如果测试数据有N组，层数D有19层呢（D<=20)，那么树将建立2^19-1个结点，时间和空间耗费都很大。那么怎么办？

下面讲一下优化算法：

               1               
        2                    3      
  4       5       6       7  
8    9    10   11    12     13   14   15 

NYOJ-63 小猴子下落（二叉树及优化算法详解）

根据右图测试数据可知，一共有n行（3，4，5），x个猴子中每2^n出现一循环，理由就是它是满二叉树。

根据左图四层我们列出数据看看：

第1只猴子 1 2 4 8
第2只猴子 1 3 6 12
第3只猴子 1 2 5 10
第4只猴子 1 3 7 14
第5只猴子 1 2 4 9
第6只猴子 1 3 6 13
第7只猴子 1 2 5 11
第8只猴子 1 3 7 15

请读者看看四层二叉树（上左图）和上表中对比不难发现，进入第n个结点的次数i为奇数（即前面已有n-1过猴子访问过该结点），那么遍历其左子树根；

若为偶数，则遍历其右子树根。

因此，对照上表，得出规律：i为奇数，k=k*2；i=(i+1)/2；//第i个进入左子树

　　　　　　　　　　　　　i为偶数，k=k*2+1；i=i/2； //第i个进入右子树

例如

第1个猴子：则对于第一个结点来说，i=1为奇数，那么下一个要走的结点k=1*2=2；然后i=(1+1)/2=1（第一个进入左子树）,继续判断其左子树i的奇偶性……

第3个猴子：则对于第一个结点来说，i=3为奇数，那么下一个要走的结点k=1*2=2；然后i=(3+1)/2=2（第二个进入左子树）……

第5个猴子：则对于第一个结点来说，i=5为奇数，那么下一个要走的结点k=1*2=2；然后i=(5+1)/2=3（第三个进入左子树）……

……

1 for (int j=0;j<d-1;j++)

2        if(i%2) {k=k*2;i=(i+1)/2;}

3        else {k=k*2+1;i /=2;}

OK接着按照输入标准写出完整算法如下：

 1

 2 #include<iostream>

 3 using namespace std;

 4

 5 int main()

 6 {

 7     int d,i,k;

 8     while(cin>>d>>i && (d+i) !=0)

 9     {

10         k=1;

11         for (int j=0;j<d-1;j++)

12             if(i%2) {k=k*2;i=(i+1)/2;}

13             else {k=k*2+1;i /=2;}

14         cout<<k<<endl;

15

16     }

17 }

当然，你可以将/2换成位运算左移一位，效率更高。

相关文章