网站 做内容分发资格,网站的优化从几个方面,搭建安装wordpress教程,网站开发年度总结二叉树的编号 例题 6-6 小球下落问题 有一棵二叉树#xff0c;最大深度为D#xff0c;且所有叶子深度都相同。所有节点从上到下#xff0c;从左到右编号为1,2,3,4#xff0c;....#xff0c;2^D-1。在节点1处放置小球#xff0c;他会往下落。每个节点上都有一个开关…二叉树的编号 例题 6-6 小球下落问题 有一棵二叉树最大深度为D且所有叶子深度都相同。所有节点从上到下从左到右编号为1,2,3,4....2^D-1。在节点1处放置小球他会往下落。每个节点上都有一个开关初始全部关闭每当有小球落到一个开关上时状态都会改变当一个小球到达节点时如果该节点上的开关关闭则往左走否则往右走直到走到叶子节点一些小球从节点1处开始依次下落。最后一个小球回到哪里呢输入叶子深度D小球个数I输入第I个小球最后所在的叶子编号。假设I不超过整棵树的叶子个数D20。输入最多包含1000组数据。 **get ** 4 2 3 4 10 1 2 2 8 128 16 12345 put 12 7 512 3 255 36358#include#includeconst int maxd20;int s[1int main(){int D,I;while((cinDI)2){memset(s,0,sizeof(s));int k1,n(1for(int i0;i{k1;for(;;;){s[k]!s[k];ks[k]?2*k:2*k1;if(kn)break;}}cout}return 0;}代码非常基础不难理解用k表示小球现在所在的节点位置再进行判断是否出界出界则跳出循环后进行下一步循环并且对k进行初始化直到循环结束即第I个小球下落到底。但是这样做的代码有一个明显的缺陷那就是时间复杂度问题运算量太大由于I可以高达2^D-1每组测试数据下落总层数可能会高达(2^19)*199961472并且一共可能有10000组数据。 还有一种方法我们可以这样理解每个小球都会落到根节点上并且前两个小球一定必然是一个落在左边子树上一个落在右边子树上一般的只需要看小球编号的奇偶性就能直到他最终会在那棵子树中对于那些落入根节点左子树的小球来说只需要知道该小球是第几个落在根的左子树就可以直到他下一步往左还是往右了依次类推直到小球落到叶子上为止。 如果使用题目中给的编号I则当I是奇数时他是往左走的第(I1)/2个小球当I是偶数时他是往右走的第I/2个小球。这样可以直接模拟最后一个小球的路线实现代码while((cinDI)2){int k1;for(int i0;iif(I%2){kk*2;I(I1)/2;}else{kk*21;I/2;}cout}
