Dãy số Fibonacci là dãy số nổi tiếng trong Toán học. Thuật toán dưới đây sẽ tìm ra số Fibonacci thứ n…
Bài toán: Cho một số nguyên dương n. Tìm số Fibonacci thứ n
Thuật toán sử dụng đệ quy:
#include <iostream>
using namespace std;
int Fibonacci(int n)
{
if (n == 1 || n == 2)
return 1;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
int main() {
freopen("FIBONACCI.INP","r",stdin);
freopen("FIBONACCI.OUT","w",stdout);
long n;
cin >> n;
cout << Fibonacci(n);
return 0;
}
Thuật toán không sử dụng đệ quy:
#include <iostream>
using namespace std;
int Fibonacci(int n)
{
int a1 = 1, a2 = 1;
if (n == 1 || n == 2)
return 1;
int i = 3, a;
while (i <= n)
{
a = a1 + a2;
a1 = a2;
a2 = a;
i++;
}
return a;
}
int main() {
freopen("FIBONACCI.INP","r",stdin);
freopen("FIBONACCI.OUT","w",stdout);
long n;
cin >> n;
cout << Fibonacci(n);
return 0;
}
Vấn đề đặt ra là nếu chúng ta sử dụng integer thì sẽ không tìm được những số nguyên lớn. Ta sử dụng int64_t để xác định dãy số Fibonacci như phần code dưới đây:
#include <iostream>
using namespace std;
int64_t Fibonacci(int n)
{
int64_t a1 = 1, a2 = 1;
if (n == 1 || n == 2)
return 1;
int i = 3; int64_t a;
while (i <= n)
{
a = a1 + a2;
a1 = a2;
a2 = a;
i++;
}
return a;
}
int main() {
freopen("FIBONACCI.INP","r",stdin);
freopen("FIBONACCI.OUT","w",stdout);
int n;
cin >> n;
cout << Fibonacci(n);
cout << endl;
for (int i=1; i <= n; i++) {
cout << Fibonacci(i) << " ";
}
return 0;
}
Kết quả tìm 50 số Fibonacci đầu tiên:
Số Fibonacci thứ 50: 12586269025
Dãy số gồm 50 phần tử đầu tiên của dãy Fibonacci: 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 12586269025