algorithm - 递归谜题

Question

最近，我的一位 friend 向我提出挑战，要求我解决这个难题，内容如下:

假设您有两个变量 x 和 y。这些是唯一可用于存储在程序中的变量。可以执行三种操作:

• 操作 1:x = x+y
• 操作 2:x = x-y
• 操作 3:y = x-y

现在，给你两个数字 n1 和 n2 以及一个目标数字 k。从 x = n1 和 y = n2 开始，有没有办法使用上述操作得出 x = k？如果是，可以生成 x = k 的运算顺序是什么？

示例:如果 n1 = 16、n2 = 6 且 k = 28，则答案为"is"。顺序是:

Operation 1
Operation 1

如果 n1 = 19、n2 = 7 且 k = 22，则答案为"is"。顺序是:

Operation 2
Operation 3
Operation 1
Operation 1

现在，我已经思考这个问题太久了，但我没有得到任何初步的想法。我有一种感觉，这是递归，但我不知道边界条件应该是什么。如果有人可以指导我找到一种可用于解决此问题的方法，那将非常有帮助。谢谢!

Answer 1

也许不是一个完整的答案，但证明序列存在当且仅当 k是 n1 的最大公约数 (GCD) 的倍数和n2 。让我们写G = GCD(n1, n2)为简洁起见。

首先我要证明x和y始终是 G 的整数倍。这个证明通过归纳法确实很简单。假设:x = p * G和y = q * G ，对于某些整数 p和q .

• 最初，根据 G 的定义，假设成立。 .
• 每条规则都遵循归纳假设。规则产生:
  1. x + y = p * G + q * G = (p + q) * G
  2. x - y = p * G - q * G = (p - q) * G
  3. y - x = q * G - p * G = (q - p) * G

由于这个结果，只能有一个序列到 k如果k是 n1 的 GCD 的整数倍和n2 .

对于另一个方向，我们需要证明 G 的任意整数倍可以通过规则来实现。如果我们能达到x = G，情况肯定是这样的。和y = G 。为此，我们使用 Euclid's algorithm 。考虑链接的 wiki 文章中的第二个实现:

function gcd(a, b)
    while a ≠ b
        if a > b
           a := a − b
        else
           b := b − a
    return a

这是规则 2 和 3 的重复应用，结果为 x = G和y = G .

---

知道存在解决方案，您可以应用 BFS，如 Amit's answer 所示，找到最短序列。