給出以(a,b)
和(c,d)
的形式輸入的四個整數。將一個點轉換爲另一個點的算法
確定是否有可能從(a,b)
獲得(c,d)
如果在每一個步驟就可以操作(a+b,b)
或(a,a+b)
之間進行選擇。
因此,例如,(1,2) -> (3,2) -> (5,2) -> (5,7) -> (12,7) -> (12,19) -> ...
我試圖解決與A + B X = C和 X + B = d的東西,但沒有奏效。有任何想法嗎?
給出以(a,b)
和(c,d)
的形式輸入的四個整數。將一個點轉換爲另一個點的算法
確定是否有可能從(a,b)
獲得(c,d)
如果在每一個步驟就可以操作(a+b,b)
或(a,a+b)
之間進行選擇。
因此,例如,(1,2) -> (3,2) -> (5,2) -> (5,7) -> (12,7) -> (12,19) -> ...
我試圖解決與A + B X = C和 X + B = d的東西,但沒有奏效。有任何想法嗎?
可達點的模式看起來不簡單。你可以看到它是一個有理性斜坡的斜線網絡,從可達點開始。
這裏是(1, 2)
的模式。這些字母對應於連續的「世代」。
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. A . B . C . D . E . F . G . H . I . J . K . L . M
. B . . C . . D . . E . . F . . G . . H . . I . . J
. C . . . D . . . E . . . F . . . G . . . H . . . I
. D . C . . E . D . . F . E . . G . F . . H . G . .
. E . . . . . F . . . . . G . . . . . H . . . . . I
. F . . D D . . G . . E E . . H . . F F . . I . . G
. G . D . . . . . H . E . . . . . I . F . . . . . J
. H . . . E . E . . I . . . F . F . . J . . . G . G
. I . . . . . E . . . J . . . . . F . . . K . . . .
. J . E E . F . . F . . K . F F . G . . G . . L . G
. K . . . E . . . . . . . L . . . F . . . . . . . M
. L . . . . . G E F F G . . M . . . . . H F G G H .
. M . F . F . . . . . . . . . N . G . G . . . . . .
. N . . F . . . H . . . . H . . O . . G . . . I . .
. O . . . . . F . . . G . G . . . P . . . . . G . .
. P . G . F G F . I . . . G . I . . Q . H . G H G .
. Q . . . . . . . . . F . F . . . . . R . . . . . .
. R . . G G . . . . J F F H . . H J . . S . . H H .
. S . H . . . H . G . . . . . . . . . . . T . I . .
. T . . . . . . F . . K . . . . H H . K . . U . . .
. U . . . G . . . G . . . . . I . . . I . . . V . .
. V . I H . H G I . G . L . G . . . G . . L . . W .
. W . . . H . G . . . H . . . . . . . . . . . . . X
. X . . . . . . . . . . . M G . G J G I . I J M . .
由於這種不看第一眼數學聽話,一個算法的解決方案可以通過從(c, d)
回溯找到。
(a, b)= (1, 2)
def Backtrack(c, d):
if c == a and d == b:
print "Reachable !"
return
if d > 0 and c >= d:
Backtrack(c - d, d)
if c > 0 and d >= c:
Backtrack(c, d - c)
Backtrack(9, 8)
Reachable !
除非c == d
,這會導致快速終止,最多是採取了遞歸調用的一個,從而使電話的數量不會成倍增長。
你圖中的模式很有趣。每行中的點數遵循重複模式。 (1,2),(5),(2,0,2),(1,5),(3,1,2),(5, 3),(1,0,1,2,2)。 –
也許有一個優雅的數學解決方案,我不知道一個方程,但對我來說這看起來像一個搜索問題。我們有一個起點(a,b)和一個終點(c,d),在搜索的每一點我們可以做兩個動作:或者轉到狀態(a + b,b)或者(a,a + b)。一個簡單的遞歸深度優先搜索可以做到。這裏唯一棘手的問題是確定何時停止搜索。
我們首先解決這個問題,當所有整數都是正數時。該限制條件,在這之後,我們不能希望找到一個解決方案是在這種情況下清楚:當超過C或B超過d,我們不能希望找到這個分支樹的液下:
bool pathExistsForPositive(int a, int b, int c, int d) {
if (a == c && b == d) return true; // success condition
if (a > c || b > d) return false; // limiting condition
return pathExistsForPositive(a+b, b, c, d)
|| pathExistsForPositive(a, a+b, c, d);
}
現在,將這種情況概括爲數字不是正數的情況會更棘手,但是可行。我希望這種直覺有所幫助。試着想想在什麼時候你不得不停止搜索。
你可以循環來找出所有可能的解決方案
var sols = [[3,2]];
var sols2 = [];
for(depth=1;depth<5;++depth) {
for(j=0;j<sols.length;++j) {
var sol = sols[j];
var sol1 = [sol[0]+sol[1],sol[1]];
var sol2 = [sol[0],sol[0]+sol[1]];
sols2.push(sol1,sol2);
console.log(sol1);
console.log(sol2);
}
sols = sols2;
sols2 = [];
console.log();
}
這只是找到每一個可能的解決方案。你可以改進代碼來過濾掉所有失敗的代碼。
快速gcd檢查將消除任何無法正常工作的輸入。
此方法將遭受指數爆炸,並且不能將深度限制爲5。 –
你介意展示一下_didn't work_的代碼。這樣有人可能會幫助你修復它。 –
這些數字可能是負數嗎? –