• Thứ Sáu, 30/01/2004 17:10 (GMT+7)

    Thuật toán: Giải bài toán poisson

    Mô tả bài toán: Có một bình đựng đầy 8 lít rượu (N) và hai bình không, một bình có dung tích là 3 lít (N1) và một bình có dung tích là 5 lít (N2) (N1+N2=N). Hãy chỉ ra cách đong chỉ sử dụng ba bình trên để lấy ra được một bình chứa đúng 4 lít (N/2).
    Một thuật toán dễ nhớ là dùng toạ độ xiên và "bàn bi-a hình bình hành" có góc 60 độ, đường đi của quả bi-a sau khi "đụng cạnh dội lại theo quy luật phản chiếu qua gương phẳng" sẽ cho lời giải của bài toán.

    Ở hình trên, cạnh dài 5 đơn vị tượng trưng cho bình chứa 5 lít, cạnh còn lại tượng trưng cho bình chứa 3 lít. Cách đong thứ nhất là quả bi-a bắt đầu đi từ 0 - 5 theo chiều mũi tên. Toạ độ các đầu mũi tên (điểm đụng cạnh bàn) là thể tích của mỗi bình khi đong. Cách này cần 6 lần đong là bình lớn nhất sẽ chứa được 4 lít (hình 1).

    Còn một cách đong nữa bắt đầu từ cạnh ngắn 0-3 nhưng thường cần nhiều lần đong hơn cách trên.
    Bài toán được mở rộng hơn khi bình lớn không nhất thiết có dung tích bằng tổng dung tích của hai bình không. Nếu bình lớn có dung tích lớn hơn tổng dung tích của hai bình nhỏ thì không thành vấn đề, nhưng nếu nhỏ hơn và không nhỏ hơn một bình nào trong hai bình nhỏ này, chẳng hạn 6 lít, thì sao? Ta chỉ cần "cắt" một góc nhọn khác gốc 0 của bàn bi-a sao cho tổng toạ độ của nó trên cạnh cắt này bằng đúng dung tích của bình rượu lớn nhất (là 6 trong trường hợp này - hình 2). Bài toán cũng được mở rộng với dung tích cần lấy không nhất thiết chia hai.

    Tuy nhiên trong trường hợp bài toán được mở rộng, thuật toán trên không cho số lần đong ít nhất. Trong hình 2, đường mũi tên đứt quãng không theo quy luật "góc tới bằng góc phản chiếu" khi đụng cạnh bị cắt lại có số lần đong ít hơn; nếu lần đầu tiên đong qua bình 3 lít thì ta có ngay kết quả.

    Trần Việt Hùng - Sóc Trăng
    VietHungTran@pmail.vnn.vn

    ID: A0401_94