Chương trình C ++ để hiển thị chuỗi Fibonacci

Dãy fibonacci chứa các số trong đó mỗi số hạng là tổng của hai số hạng trước đó. Điều này tạo ra chuỗi số nguyên sau -

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

Quan hệ lặp lại xác định các số fibonacci như sau -

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

Các chương trình hiển thị chuỗi Fibonacci

Có hai phương pháp để hiển thị chuỗi fibonacci, tức là sử dụng lập trình động và lập trình đệ quy. Những điều này được giải thích thêm như sau -

Lập trình động

Ví dụ

#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;
}

Kết quả của chương trình trên như sau.

Đầu ra

0 1 1 2 3 5 8 13 21 34

Trong chương trình, main () là hàm trình điều khiển. Mã thực sự để tạo chuỗi fibonacci được lưu trữ trong hàm fib () được gọi từ hàm main.

Một mảng f [n] được tạo sẽ lưu trữ n số hạng đầu tiên của chuỗi fibonacci. Phần tử đầu tiên và phần tử thứ hai của mảng này được khởi tạo lần lượt là 0 và 1..

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

Sau đó, vòng lặp for được sử dụng để lưu trữ từng phần tử trong mảng dưới dạng tổng của hai phần tử trước đó của nó.

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

Cuối cùng thì chuỗi fibonacci được hiển thị.

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

Lập trình đệ quy

Hãy để chúng tôi xem cách hiển thị chuỗi fibonacci bằng cách sử dụng đệ quy.

Ví dụ

#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;
}

Đầu ra

0 1 1 2 3 5 8 13 21 34

Trong chương trình trên, một vòng lặp for được thiết lập để tạo ra từng số hạng của chuỗi fibonacci bằng cách sử dụng đệ quy. Điều này được thực hiện bằng cách gọi hàm fib () cho mỗi thuật ngữ trong chuỗi.

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

Hàm fib () trả về 0 hoặc 1 nếu n tương ứng là 0 hoặc 1. Nếu không, nó tự gọi đệ quy là tổng của hai số hạng trước đó cho đến khi giá trị chính xác được trả về.

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