๋ฌธ์
ํผ๋ณด๋์น ์๋ 0๊ณผ 1๋ก ์์ํ๋ค. 0๋ฒ์งธ ํผ๋ณด๋์น ์๋ 0์ด๊ณ , 1๋ฒ์งธ ํผ๋ณด๋์น ์๋ 1์ด๋ค. ๊ทธ๋ค์ 2๋ฒ์งธ๋ถํฐ๋ ๋ฐ๋ก ์ ๋ ํผ๋ณด๋์น ์์ ํฉ์ด ๋๋ค.
์ด๋ฅผ ์์ผ๋ก ์จ๋ณด๋ฉด Fn = Fn-1 + Fn-2 (n ≥ 2)๊ฐ ๋๋ค.
n=17์ผ๋ ๊น์ง ํผ๋ณด๋์น ์๋ฅผ ์จ๋ณด๋ฉด ๋ค์๊ณผ ๊ฐ๋ค.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
n์ด ์ฃผ์ด์ก์ ๋, n๋ฒ์งธ ํผ๋ณด๋์น ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ n์ด ์ฃผ์ด์ง๋ค. n์ 20๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์ ๋๋ 0์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ n๋ฒ์งธ ํผ๋ณด๋์น ์๋ฅผ ์ถ๋ ฅํ๋ค.
ํ์ด
Fn = Fn-1 + Fn-2 (n ≥ 2) ๊ณต์์ ์ฌ์ฉํ๋ฉด ๋๋ค.
f0 = 0, f1 = 1, f2 = 1 ์์ ์ ์ํ์
// ํผ๋ณด๋์น ์
#include <iostream>
using namespace std;
int fibonacci(int n){
if (n==0)
return 0;
else if (n==1 || n==2)
return 1;
return fibonacci(n-1)+fibonacci(n-2);
}
int main() {
int n;
cin >> n;
cout << fibonacci(n);
}
'โจ Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[ํ๋ก๊ทธ๋๋จธ์ค/C++] ๋คํธ์ํฌ (0) | 2021.08.24 |
---|---|
[๋ฐฑ์ค/C++] 2606๋ฒ : ๋ฐ์ด๋ฌ์ค(BFS) (0) | 2021.08.24 |
[๋ฐฑ์ค/C++] 10872๋ฒ : ํฉํ ๋ฆฌ์ผ (0) | 2021.08.24 |
[๋ฐฑ์ค/C++] 1260๋ฒ : DFS์ BFS (0) | 2021.08.24 |
[๊ฐ๋ ] DFS์ BFS (0) | 2021.08.24 |
๋๊ธ