Dãy số Fibonaci

Dãy số Fibonaci là dãy số vô hạn các số tự nhiên bắt đầu bằng 0 và 1. Các phần tử sau được thiết lập theo quy tắc bằng tổng hai phần tử đứng trước nó.

Công thức truy hồi của dãy Fibonaci

Để tìm dãy Fibonaci ta có thể dùng thuật toán đệ quy hoặc quy hoạch động, tất nhiên là độ phức tạp của thuật toán sẽ khác.

Đoạn code mẫu

Dùng đệ quy truy hồi

Ví dụ

Function fibo (n : byte) : longint;
  Begin
    if(n = 0) then exit(0)
    else if(n = 1) then exit(1)
    else exit(fibo(n-1) + fibo(n-2));
  End;

Mã nguồn đầy đủ »

Dùng quy hoạch động

Ví dụ

Function fibo (n : byte) : longint;
  var i : byte;
  Begin
    if(n = 0) then exit(0)
    else if(n = 1) then exit(1)
    else
     Begin
       F[0] := 0;
       F[1] := 1;
       for i := 2 to N do
           f[i] := F[i-1] + F[i-2];
     End;
     exit(F[n]);
  End;

Mã nguồn đầy đủ »

Lời kết

Trong ví dụ, Tin Học Sóc Trăng chỉ hướng dẫn ví dụ nên sử dụng kiểu dữ liệu nhỏ, bạn cần tính toán và dùng dữ liệu phù hợp với bài toán của bạn.