Chuỗi Fibonacci trong Java

1. Khái quát chung

Trong hướng dẫn này, chúng ta sẽ xem xét chuỗi Fibonacci.

Cụ thể, chúng tôi sẽ thực hiện ba cách để tính số hạng thứ n của chuỗi Fibonacci, cách cuối cùng là giải pháp thời gian không đổi.

2. Chuỗi Fibonacci

Dãy Fibonacci là một dãy số trong đó mỗi số hạng là tổng của hai số hạng đứng trước . Hai số hạng đầu tiên là 01 .

Ví dụ: 11 số hạng đầu tiên của chuỗi là 0, 1, 1, 2, 3, 5, 8, 13, 21, 3455 .

Theo thuật ngữ toán học, dãy S n của các số Fibonacci được xác định bằng quan hệ lặp lại:

S(n) = S(n-1) + S(n-2), with S(0) = 0 and S(1) = 1

Bây giờ, chúng ta hãy xem cách tính số hạng thứ n của chuỗi Fibonacci. Ba phương pháp chúng tôi sẽ tập trung vào là đệ quy, lặp lại và sử dụng công thức của Binet.

2.1. Phương pháp đệ quy

Đối với giải pháp đầu tiên của chúng tôi, hãy đơn giản biểu thị quan hệ lặp lại trực tiếp trong Java:

public static int nthFibonacciTerm(int n) { if (n == 1 || n == 0) { return n; } return nthFibonacciTerm(n-1) + nthFibonacciTerm(n-2); }

Như chúng ta thấy, chúng ta kiểm tra xem n bằng 0 hay 1. Nếu đúng, thì chúng ta trả về giá trị đó. Trong bất kỳ trường hợp khác, chúng ta đệ quy gọi hàm để tính toán (n-1) lần thứ hạn và (n-2) thứ hạn và trả lại số tiền của họ.

Mặc dù phương pháp đệ quy thực hiện đơn giản nhưng chúng ta thấy rằng phương pháp này thực hiện rất nhiều phép tính lặp lại. Ví dụ, để tính số hạng thứ 6 , chúng ta thực hiện các cuộc gọi để tính số hạng thứ 5 và số hạng thứ 4 . Hơn nữa, lệnh gọi để tính số hạng thứ 5 thực hiện một cuộc gọi để tính số hạng thứ 4 một lần nữa. Bởi vì thực tế này, phương pháp đệ quy thực hiện rất nhiều công việc thừa.

Hóa ra, điều này làm cho độ phức tạp về thời gian của nó theo cấp số nhân; Chính xác là O (Φn) .

2.2. Phương pháp lặp lại

Trong phương pháp lặp, chúng ta có thể tránh các phép tính lặp lại được thực hiện trong phương pháp đệ quy. Thay vào đó, chúng tôi tính toán các số hạng của chuỗi và lưu trữ hai số hạng trước đó để tính toán tiếp theo.

Hãy xem cách triển khai của nó:

public static int nthFibonacciTerm(int n) { if(n == 0 || n == 1) { return n; } int n0 = 0, n1 = 1; int tempNthTerm; for (int i = 2; i <= n; i++) { tempNthTerm = n0 + n1; n0 = n1; n1 = tempNthTerm; } return n1; }

Trước hết, chúng ta kiểm tra xem số hạng cần tính là số hạng thứ 0 hay số hạng thứ nhất . Nếu đúng như vậy, chúng tôi trả về các giá trị ban đầu. Nếu không, chúng tôi tính số hạng thứ 2 bằng cách sử dụng n0n1 . Sau đó, chúng ta sửa đổi các giá trị của n0n1 biến để lưu trữ số hạng thứ nhấtsố hạng thứ hai tương ứng. Chúng tôi tiếp tục lặp lại cho đến khi chúng tôi tính được số hạng cần thiết.

Phương pháp lặp lại tránh công việc lặp lại bằng cách lưu trữ hai số hạng Fibonacci cuối cùng trong các biến. Độ phức tạp thời gian và độ phức tạp không gian của phương pháp lặp lần lượt là O (n)O (1) .

2.3. Công thức của Binet

Chúng tôi mới chỉ xác định số Fibonacci thứ n trong số hai số trước nó. Bây giờ, chúng ta sẽ xem xét công thức của Binet để tính số Fibonacci thứ n trong thời gian không đổi.

Các thuật ngữ Fibonacci duy trì một tỷ lệ được gọi là tỷ lệ vàng ký hiệu là Φ , ký tự Hy Lạp phát âm là 'phi' .

Trước tiên, hãy xem cách tính tỷ lệ vàng :

Φ = ( 1 + √5 )/2 = 1.6180339887...

Bây giờ, hãy xem công thức của Binet :

Sn = Φⁿ–(– Φ⁻ⁿ)/√5

Trên thực tế, điều này có nghĩa là chúng ta sẽ có thể nhận được số Fibonacci thứ n chỉ bằng một số phép tính.

Hãy diễn đạt điều này bằng Java:

public static int nthFibonacciTerm(int n) { double squareRootOf5 = Math.sqrt(5); double phi = (1 + squareRootOf5)/2; int nthTerm = (int) ((Math.pow(phi, n) - Math.pow(-phi, -n))/squareRootOf5); return nthTerm; }

Đầu tiên chúng ta tính toán squareRootof5phi và lưu trữ chúng trong các biến. Sau đó, chúng tôi áp dụng công thức của Binet để có được điều khoản cần thiết.

Vì chúng ta đang giải quyết các số vô tỉ ở đây, chúng ta sẽ chỉ nhận được một giá trị gần đúng. Do đó, chúng ta sẽ cần giữ nhiều chữ số thập phân hơn cho các số Fibonacci cao hơn để giải thích cho lỗi làm tròn số.

Chúng ta thấy rằng phương pháp trên tính toán số hạng Fibonacci thứ n trong thời gian không đổi, hoặc O (1).

3. Kết luận

Trong bài viết ngắn gọn này, chúng ta đã xem xét chuỗi Fibonacci. Chúng tôi đã xem xét một giải pháp đệ quy và một giải pháp lặp lại. Sau đó, chúng tôi áp dụng công thức của Binet để tạo ra một giải pháp thời gian không đổi.

Như mọi khi, mã nguồn đầy đủ của các ví dụ hoạt động có sẵn trên GitHub.