山东省建设厅注册中心网站,广西网站建设制作,纺织厂网站模板,网站流量突然增大题目
有一棵二叉树#xff0c;最大深度为D#xff0c;且所有的叶子深度都相同。所有结点从上到下从左到右编号为1#xff0c;2#xff0c;3#xff0c;…#xff0c;2eD-1。在结点1处放一个小球#xff0c;它会往下落。每个结点上都有一个开关#xff0c;初始全部关闭…题目
有一棵二叉树最大深度为D且所有的叶子深度都相同。所有结点从上到下从左到右编号为123…2eD-1。在结点1处放一个小球它会往下落。每个结点上都有一个开关初始全部关闭当每次有小球落到一个开关上时它的状态都会改变。当小球到达一个内结点时如果该结点的开关关闭则往上走否则往下走直到走到叶子结点如下图所示。 一些小球从结点1处依次开始下落最后一个小球将会落到哪里呢输入叶子深度D和小球个数I输出第I个小球最后所在的叶子编号。假设I不超过整棵树的叶子数D20。输出最多包含1000组数据。 样例输入 4 2 3 4 10 1 2 2 8 128 16 12345 样例输出 12 7 512 3 255 36358
分析与解答
0.给定一颗2^d个结点的完全二叉树如果把结点从上到下从左到右编号则结点k的左右子结点编号分别为2k2k1 1.根据观察对于根结点小球编号为奇数落在左子树偶数落在右子树 2.每个节点都可以看成根结点并且与他两个子结点组成一个新的二叉树 3.根据根结点1找规律发现如果小球编号为奇数他是往左走的第i1)/2个小球如果小球编号为偶数他是往右走的第i/2个小球。 4.如果把每个子节点看成一个根结点那么每个结点的小球也满足3的规律 5.第i个小球从结点编号为k的地方下落如果i为奇数那么此时等价于第(i1)/2个小球从结点编号为k*2的地方下落如果i为偶数那么此时等价于第i/2个小球从结点编号为k*21的地方下落然后通过1我们就知道他下一步是向左还是向右走 6.二叉树深度为d小球下落d-1次每循环一次我们就知道他落在哪下一步怎么走如果循环d-1次刚好走到最后的叶子结点此时知道他落在哪输出k就行
代码
#includecstdioint main(){int d,I;while(scanf(%d%d,d,I)2){int k1;for(int i0;id-1;i){if(I%2){kk*2;I(I1)/2;}else {kk*21;I/2;}}printf(%d\n,k);}
}
方法二 利用模拟二叉树编号
#includecstdio
#includecstring
const int maxd 20;
int s[1maxd];
int main(){int D,I;while(scanf(%d%d,D,I)){memset(s,0,sizeof(s));int k,n (1D)-1;//n是最大节点编号 for(int i0;iI;i){k1;for(;;){s[k]!s[k];//每次开关变化 ks[k]?k*2:k*21;//根据开关状态选择下落方向 if(kn) break;//出界了 }}printf(%d\n,k/2);//出界之前叶子编号 }
}
