피보나치 수열을 표시하는 C++ 프로그램

피보나치 수열은 각 항이 이전 두 항의 합인 숫자를 포함합니다. 이것은 다음 정수 시퀀스를 생성합니다 -

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377…….

피보나치 수를 정의하는 반복 관계는 다음과 같습니다. -

F(n) = F(n-1) + F(n-2) F(0)=0 F(1)=1

피보나치 수열을 표시하는 프로그램

동적 계획법과 재귀 계획법을 사용하여 피보나치 수열을 표시하는 두 가지 방법이 있습니다. 이들은 다음과 같이 추가로 설명됩니다 -

동적 프로그래밍

예시

#include<iostream>
using namespace std;
void fib(int n) {
   int f[n];
   int i;
   f[0] = 0;
   f[1] = 1;
   for (i = 2; i < n; i++) {
      f[i] = f[i-1] + f[i-2];
   }
   for (i = 0; i < n; i++) {
      cout<<f[i]<<" ";
   }
}
int main () {
   int n = 10;
   fib(n);
   getchar();
   return 0;
}

위 프로그램의 출력은 다음과 같습니다.

출력

0 1 1 2 3 5 8 13 21 34

프로그램에서 main()은 드라이버 함수입니다. 피보나치 수열 생성을 위한 실제 코드는 main에서 호출되는 fib() 함수에 저장됩니다.

피보나치 수열의 처음 n항을 저장할 배열 f[n]이 생성됩니다. 이 배열의 첫 번째 요소와 두 번째 요소는 각각 0과 1로 초기화됩니다.

f[0] = 0;
f[1] = 1;

그런 다음 for 루프를 사용하여 배열의 각 요소를 이전 두 요소의 합으로 저장합니다.

for (i = 2; i < n; i++) {
   f[i] = f[i-1] + f[i-2];
}

마지막으로 피보나치 수열이 표시됩니다.

for (i = 0; i < n; i++) {
   cout<<f[i]<<" ";
}

재귀 프로그래밍

재귀를 사용하여 피보나치 수열을 표시하는 방법을 살펴보겠습니다.

예시

#include<iostream>
using namespace std;
int fib(int n) {
   if (n <= 1)
   return n;
   return fib(n-1) + fib(n-2);
}
int main () {
   int n = 10, i;
   for(i=0;i<n;i++)
   cout<<fib(i)<<" ";
   return 0;
}

출력

0 1 1 2 3 5 8 13 21 34

위의 프로그램에서 재귀를 사용하여 피보나치 수열의 각 항을 생성하는 for 루프가 설정되었습니다. 이것은 시리즈의 각 용어에 대해 fib() 함수를 호출하여 수행됩니다.

for(i=0;i<n;i++)
cout<<fib(i)<<" ";

fib() 함수는 n이 각각 0 또는 1이면 0 또는 1을 반환합니다. 그렇지 않은 경우 올바른 값이 반환될 때까지 이전 두 항의 합으로 자신을 재귀적으로 호출합니다.

if (n <= 1)
return n;
return fib(n-1) + fib(n-2);