Quy luật của dãy số Fibonacci: số tiếp theo bằng tổng của 2 số trước, 2 số đầu tiên của dãy số là 0, 1. Ví dụ: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …
Có 2 cách để viết chương trình dãy số Fibonacci trong C++
- Tính dãy số Fibonacci trong C++ không dùng phương pháp đệ quy
- Tính dãy số Fibonacci trong C++ sử dụng phương pháp đệ quy
Tính dãy số Fibonacci không dùng phương pháp đệ quy
Ví dụ chương trình tính dãy số Fibonacci không sử dụng phương pháp đệ quy:
File: FibonacciExample1.cpp
/**
* Tinh day so Fibonacci KHONG dung phuong phap de quy
*
* @author viettuts.vn
*/
#include <iostream>
using namespace std;
/**
* Tinh so Fibonacci thu n
*
* @param n: chi so cua so Fibonacci tinh tu 0
* vd: F0 = 0, F1 = 1, F2 = 1, F3 = 2
* @return So Fibonacci thu n
*/
int fibonacci(int n) {
int f0 = 0;
int f1 = 1;
int fn = 1;
int i;
if (n < 0) {
return -1;
} else if (n == 0 || n == 1) {
return n;
} else {
for (i = 2; i < n; i++) {
f0 = f1;
f1 = fn;
fn = f0 + f1;
}
}
return fn;
}
/**
* Ham main
*/
int main() {
int i;
cout << "10 so dau tien cua day so Fibonacci: \n";
for (i = 0; i < 10; i++) {
cout << fibonacci(i) << " ";
}
}
Kết quả:
10 so dau tien cua day so Fibonacci: 0 1 1 2 3 5 8 13 21 34
Tính dãy số Fibonacci sử dụng phương pháp đệ quy
Ví dụ chương trình tính dãy số Fibonacci sử dụng phương pháp đệ quy:
File: FibonacciExample2.cpp
/**
* Tinh day so Fibonacci bang phuong phap de quy
*
* @author viettuts.vn
*/
#include <iostream>
using namespace std;
/**
* Tinh so Fibonacci thu n
*
* @param n: chi so cua so Fibonacci tinh tu 0
* vd: F0 = 0, F1 = 1, F2 = 1, F3 = 2
* @return So Fibonacci thu n
*/
int fibonacci(int n) {
if (n < 0) {
return -1;
} else if (n == 0 || n == 1) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
/**
* Ham main
*/
int main() {
int i;
cout << "10 so dau tien cua day so Fibonacci: \n";
for (i = 0; i < 10; i++) {
cout << fibonacci(i) << " ";
}
}
Kết quả:
10 số đầu tiên của dãy số fibonacci: 0 1 1 2 3 5 8 13 21 34