技术问询：求从(1,1)经指定操作到达目标点(x,y)的最少步数

问题描述 #

给定起点(1,1)，每次只能从当前点(a,b)执行以下两种操作之一：

• 移动到(a, b+a)
• 移动到(a+b, b)
  需要计算到达目标点(x,y)的最少步数。

原提供代码（存在逻辑错误） #

a = 1
b = 1

x = int(input())
y = int(input())

def minsteps(x, y):
    if x == a and y == b:
        print(1)
        return 1
    if x < a and y < b:
        print(2)
        return 20
    
    count = 1 + min(minsteps(x, x+y), minsteps(x+y, y))
    return count

print(minsteps(x, y))

代码问题分析

1. 递归方向错误：代码采用正向递归，每次生成比当前坐标更大的点，会导致无限递归（永远无法触达目标点的终止条件），完全偏离解题逻辑。
2. 终止条件不合理：当x或y小于起点坐标时返回20，实际这种情况根本无法到达目标点，应该直接判定为不可达。
3. 计数逻辑错误：起点(1,1)本身不需要步数，代码却返回1，不符合实际需求。

测试用例 #

输入：

3
2

输出：2

步骤解释

1. 第一步：从(1,1)移动到(1, 1+1) = (1,2)
2. 第二步：从(1,2)移动到(1+2, 2) = (3,2)

正确解法（反向迭代法） #

由于正向推导会产生大量无效分支，我们可以从目标点反向推导到起点(1,1)，每次用较大的数减去较小的数，直到回到(1,1)：

基础版本

x = int(input())
y = int(input())

steps = 0
while x != 1 or y != 1:
    # 若坐标小于1，直接判定不可达
    if x < 1 or y < 1:
        print("无法到达")
        exit()
    if x > y:
        x -= y
    else:
        y -= x
    steps += 1
print(steps)

优化版本（减少循环次数）

当其中一个坐标远大于另一个时，可以直接计算能减去的次数，避免多次循环：

x = int(input())
y = int(input())

steps = 0
while x != 1 or y != 1:
    if x < 1 or y < 1:
        print("无法到达")
        exit()
    if x > y:
        # 计算可减去y的次数，避免逐次相减
        steps += x // y
        x = x % y
        # 处理取余后为0的情况（比如x是y的倍数时，需调整）
        if x == 0:
            x = y
            steps -= 1
    else:
        steps += y // x
        y = y % x
        if y == 0:
            y = x
            steps -= 1
print(steps)

内容的提问来源于stack exchange，提问作者user17931091