LRJ入门经典(基础篇)——6.小球下落

6.小球下落

问题描述:
有一棵二叉树,最大深度为D,且所有的叶子深度都相同。所有结点从上到下从左到右编号为1,2,3,…,2eD-1。在结点1处放一个小球,它会往下落。每个结点上都有一个开关,初始全部关闭,当每次有小球落到一个开关上时,它的状态都会改变。当小球到达一个内结点时,如果该结点的开关关闭,则往上走,否则往下走,直到走到叶子结点,如下图所示。
一些小球从结点1处依次开始下落,最后一个小球将会落到哪里呢?输入叶子深度D和小球个数I,输出第I个小球最后所在的叶子编号。假设I不超过整棵树的叶子数;D<=20。输出最多包含1000组数据。


样例输入:
4 2
3 4
10 1
2 2
8 128
16 12345
样例输出:
12
7
512
3
255
36358
分析:二叉树性质的简单应用

//输入深度和小球个数
//确定最大的小球编号、确定叶子起始节点编号
//重起始节点开始当前节点为(n):如果为0则下一个节点为男2n,否者为2n+1;束条件为:n> 最大叶子节点。
#include <cstdio>
#include <cstring>
const int maxd = 20;
int s[1<<maxd];
int main() {
    int d, t;
    while(scanf("%d %d",&d,&t) == 2){
        memset(s, 0, sizeof(s));//用于某一块内存的初始化
        int max_leaf_node = (1<<d)-1;// 确定最大叶子编号;
        int k;
        for(int i = 0;i < t;i++){
            k=1;
            for(;;){
                if(s[k] == 0) {
                    s[k] = 1;
                    k = k*2;
                }
                if(s[k] == 1){
                    s[k] = 0;
                    k = k*2 + 1;
                }
                if(k>max_leaf_node) break;
            }
        }

        printf("%d\n",k/2);
    }
    return 0;
}

测试数据

4 2
12
3 4
7
10 1
512
2 2
3
8 128
255
16 12345
36358
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 80末班车,90早班车的娃。不知不觉的,你已经在奔三的路上了。工作还是如此的不安分,情感居然还是单身,人生...
    为活着而活着_傻梦阅读 289评论 0 2
  • 你伫立在许墨脑神经专家室的门口,凝视着门上已经标记“外出”已久的铭牌,大概有多久时间没有见到过许墨了呢?他会...
    刘小萌斯基阅读 240评论 0 0
  • 少女心满满的天使之翼,可爱优雅的天使翅膀造型通体925纯银采用微镶满钻5a级锆石,送给最可爱的姑娘,带你翱翔天空,...
    喵小圈阅读 2,896评论 0 0
  • 感恩祖国日新月异的发展,现在出门越来越便捷,感谢高铁的快捷,让出行更方便! 感恩一位素不相识的帅哥,主动给我调换座...
    那朵花蕾阅读 218评论 0 0
  • 诺斯清生理性海水
    叶散天阅读 124评论 0 0