递归难题

Question

最近，我的一个朋友向我挑战，让我解决这个谜题，如下所示：

假设你有两个变量x和y，这是程序中唯一可以用来存储的变量。有三种操作可以完成：

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

现在，我们给出了两个数字n1和n2，以及一个目标数k。从x= n1和y= n2开始，是否有办法使用上面提到的操作到达x=k？如果是，可以生成x= k的操作序列是什么。

示例:如果n1 = 16，n2 =6，k= 28，则答案是肯定的。顺序如下：

Operation 1
Operation 1

如果n1 = 19，n2 =7，k= 22，则答案是肯定的。顺序如下：

Operation 2
Operation 3
Operation 1
Operation 1

现在，我已经为这个问题花了很长时间，但我没有得到任何初步的想法。我有一种感觉，这是递归，但我不知道边界条件应该是什么。如果有人能引导我找到解决这个问题的方法，那将是很有帮助的。谢谢!

Answer 1

可能不是一个完整的答案，而是一个证明序列存在的证明当且仅当k是n1和n2的最大公共因子(GCD)的倍数。为了简洁起见，让我们编写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是n1和n2的GCD的整数倍数，则只能有一个到n2的序列。

另一方面，我们需要证明G的任何整数倍数都可以通过规则来实现。如果我们能够到达x = G和y = G，情况肯定是这样的。为此，我们使用欧几里得算法。考虑链接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 (如阿米特的回答中所示)来找到最短的序列。

Answer 2

假设存在一个解决方案，可以使用一个BFS来找到到达它的最短序列。

伪代码应该类似于：

queue <- new empty queue
parent <- new map of type map:pair->pair
parent[(x,y)] = 'root' //special indicator to stop the search there
queue.enqueue(pair(x,y))
while !queue.empty():
   curr <- queue.dequeue()
   x <- curr.first
   y <- curr.second
   if x == target or y == target:
      printSolAccordingToMap(parent,(x,y))
      return
   x1 <- x+y
   x2 <- x-y
   y1 <- x-y
   if (x1,y) is not a key in parent:    
      parent[(x1,y)] = (x,y)
      queue.enqueue(pair(x1,y))
   //similarly to (x2,y) and (x,y1)

函数printSolAccordingToMap()只是在地图上追溯，直到它找到根目录，然后打印出来。

请注意，此解决方案仅在存在的情况下才能找到最佳序列，但如果不存在则会导致无限循环，因此这只是部分答案。

Answer 3

考虑到您有两个(x,y) always <= target & >0，如果没有，可以通过简单的操作始终将它们带到范围内。如果考虑到这些约束，您可以通过在该节点上的三个节点之间执行操作来生成一个有O(target*target)节点和边缘的图。现在您需要评估从起始位置节点到目标节点的最短路径，即(target,any)。这里的假设是(x,y)值始终停留在(0,target)内。时间复杂度是O(target*target*log(target))使用djikstra。