Minmuim步驟達到一個數組點

Question

有一個無限的一維數組範圍從（-infinity，無窮大）。你目前在0號單元。你的目標是達到H號單元。允許有兩種移動。

U =右邊的步驟（正面）。
D =左側的步數（負側）。
我們必須找到最低數量。的移動如果（possiable）

用於h = 2 U = 2 d = 1個

第一個舉動2個步驟，以達到細胞數目2。然後1個步驟向右向左到達單元編號1和2最後更多的步驟來實現目標的權利。因此需要3次移動，這是最小的。

什麼是算法來解決這個問題。我的方法進行遞歸調用，即h + u和h-d，直到h == 0。

Answer 1

讓我們米是數字的移動必須被朝向的移動的正側和Ñ許多必須被向負側進行製造。 米和ñ必須滿足以下公式：

h = u * m - d * n 

我們知道^h，ü和d。爲你的例子將如下所示的公式（我假設^h應該是3而不是2，還看到我的評論）：

3 = m * 2 - n * 1 
-> 
n = 2 * m - 3 

我們也知道，米> = 0，ñ > = 0和m和n是整數。現在，最簡單的方式找到米和ñ將計算ñ爲米 = 0,1,2,3,4 ......直到你將收到ň滿足所有條件（你也可以根據n計算m）。在您的例子將是：

m = 0 -> n = -3 is an integer but n < 0 so it is not an answer 
m = 1 -> n = -1 is an integer but n < 0 so it is not an answer 
m = 2 -> n = 1 

所以答案是米 = 2和ñ = 1。您不必檢查其他m的結果，因爲您將始終收到更高的值（h = u * m - d * n是一個正在增加的功能）。

這不是一切。可能存在沒有整數解的方程。在這種partocular情況下，我們正在考慮的線性不定方程根據Wikipedia具有整數解：

當且僅當ħ是d和ü

的最大公約數的倍數

讓我們再次回到您的例子。 2和1的GCD是1，3是1的乘積，因此存在整數解。然而，讓我們考慮h = 9,d = 2和u = 4。 GCD（2,4）是2並且9不是乘法2，所以沒有解決方案。您必須在嘗試查找m和n之前檢查此條件，否則您將以不定式循環結束。