Một số thuật toán cơ bản

1) Giai thừa

Phân tích :

– Theo giả thiết, ta có : n! = (n-1)! x n. Như vậy :

  • Để tính n! ta cần phải tính (n-1)!
  • Để tính (n-1)! ta phải tính (n-2)!

– Cứ như vậy, cho tới khi gặp trường hợp 0!. Khi đó ta lập tức có được kết quả là 1, không cần phải tính thông qua một kết quả trung gian khác

2) Fibonanci

Dãy Fibonaci là dãy vô hạn các số tự nhiên. Số Fibonaci thứ n, ký hiệu F(n), được định nghĩa như sau :

  • F(n) = 1, nếu n=1 hoặc n=2
  • F(n) = F(n-1) + F(n-2), nếu n>=3

Yêu cầu : tính số fibonaci thứ n với n cho trước.

Phân tích : theo giả thiết

– Với n<3 :=”” ta=”” suy=”” ra=”” ngay=”” k=”” t=”” qu=”” f=”” n=”” 1=”” span=”” style=”font-size: 10pt;” data-mce-style=”font-size: 10pt;”>

– Với n>=3 :

  • Đế tính F(n) ta phải tính F(n-1) và F(n-2).
  • Để tính F(n-1) ta lại phải tính F(n-2) và F(n-3), và để tính F(n-2) ta phải tính F(n-3) và F(n-4).
  • Cứ như vậy cho đến khi n=1 và n=2

 

Leave a Reply

Your email address will not be published.