【港】Dynamic Programming Intro Ep1 | 495. Teemo Attacking
MAGA
37 回覆
24 Like
0 Dislike
畢左業，做緊嘢。
Matrix multiplication 不過係recurrence relation嘅另一種寫法，唔係用Golden Ratio。
我係講Binet's Formula
https://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html
F(n) = (phi^n-(-phi)^(-n))/(sqrt(5))
= ((1+sqrt(5))^n-(1-sqrt(5))^n)/(2^n * sqrt(5))
有無方法用呢條formula而又無precsion error。
我係講Binet's Formula
https://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html
F(n) = (phi^n-(-phi)^(-n))/(sqrt(5))
= ((1+sqrt(5))^n-(1-sqrt(5))^n)/(2^n * sqrt(5))
有無方法用呢條formula而又無precsion error。
大家聽開印度人
推，我都想學多啲嘢，大家交流吓
numerically stable少少姐...
lm
點stable法？
BTW，黃金比例Phi係 (1+sqrt(5)) / 2, 可以睇成1/2 + 1/2*sqrt(5)。如果考慮a，b係有理數（份數）所有 a + b * sqrt(5) 所代表嘅數組成一個叫field嘅數學結構。加減乘除後嘅結果都係響個field裡面。
如果要無precision error用Binet's formula去計Fibonacci numbers其中一個方法係用一個abstract data type去代表呢個field然後去計算Binet‘s formula。呢個方法係會計算到準確答案。不過呢個方法要處理好大嘅份數，有啲language例如Python或Haskell有常用library，C++/C要另外搵library
BTW，黃金比例Phi係 (1+sqrt(5)) / 2, 可以睇成1/2 + 1/2*sqrt(5)。如果考慮a，b係有理數（份數）所有 a + b * sqrt(5) 所代表嘅數組成一個叫field嘅數學結構。加減乘除後嘅結果都係響個field裡面。
如果要無precision error用Binet's formula去計Fibonacci numbers其中一個方法係用一個abstract data type去代表呢個field然後去計算Binet‘s formula。呢個方法係會計算到準確答案。不過呢個方法要處理好大嘅份數，有啲language例如Python或Haskell有常用library，C++/C要另外搵library
(1+sqrt(5))^n-(1-sqrt(5))^n=2(nC1*sqrt(5)+nC3*sqrt(5)^3+nC5*sqrt(5)+...)
=sqrt(5)*(2nC1+2*nC3*5+2*nC5*5^2+...)
所以F(n)=(2nC1+2*nC3*5+2*nC5*5^2+...)/(2^n)
咁咪冇precision error
=sqrt(5)*(2nC1+2*nC3*5+2*nC5*5^2+...)
所以F(n)=(2nC1+2*nC3*5+2*nC5*5^2+...)/(2^n)
咁咪冇precision error
都得，不過咁就唔係直接用條formula。
Any肥，只係想討論下黃金分割率用簡單方法計Fibonacci numbers係有啲限制。
Any肥，只係想討論下黃金分割率用簡單方法計Fibonacci numbers係有啲限制。