Thuật toán tính dãy số Fibonacci bằng 3 cách trong C/C++

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.

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 <iostream>
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: "<<tinhFibonaci(n);
}

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 <iostream>
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: "<<fibo;
}

Ở đâ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ị.

Kết quả thực hiện chương trình

Sử dụng quy hoạch động để tính Fibonacci

Chương trình minh họa cho thuật toán

#include <iostream>
using namespace std;
int QHD(int n)//Hàm quy hoạch động
{
	int a[n+1];
	a[0]=0; a[1]=1; a[2]=1;
	for(int i=3;i<=n;i++){
		a[i]=a[i-1]+a[i-2];// công thức truy hồi quy hoạch động 
	}
	return a[n];//Trả về kết quả cho hàm quy hoạch
}
int main()
{
	int n;
	cout<<"Nhap n:"; cin>>n;
	cout<<"Fibonacci thu n la: "<<QHD(n);

}

Kết quả thực hiện chương trình

Cảm ơn bạn đã theo dõi bài viết! Chúc sớm trở thành một Developer thực thụ!!

5

2

Phiếu bình chọn

Xếp hạng bài viết