HomeLập trìnhPythonChương trình Python...

Chương trình Python để in dãy Fibonacci


Các câu hỏi về Chuỗi Fibonacci là một số câu hỏi thường gặp nhất trong các cuộc phỏng vấn Python.

Trong bài viết này, tôi sẽ giải thích cách tiếp cận từng bước về cách in dãy Fibonacci bằng hai kỹ thuật khác nhau, phép lặp và phép đệ quy.

Trước khi bắt đầu, trước tiên chúng ta hãy hiểu một số thuật ngữ cơ bản.

Dãy Fibonacci là gì?

Dãy Fibonacci là một dãy số trong đó một số đã cho là kết quả của việc cộng 2 số đứng trước nó. Và thêm 2 số trước đó một số lần tạo thành một chuỗi mà chúng ta gọi là Chuỗi Fibonacci.

Dãy Fibonacci bắt đầu bằng hai số, đó là 0 và 1. Sau đó, mọi số tiếp theo được tạo thành từ việc cộng hai số trước đó lại với nhau.

Ví dụ: lấy 0 và 1. Đây là hai số đầu tiên trong dãy. Nếu bạn cộng chúng lại với nhau, bạn sẽ nhận được 1. Vì vậy, chuỗi bắt đầu 0, 1, 1,…

Sau đó, để tìm số tiếp theo, bạn cộng số cuối cùng bạn có và số trước nó. Vậy 1+1 = 2. Vậy dãy cho đến nay là 0, 1, 1, 2, … Có nghĩa không?

Chúng ta có thể biểu diễn điều này một cách toán học hơn như 0, 1, (1) – [0 + 1]. Tương tự, số Fibonacci tiếp theo là – 0, 1, 1, (2) – [1 + 1]. Và như thế. Đây là sơ đồ hiển thị 10 số Fibonacci đầu tiên:

chuỗi Fibonacci

Đây là một ví dụ về chuỗi Fibonacci – 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. Trong chuỗi liên tục này, mỗi số riêng lẻ là một số Fibonacci.

Về mặt toán học, Dãy Fibonacci được biểu diễn bằng công thức sau:

F(n) = F(n-1) + F(n-2)ở đâu n > 1.

Chúng ta có thể sử dụng chuỗi này để tìm bất kỳ số Fibonacci thứ n nào.

Chuỗi hấp dẫn này được liên kết rộng rãi với nhà toán học Leonardo Pisano, còn được gọi là Fibonacci. Anh ấy đến từ Cộng hòa Pisa, đó là lý do tại sao anh ấy còn được gọi là Leonardo of Pisa.

Leonardo được biết đến như một trong những nhà toán học tài năng nhất thời trung cổ.

Cách in dãy Fibonacci bằng Python

Bạn có thể viết chương trình máy tính để in dãy Fibonacci theo 2 cách khác nhau:

  • Lặp đi lặp lại và
  • đệ quy.

Lặp lại có nghĩa là lặp lại công việc cho đến khi thỏa mãn điều kiện quy định. Mặt khác, đệ quy có nghĩa là thực hiện một nhiệm vụ duy nhất và chuyển sang nhiệm vụ tiếp theo để thực hiện nhiệm vụ còn lại.

Đây là thuật toán lặp để in dãy Fibonacci:

  1. Tạo 2 biến và khởi tạo chúng với 0 và 1 (first = 0, second = 1)
  2. Tạo một biến khác để theo dõi độ dài của dãy Fibonacci sẽ được in (độ dài)
  3. Vòng lặp (độ dài nhỏ hơn độ dài sê-ri)
  4. In thứ nhất + thứ hai
  5. Cập nhật đầu tiênthứ hai biến (đầu tiên sẽ trỏ đến biến thứ hai và biến thứ hai sẽ trỏ đến thứ nhất + thứ hai)
  6. Giảm biến chiều dài và lặp lại từ bước 3
  7. Khi vòng lặp kết thúc, kết thúc chương trình
Đọc thêm  Cách đọc từng dòng tệp trong Python

Cách hoạt động của thuật toán lặp:

Hãy xem xét rằng chúng ta cần in một dãy Fibonacci có độ dài 7. Khi đó quy trình của thuật toán sẽ như sau:

lặp đi lặp lại Các bước giải thích đầu ra
Ban đầu Đầu tiên = 0, Thứ hai = 1 [0, 1]
1 In (thứ nhất + thứ hai) = [0+1] Bây giờ biến first sẽ trỏ đến biến second. Và thứ hai sẽ trỏ đến số Fibonacci tiếp theo mà chúng ta đã tính toán ở trên. [0, 1, 1]
2 In (thứ nhất + thứ hai) = [1+1] Bây giờ biến đầu tiên sẽ trỏ đến biến thứ hai. Và thứ hai sẽ trỏ đến số Fibonacci tiếp theo mà chúng ta đã tính toán ở trên. [0, 1, 1, 2]
3 In (thứ nhất + thứ hai) = [1+2] Bây giờ biến đầu tiên sẽ trỏ đến biến thứ hai. Và thứ hai sẽ trỏ đến số Fibonacci tiếp theo mà chúng ta đã tính toán ở trên. [0, 1, 1, 2, 3]
4 In (thứ nhất + thứ hai) = [2+3] Bây giờ biến đầu tiên sẽ trỏ đến biến thứ hai. Và thứ hai sẽ trỏ đến số Fibonacci tiếp theo mà chúng ta đã tính toán ở trên. [0, 1, 1, 2, 3, 5]
5 In (thứ nhất + thứ hai) = [3+5] Bây giờ biến đầu tiên sẽ trỏ đến biến thứ hai. Và thứ hai sẽ trỏ đến số Fibonacci tiếp theo mà chúng ta đã tính toán ở trên. [0, 1, 1, 2, 3, 5, 8]

