给定一对整数，达到目标 N 所执行的最少操作数

Question

给定一对数字（A，B）。您可以执行操作 (A + B, B) 或 (A, A + B)。(A, B) 被初始化为 (1, 1)。对于任何 N > 0，找到需要对 (A, B) 执行的最少操作数，直到 A = N 或 B = N

在 glassdoor 的采访摘要中遇到这个问题。通过几种方法进行思考，在网上搜索但找不到解决此问题的任何文章/答案。我有一个如下所示的强力方法，但是它必须遍历 O(2^N) 路径，想知道是否有一个我没有看到的优雅的解决方案。

def pairsum(N):
    A = 1
    B = 1

    return helper(N, A, B, 0)

def helper(N, A, B, ops):
    # Solution found
    if A == N or B == N:
        return ops

    # We've gone over, invalid path taken
    if A > N or B > N:
        return float("inf")

    return min(helper(N, A + B, B, ops + 1), helper(N, A, A + B, ops + 1))

Answer 1

给定一个目标 number N，可以计算大约O(N log(N))基本算术运算中的最小运算数（尽管我怀疑有更快的方法）。就是这样：

对于这个问题，我认为向后比向前更容易。假设我们正在尝试达到一对目标(a, b)正整数。我们从 开始(a, b)，向后计算(1, 1)，边走边计算步数。这很容易的原因是，从一对(a, b)返回到(1, 1): if a > b，那么该对(a, b)不可能是第二个操作的结果，因此我们可能到达该对的唯一方法是应用第一次操作到(a - b, b). 类似地，如果a < b，我们只能通过应用于 的第二个操作来达到该对(a, b - a)。案情又如何呢a = b？好吧，如果a = b = 1，那就没什么可做的了。如果a = b和a > 1，那么我们根本无法达到该对：请注意，这两个操作都将整数互质对变为整数互质对，因此如果我们从 开始(1, 1)，我们永远无法达到具有最大公约数的整数对大于 1。

这导致以下代码计算从 到 的步数(1, 1)，(a, b)对于任何正整数对a和b：

def steps_to_reach(a, b):
    """
    Given a pair of positive integers, return the number of steps required
    to reach that pair from (1, 1), or None if no path exists.
    """
    steps = 0
    while True:
        if a > b:
            a -= b
        elif b > a:
            b -= a
        elif a == 1:  # must also have b == 1 here
            break
        else:
            return None  # no path, gcd(a, b) > 1
        steps += 1
    return steps

看看上面的代码，它与计算最大公约数的欧几里德算法非常相似，只是我们的效率非常低，通过使用重复的减法而不是通过欧几里德除法步骤直接求余数。因此可以用以下等效、更简单、更快的版本替换上面的版本：

def steps_to_reach_fast(a, b):
    """
    Given a pair of positive integers, return the number of steps required
    to reach that pair from (1, 1), or None if no path exists.

    Faster version of steps_to_reach.
    """
    steps = -1
    while b:
        a, (q, b) = b, divmod(a, b)
        steps += q
    return None if a > 1 else steps

我让您检查这两段代码是否等效：证明并不难，但如果您不想拿出笔和纸，那么在提示符下快速检查应该是令人信服的：

>>> all(steps_to_reach(a, b) == steps_to_reach_fast(a, b) for a in range(1, 1001) for b in range(1, 1001))
True

该调用steps_to_reach_fast(a, b)需要O(log(max(a, b)))算术运算。（这是根据欧几里得算法的标准分析得出的。）

现在可以很简单地找到给定的最小操作数n：

def min_steps_to_reach(n):
    """
    Find the minimum number of steps to reach a pair (*, n) or (n, *).
    """
    # Count steps in all paths to (n, a). By symmetry, no need to
    # check (a, n) too.
    all_steps = (steps_to_reach_fast(n, a) for a in range(1, n+1))
    return min(steps for steps in all_steps if steps is not None)

该函数运行速度相当快，n = 1000000大约可达。让我们打印出前几个值：

>>> min_steps_to_reach(10**6)  # takes ~1 second on my laptop
30
>>> [min_steps_to_reach(n) for n in range(1, 50)]
[0, 1, 2, 3, 3, 5, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 6, 7, 7, 7, 7, 7, 7, 8, 7, 7, 7, 8, 8, 7, 8, 8, 8, 9, 8, 8, 8, 9, 8, 8, 8, 8, 8, 9, 8]

在在线整数序列百科全书中搜索很快就会得到序列A178047，它与我们的序列完美匹配。该顺序描述如下：

考虑 Farey 树 A006842/A006843；a(n) = 分母 n 首次出现的行（假设第一行标记为第 0 行）。

事实上，如果您查看由两个操作生成的树（从 开始）(1, 1)，并将每一对视为一个分数，您会得到与Stern-Brocot树（Farey 树的另一个名称）非常相似的东西：内容每行的内容相同，但每行内的顺序不同。事实证明，这是伪装的 Stern-Brocot 树！

这一观察结果为我们提供了一个易于计算的下界min_steps_to_reach：很容易证明，在iStern-Brocot 树的第 3 行中作为分子或分母出现的最大整数是第i+2一个斐波那契数。因此，如果n > Fib(i+2)，则min_steps_to_reach(n) > i（并且如果n == Fib(i+2)，则恰好min_steps_to_reach(n)是）。获得上限（或无需详尽搜索的精确值）似乎有点困难。以下是最坏的情况：对于每个整数，需要的最小步骤（例如，是需要步骤的第一个数字）： is >= 0ns50615

[1, 2, 3, 4, 7, 6, 14, 20, 28, 38, 54, 90, 150, 216, 350, 506, 876, 1230, 2034, 3160, 4470, 7764]

如果这里有一个模式，我不会发现它（但它本质上是 OEIS 上的序列A135510）。