Viết chương trình giải bài toán cổ trăm trâu trăm cỏ 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 

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 

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 

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:

Cảm ơn bạn đã đọc bài viết của Cuộc Sống Tối Giản. Đây là một blog cá nhân, được lập ra nhằm mục đích lưu trữ và chia sẻ mọi thứ hay ho theo chủ quan của chủ sở hữu. Có lẽ vì vậy mà bạn sẽ thấy blog này hơi (rất) tạp nham. Mọi chủ đề đều có thể được tìm thấy ở đây, từ tâm sự cá nhân, kinh nghiệm sống, phim ảnh, âm nhạc, lập trình... Phần lớn các bài đăng trong blog này đều được tự viết, trừ các bài có tag "Sponsored" là được tài trợ, quảng cáo, hoặc sưu tầm. Để ủng hộ blog, bạn có thể share những bài viết hay tới bạn bè, người thân, hoặc có thể follow Kênh YouTube của chúng tôi. Nếu cần liên hệ giải đáp thắc mắc hoặc đặt quảng cáo, vui lòng gửi mail theo địa chỉ . Một lần nữa xin được cảm ơn rất nhiều!!!

Code c:

#include

void main()

{

            int traudung , traunam , traugia;

            for(traudung = 1 ; traudung <= 100 ; traudung++)

                        for(traunam = 1 ; traunam <= 100 ; traunam++)

                                    for(traugia = 1 ; traugia <= 100 ; traugia++)

                                                if((5*traudung + 3*traunam + traugia/3 == 100) && (traugia%3 == 0) && (traudung + traunam + traugia == 100))

                                                            printf ("Trau dung : %d con Trau nam : %d con Trau gia : %d con\n", traudung , traunam , traugia);

}