有一棵二叉树，最大深度为D，且所有叶子的深度都相同。所有结点从上到下从左到右编号为1，2，3，...，2^D-1。在结点1处放一个小球，它会往下落。每个内结点上都有一个开关，初始全部关闭，当每次有小球落到一个开关上时，它的状态都会改变。当小球到达一个内结点时，如果该结点上的开关关闭，则往左走，否者往右走，直到走到叶子结点。 一些小球从结点1处依次开始下落，最后一个小球将会落到哪里呢？输入叶子深度D和小球个数I，输出第I个小球最后所在的叶子编号。假设I不超过整棵树的叶子个数（即2^(D-1)）。D<=20。输入最多包含1000组数据。 样例输入： 4 2 3 4 10 1 2 2 8 128 16 12345 样例输出： 12 7 512 3 255 36358
第一种方法，有bug，无法满足边界数据测试
#include<iostream> #include<cstring> #include<cmath> using namespace std; int k[100000]; int main() { int d,num; while(cin>>d>>num) { int ans; memset(k,0,sizeof(k));//初始化开关 int maxdep=pow(2,d)-1; int mindep=pow(2,d-1); for(int i=1;i<=num;i++)//小球开始下落 { int s=1; for(;;) { if(s>=mindep&&s<=maxdep) break; if(k[s]==1) { k[s]=!k[s]; s=2*s+1; } else { k[s]=!k[s]; s=2*s; } ans=s; } } cout<<ans<<endl; } return 0; }
第二种方法，根据规律进行求解。
//相当于直接计算最后一个小球的运动轨迹，大大减少了运算时间，偶数往右下，奇数往左上。 #include<iostream> using namespace std; int main() { int d,num; while(cin>>d>>num) { int k=1;//k代表编号 for(int i=1;i<d;i++)//注意一定是循环了d-1次; { if(num%2==1) { k=k*2; num=(num+1)/2;//第（num+1）/2个往左走的 } else { k=k*2+1; num=num/2; } } cout<<k<<endl; } return 0; }
只是在本地端codeblocks测试通过，若有问题，请联系我。
