Dãy Fibonacci là một dãy số trong toán học, bắt đầu bằng hai số 0 và 1, với mỗi số sau đó là tổng của hai số liền trước. Dãy số này có dạng: 0, 1, 1, 2, 3, 5, 8, 13, 21,… Fibonacci xuất hiện trong nhiều lĩnh vực khác nhau, từ sinh học đến tin học, và thường được sử dụng trong các bài toán tối ưu, thuật toán và lập trình.

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));
}