우리에게 많이 알려진 점화식으로 피보나치를 구하면 피보나치 재귀에서 엄청난 중복이 생긴다.
피보나치 수열을 아래와 같이 행렬식으로 변환하면 n번의 제곱으로 수를 구할 수 있다.
n 번째 피보나치 수열의 수를 Fn 이라 할 때,
|F2 F1| = |1 1|
|F1 F0| |1 0|
이 된다.
이 정사각 행렬을 n 번 제곱하면
|Fn+1 Fn| = |1 1|^n
|Fn Fn-1| |1 0|
이 된다.
(http://en.wikipedia.org/wiki/Fibonacci_number 의 Matrix form 참조)
이 때, 정사각 행렬 A 에 대해 A^nA^m = A^(n+m), A^nA^n = A^2n 이 성립하므로
이를 이용하면 Divide & Conquer 를 적용하여 log 2 n 번의 제곱으로 수를 구할 수 있다.
아래는 구현한 소스이다. 링크를 따라가면, 코드 하이라이트가 적용된 소스를 볼 수 있다.
피보나치 수열을 아래와 같이 행렬식으로 변환하면 n번의 제곱으로 수를 구할 수 있다.
n 번째 피보나치 수열의 수를 Fn 이라 할 때,
|F2 F1| = |1 1|
|F1 F0| |1 0|
이 된다.
이 정사각 행렬을 n 번 제곱하면
|Fn+1 Fn| = |1 1|^n
|Fn Fn-1| |1 0|
이 된다.
(http://en.wikipedia.org/wiki/Fibonacci_number 의 Matrix form 참조)
이 때, 정사각 행렬 A 에 대해 A^nA^m = A^(n+m), A^nA^n = A^2n 이 성립하므로
이를 이용하면 Divide & Conquer 를 적용하여 log 2 n 번의 제곱으로 수를 구할 수 있다.
아래는 구현한 소스이다. 링크를 따라가면, 코드 하이라이트가 적용된 소스를 볼 수 있다.
class Matrix2x2
attr_accessor :matrix
def initialize
@matrix = []
@matrix[0] = []
@matrix[1] = []
end
def set_value(row1col1, row1col2, row2col1, row2col2)
@matrix[0][0] = row1col1
@matrix[0][1] = row1col2
@matrix[1][0] = row2col1
@matrix[1][1] = row2col2
self
end
def multiply(mat)
mat_ret = Matrix2x2.new.set_value(
@matrix[0][0] * mat.matrix[0][0] + @matrix[0][1] * mat.matrix[1][0],
@matrix[0][0] * mat.matrix[0][1] + @matrix[0][1] * mat.matrix[1][1],
@matrix[1][0] * mat.matrix[0][0] + @matrix[1][1] * mat.matrix[1][0],
@matrix[1][0] * mat.matrix[0][1] + @matrix[1][1] * mat.matrix[1][1]
)
mat_ret
end
def power(exp)
return Matrix2x2.unit if 0 == exp
return dclone if 1 == exp
if 1 == exp & 1
mat_ret = power((exp - 1) / 2)
mat_ret = mat_ret.multiply( mat_ret ).multiply( self )
else
mat_ret = power(exp / 2)
mat_ret = mat_ret.multiply( mat_ret )
end
mat_ret
end
def Matrix2x2.unit
Matrix2x2.new.set_value(1, 0, 0, 1)
end
def dclone()
Matrix2x2.new.set_value(
@matrix[0][0], @matrix[0][1],
@matrix[1][0], @matrix[1][1]
)
end
end
def fibonacci(n)
mat = Matrix2x2.new.set_value(1, 1, 1, 0)
mat.power(n).matrix[0][1]
end
puts "100th Fibonacci number is " + fibonacci(100).to_s
'Dev.Programming > DS/Algorithm' 카테고리의 다른 글
| Backtracking : N-Queen Problem (2) | 2009/05/07 |
|---|---|
| Backtracking : 미로 찾기 (0) | 2009/05/07 |
| Divide & Conquer : n 번째 피보나치 수열의 수를 구하기 (2) | 2009/05/06 |
| Divide & Conquer : 거듭제곱 알고리즘 (0) | 2009/05/06 |
| 해시 검색 - in Ruby (0) | 2009/03/18 |
| 이진 검색 - in Ruby (0) | 2009/03/18 |
