Hướng Dẫn Thuật Toán Fibonacci Trong Java
Dãy Fibonacci là dãy số trong đó số tiếp theo được tính bằng cách cộng hai số trước đó.
Dãy này nổi tiếng trong toán học. Nó cũng xuất hiện trong tự nhiên. Ví dụ, hầu hết hoa có cánh hoa được sắp xếp như dãy Fibonacci.
Trong hướng dẫn này, chúng ta sẽ nói về cách tính dãy số Fibonacci bằng Java. Chúng ta sẽ đi qua hai thuật toán Fibonacci Java để giúp bạn bắt đầu.
Dãy Fibonacci Là Gì?
Bạn có thể đã học về dãy Fibonacci trong toán trung học.
Hai số đầu tiên trong dãy Fibonacci là 0 và 1. Các số tiếp theo được tính bằng cách cộng hai số liền trước. Hãy xem danh sách dài hơn của dãy:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
Dãy này có thể tiếp tục vô hạn tùy thuộc vào số lượng số bạn muốn tính.
Dãy Fibonacci có thể triển khai theo hai cách:
- Sử dụng hàm lặp (iterative)
- Sử dụng thuật toán đệ quy (recursive)
Chúng ta sẽ đi qua cả hai cách tiếp cận.
Chương Trình Fibonacci Java Lặp (Iterative)
Cách tiếp cận lặp là nơi tốt nhất để bắt đầu. Lập trình lặp là khi bạn dùng vòng lặp, như for loop, để lặp qua danh sách và thực hiện tác vụ.
Lập trình lặp cho phép tự động hóa các thủ tục lặp lại. Vì có công thức rõ ràng để tính số tiếp theo trong dãy Fibonacci, chúng ta có thể dùng cách tiếp cận lặp để triển khai thuật toán.
Hãy bắt đầu bằng khai báo lớp và phương thức cho chương trình. Chúng ta cũng định nghĩa ba biến sẽ dùng cho chương trình.
public class FibonacciSequence {
public static void main(String[] args) {
int number = 5, firstTerm = 0, secondTerm = 1;
}
}
Biến "number" theo dõi số lượng hạng tử sẽ tính. "firstTerm" và "secondTerm" lưu giá trị đầu tiên và thứ hai trong dãy, tương ứng. Điều này sẽ thay đổi để lưu hai mục trước mục vừa tính sau này trong chương trình.
Bây giờ, viết vòng lặp for tính các số Fibonacci tiếp theo:
for (int i = 0; i < number; ++i) {
System.out.println(firstTerm);
int nextNumber = firstTerm + secondTerm;
firstTerm = secondTerm;
secondTerm = nextNumber;
}
Vòng lặp đầu tiên in giá trị firstTerm. Trong lần lặp đầu, giá trị này là 0. Tiếp theo, vòng lặp tính số tiếp theo bằng cách cộng firstTerm và secondTerm.
Mã sau đó gán giá trị firstTerm thành giá trị secondTerm. secondTerm trở thành số tiếp theo.
Hãy chạy mã và xem kết quả:
0 1 1 2 3
Mã đã tính năm giá trị đầu tiên trong dãy.
Chương Trình Fibonacci Java Đệ Quy (Recursive)
Dãy Fibonacci có thể tính bằng thuật toán đệ quy. Đây là hàm tự gọi chính nó để giải quyết vấn đề. Thuật toán đệ quy có thể dùng vì có công thức nhất quán để tính số trong dãy Fibonacci.
Hãy bắt đầu bằng khởi tạo lớp:
class FibonacciSequence { }
Tiếp theo, viết hàm dùng đệ quy tính giá trị tiếp theo trong dãy:
static void getNextValue(int number, int firstTerm, int secondTerm) {
if (number > 0) {
System.out.println(firstTerm);
int nextNumber = firstTerm + secondTerm;
firstTerm = secondTerm;
secondTerm = nextNumber;
getNextValue(number - 1, firstTerm, secondTerm);
}
}
Phương pháp này cộng giá trị firstTerm và secondTerm để tính giá trị tiếp theo. Điều này xảy ra miễn là giá trị "number" lớn hơn 0. "number" theo dõi còn bao nhiêu số cần tính trong dãy.
Sau khi giá trị tiếp theo được tính, hàm getNextValue() được gọi đệ quy. Lần này, giá trị "number" giảm đi một. Điều này vì mỗi lần hàm chạy, một số mới được tính.
Hãy viết chương trình chính dùng hàm đệ quy và khai báo biến sẽ dùng:
public static void main(String args[]) {
int number = 5, firstTerm = 0, secondTerm = 1;
getNextValue(number, firstTerm, secondTerm);
}
"number" phản ánh số giá trị muốn tính. firstTerm là hạng tử đầu tiên. secondTerm là hạng tử thứ hai.
Khi gọi phương thức getNextValue, tính toán bắt đầu. Hãy chạy mã hiển thị số Fibonacci:
0 1 1 2 3
Năm giá trị đầu tiên trong dãy Fibonacci đã được tính!
Kết Luận
Dãy Fibonacci phổ biến trong toán học, tin học và tự nhiên. Số tiếp theo trong dãy được tính bằng cách cộng hai số trước đó. Dãy bắt đầu với hai số 0 và 1.
Dãy này có thể tính bằng cách tiếp cận lặp hoặc đệ quy. Bây giờ bạn đã sẵn sàng tính dãy Fibonacci trong Java.