遞歸益智

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。