피보나치 수열 심화과정5 -피보나치 수열의 합을 가장 빠르게 구하는 방법-

1. 피보나치 수열 $F_{0} = 0, F_{1} = 1, F_{n} = F_{n-1}+F_{n-2}, n \geq 2$로 정의되는 수열 $F_{n}$ 2. 홀수번째 항의 합 1항부터 $2n-1$번째 항까지의 합은 다음과 같이 $2n$번째 항과 동일하다. $$\sum_{k = 1}^{n} F_{2k-1} = F_{2n}$$ 증명) $F_{n+2} = F_{n+1} + F_{n}$에서 n = 2n - 2를 대입하면, $F_{2n} = F_{2n-1} + F_{2n-2}$ 그러면, $F_{2n-1} = F_{2n} - F_{2n-2}$이므로, $$\sum_{k=1}^{n} F_{2k-1} = F_{1} + \sum_{k=2}^{n} (F_{2k} - F_{2k-2})$$ 이 식을 풀어서 써보면, 망원급수임..

• format_list_bulleted 정수론
• · 2023. 5. 27.
• textsms

필승 전략 게임 - 돌 줍기 게임에서 반드시 이기는 방법

1. 돌 줍기 게임 1) A부터 시작하여, A와 B가 번갈아가며 쌓여 있는 돌 무더기에서 돌을 1개 이상 집어온다. 2) 자기 차례가 되어 돌을 집어 올때는, 반드시 상대방이 조금 전에 집어간 돌의 개수의 2배 이하로 집어와야 한다. 예를 들어, A가 2개를 집고 차례를 넘겼다면, B는 1개~4개까지 범위에서 돌을 집어와야한다. 이제 B가 3개를 집고 넘겨준다면, A는 다시 1개~6개 범위에서 마음대로 돌을 집어갈 수 있다. 3) 마지막 돌을 집어간 사람이 게임에서 승리한다. 4) 맨 처음 시작하는 사람이 돌을 다 집어갈 수는 없다 2. 반드시 이길 수는 없나? A,B가 최선의 전략으로 게임할때, 누가 이기는지 예측할 수 있을까? 1) 돌멩이가 1개 있을때, 게임 자체가 성립하지 않는다. 맨 처음 시작하..

• format_list_bulleted 게임이론
• · 2023. 5. 23.
• textsms

피보나치 수열 심화과정3 -모든 자연수는 피보나치 수의 합으로 유일하게 분해할 수 있다(제켄도르프의 정리)-

1. 피보나치 수 피보나치 수열 $F_{n}$을 다음과 같이 정의하고, $F_{n}$을 피보나치 수라고 하자. $F_{0} = 0, F_{1} = F_{2} = 1$, $F_{n} = F_{n-1} + F_{n-2}, n \geq 2$ 두 피보나치 수 $F_{m}$과 $F_{n}$에 대하여 m = n+1 혹은 m = n-1이면 두 피보나치 수가 인접하다고 한다. 즉, $F_{n+1}$과 $F_{n}$은 인접한 피보나치 수이며 $F_{n}$과 $F_{n-1}$은 인접한 피보나치 수이다. 2. 제켄도르프의 정리(Zeckendorf's theorem) "모든 자연수는 인접하지 않은 피보나치 수($F_{0}$, $F_{1}$을 제외한)들의 합으로 표현할 수 있으며, 그 표현 방법이 유일하다" 예를 들어 n = ..

• format_list_bulleted 정수론
• · 2023. 5. 23.
• textsms

피보나치 수열 심화과정2 - 자연수 n이 피보나치 수인지 바로 알 수 있을까? -

1. 주어진 수가 피보나치 수인지 바로 알 수 있을까? 피보나치 수는 $F_{1} = F_{2} = 1$이고 $F_{i} = F_{i-1} + F_{i-2}$을 만족하는 $F_{i}$이다. 반대로 어떤 자연수 n이 주어질때 그 수가 피보나치 수열 $F_{i}$의 하나인지 바로 판단할 수 있을까? 2. 행렬을 이용해 피보나치 수를 만드는 방법 일반적으로는 $F_{1} = F_{2} = 1$부터 차근차근 만들어나가는 것이다. 그러면 언젠가 주어진 자연수 n 근처에 도달할 것이고, n에 정확히 도달하면 n은 피보나치 수이고 n을 넘어가면 n은 피보나치 수가 아니다. 행렬을 이용한 피보나치 수 생성하는 방법이 O(logN)으로 가장 빠르면서 유의미한데, 이정도만 해도 사실 상당히 빠르다 https://deepd..

• format_list_bulleted 정수론
• · 2023. 5. 23.
• textsms

피보나치 수열 심화과정1 - n번째 피보나치 수를 바로 계산할 수 있을까? (피보나치 수열의 일반항과 황금비)-

1. 피보나치 수열 $F_{1} = F_{2} = 1$이고 3이상의 자연수 n에 대하여, $F_{n} = F_{n-1} + F_{n-2}$를 만족하는 수열 $F_{n}$을 피보나치 수열이라고 부른다. 2. 피보나치 수열을 만드는 방법 어떤 자연수 n이 주어졌을때, $F_{n}$을 O(1)에 바로 계산할 수 있는가? 1,1,2,3,5,...로 더해나가 n번째 피보나치 수열의 항을 구하는 것이 아니라 n만 알면 n번째 피보나치 수를 바로 구할 수 있는지? 3. 선형점화식의 특성방정식(characteristic equation) 선형점화식 $$f(n) = a_{n+k} + c_{1}a_{n+k-1} + c_{2}a_{n+k-2} + ... + c_{k}a_{n}$$ 에 대하여, 모든 i = 0, 1, 2, ....

• format_list_bulleted 정수론
• · 2023. 5. 22.
• textsms

행렬을 이용한 피보나치 수열 문제의 해법

1. 피보나치 수열의 행렬 표현 피보나치 수열의 점화식은 다음과 같다. $a_{n+1} = a_{n} + a_{n-1}$ $a_{n} = a_{n} + 0$ 따라서 행렬로 나타내면 다음과 같다 $$\begin{pmatrix} a_{n+1} \\ a_{n} \end{pmatrix}=\begin{pmatrix} 1 & 1 \\ 1 & 0 \\ \end{pmatrix}\begin{pmatrix} a_{n} \\ a_{n-1} \end{pmatrix}$$ n = 1부터 반복적으로 곱해보면... $$ $$\begin{pmatrix} a_{2} \\ a_{1} \end{pmatrix}$$ = $$\begin{pmatrix} 1 & 1 \\ 1 & 0 \\ \end{pmatrix}$$ \begin{pmatrix} a_{1} \\ a_{0..

• format_list_bulleted 선형대수학 알고리즘
• · 2023. 3. 19.
• textsms