Dãy Fibonacci C++

Dãy Fibonacci trong C: Chương trình C cho dãy Fibonacci sử dụng vòng lặp và đệ quy. Sử dụng mã bên dưới, bạn có thể in bao nhiêu cụm từ của dãy theo yêu cầu. Các số của chuỗi này được gọi là số Fibonacci. Một vài số đầu tiên của chuỗi là 0, 1, 1, 2, 3, 5, 8, ...,. Ngoại trừ hai thuật ngữ đầu tiên của dãy thì mỗi cụm từ khác là tổng của hai cụm từ trước, ví dụ: 8 = 3 + 5 (bổ sung 3 và 5).

Dãy Fibonacci là một dãy trong đó thuật ngữ tiếp theo là tổng của hai thuật ngữ có thể qua được. Hai thuật ngữ đầu tiên của dãy Fibonacci là 0 theo sau là 1.

Chuỗi Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21

1. Chương trình in dãy Fibonacci không sử dụng hàm đệ qui trong C

Ví dụ cho chạy chương trình sau:

#include

int main()

{

   int i, n, t1 = 0, t2 = 1, nextTerm;

   printf("Enter the number of terms: ");

   scanf("%d", &n);

   printf("Fibonacci Series: ");

   for (i = 1; i <= n; ++i)

   {

       printf("%d, ", t1);

       nextTerm = t1 + t2;

       t1 = t2;

       t2 = nextTerm;

   }

   return 0;

}

Kết quả:

2. Chương trình in dãy Fibonacci sử dụng hàm đệ qui trong C

Chương trình ví dụ:

#include

int main()

{

   int t1 = 0, t2 = 1, nextTerm = 0, n;

   printf("Enter a positive number: ");

   scanf("%d", &n);

   // displays the first two terms which is always 0 and 1

   printf("Fibonacci Series: %d, %d, ", t1, t2);

   nextTerm = t1 + t2;

   while(nextTerm <= n)

   {

       printf("%d, ",nextTerm);

       t1 = t2;

       t2 = nextTerm;

       nextTerm = t1 + t2;

   }

   return 0;

}

Kết quả:

Phương thức đệ quy kém hiệu quả hơn vì nó liên quan đến các cuộc gọi hàm lặp lại và có khả năng tràn ngăn xếp vì hàm này thường được gọi để tính các số Fibonacci lớn hơn.

Trong bài viết này chúng ta sẽ giải bài tập in ra dãy số fibonacci bằng ngôn ngữ lập trình C. Thông thường với bài toán này thì ta hay sử dụng giải thuật đệ quy. Tuy nhiên bạn cũng có thể sử dụng vòng lặp while để giải quyết một cách dễ dàng. Vi dụ người dùng yêu cầu in ra 6 số đầu tiên thì kết quả là: "0, 1, 1, 2, 3, 5".

Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

Vậy trong bài này bạn sẽ áp dụng hai kiến thức như sau:

• Đệ quy
• Vòng lặp for

Dãy số fibonacci là gi? Đó là số mà tổng của hai số fibonacci đằng trước bằng chính nó. Hai số đầu tiên ngoại lệ là 0 và 1.

I. In dãy số fibonacci bằng vòng lặp while

Vòng lặp while ta sẽ không thể biết được số lần lặp, vì vậy có thể sử dụng để thay thế cho các bài toán đệ quy, hay còn gọi là khử đệ quy.

Fibonacci là dãy số kinh điển trong toán học được tìm thấy cách đây hơn 800 năm. Đến nay các nhà khoa học phát hiện nhiều trùng hợp thú vị về dãy số này trong tự nhiên.

Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng 1 và 1, sau đó các số tiếp theo sẽ bằng tổng của 2 số liền trước nó. 

Cụ thể, các số đầu tiên của dãy Fibonacci là 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610…

Xem thêm hình minh họa dưới đây để hiểu thêm về dãy Fibonacci.

Trong bài viết này chúng ta sẽ thực hiện viết thuật toán cho chương trình tính số Fibonacci.

• Kiếm tiền Accesstrade, kiếm tiền tại nhà với Accesstrade.vn – Tiếp thị liên kết
• MegaURL – Rút gọn link kiếm tiền có giá cao tại Việt Nam
• Top 4 App kiếm tiền online trên điện thoại tốt nhất 2022

Sử dụng đệ quy để tính Fibonacci

Đối với cách này đòi hỏi bạn cần phải nắm rõ về cách hoạt động của hàm Đệ quy, nếu bạn vẫn chưa biết về đệ quy có thể theo dõi ở các bài viết tiếp theo mình sẽ có bài viết cụ thể.

Chương trình minh họa

#include 
using namespace std;
int tinhFibonaci(int n)//Hàm tính Fibonaci bằng đệ quy
{
	if(n==0) return 0;
	if(n<=2) return 1; //Trường hợp suy biến
	return tinhFibonaci(n-1)+tinhFibonaci(n-2); //Đệ quy gọi lại 2 hàm con để thực hiện tính toán
}
int main()
{
	int n;
	cout<<"Nhap n:"; cin>>n;
	cout<<"Fibonacci thu n la: "<
Tuy nhiên đối với bản thân mình thì mình không khuyến khích áp dụng cách này cho bài toán này, bởi vì chương trình chạy rất chậm.
Hãy hình dung hàm tinhFibonaci(int n) mỗi lần thực hiện nó sẽ gọi lại 2 hàm con để thực hiện tính toán trừ trường hợp n<3 trả về kết quả ngay(trường hợp này gọi là Trường hợp suy biến trong đệ quy). Như vậy để tính toán số Fibonacci thứ n thì cần tới n^2 lần tính toán nên dẫn tới thời gian tính toán rất lâu.
Kết quả thực hiện chương trình
Sử dụng vòng lặp để tính Fibonacci
Đối với cách này chương trình chạy sẽ rất nhanh, độ phức tạp của thuật toán là n.
Chương trình minh họa
#include 
using namespace std;
int main()
{
	int n;
	cout<<"Nhap n:"; cin>>n;
	
	int a=0, b=1, fibo; //Khai báo giá trị ban đầu
	for(int i=1;i<=n;i++){
		fibo=a+b;
		b=a;
		a=fibo;
	}
	cout<<"Fibonacci thu n la: "<
Ở đây mình gọi a là Fibo(0), b là Fibo(1), biến fibo để tính và lưu giá trị fibo thứ n…..Sau mỗi vòng lặp biến fibo sẽ được tính toán bằng a+b, 2 biến a và b sẽ được gắn lại giá trị.