首页 > 其他 > 详细

紫书——小球下落

时间:2021-09-21 00:58:54      阅读:4      评论:0      收藏:0      [点我收藏+]

小球下落

有一棵二叉树,最大的深度为D,所有叶子的深度都相同,所有节点从上到下从左到右的编号为 1,2,3,4....2^(D-1)

在节点1处放一个小球,它会往下落,每个内节点上都有一个开关,初始化的时候都是关着的,当每次有小球落到一个开关的时候,它的状态就会变化

当小球到达一个内节点的时候,如果开关是关闭的,就往左走,否则就往右走,直到走到叶子节点。

输入 D I

D表示二叉树的深度,在输入I表示第几个小球

(D <= 20 输入最多包含1000组数据);

输出

第I个小球最后落入的叶子节点数目。

技术分享图片

 

 

分析: 本质  -> 二叉树
技术分享图片

 

 

 知识:

结点的度:一个结点拥有子树的数目称为结点的度

树的度:树中所有结点的度的最大值

叶子结点:也称为终端结点,没有子树的结点或者度为零的结点

二叉树的性质:

性质1:二叉树的第i层上至多有2i-1(i≥1)个节点
性质2:深度为h的二叉树中至多含有2h-1个节点
性质3:若在任意一棵二叉树中,有n0个叶子节点,有n2个度为2的节点,则必有n0=n2+1
性质4:具有n个节点的完全二叉树深为log2x+1(其中x表示不大于n的最大整数)
性质5:若对一棵有n个节点的完全二叉树进行顺序编号(1≤i≤n),那么,对于编号为i(i≥1)的节点:
    当i=1时,该节点为根,它无双亲节点
    当i>1时,该节点的双亲节点的编号为i/2
    若2i≤n,则有编号为2i的左节点,否则没有左节点
    若2i+1≤n,则有编号为2i+1的右节点,否则没有右节点
重点:
对于一个结点,其左右结点分别为 2k 和 2k+1,其父结点为 k/2
多运用位运算  1 << maxd
书中参考代码:
 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 const int maxn = 20;
 5 int s[1<<maxn];
 6 int main(){
 7     int D,I,k;      
 8     while(scanf("%d %d",&D,&I)==2){
 9         memset(s,0,sizeof(s));
10         int n=(1<<D)-1;    // n为最大结点编号
11         for(int i=0;i<I;i++){   // I个小球下落 
12             k=1;
13              while(1){
14                  s[k] = !s[k];
15                  k = s[k] ? k*2 : k*2+1;
16                  if(k > n)  break; 
17              }
18         } 
19         printf("%d\n",k/2);
20     }
21 } 

 


 

 

 

 

 

 

紫书——小球下落

原文:https://www.cnblogs.com/religious-chen/p/15311188.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!