Java - Đệ quy bài toán con thỏ của dãy số vô hạn Fibonacci.

Như trong bài Đệ Quy trước tôi đã giới thiêu, bài hôm nay sẽ hướng dẫn xử lý bài toán con thỏ của dãy số vô hạn Fibonacci để hiểu rõ hơn về đệ quy trong ngôn ngữa lập trình Java.

Bài toán con thỏ là 1 trong 2 bài toán được trích từ sách Liber Abacci do Fibonacci viết vào năm 1202. Đây là những bài toán mẫu mực dẫn đến khảo sát dãy số mà chúng ta gọi là dãy Fibonacci. Bạn có thể tìm thêm thông tin tại Wikipedia.







Đề mục bài toán như sau:

"Một đôi thỏ (gồm một thỏ đực và một thỏ cái) cứ mỗi tháng đẻ được một đôi thỏ con (cũng gồm một thỏ đực và thỏ cái); một đôi thỏ con, khi tròn 2 tháng tuổi, sau mỗi tháng đẻ ra một đôi thỏ con, và quá trình sinh nở cứ thế tiếp diễn. Hỏi n tháng bao nhiêu đôi thỏ, nếu đầu năm (tháng Giêng) có một đôi thỏ sơ sinh?"

Theo đề mục bài toán ta sẽ có một mô hình cơ sở số thỏ trong tám tháng như sau:

Những chú thỏ dễ thương đang tung tăng trên bếp nướng chẹp chẹp....

Trong hình vẽ trên, ta quy ước:

• Cặp thỏ nâu là cặp thỏ có độ tuổi 1 tháng.
• Cặp thỏ được đánh dấu (màu đỏ và màu xanh) là cặp thỏ có khả năng sinh sản.

Nhìn vào hình vẽ trên ta nhận thấy:

• Tháng Giêng và tháng Hai: Chỉ có 1 đôi thỏ.
• Tháng Ba: đôi thỏ này sẽ đẻ ra một đôi thỏ con, do đó trong tháng này có 2 đôi thỏ.
• Tháng Tư: chỉ có đôi thỏ ban đầu sinh con nên đến thời điểm này có 3 đôi thỏ.
• Tháng Năm: có hai đôi thỏ (đôi thỏ đầu và đôi thỏ được sinh ra ở tháng Ba) cùng sinh con nên ở tháng này có 2 + 3 = 5 đôi thỏ.
• Tháng Sáu: có ba đôi thỏ (2 đôi thỏ đầu và đôi thỏ được sinh ra ở tháng Tư) cùng sinh con ở thời điểm này nên đến đây có 3 + 5 = 8 đôi thỏ.
• ...

 Nói theo nghĩa đệ quy ta có thể nói như như sau:

• Một đôi thỏ.
• Một đôi thỏ sau một tháng đẻ một đôi thỏ
• Một đôi thỏ sau một tháng dẻ một đôi thỏ sau một tháng để một đôi thỏ.

Tóm lại ta sẽ có một đàn thỏ, sau môt đàn thỏ ta sẽ một trang trại thỏ, sau một trang trại thỏ ta có một tập đoàn đỏ, nói vui thôi nha không có liên quan tới bài toán.

Như trong bài đệ quy trước tôi có giới thiệu công thức tình số n của Fibonacci, và trong bài toán này ta hoàn toàn có thể áp dụng được.

Ở trong bài toán này ta có thể loại trừ trường hợp n = 0, nhưng để cho thống nhất giữa các bài viết nên tôi vẫn giữ nguyên cách tính theo công thức Fibonacci.

Sau đây là toàn bộ mã cho đề bài này:

 /**
 * @(#)Fibonacy.java
 *
 * Fibonacy application
 *
 * @author VNLIVES.NET
 * @version 1.00 2013/9/22
 */

public class Fibonacy {

    public static void main(String[] args) {
        // TODO, add your application code 
        //System.out.println("Thang 0 co " + Fibo(0) + " doi tho.");
        System.out.println("Thang 1 co " + Fibo(1) + " doi tho.");
        System.out.println("Thang 2 co " + Fibo(2) + " doi tho.");
        System.out.println("Thang 3 co " + Fibo(3) + " doi tho.");
        System.out.println("Thang 4 co " + Fibo(4) + " doi tho.");
        System.out.println("Thang 5 co " + Fibo(5) + " doi tho.");
        System.out.println("Thang 6 co " + Fibo(6) + " doi tho.");
        System.out.println("Thang 7 co " + Fibo(7) + " doi tho.");                                       
        System.out.println("Thang 8 co " + Fibo(8) + " doi tho.");
       
    }
   

    public static int Fibo(int n) {

        if(n == 0) {
            return 0;
        }
       
        if(n == 1) {
            return 1;
        }

        return (Fibo(n-1) + Fibo(n-2));

    } 

}

Kết quả sau khi thực thi sẽ là:

Thang 1 co 1 doi tho.
Thang 2 co 1 doi tho.
Thang 3 co 2 doi tho.
Thang 4 co 3 doi tho.
Thang 5 co 5 doi tho.
Thang 6 co 8 doi tho.
Thang 7 co 13 doi tho.
Thang 8 co 21 doi tho.

Đọc bài toán thì thấy mệt ghê mà khi áp dụng công thức vào thì có mấy dòng, ở đây ta mới thấy được sự lợi hại của các phương pháp tính toán.