Vì vậy, dãy Fibonacci cuối cùng cho độ dài 7 sẽ là [0, 1, 1, 2, 3, 5, 8].

Mã Python lặp để in Chuỗi Fibonacci:

def PrintFibonacci(length):
    #Initial variable for the base case. 
    first = 0
    second = 1

    #Printing the initial Fibonacci number.
    print(first, second, end=" ")

    #decreasing the length by two because the first 2 Fibonacci numbers 
    #already printed.
    length -= 2
    
    #Loop until the length becomes 0.
    while length > 0:

        #Printing the next Fibonacci number.
        print(first + second, end=" ")

        #Updating the first and second variables for finding the next number. 
        temp = second
        second = first + second
        first = temp

        #Decreasing the length that states the Fibonacci numbers to be 
        #printed more.
        length -= 1

if __name__ == "__main__":
    print("Fibonacci Series - ")
    PrintFibonacci(7)
    pass

Đầu ra cho độ dài 7:

Fibonacci Series - 
1 1 2 3 5 8

Giải thích về Bộ luật:

Trong đoạn mã trên, đầu tiên chúng ta đã định nghĩa một hàm sẽ in ra chuỗi Fibonacci. Nó chấp nhận một tham số cho độ dài và hàm cần in chuỗi Fibonacci.

Tiếp theo, chúng ta đã tạo 2 biến chứa 2 giá trị Fibonacci ban đầu, đó là 0 và 1.

Sau đó, chúng tôi đã in 2 giá trị đầu tiên [0, 1] và giảm chiều dài đi 2, vì 2 giá trị đã được in.

Chúng tôi sẽ chạy một vòng lặp trong khoảng thời gian còn lại và mỗi lần in giá trị Fibonacci tiếp theo bằng cách thêm 2 thuật ngữ trước đó được lưu trữ trong biến thứ nhất và biến thứ hai (mà chúng tôi đã tạo ban đầu để theo dõi 2 giá trị trước đó).

Đọc thêm  Cách xóa khóa khỏi từ điển Python – Xóa khóa khỏi Dict

Cập nhật giá trị thứ nhất và thứ hai sẽ trỏ đến 2 giá trị trước đó [first = second, and second = previous first + second].

Vòng lặp sẽ chạy cho đến khi độ dài trở thành 0, điều này cho biết độ dài cần thiết của dãy Fibonacci được in ra.

Sau đó, chúng tôi gọi hàm được xác định để in Fibonacci từ hàm chính bằng cách chuyển đối số độ dài yêu cầu được in. Và bạn có nó rồi đấy!

Có một cách tiếp cận khác để in dãy Fibonacci bằng cách sử dụng sự trợ giúp của đệ quy. Vì vậy, hãy hiểu cách tiếp cận đó.

Thuật toán đệ quy để in dãy Fibonacci:

  • Chấp nhận giá trị của số Fibonacci thứ nhất và thứ hai trước đó làm độ dài được in.
  • Kiểm tra nếu độ dài bằng 0 thì kết thúc lệnh gọi hàm.
  • In giá trị Fibonacci bằng cách thêm 2 giá trị nhận được trước đó vào tham số của hàm (thứ nhất và thứ hai).
  • Gọi đệ quy hàm để biết giá trị cập nhật của giá trị thứ nhất và thứ hai, cũng như giá trị độ dài đã giảm.

Đối với lệnh gọi hàm đệ quy này, chúng ta cần chuyển giá trị ban đầu của Fibonacci, tức là (0 và 1), vào biến thứ nhất và biến thứ hai.

Để giúp bạn hiểu rõ hơn về thuật toán này, chúng ta hãy xem Python triển khai các thuật toán. Sau đó, chúng ta sẽ xem xét một ví dụ để bạn có thể thấy thuật toán đệ quy này hoạt động như thế nào.

Mã Python đệ quy để in dãy Fibonacci:

def PrintFibonacci(first, second, length):

    #Stop the printing and recursive calling if length reaches 
    #the end.
    if(length == 0):
        return

    #Printng the next Fibonacci number.
    print(first + second, end=" ")

    #Recursively calling the function by updating the value and 
    #decrementing the length.
    PrintFibonacci(second, first+second, length-1)

if __name__ == "__main__":
    #Print initial 2 values.
    print(0,1,end=" ")

    #Calling the Function to print the remaining length 
    #fibonacci series
    PrintFibonacci(0,1,7-2)

Đầu ra:

