戰略理解的代碼，我不能讓

-2

快速的方法來快速計算斐波那契數，使用矩陣屬性戰略理解的代碼，我不能讓

Divide_Conquer_Fib(n) { 
    i = h = 1; 
    j = k = 0; 
    while (n > 0) { 
    if (n%2 == 1) { // if n is odd 
    t = j*h; 
    j = i*h + j*k + t; 
    i = i*k + t; 
    } 
t = h*h; 
h = 2*k*h + t; 
k = k*k + t; 
n = (int) n/2; 
} 
    return j;

}

我如何理解這段代碼？你的戰略是什麼？你會寫很多打印語句來查看變量的狀態是如何變化的？瞭解各種開發人員的想法對理解這些代碼非常重要。

來源

2013-11-22 ERJAN

我會看到它是如何表現爲1,2,3,2n，2n + 1，因爲此算法適用於偶數和奇數。我會用紙和筆代替printf – Jekyll

我會拿一張紙和「使用我的鉛筆運行該功能」，這是一個非常簡單的案例 – JoeC

這個問題似乎是無關緊要的，因爲它要求程序員的意見，而且指出瞭解各種開發者的想法對於理解這些代碼是非常重要的，「這對於這個站點來說是非常偏離主題的。 –

我會首先運行它反對n的幾個值，以檢查它是否真正顯示出正確的答案。然後，我讀了數學理論，以瞭解它是如何工作的，並最終使用這些知識將其轉化爲位...

Matrix form的維基百科條目部分解釋了該算法的基礎。

來源

2013-11-22 22:04:38 EricM

嗯，看這段代碼的正確方法是知道它的作用：斐波納契數字經常作爲一個有趣的練習出現，另外還有相當多的上下文來說明它的作用：它使用矩陣屬性與分而治之。事實證明，就可以計算矢量（FIB _Ñ，Fib的_n-1個）一些矩陣的的產物和（FIB _n-1個，Fib的_N-2）。讓我們假設兩列在下面的代碼只是兩行相同的矩陣：

(Fib[n] ) (1 1) (Fib[n-1]) 
(  ) = ( ) * (  ) 
(Fib[n-1]) (1 0) (Fib[n-2])

現在，二次矩陣的矩陣乘法是關聯的，也就是說，如果上面的矩陣是中號可以計算蛋白原_n as M ⁿ times （1,0）。

下一步是計算M ⁿ使用分而治之。這裏的基本技巧是根據ñ位是中號^ň可以分解：而不是由ň乘法計算電源就分解計算成計算正方形，如果該值乘以一個額外的項奇。

這是基本的基本方法。功率的計算是在另一個方向完成的，然而，這是有效的 - 我認爲 - 因爲矩陣是對稱的。如果您不瞭解基本方法，我認爲您不能從代碼中輕鬆推導出算法。

來源

2013-11-22 22:33:52

戰略理解的代碼，我不能讓

回答

相關問題