피사노 주기
-
피사노 주기알고리즘 2020. 8. 9. 21:47
피보나치- 개념 : F0 = 0 , F1 = 1일때 Fn = Fn-1 + Fn-2- 구현 방법 1. 재귀적 방법 : O(2^n) 2. dp 방법 (= memoization 방법) : O(n) 3. 피사노 주기 피사노 주기(Pisano period) - 개념 : 피보나치 수를 어떤 수 K로 나눌 때, 나머지는 항상 주기를 가지게 되는데 이를 피사노 주기라고 한다. ex) 피보나치 수를 3으로 나누었을때, 주기의 길이는 8 N 0 1 2 3 4 5 6 7 89101112131415 Fn 0 1 1 2 3 5 8 13 21 34 55 89 144 233377 610 PP 0 1 1 2 0 2 2 1 0 1 1 2 0 2 2 1 - 성질 : 주기의 길이를 P라고 하면 N번째 피보나치 수를 M으로 나눈 나머지는 ..