For Length 7 
1 1 2 3 5 8

For Length 10
1 1 2 3 5 8 13 21 34

Giải thích về mã:

Đầu tiên, chúng ta tạo một hàm và thực hiện đệ quy trên nó. Trong hàm đó, ta đã nhận giá trị của 2 số Fibonacci trước đó để tính ra số Fibonacci hiện tại. Và chúng tôi có một chiều dài theo dõi trường hợp cơ sở.

Đối với trường hợp cơ sở của đệ quy, chúng tôi đang kiểm tra xem độ dài có đạt tới 0 hay không. Nếu đúng như vậy, thì chúng tôi sẽ chấm dứt lệnh gọi đệ quy.

Trong các trường hợp khác, chúng tôi đang in số Fibonacci bằng cách thêm 2 số Fibonacci trước đó.

Và sau đó chúng ta gọi đệ quy hàm để in giá trị Fibonacci tiếp theo bằng cách cập nhật 2 giá trị trước đó và giảm độ dài.

Bây giờ, hãy hình dung các lời gọi đệ quy của hàm này với sự trợ giúp của cây đệ quy. Độ dài chúng tôi muốn in là 7.

Đọc thêm  Python String.replace() – Cách thay thế ký tự trong chuỗi
chiều dài-được-in-là-7

Trước khi lệnh gọi đệ quy được thực hiện, hàm main in 2 giá trị ban đầu là 0 và 1. Sau đó, nó chuyển các giá trị này cho hàm đệ quy.

main-function-prints-the-initial-2-values.-0-and-1

Hàm đệ quy đang in giá trị (0 + 1) và gọi đệ quy với giá trị được cập nhật tiếp theo.

Đệ quy-hàm-là-in-giá-trị--0---1-

Sau đó, hàm đệ quy đang in giá trị (1+1) và gọi đệ quy với giá trị được cập nhật tiếp theo.

printfibonacci-1-2-3-

Bây giờ hàm đệ quy đang in giá trị (1 + 2) và gọi đệ quy với giá trị được cập nhật tiếp theo.

printfibonacci-2-3-2-

Và sau đó hàm đệ quy đang in giá trị (2 + 3) và gọi đệ quy với giá trị được cập nhật tiếp theo.

printfibonacci-3-5-1-

Bây giờ hàm đệ quy đang in giá trị (3 + 5) và gọi đệ quy với giá trị được cập nhật tiếp theo.

printfibonacci-5-8-0-

Cuối cùng, cuộc gọi cuối cùng được thực hiện. Và độ dài là 0, vì vậy nó sẽ kết thúc cuộc gọi đệ quy một lần nữa và chuỗi được in trên bàn điều khiển.

Phân tích độ phức tạp thời gian

Đối với phương pháp lặp

Trong thuật toán Lặp lại, chúng ta lặp cho đến khi độ dài bằng 0. Trong vòng lặp, chúng ta đang thực hiện thao tác in giá trị và cập nhật các biến theo thời gian không đổi.

Nếu chúng ta coi độ dài đó là n, thì độ phức tạp thời gian sẽ là Trên).

Đối với phương pháp đệ quy

Trong cách tiếp cận đệ quy, chúng tôi đang gọi các hàm đệ quy lên đến số lần có độ dài nhất định. Chúng tôi cũng đang thực hiện một thao tác in liên tục đơn giản.

Vì vậy, trong điều này cũng vậy, nếu chúng ta coi độ dài là n số, thì độ phức tạp thời gian sẽ là Trên).

Phân tích độ phức tạp không gian

Đối với phương pháp lặp

Trong cách tiếp cận lặp lại, chúng tôi đã không sử dụng thêm bộ nhớ để chấp nhận hai biến theo dõi hai số Fibonacci trước đó và hằng số cho bất kỳ số nào trong độ dài của chuỗi. Vì vậy, độ phức tạp không gian sẽ là hằng số O(1).

Đối với phương pháp đệ quy

Trong cách tiếp cận đệ quy, chúng tôi đang gọi các hàm của độ dài số lần. Chúng tôi biết rằng đệ quy bên trong sử dụng ngăn xếp cuộc gọi.

Vì vậy, nếu chúng ta coi đó là bộ nhớ do chương trình sử dụng, thì lệnh gọi đệ quy được thực hiện theo số lần. Khi đó độ phức tạp không gian sẽ là O(n).

Phần kết luận

Dãy Fibonacci là dãy số trong đó mỗi số là phép cộng của hai số liền trước nó.

Dãy số Fibonacci không chỉ được tìm thấy trong toán học mà còn ở khắp thế giới tự nhiên – như trong cánh hoa, lá hoặc gai của cây xương rồng, v.v.

Đây cũng là một câu hỏi phỏng vấn thường gặp – vì vậy thật tốt khi biết nó hoạt động như thế nào.

Tôi đã lấy cảm hứng từ bài đăng này từ InterviewBit.



Zik.vn – Biên dịch & Biên soạn Lại

spot_img

Create a website from scratch

Just drag and drop elements in a page to get started with Newspaper Theme.

Buy Now ⟶

Bài viết liên quang

DMCA.com Protection Status