0%

算法竞赛入门经典 例题6-6 小球(C、python)

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

一些小球从结点1处下落,最后一个小球将会落到哪里呢?输入叶子深度 D 和小球个数 I,输出第 I 个小球最后所在的叶子编号。假设 I 不超过整棵树的叶子个数,D ≤ 20。
在这里插入图片描述

tips:
给定一颗包含2^d^个结点(其中d为树的高度)的完全二叉树,如果把结点从上到下从左到右编号为1,2,3……,则结点k的左右子结点编号分别为2k2k+1

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
while True:
try:
D, I = list(map(int, input().split()))
n = (1<<D) - 1 # n是最大结点编号
s = [False for _ in range (1<<20)] # 初始值都为假

for i in range (I):
k = 1
while True:
s[k] = ~s[k] # 状态改变
if s[k] == 0:
k = 2 * k + 1
else:
k = 2 * k
if k > n: # 出界
break
print (k//2) # 出界之前的叶子编号
except:
break

C:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<cstdio>
#include<cstring>

const int maxd = 20;
int main() {
int D, I;
while(scanf("%d%d", &D, &I) == 2) {
memset(s, 0, sizeof(s));
int k, n = (1<<D)-1;
for(int i = 0; i < I; i++) {
k = 1;
for(;;) {
s[k] = !s[k];
k = s[k] ? k*2 : k*2+1;
if(k > n) break;
}
}
printf("%d\n", k/2);
}
return 0;
}

如果使用题目中给的编号 I,则当 I 是奇数时,它是往左走的的第(I+1)/ 2个小球;当 I 是偶数时,它是往右走的第 I/2 个小球。这样,可以直接模拟最后一个小球的路线:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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)
}
}
-------------    本文结束  感谢您的阅读    -------------