Bài toán này hay một phần là nhờ ngôn từ đầy chất thơ, một phần là nhờ những phương pháp giải rất sáng tạo (trong đó có phương pháp giả thiết tạm). Trong các phương pháp giải đó có một phương pháp mà tôi đặc biệt lưu ý. Đó là phương pháp sau:

Tất cả có 36 con vật. Chúng không thể đều là gà vì như vậy sẽ chỉ có 72 chân. Cũng không thể nào là chó cả vì như vậy sẽ có cả thảy 144 chân (Số chân của chúng là 100 chân). Ta hãy khảo sát :

Nếu lấy số gà ít đi thì buộc ta phải lấy số chó nhiều lên, như vậy số chân sẽ tăng lên. Ngược lại, nếu lấy số gà nhiều lên thì số chó ít đi và số chân sẽ giảm xuống. Do đo, ta có các khảo sát tiếp theo :

Đây đúng là số gà và số chó cần tìm: Số gà là 22 con, số chó là 14 con.

Như vậy nội dung của phương pháp trên đó là:

. Sắp xếp số gà theo thứ tự tăng dần (theo chiều từ dưới lên)

. Chia đôi tổng số gà, nếu tại điểm giữa đó tổng số chân gà và chân gà và chân chó lớn hơn 100 thì lấy nửa trên, và ngược lại lấy nửa dưới.

Đến đây ta nhận ra phương pháp này có mối liên hệ mật thiết với phương pháp tìm kiếm nhị phân. Vì rằng, bài toán nhị phân:

" Cho mảng n phần tử đã được sắp xếp tăng dần và một phần tử x. Tìm x có trong mảng hay không? Nếu có trong mảng thì cho kết quả là 1, ngược lại cho kết quả là 0" có thuật toán tương tự với cách làm trên:

. Số phần tử được sắp xếp theo thứ tự tăng dần (Theo giả thiết).

. Chia đôi mảng, mỗi lần so sánh phần tử giữa với x. Nếu phần tử x nhỏ hơn thì lấy nửa trái, ngược lại thì lấy nửa phải.

Cài đặt thuật toán bằng ngôn ngữ lập trình C++:

Thật tuyệt vời, phương pháp tìm số gà và số chó lại liên quan chặt chẽ đến phương pháp tìm kiếm nhị phân - một phương pháp tìm kiếm rất quan trọng trong tin học. Qua đây ta mới thấy rõ vẽ đẹp của sự tác động qua lại giữa tư duy toán học và tư duy tin học. Nhiều khi một thuật toán nào đó trong tin học lại có khởi nguồn sâu xa từ một phương pháp giải trong toán. Chính vì thế, việc nhìn ra được sự tác động giữa chúng có một tầm quan trọng rất lớn đối với những bạn yêu tin, cũng như giúp các bạn có cách nhìn sâu sắc và toàn diện hơn về một vấn đề nào đó trong tin học.

Để kết thúc bài viết, xin mời các bạn sử dụng thuật toán tìm kiếm nhị phân để giải bài toán rất thú vị và cũng đầy chất thơ sau :

Chúc các bạn thành công./.

(Nguyễn Ngọc Giang - Cử nhân Sư Phạm Toán - Lớp 04B- Khoa Ngữ

Văn Anh -Đại họcKhoa HọcXã Hội VàNhân Văn -TPHCM)

School@net