02499: Binary Tree

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

Binary trees are a common data structure in computer science. In this problem we will look at an infinite binary tree where the nodes contain a pair of integers. The tree is constructed like this:

The root contains the pair (1, 1).
If a node contains (a, b) then its left child contains (a + b, b) and its right child (a, a + b)

Problem Given the contents (a, b) of some node of the binary tree described above, suppose you are walking from the root of the tree to the given node along the shortest possible path. Can you find out how often you have to go to a left child and how often to a right child?

输入

The first line contains the number of scenarios. Every scenario consists of a single line containing two integers i and j (1 <= i, j <= 2*109) that represent a node (i, j). You can assume that this is a valid node in the binary tree described above.

输出

The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing two numbers l and r separated by a single space, where l is how often you have to go left and r is how often you have to go right when traversing the tree from the root to the node given in the input. Print an empty line after every scenario.

样例输入

样例输出

Scenario #1:
41 0

Scenario #2:
2 1

Scenario #3:
4 6

来源

TUD Programming Contest 2005 (Training Session), Darmstadt, Germany

这个问题可以用 递归或迭代方法 解决，我们需要从 (1,1) 根节点出发，找到从根到 (i,j) 这个节点的路径，并统计 左移和右移的次数。

分析题目

树的结构：

根节点 (1,1)
左子树： (a + b, b)
右子树： (a, a + b)

对于 给定的 (i, j)，我们要找到它在二叉树中的位置，并计算 左转和右转的次数：

如果 i > j，意味着 (i, j) 来自 左子树，所以左转。
如果 i < j，意味着 (i, j) 来自 右子树，所以右转。
如果 i == j，那么 i, j 必须是 (1,1)，但由于题目保证 (i,j) 是合法的，我们不需要考虑这种情况。

因此，我们可以不断递归：

如果 (i > j)，它的 父节点 是 (i - j, j)，左转计数 +1。
如果 (i < j)，它的 父节点 是 (i, j - i)，右转计数 +1。

最终 (1,1) 会是终点。

Python 代码

python

def count_moves(i, j):
    left_moves = 0
    right_moves = 0

    while i != 1 and j != 1:  # 终止条件: (1,1)
        if i > j:
            left_moves += i // j  # 计算可以跳跃多少次
            i %= j  # 直接更新 i，减少迭代次数
            if i == 0:  # 避免 ZeroDivisionError
                i = 1
        else:
            right_moves += j // i  # 计算可以跳跃多少次
            j %= i  # 直接更新 j，减少迭代次数
            if j == 0:  # 避免 ZeroDivisionError
                j = 1

    # 可能 i != 1 或 j != 1，需要再补一次
    if i > 1:
        left_moves += i - 1
    elif j > 1:
        right_moves += j - 1

    return left_moves, right_moves


n = int(input())  # 读取测试用例数量
for case_num in range(1, n + 1):
    i, j = map(int, input().split())  # 读取 i, j
    left, right = count_moves(i, j)

    # 输出格式
    print(f"Scenario #{case_num}:")
    print(left, right)
    if case_num != n:
        print()  # 题目要求每个案例后面空行

优化点
使用 i // j 和 i % j 来优化计算：
由于 (i, j) 总是其父节点 (i - j, j) 或 (i, j - i)，我们可以直接跳跃 i // j 或 j // i 步，而不是一层层递归，减少递归调用。
例如 (42, 1)，它的 父节点 是 (41,1)，然后 (40,1)，一直到 (1,1)，所以左转 41 次，而不是递归 41 次。
用 while 迭代代替递归：
避免递归的栈溢出问题（因为 i, j 可以达到 2 * 10^9）。
迭代方式更加高效，可以 O(log(max(i, j))) 解决问题。
复杂度分析
每次迭代都将 i, j 变成 i % j 或 j % i，类似 欧几里得算法（求 GCD），因此：
时间复杂度： O(log(max(i, j)))
空间复杂度： O(1)
这个方法在大数据情况下也能高效运行！

ee-张坤思路：减法变成除法，就可以大大提高效率。可以假设一个极端情况 1和10000 减法要用9999次除法只用1次。武昱达：辗转相除。

python

n = int(input())
for i in range(n):
    a, b = map(int, input().split())
    l, r = 0, 0
    while a != 1 or b != 1:
        if a == 1:
            r += b - a
            b = 1
        elif b == 1:
            l += a - 1
            a = 1
        elif a > b:
            l += a // b
            a -= b * (a // b)
        elif a < b:
            r += b // a
            b -= a * (b // a)
    print("Scenario #{}:".format(i + 1))
    print(l, r)
    print()

只要结点不包含1值，左右整除不会余0。

python

# 23n2300011329 洪亮
def binarytree(l, r, x, y):
    if l == 1:
        return [x, y+r-l]
    elif r == 1:
        return [x+l-r, y]
    elif l > r:
        n = l // r
        # if l == r * n:
        #     n -= 1
        ans = binarytree(l - r * n, r, x + n, y)
    else:
        n = r // l
        # if r == l * n:
        #     n -= 1
        ans = binarytree(l, r - l * n, x, y + n)
    return ans


for _ in range(int(input())):
    l, r = map(int, input().split())
    ans = binarytree(l, r, 0, 0)
    print(f'Scenario #{_ + 1}:')
    print(ans[0], ans[1])
    print()

02499: Binary Tree ​

02499: Binary Tree