02756: 二叉树（1）

http://cs101.openjudge.cn/practice/02756/

如上图所示，由正整数1, 2, 3, ...组成了一棵无限大的二叉树。从某一个结点到根结点（编号是1的结点）都有一条唯一的路径，比如从10到根结点的路径是(10, 5, 2, 1)，从4到根结点的路径是(4, 2, 1)，从根结点1到根结点的路径上只包含一个结点1，因此路径就是(1)。对于两个结点x和y，假设他们到根结点的路径分别是(x1, x2, ... ,1)和(y1, y2, ... ,1)（这里显然有x = x1，y = y1），那么必然存在两个正整数i和j，使得从xi和 yj开始，有$x_i = y_j , x_{i + 1} = y_{j + 1}, x_{i + 2} = y_{j + 2},...$ 现在的问题就是，给定x和y，要求xi（也就是yj)。

输入

输入只有一行，包括两个正整数x和y，这两个正整数都不大于1000。

输出

输出只有一个正整数xi。

样例输入

10 4

样例输出

这个问题涉及到二叉树中两个节点的最近公共祖先问题。这里的二叉树是一个特殊的完全二叉树，其中节点编号的方式是根节点编号为1，对于任意节点N，其左子节点的编号为2 * N，右子节点的编号为2 * N + 1。

要找到两个节点x和y的公共祖先，我们可以回溯其到根节点的路径，并找到路径上的最后一个公共节点。在这个完全二叉树中，我们可以简单地通过整除2来获得父节点的编号，即节点N的父节点是N // 2。

下面是Python代码示例，用于找到任意两个节点的最近公共祖先：

python

def find_common_ancestor(x, y):
    # 创建两个集合用于存储x和y的所有祖先节点
    ancestors_x = set()
    ancestors_y = set()
  
    # 回溯x到根节点的路径并保存
    while x > 0:
        ancestors_x.add(x)
        x //= 2

    # 回溯y到根节点的路径
    # 并在每一步检查当前节点是否也是x的祖先节点
    while y > 0:
        if y in ancestors_x:
            return y  # 找到了公共祖先
        y //= 2

    return 1  # 如果没有找到公共祖先，默认返回根节点1

# 读取输入
x, y = map(int, input().split())

# 查找并输出x和y的最近公共祖先
print(find_common_ancestor(x, y))

python

def common(x, y):
    if x == y:
        return x
    if x < y:
        return common(x, y//2)
    else:
        return common(x//2, y)


m, n = map(int, input().split())

print(common(m, n))

02756: 二叉树（1） ​

02756: 二叉树（1）