Quảng cáo

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.



Không có nhận xét nào

Được tạo bởi Blogger.