需要幫助理解算法

-3

public static int mystery (int m, int n){ 
    if (n==0||n==m) 
     return 1; 
    return mystery (m-1, n) + mystery(m-1, n-1); 
}

這是調用mystery（7,5）時的算法，輸出是21.我只是不知道這個算法是如何工作的，任何幫助都會受到歡迎。需要幫助理解算法

來源

2014-10-19 Fredamabob

使用鉛筆和紙，玩電腦。 – 2014-10-19 00:49:06

神祕（7,5）=神祕（6,5）+神祕（6,4）= ...繼續:) – 2014-10-19 00:52:27

我明白，我不明白的是輸出是如何21.不應該它是1，因爲基本情況會返回1？我對此感到困惑，應該很簡單，但我無法掌握這裏發生的事情。 – Fredamabob 2014-10-19 00:56:43

-1

這個算法是遞歸的一個典型例子。有一個非常簡單的例子來解釋它：把兩面鏡子放在對方的前面 - 你會看到什麼？無數的鏡子：所以這裏是一樣的。當條件爲假時，函數一次又一次地調用自己，直到'n'爲0或等於'm'。

打開Excel並逐步自行計算。這是否回答你的問題？

來源

2014-10-19 00:51:25 Eru

我明白，我不明白的是輸出是21.如果不是1，因爲基本情況會返回1？我對此感到困惑，應該很簡單，但我無法掌握這裏發生的事情。 – Fredamabob 2014-10-19 00:57:47

@Fredamabob：基本情況返回1，但整個遞歸調用樹正在總結所有基本情況。 – Blastfurnace 2014-10-19 01:00:58

@Blastfurnace哦..我覺得沒有抓住這個蠢事，我現在明白了。 – Fredamabob 2014-10-19 01:03:53

-1

這只是遞歸定義的數學。

M(7, 5) = M(6, 5) + M(6, 4) 
M(6, 5) = M(5, 5) + M(5, 4) = 1 + M(5, 4) 
M(6, 4) = M(5, 4) + M(5, 3) 
M(5, 4) = M(4, 4) + M(4, 3) = 1 + M(4, 3) 
M(5, 3) = M(4, 3) + M(4, 2) 
M(4, 3) = M(3, 3) + M(3, 2) = 1 + M(3, 2) 
M(4, 2) = M(3, 2) + M(3, 1) 
M(3, 2) = M(2, 2) + M(2, 1) = 1 + M(2, 1) 
M(3, 1) = M(2, 1) + M(2, 0) = M(2, 1) + 1 
M(2, 1) = M(1, 1) + M(1, 0) = 1 + 1 = 2

現在我們可以「放鬆」遞歸，代找到了答案：

M(3, 1) = M(2, 1) + M(2, 0) = M(2, 1) + 1 = 2 + 1 = 3 
M(3, 2) = M(2, 2) + M(2, 1) = 1 + M(2, 1) = 1 + 2 = 3 
M(4, 2) = M(3, 2) + M(3, 1) = 3 + 3 = 6 
M(4, 3) = M(3, 3) + M(3, 2) = 1 + M(3, 2) = 1 + 3 = 4 
M(5, 3) = M(4, 3) + M(4, 2) = 4 + 6 = 10 
M(5, 4) = M(4, 4) + M(4, 3) = 1 + M(4, 3) = 1 + 4 = 5 
M(6, 4) = M(5, 4) + M(5, 3) = 5 + 10 = 15 
M(6, 5) = M(5, 5) + M(5, 4) = 1 + M(5, 4) = 1 + 5 = 6 
M(7, 5) = M(6, 5) + M(6, 4) = 15 + 6 = 21

我只是沒被模仿（大致）由函數的遞歸調用數學

來源

2014-10-19 01:02:32 Gene

-1

我建議你通過你的程序來了解發生了什麼。

拿一張紙，畫一個盒子。裏面那個盒子，寫：

m = 7, n = 5 

Is n == 0 or n == m? (y/n) 

return mystery(6,5) + mystery(6,4)

然後，畫出低於兩個箱，使用相同的數據，一個用於函數中每次調用謎。重複，直到每個到達基本情況。

當您到達函數的基本大小寫時，繪製一個箭頭指向任何稱爲它的「框」。然後，總結一下你的條款。

此方法適用於每個遞歸函數，並且是一個強大的工具。

來源

2014-10-19 01:04:35 Tetramputechture

需要幫助理解算法

回答

相關問題