N번째 피보나치 수
숫자가 주어지면 N , 인쇄 n번째 피보나치 수 .
피보나치 수열은 다음과 같은 정수 시퀀스의 숫자입니다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
예:
권장 문제 문제 해결 [/Tex] 시드 값과입력 : n = 1
출력 : 1
입력 : n = 9
출력 : 3. 4
입력 : n = 10
출력 : 55
그리고 
.
C++
// Fibonacci Series using Space Optimized Method> #include> using> namespace> std;> int> fib(> int> n)> {> > int> a = 0, b = 1, c, i;> > if> (n == 0)> > return> a;> > for> (i = 2; i <= n; i++) {> > c = a + b;> > a = b;> > b = c;> > }> > return> b;> }> // Driver code> int> main()> {> > int> n = 9;> > cout < < fib(n);> > return> 0;> }> // This code is contributed by Code_Mech> |
씨
// Fibonacci Series using Space Optimized Method> #include> int> fib(> int> n)> {> > int> a = 0, b = 1, c, i;> > if> (n == 0)> > return> a;> > for> (i = 2; i <= n; i++) {> > c = a + b;> > a = b;> > b = c;> > }> > return> b;> }> int> main()> {> > int> n = 9;> > printf> (> '%d'> , fib(n));> > getchar> ();> > return> 0;> }> |
자바
// Java program for Fibonacci Series using Space> // Optimized Method> public> class> fibonacci {> > static> int> fib(> int> n)> > {> > int> a => 0> , b => 1> , c;> > if> (n ==> 0> )> > return> a;> > for> (> int> i => 2> ; i <= n; i++) {> > c = a + b;> > a = b;> > b = c;> > }> > return> b;> > }> > public> static> void> main(String args[])> > {> > int> n => 9> ;> > System.out.println(fib(n));> > }> };> // This code is contributed by Mihir Joshi> |
파이썬3
# Function for nth fibonacci number - Space Optimisation> # Taking 1st two fibonacci numbers as 0 and 1> def> fibonacci(n):> > a> => 0> > b> => 1> > if> n <> 0> :> > print> (> 'Incorrect input'> )> > elif> n> => => 0> :> > return> a> > elif> n> => => 1> :> > return> b> > else> :> > for> i> in> range> (> 2> , n> +> 1> ):> > c> => a> +> b> > a> => b> > b> => c> > return> b> # Driver Program> print> (fibonacci(> 9> ))> # This code is contributed by Saket Modi> |
씨#
// C# program for Fibonacci Series> // using Space Optimized Method> using> System;> namespace> Fib {> public> class> GFG {> > static> int> Fib(> int> n)> > {> > int> a = 0, b = 1, c = 0;> > // To return the first Fibonacci number> > if> (n == 0)> > return> a;> > for> (> int> i = 2; i <= n; i++) {> > c = a + b;> > a = b;> > b = c;> > }> > return> b;> > }> > // Driver function> > public> static> void> Main(> string> [] args)> > {> > int> n = 9;> > Console.Write(> '{0} '> , Fib(n));> > }> }> }> // This code is contributed by Sam007.> |
자바스크립트
> // Javascript program for Fibonacci Series using Space Optimized Method> function> fib(n)> {> > let a = 0, b = 1, c, i;> > if> ( n == 0)> > return> a;> > for> (i = 2; i <= n; i++)> > {> > c = a + b;> > a = b;> > b = c;> > }> > return> b;> }> // Driver code> > let n = 9;> > > document.write(fib(n));> // This code is contributed by Mayank Tyagi> > |
PHP
// PHP program for Fibonacci Series // using Space Optimized Method function fib( $n) { $a = 0; $b = 1; $c; $i; if( $n == 0) return $a; for($i = 2; $i <= $n; $i++) { $c = $a + $b; $a = $b; $b = $c; } return $b; } // Driver Code $n = 9; echo fib($n); // This code is contributed by anuj_67. ?>> |
산출
34
시간 복잡도: 에)
보조 공간: 오(1)
N번째 피보나치 수를 찾고 인쇄하는 재귀 접근 방식:
수학적인 용어로 피보나치 수열의 Fn은 반복 관계로 정의됩니다.
시드 값과
그리고
.
N번째 피보나치 수는 위에 표시된 반복 관계를 사용하여 찾을 수 있습니다.
- 만약에 N = 0이면 0을 반환합니다.
- n = 1이면 1을 반환해야 합니다.
- n> 1인 경우 F를 반환해야 합니다. n-1 + 에프 n-2
다음은 위의 접근 방식을 구현한 것입니다.
C++
// Fibonacci Series using Recursion> #include> using> namespace> std;> int> fib(> int> n)> {> > if> (n <= 1)> > return> n;> > return> fib(n - 1) + fib(n - 2);> }> int> main()> {> > int> n = 9;> > cout < < n < <> 'th Fibonacci Number: '> < < fib(n);> > return> 0;> }> // This code is contributed> // by Akanksha Rai> |
씨
// Fibonacci Series using Recursion> #include> int> fib(> int> n)> {> > if> (n <= 1)> > return> n;> > return> fib(n - 1) + fib(n - 2);> }> int> main()> {> > int> n = 9;> > printf> (> '%dth Fibonacci Number: %d'> , n, fib(n));> > return> 0;> }> |
자바
// Fibonacci Series using Recursion> import> java.io.*;> class> fibonacci {> > static> int> fib(> int> n)> > {> > if> (n <=> 1> )> > return> n;> > return> fib(n -> 1> ) + fib(n -> 2> );> > }> > public> static> void> main(String args[])> > {> > int> n => 9> ;> > System.out.println(> > n +> 'th Fibonacci Number: '> + fib(n));> > }> }> /* This code is contributed by Rajat Mishra */> |
파이썬3
# Fibonacci series using recursion> def> fibonacci(n):> > if> n <> => 1> :> > return> n> > return> fibonacci(n> -> 1> )> +> fibonacci(n> -> 2> )> if> __name__> => => '__main__'> :> > n> => 9> > print> (n,> 'th Fibonacci Number: '> )> > print> (fibonacci(n))> > # This code is contributed by Manan Tyagi.> |
씨#
// C# program for Fibonacci Series> // using Recursion> using> System;> public> class> GFG {> > public> static> int> Fib(> int> n)> > {> > if> (n <= 1) {> > return> n;> > }> > else> {> > return> Fib(n - 1) + Fib(n - 2);> > }> > }> > // driver code> > public> static> void> Main(> string> [] args)> > {> > int> n = 9;> > Console.Write(n +> 'th Fibonacci Number: '> + Fib(n));> > }> }> // This code is contributed by Sam007> |
자바스크립트
// Javascript program for Fibonacci Series> // using Recursion> function> Fib(n) {> > if> (n <= 1) {> > return> n;> > }> else> {> > return> Fib(n - 1) + Fib(n - 2);> > }> }> // driver code> let n = 9;> console.log(n +> 'th Fibonacci Number: '> + Fib(n));> |
PHP
// PHP program for Fibonacci Series // using Recursion function Fib($n) { if ($n <= 1) { return $n; } else { return Fib($n - 1) + Fib($n - 2); } } // driver code $n = 9; echo $n . 'th Fibonacci Number: ' . Fib($n); // This code is contributed by Sam007 ?>> |
산출
34
시간 복잡도: 지수, 모든 함수는 두 개의 다른 함수를 호출합니다.
보조 공간 복잡성: O(n), 재귀 트리의 최대 깊이는 n입니다.
N번째 피보나치 수를 찾고 인쇄하기 위한 동적 프로그래밍 접근 방식:
위의 접근 방식에서 5번째 피보나치 수에 대한 재귀 트리를 고려해보세요.
fib(5) / fib(4) fib(3) / / fib(3) fib(2) fib(2) fib(1) / / / fib(2) fib(1) fib(1) fib(0) fib(1) fib(0) / fib(1) fib(0)
보시다시피, 동일한 값에 대해 동일한 메서드 호출이 여러 번 수행되고 있습니다. 이는 동적 프로그래밍의 도움으로 최적화될 수 있습니다. 지금까지 계산된 피보나치 수를 저장하면 재귀 접근 방식에서 수행되는 반복 작업을 피할 수 있습니다.
N번째 피보나치 수를 찾고 인쇄하기 위한 동적 프로그래밍 접근 방식:
다음은 위의 접근 방식을 구현한 것입니다.
C++
// C++ program for Fibonacci Series> // using Dynamic Programming> #include> using> namespace> std;> class> GFG {> public> :> > int> fib(> int> n)> > {> > // Declare an array to store> > // Fibonacci numbers.> > // 1 extra to handle> > // case, n = 0> > int> f[n + 2];> > int> i;> > // 0th and 1st number of the> > // series are 0 and 1> > f[0] = 0;> > f[1] = 1;> > for> (i = 2; i <= n; i++) {> > // Add the previous 2 numbers> > // in the series and store it> > f[i] = f[i - 1] + f[i - 2];> > }> > return> f[n];> > }> };> // Driver code> int> main()> {> > GFG g;> > int> n = 9;> > cout < < g.fib(n);> > return> 0;> }> // This code is contributed by SoumikMondal> |
씨
// Fibonacci Series using Dynamic Programming> #include> int> fib(> int> n)> {> > /* Declare an array to store Fibonacci numbers. */> > int> f[n + 2];> // 1 extra to handle case, n = 0> > int> i;> > /* 0th and 1st number of the series are 0 and 1*/> > f[0] = 0;> > f[1] = 1;> > for> (i = 2; i <= n; i++) {> > /* Add the previous 2 numbers in the series> > and store it */> > f[i] = f[i - 1] + f[i - 2];> > }> > return> f[n];> }> int> main()> {> > int> n = 9;> > printf> (> '%d'> , fib(n));> > getchar> ();> > return> 0;> }> |
자바
// Fibonacci Series using Dynamic Programming> public> class> fibonacci {> > static> int> fib(> int> n)> > {> > /* Declare an array to store Fibonacci numbers. */> > int> f[]> > => new> int> [n> > +> 2> ];> // 1 extra to handle case, n = 0> > int> i;> > /* 0th and 1st number of the series are 0 and 1*/> > f[> 0> ] => 0> ;> > f[> 1> ] => 1> ;> > for> (i => 2> ; i <= n; i++) {> > /* Add the previous 2 numbers in the series> > and store it */> > f[i] = f[i -> 1> ] + f[i -> 2> ];> > }> > return> f[n];> > }> > public> static> void> main(String args[])> > {> > int> n => 9> ;> > System.out.println(fib(n));> > }> };> /* This code is contributed by Rajat Mishra */> |
파이썬3
# Fibonacci Series using Dynamic Programming> def> fibonacci(n):> > # Taking 1st two fibonacci numbers as 0 and 1> > f> => [> 0> ,> 1> ]> > for> i> in> range> (> 2> , n> +> 1> ):> > f.append(f[i> -> 1> ]> +> f[i> -> 2> ])> > return> f[n]> print> (fibonacci(> 9> ))> |
씨#
// C# program for Fibonacci Series> // using Dynamic Programming> using> System;> class> fibonacci {> > static> int> fib(> int> n)> > {> > // Declare an array to> > // store Fibonacci numbers.> > // 1 extra to handle> > // case, n = 0> > int> [] f => new> int> [n + 2];> > int> i;> > /* 0th and 1st number of the> > series are 0 and 1 */> > f[0] = 0;> > f[1] = 1;> > for> (i = 2; i <= n; i++) {> > /* Add the previous 2 numbers> > in the series and store it */> > f[i] = f[i - 1] + f[i - 2];> > }> > return> f[n];> > }> > // Driver Code> > public> static> void> Main()> > {> > int> n = 9;> > Console.WriteLine(fib(n));> > }> }> // This code is contributed by anuj_67.> |
자바스크립트
> // Fibonacci Series using Dynamic Programming> > function> fib(n)> > {> > /* Declare an array to store Fibonacci numbers. */> > let f => new> Array(n+2);> // 1 extra to handle case, n = 0> > let i;> > /* 0th and 1st number of the series are 0 and 1*/> > f[0] = 0;> > f[1] = 1;> > for> (i = 2; i <= n; i++)> > {> > /* Add the previous 2 numbers in the series> > and store it */> > f[i] = f[i-1] + f[i-2];> > }> > return> f[n];> > }> > let n=9;> > document.write(fib(n));> > > // This code is contributed by avanitrachhadiya2155> > > |
PHP
//Fibonacci Series using Dynamic // Programming function fib( $n) { /* Declare an array to store Fibonacci numbers. */ // 1 extra to handle case, // n = 0 $f = array(); $i; /* 0th and 1st number of the series are 0 and 1*/ $f[0] = 0; $f[1] = 1; for ($i = 2; $i <= $n; $i++) { /* Add the previous 2 numbers in the series and store it */ $f[$i] = $f[$i-1] + $f[$i-2]; } return $f[$n]; } $n = 9; echo fib($n); // This code is contributed by // anuj_67. ?>> |
산출
34
시간 복잡도 : 주어진 n에 대해 O(n)
보조 공간 : 에)
N번째 피보나치 수를 찾고 인쇄하기 위한 행렬 접근법의 N번째 거듭제곱
이 접근 방식은 행렬 M = {{1,1},{1,0}}을 그 자체에 n번 곱하면(즉, 거듭제곱(M, n)을 계산) 다음을 얻는다는 사실에 의존합니다. +1) 결과 행렬의 행과 열(0, 0)의 요소인 피보나치 수입니다.
- n이 짝수이면 k = n/2:
- 따라서 N번째 피보나치 수 = F(n) = [2*F(k-1) + F(k)]*F(k)
- n이 홀수이면 k = (n + 1)/2:
- 따라서 N번째 피보나치 수 = F(n) = F(k)*F(k) + F(k-1)*F(k-1)
이 공식은 어떻게 작동하나요?
공식은 행렬 방정식에서 파생될 수 있습니다.
양변에 행렬식을 취하면 (-1)을 얻습니다. N = F n+1 에프 n-1 – 에프 N 2
게다가 A 이후로 N ㅏ 중 =A n+m 임의의 정사각 행렬 A에 대해 다음 항등식을 도출할 수 있습니다(행렬 곱의 두 가지 서로 다른 계수에서 얻음).
에프 중 에프 N + 에프 m-1 에프 n-1 = F m+n-1 —————————(1)
식(1)에 n = n+1을 대입하면,
에프 중 에프 n+1 + 에프 m-1 에프 N = F m+n ————————–(2)
방정식(1)에 m = n을 대입합니다.
에프 2n-1 = F N 2 + 에프 n-1 2
방정식(2)에 m = n을 넣으면
에프 2n = (에프 n-1 + 에프 n+1 )에프 N = (2층 n-1 + 에프 N )에프 N ——–
(Fn+1 = Fn + Fn-1을 넣어서)
공식을 증명하려면 다음을 수행하면 됩니다.
- n이 짝수이면 k = n/2라고 놓을 수 있습니다.
- n이 홀수이면 k = (n+1)/2라고 할 수 있습니다.
아래는 위의 접근 방식을 구현한 것입니다.
C++
// Fibonacci Series using Optimized Method> #include> using> namespace> std;> void> multiply(> int> F[2][2],> int> M[2][2]);> void> power(> int> F[2][2],> int> n);> // Function that returns nth Fibonacci number> int> fib(> int> n)> {> > int> F[2][2] = { { 1, 1 }, { 1, 0 } };> > if> (n == 0)> > return> 0;> > power(F, n - 1);> > return> F[0][0];> }> // Optimized version of power() in method 4> void> power(> int> F[2][2],> int> n)> {> > if> (n == 0 || n == 1)> > return> ;> > int> M[2][2] = { { 1, 1 }, { 1, 0 } };> > power(F, n / 2);> > multiply(F, F);> > if> (n % 2 != 0)> > multiply(F, M);> }> void> multiply(> int> F[2][2],> int> M[2][2])> {> > int> x = F[0][0] * M[0][0] + F[0][1] * M[1][0];> > int> y = F[0][0] * M[0][1] + F[0][1] * M[1][1];> > int> z = F[1][0] * M[0][0] + F[1][1] * M[1][0];> > int> w = F[1][0] * M[0][1] + F[1][1] * M[1][1];> > F[0][0] = x;> > F[0][1] = y;> > F[1][0] = z;> > F[1][1] = w;> }> // Driver code> int> main()> {> > int> n = 9;> > cout < < fib(9);> > getchar> ();> > return> 0;> }> // This code is contributed by Nidhi_biet> |
씨
#include> void> multiply(> int> F[2][2],> int> M[2][2]);> void> power(> int> F[2][2],> int> n);> /* function that returns nth Fibonacci number */> int> fib(> int> n)> {> > int> F[2][2] = { { 1, 1 }, { 1, 0 } };> > if> (n == 0)> > return> 0;> > power(F, n - 1);> > return> F[0][0];> }> /* Optimized version of power() in method 4 */> void> power(> int> F[2][2],> int> n)> {> > if> (n == 0 || n == 1)> > return> ;> > int> M[2][2] = { { 1, 1 }, { 1, 0 } };> > power(F, n / 2);> > multiply(F, F);> > if> (n % 2 != 0)> > multiply(F, M);> }> void> multiply(> int> F[2][2],> int> M[2][2])> {> > int> x = F[0][0] * M[0][0] + F[0][1] * M[1][0];> > int> y = F[0][0] * M[0][1] + F[0][1] * M[1][1];> > int> z = F[1][0] * M[0][0] + F[1][1] * M[1][0];> > int> w = F[1][0] * M[0][1] + F[1][1] * M[1][1];> > F[0][0] = x;> > F[0][1] = y;> > F[1][0] = z;> > F[1][1] = w;> }> /* Driver program to test above function */> int> main()> {> > int> n = 9;> > printf> (> '%d'> , fib(9));> > getchar> ();> > return> 0;> }> |
자바
// Fibonacci Series using Optimized Method> public> class> fibonacci {> > /* function that returns nth Fibonacci number */> > static> int> fib(> int> n)> > {> > int> F[][] => new> int> [][] { {> 1> ,> 1> }, {> 1> ,> 0> } };> > if> (n ==> 0> )> > return> 0> ;> > power(F, n -> 1> );> > return> F[> 0> ][> 0> ];> > }> > static> void> multiply(> int> F[][],> int> M[][])> > {> > int> x = F[> 0> ][> 0> ] * M[> 0> ][> 0> ] + F[> 0> ][> 1> ] * M[> 1> ][> 0> ];> > int> y = F[> 0> ][> 0> ] * M[> 0> ][> 1> ] + F[> 0> ][> 1> ] * M[> 1> ][> 1> ];> > int> z = F[> 1> ][> 0> ] * M[> 0> ][> 0> ] + F[> 1> ][> 1> ] * M[> 1> ][> 0> ];> > int> w = F[> 1> ][> 0> ] * M[> 0> ][> 1> ] + F[> 1> ][> 1> ] * M[> 1> ][> 1> ];> > F[> 0> ][> 0> ] = x;> > F[> 0> ][> 1> ] = y;> > F[> 1> ][> 0> ] = z;> > F[> 1> ][> 1> ] = w;> > }> > /* Optimized version of power() in method 4 */> > static> void> power(> int> F[][],> int> n)> > {> > if> (n ==> 0> || n ==> 1> )> > return> ;> > int> M[][] => new> int> [][] { {> 1> ,> 1> }, {> 1> ,> 0> } };> > power(F, n /> 2> );> > multiply(F, F);> > if> (n %> 2> !=> 0> )> > multiply(F, M);> > }> > /* Driver program to test above function */> > public> static> void> main(String args[])> > {> > int> n => 9> ;> > System.out.println(fib(n));> > }> };> /* This code is contributed by Rajat Mishra */> |
파이썬3
# Fibonacci Series using> # Optimized Method> # function that returns nth> # Fibonacci number> def> fib(n):> > F> => [[> 1> ,> 1> ],> > [> 1> ,> 0> ]]> > if> (n> => => 0> ):> > return> 0> > power(F, n> -> 1> )> > return> F[> 0> ][> 0> ]> def> multiply(F, M):> > x> => (F[> 0> ][> 0> ]> *> M[> 0> ][> 0> ]> +> > F[> 0> ][> 1> ]> *> M[> 1> ][> 0> ])> > y> => (F[> 0> ][> 0> ]> *> M[> 0> ][> 1> ]> +> > F[> 0> ][> 1> ]> *> M[> 1> ][> 1> ])> > z> => (F[> 1> ][> 0> ]> *> M[> 0> ][> 0> ]> +> > F[> 1> ][> 1> ]> *> M[> 1> ][> 0> ])> > w> => (F[> 1> ][> 0> ]> *> M[> 0> ][> 1> ]> +> > F[> 1> ][> 1> ]> *> M[> 1> ][> 1> ])> > F[> 0> ][> 0> ]> => x> > F[> 0> ][> 1> ]> => y> > F[> 1> ][> 0> ]> => z> > F[> 1> ][> 1> ]> => w> # Optimized version of> # power() in method 4> def> power(F, n):> > if> (n> => => 0> or> n> => => 1> ):> > return> > M> => [[> 1> ,> 1> ],> > [> 1> ,> 0> ]]> > power(F, n> /> /> 2> )> > multiply(F, F)> > if> (n> %> 2> !> => 0> ):> > multiply(F, M)> # Driver Code> if> __name__> => => '__main__'> :> > n> => 9> > print> (fib(n))> # This code is contributed> # by ChitraNayal> |
씨#
// Fibonacci Series using> // Optimized Method> using> System;> class> GFG {> > /* function that returns> > nth Fibonacci number */> > static> int> fib(> int> n)> > {> > int> [, ] F => new> int> [, ] { { 1, 1 }, { 1, 0 } };> > if> (n == 0)> > return> 0;> > power(F, n - 1);> > return> F[0, 0];> > }> > static> void> multiply(> int> [, ] F,> int> [, ] M)> > {> > int> x = F[0, 0] * M[0, 0] + F[0, 1] * M[1, 0];> > int> y = F[0, 0] * M[0, 1] + F[0, 1] * M[1, 1];> > int> z = F[1, 0] * M[0, 0] + F[1, 1] * M[1, 0];> > int> w = F[1, 0] * M[0, 1] + F[1, 1] * M[1, 1];> > F[0, 0] = x;> > F[0, 1] = y;> > F[1, 0] = z;> > F[1, 1] = w;> > }> > /* Optimized version of> > power() in method 4 */> > static> void> power(> int> [, ] F,> int> n)> > {> > if> (n == 0 || n == 1)> > return> ;> > int> [, ] M => new> int> [, ] { { 1, 1 }, { 1, 0 } };> > power(F, n / 2);> > multiply(F, F);> > if> (n % 2 != 0)> > multiply(F, M);> > }> > // Driver Code> > public> static> void> Main()> > {> > int> n = 9;> > Console.Write(fib(n));> > }> }> // This code is contributed> // by ChitraNayal> |
자바스크립트
> // Fibonacci Series using Optimized Method> // Function that returns nth Fibonacci number> function> fib(n)> {> > var> F = [ [ 1, 1 ], [ 1, 0 ] ];> > if> (n == 0)> > return> 0;> > > power(F, n - 1);> > return> F[0][0];> }> function> multiply(F, M)> {> > var> x = F[0][0] * M[0][0] + F[0][1] * M[1][0];> > var> y = F[0][0] * M[0][1] + F[0][1] * M[1][1];> > var> z = F[1][0] * M[0][0] + F[1][1] * M[1][0];> > var> w = F[1][0] * M[0][1] + F[1][1] * M[1][1];> > F[0][0] = x;> > F[0][1] = y;> > F[1][0] = z;> > F[1][1] = w;> }> // Optimized version of power() in method 4 */> function> power(F, n)> > > if> (n == 0> // Driver code> var> n = 9;> document.write(fib(n));> // This code is contributed by gauravrajput1> > |
산출
34
시간 복잡도: O(로그n)
보조 공간: 함수 호출 스택 크기를 고려하면 O(Log n)이고, 그렇지 않으면 O(1)입니다.
관련 기사:
Java의 큰 피보나치 수
