Một thuật toán đơn giản

Số Fibonacci

Các số Fibonacci rất hữu ích cho việc giới thiệu các thuật toán, vì vậy trước khi chúng ta tiếp tục, đây là phần giới thiệu ngắn gọn về các số Fibonacci.

Các số Fibonacci được đặt theo tên của nhà toán học người Ý thế kỷ 13 tên là Fibonacci.

Hai số Fibonacci đầu tiên là 0 và 1, số Fibonacci tiếp theo luôn là tổng của hai số trước đó nên ta được 0, 1, 1, 2, 3, 5, 8, 13, 21,...

Hướng dẫn này sẽ sử dụng vòng lặp và đệ quy rất nhiều. Vì vậy, trước khi tiếp tục, chúng ta hãy triển khai ba phiên bản khác nhau của thuật toán để tạo số Fibonacci, để thấy sự khác biệt giữa lập trình bằng vòng lặp và lập trình bằng đệ quy một cách đơn giản.

Thuật toán số Fibonacci

Để tạo số Fibonacci, tất cả những gì chúng ta cần làm là cộng hai số Fibonacci trước đó.

Các số Fibonacci là một cách hay để thể hiện thuật toán là gì. Chúng ta biết nguyên tắc tìm số tiếp theo nên có thể viết thuật toán tạo ra càng nhiều số Fibonacci càng tốt.

Dưới đây là thuật toán tạo 20 số Fibonacci đầu tiên.

Vòng lặp vs đệ quy

Để thể hiện sự khác biệt giữa vòng lặp và đệ quy, chúng ta sẽ triển khai các giải pháp tìm số Fibonacci theo ba cách khác nhau:

1. Việc triển khai thuật toán Fibonacci ở trên bằng vòng lặp for .
2. Việc triển khai thuật toán Fibonacci ở trên bằng cách sử dụng đệ quy.
3. Tìm số Fibonacci thứ \(n\) bằng cách sử dụng đệ quy.

1. Triển khai bằng vòng lặp For

Bạn có thể liệt kê những gì mã phải chứa hoặc phải làm trước khi lập trình:

• Hai biến để giữ hai số Fibonacci trước đó
• Một vòng lặp for chạy 18 lần
• Tạo số Fibonacci mới bằng cách cộng hai số trước đó
• In số Fibonacci mới
• Cập nhật các biến chứa hai số Fibonacci trước đó

Sử dụng danh sách trên, việc viết chương trình sẽ dễ dàng hơn:

 prev2 = 0
prev1 = 1

print(prev2)
print(prev1)
for fibo in range(18):
    newFibo = prev1 + prev2
    print(newFibo)
    prev2 = prev1
    prev1 = newFibo

2. Triển khai bằng đệ quy

Đệ quy là khi một hàm gọi chính nó.

Để triển khai thuật toán Fibonacci, chúng ta cần hầu hết những thứ tương tự như trong ví dụ về mã ở trên, nhưng chúng ta cần thay thế vòng lặp for bằng đệ quy.

Để thay thế vòng lặp for bằng đệ quy, chúng ta cần gói phần lớn mã trong một hàm và chúng ta cần hàm gọi chính nó để tạo một số Fibonacci mới miễn là số Fibonacci được tạo ra thấp hơn hoặc bằng, 19.

Mã của chúng tôi trông như thế này:

 print(0)
print(1)
count = 2

def fibonacci(prev1, prev2):
    global count
    if count <= 19:
        newFibo = prev1 + prev2
        print(newFibo)
        prev2 = prev1
        prev1 = newFibo
        count += 1
        fibonacci(prev1, prev2)
    else:
        return

fibonacci(1,0)

3. Tìm số Fibonacci thứ \(n\)bằng đệ quy

Để tìm số Fibonacci thứ \(n\) chúng ta có thể viết mã dựa trên công thức toán học cho số Fibonacci \(n\):

\[F(n) = F(n-1) + F(n-2) \]

Điều này chỉ có nghĩa là ví dụ số Fibonacci thứ 10 là tổng của số Fibonacci thứ 9 và thứ 8.

Khi sử dụng khái niệm này với đệ quy, chúng ta có thể để hàm gọi chính nó miễn là \(n\) nhỏ hơn hoặc bằng 1. Nếu \(n \le 1\) điều đó có nghĩa là quá trình thực thi mã đã đạt đến một của hai số Fibonacci đầu tiên là 1 hoặc 0.

Mã trông như thế này:

 def F(n):
    if n <= 1:
        return n
    else:
        return F(n - 1) + F(n - 2)

print(F(19))

Lưu ý rằng phương thức đệ quy này tự gọi chính nó hai lần, không chỉ một. Điều này tạo ra sự khác biệt lớn về cách chương trình thực sự chạy trên máy tính của chúng tôi. Số lượng phép tính sẽ bùng nổ khi chúng ta tăng số lượng dãy số Fibonacci mà chúng ta mong muốn. Nói chính xác hơn, số lượng lệnh gọi hàm sẽ tăng gấp đôi mỗi khi chúng ta tăng số Fibonacci mà chúng ta muốn lên một.

Chỉ cần nhìn vào số lượng lệnh gọi hàm \(F(5)\):

Để hiểu rõ hơn về mã, đây là cách hàm đệ quy gọi các giá trị trả về để cuối cùng \(F(5)\) trả về giá trị đúng:

Có hai điều quan trọng cần lưu ý ở đây: Số lượng lệnh gọi hàm và số lần hàm được gọi với cùng các đối số.

Vì vậy, mặc dù mã rất hấp dẫn và cho thấy cách thức hoạt động của đệ quy, việc thực thi mã thực tế quá chậm và không hiệu quả để sử dụng để tạo các số Fibonacci lớn.

Bản tóm tắt

Trước khi tiếp tục, chúng ta hãy nhìn vào những gì chúng ta đã thấy cho đến nay:

• Một thuật toán có thể được thực hiện theo nhiều cách khác nhau và bằng các ngôn ngữ lập trình khác nhau.
• Đệ quy và vòng lặp là hai kỹ thuật lập trình khác nhau có thể được sử dụng để thực hiện các thuật toán.

Đã đến lúc chuyển sang cấu trúc dữ liệu đầu tiên mà chúng ta sẽ xem xét, mảng.

Nhấp vào nút Next để tiếp tục.

in(0)
in(1)
đếm = 2

def fibonacci(prev1, prev2):
    số lượng toàn cầu
    nếu đếm <= 19:
        newFibo = prev1 + prev2
        in(newFibo)
        trước2 = trước1
        trước1 = newFibo
        đếm += 1
        (trước1, trước2)
    khác:
        trở lại

fibonacci(1,0)