递归益智

Question

最近，我的一个朋友向我挑战解决这个难题肚里如下：

假设你有两个变量x和y。这些是可以用于程序存储的唯一变量。有三种操作可做到：

• 操作1：X = X + Y
• 操作2：X = XY
• 动作3：Y = XY

现在，你给出两个数字n1和n2以及一个目标数字k。用x = n1和y = n2开始，有没有办法通过上面提到的操作到达x = k？如果是，那么可以生成x = k的操作顺序是什么。

例如：如果n1 = 16，n2 = 6且k = 28，则答案为YES。顺序是：

Operation 1 
Operation 1 

如果n1 = 19，n2 = 7且k = 22，则答案为YES。顺序是：

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的序列如果k是的GCD的整数倍n1和n2。

对于其他方向我们需要显示的任何整数倍的G可以通过规则来实现。如果我们能达到x = G和y = G，情况绝对如此。为此我们使用Euclid's algorithm。考虑第二种实现链接的维基文章：

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所示，找到最短的序列。

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。

Answer 4

在Vincent's answer，我认为证据不完整。

让我们假定有两个相对的素数猜想N1 = 19和N2 = 13其GCD将。据他说，如果k是GCD的倍数，序列退出。因为每个数字是的倍数。我认为这是不可能的每个k。