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.

DANH SÁCH BÀI VIẾT Chương trình cộng trừ 2 số phức trong Lập trình C/C++ Cách tìm UCLN và BCNN trong lập trình C/C++ Thuật toán tính dãy số Fibonacci bằng 3 cách trong C/C++ Kiểm tra số chẵn lẻ trong lập trình C/C++ Cách kiểm tra Số hoàn hảo trong Lập trình C/C++

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 <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ụ!!

XEM THÊM Thuật toán đếm số lượng chữ số của số nguyên dương n bằng C / C++ Thuật toán sắp xếp nhanh (Quick Sort) Thuật toán sắp xếp trộn (Merge Sort) Một số chương trình xây dựng trên Graphics C/C++ Hướng dẫn cài đặt thư viện Graphics trên IDE Devc++ 3.2 6 Phiếu bình chọn Xếp hạng bài viết