算法刷题——小球下落(Uva 679)

  |   0 评论   |   0 浏览

1. 题目描述

有一棵二叉树,最大深度为 D ,且所有叶子深度都相同。所有节点从上到下从左到右编号为 $1,2,3,..., 2^D -1 $。在节点 1 处放一个小球,它会往下落。每个内节点上都有一个开关,初始全部关闭,每次有小球落到一个开关上,状态都会改变。党校求到达一个内节点时,如果该节点上的开关关闭,则往左走,否则往右走,直到走到叶子结点。如下图所示:
15779420021.png

一些小球从节点 1 开始下落,最后一个小球会落到哪里呢?输入叶子深度 D 和小球个数 I,输出第 I 个小球最后所在的叶子编号。假设 I 不超过整棵树叶子的个数。 D\leq20 。输入数据最多 1000 组。


样例输入

4 2
3 4
10 1
2 2
8 128
16 12345

样例输出

12
7
512
3
255
36358


2. 问题分析

  1. 使用建立二叉树模拟整个小球下落的过程时间复杂度为 O(ID) ,易造成超时。
  2. 通过分析可以看出,对于下落的第 k 个小球,若 k 为奇数,则落在其左子树,且为左子树的 (k+1)/2 个小球,若 k 为偶数,则落在其右子树,且为其右子树的 (k/2) 个小球。
  3. 具体实现上,我使用了一个变量 l 记录其所在子树最左边的节点, w 记录当前子树的宽度,依次迭代到子树宽度为 1 时得到叶子的编号。
  4. 书中给出的解答为使用一个变量 k 记录树的根节点,并从完全二叉树的根节点向下走 D-1 次,更加直观易于理解,代码如下。
while(scanf("%d%d",&D,&I) == 2){
	int k = 1;
	for(int i = 0; i < D-1 ;i++)
		if( i%2 ){ k = k * 2; I = (I+1)/2; }
		else{ k = k*2+1; I /= 2; }
	printf("%d\n",k);
}

Tips

  1. Uva OJ 网站中给出的输入格式与题目描述略有不同,易踩坑,其中给出的第一个数字测试数据的组数 t 貌似没什么用,使用 D == -1 作退出循环的条件。

My code

#include <iostream>
#include <cstdio>
/**
Date: 2019/12/30
Author: YC
*/
using namespace std;

int D,I;

int cal(int d,int i){
    int l = 1 << (d-1);
    int w = d - 2;
    while(i != 1){
        if(i%2 == 0)//right
            l += (1 << w);
        w--;
        i = (i + 1) >> 1;
    }
    return l;
}

int main()
{
    int r;
    /*
    //The following code is for test in UVA 679
    int t;
    scanf("%d",&t);
    while(1){
        scanf("%d",&D);
        if(D==-1) break;
        scanf("%d",&I);
        r = cal(D,I);
        printf("%d\n",r);
    }
    */
    while(scanf("%d%d",&D,&I) == 2){
        r=cal(D,I);
        printf("%d\n",r);
    }
    return 0;
}

Uva 原题链接
Uva679


标题:算法刷题——小球下落(Uva 679)
作者:YaoCheng8667
地址:https://ycisme.xyz/articles/2019/12/31/1577803634360.html