[Lập trình C] Trăm trâu trăm bó cỏ

Bài tập số 40 khá thú vị trích trong quyển "250 bài kỹ thuật lập trình C" của tác giả Dương Thiên Tứ. Đề bài như sau:

Tìm các bộ (trâu đứng, trâu nằm, trâu già) thỏa mãn bài toán cổ:

Trăm trâu ăn trăm bó cỏ
Trâu đứng ăn năm
Trâu nằm ăn ba
Lụ khụ trâu già
Ba con một bó

Thử tìm cách giảm số vòng lặp khi tính toán xuống.

Kết quả:

(4, 18, 78)
(8, 11, 81)
(12, 4, 84)

Lời bàn

Bài tập này nghe qua có vẻ khá dễ nếu chỉ cần xuất được đáp án giống như trên. Nhưng cái khó nằm ở câu chốt của đề: "Thử tìm cách giảm số vòng lặp khi tính toán xuống".

Người mới học lập trình nhìn qua cũng biết cách giải đơn giản nhất là dùng 3 vòng lặp lồng nhau và một câu lệnh if để check điều kiện của 2 phương trình bậc nhất 3 ẩn (với x là số trâu đứng, y là số trâu nằm, và z là số trâu già):

Đấy gọi là xét toàn bộ nghiệm có thể của hệ phương trình.

#include <stdio.h>

int main()
{
    int x, y, z;
    for (x = 1; x < 100; x++)
        for (y = 1; y < 100; y++)
            for (z = 1; z < 100; z++) {
                if ((x + y + z == 100) && (15*x + 9*y + z == 300))
                    printf("(%d %d %d)\n", x, y, z);
            }

    return 0;
}

Tuy nhiên, dễ nhận thấy cách giải này sẽ khiến cho vòng lặp phải chạy ít nhất 100^3 = 1,000,000 lần, chưa kể 2 phép tính của câu lệnh if.

Với dạng bài tập này, chúng ta nên tính tay trước để xem có thể tối ưu như thế nào. Gọi số trâu đứng là x, số trâu nằm là y, và số trâu già là z. Dựa theo đề bài ta có:

(1) x + y + z = 100 (con)
(2) 5x + 3y + z/3 = 100 (bó cỏ) <=> 15x + 9y + z = 300
(2) - (1) = 14x + 8y = 200 <=> (3) 7x + 4y = 100
=> y = (100 - 7x) / 4 = 25 - 1.75x
(3) - (1) = 6x + 3y - z = 0 <=> z = 6x + 3y

Như vậy, dựa vào x có thể tính được y, và dựa vào x và y có thể tính được z.

- Từ (2) ban đầu có thể suy ra x không thể lớn hơn 100/5 = 20 do 5x < 100. Vậy tôi cho vòng lặp bắt đầu từ x = 1 cho tới 19.
- Vì chỉ muốn nhận kết quả là các số nguyên không có phần thập phân nên tôi bỏ qua bước lặp nếu như 3*x % 4 != 0.
- Khi chạy chương trình, tôi nhận thấy nếu x > 12 thì y sẽ < 0, đó là lý do tôi bỏ qua bước lặp bằng câu lệnh continue nếu như y < 0.

Cuối cùng dây là cài đặt bằng C của tôi, sử dụng 1 vòng lặp cho x, từ đó tính ra y và z cùng với 2 câu lệnh if:

#include <stdio.h>

int main()
{
    int x, y;
    for (x = 1; x < 20; x++) {
        if (3*x % 4) continue;
        if ((y = 25 - 1.75*x) < 0) continue;
        printf("(%d, %d, %d)\n", x, y, 6*x + 3*y);
    }
    return 0;
}

Vậy từ 100^3 bước lặp ban đầu, tôi đã giảm xuống chỉ còn 19 bước lặp.

Còn đây là cách giải trong sách của tác giả, ông sử dụng 2 vòng lặp cho x và y, từ đó tính ra z.

#include <stdio.h>

int main() {
  unsigned x, y, z;
  for ( x = 1; x < 100 / 5; ++x )
    for ( y = 1; y < 100 / 3; ++y ) {
      z = 100 - ( x + y );
      if ( 300 == 15 * x + 9 * y + z )
        printf( "( %2u, %2u, %2u )\n", x, y, z );
    }
  return 0;
}

Còn đây là phần giải thích của ông: