Cách tính số Fibonacci trong C/C++

Bài toán

Đề bài: Nhập vào một số nguyên dương n hãy tính số Fibonacci thứ n.

Ví dụ:

Input: 1
Output: 1

Input: 5
Output: 5

Hướng dẫn giải

Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử 0 và 1 hoặc 1 và 1, các phần tử sau đó được thiết lập theo quy tắc mỗi phần tử luôn bằng tổng hai phần tử trước nó. Công thức truy hồi của dãy Fibonacci là:

F(n) = 1; với n=1, n=2
F(n) = F(n-1) + F(n-2); với n > 2

Dựa vào công thức truy hồi như trên ta có thể dễ dàng dùng đệ quy để tính F(n). Ta cùng xem đoạn code sau:

int fibonacci(int n) {
  if (n <= 2) return 1;

  return fibonacci(n - 1) + fibonacci(n - 2);
}

Như vậy ta chỉ cần dùng điều kiện n <= 2 để dừng đệ quy.

Code

Dưới đây là đoạn code tham khảo:

#include <stdio.h>

int fibonacci(int n) {
  if (n <= 2) return 1;

  return fibonacci(n - 1) + fibonacci(n - 2);
}

int main()
{
  int n;

  printf("Enter n: ");
  scanf("%d", &n);

  printf("F(n): %d\n", fibonacci(n));
}