Bài toán trăm trâu trăm cỏ là một bài toán dân gian cổ, có lẽ trong chúng ta ít nhất cũng có từng 1 lần nghe qua rồi, nhưng trong bài viết này chúng ta sẽ cùng đi giải bài toán với ngôn ngữ lập trình C/C++.
Bài toán trăm trâu trăm cỏ c++
Cụ thể bài toán phát biểu
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ó => Hãy đi tìm số lượng trâu đứng, trâu nằm, trâu già trong câu thơ trên.
Ta gọi, x là số trâu đứng, y là số trâu nằm, z là số trâu già.
Tất cả có 100 trâu, như vậy tức là x + y + z = 100(trâu)
Và 100 con trâu chỉ ăn 100 bó cỏ, mà trâu đứng thì 1 con ăn 5 bó, trâu nằm ăn 3 bó, trâu già thì 3 con ăn được 1 bó. Như vậy tức là x*5 + y*3 + z/3 = 100 (bó cỏ).
Để tránh trường hợp sử dụng kiểu số thực(x/3 = 0.3333333) trong tính toán có thể dẫn đến kết quá sai ta quy đồng phương trình thứ 2 và phương trình trở thành: x*15 + y*9 + z = 100 .
Ta sẽ có hệ phương trình:
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 2 phương trình.
Cụ thể code C++ như sau:
#include <iostream>
using namespace std;
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) && (x*15 + y*9 + z) == 300){
cout<<"\nSo trau dung: "<<x;
cout<<"\nSo trau nam: "<<y;
cout<<"\nSo trau gia: "<<z<<"\n";
}
}
}
}
}
Và nếu C ta sẽ thay một số câu lệnh thà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) && (x*15 + y*9 + z) == 300){
printf("So trau dung: %d",x);
printf("\nSo trau nam: %d",y);
printf("\nSo trau gia: %d\n\n",z);
}
}
}
}
}
Và đây là kết quả của chương trình, ta sẽ tìm được 3 bộ số thỏa mãn.
Bài toán này nghe qua có vẻ khá dễ nếu chỉ cần xuất được đáp án giống như trên. Tuy nhiên, cách này chỉ nên áp dụng với những người mới làm quen lập trình. Cách này chạy quá tiêu tốn thời gian, bạn biết đây là 3 vòng lặp lồng nhau tức là sẽ có 100*100*100 = 1.000.000 lần. Tất nhiên với bài toán này thì số cũng nhỏ nên chương trình chỉ chạy mất có 0.07s giây thôi, nhưng hãy thử tưởng tượng nếu số đấy không phải 100 mà là 1000, 10.000 hay 100.000 mũ 3 lên con số sẽ lớn như thế nào.
- Kiếm tiền Accesstrade, kiếm tiền tại nhà với Accesstrade.vn – Tiếp thị liên kết
- MegaURL – Rút gọn link kiếm tiền có giá cao tại Việt Nam
- Top 4 App kiếm tiền online trên điện thoại tốt nhất 2022
Vậy chúng ta hãy cùng rút ngắn bước lặp lại.
Nếu chúng ta để ý đề bài một chút sẽ thấy, số bó cỏ chỉ là 100 bó.
Mà 1 con trâu đứng thi ăn tận 5 bó, như vậy tối đa số trâu đứng là 100/5 = 20(con).
Trâu nằm là 100/3 = 33(con)(bao nhiêu con trâu thì không thể là 0.5 hay 0.3 con được nên ta làm tròn là 33).
Và tất cả cũng chỉ có 100 con trâu, như vậy khi đã có số trâu đứng + số trâu nằm thì số trâu già sẽ bằng 100 – tổng trâu đứng + trâu nằm.
Và tất nhiên là mỗi loại trâu sẽ cũng phải có ít nhất 1 con nên vòng lặp ta sẽ chạy từ 1 cho đến MAX(loại trâu) – 1.
Ta code như sau:
#include <stdio.h>
int main()
{
int x , y, z;
for(x = 1; x<20; x++){
for(y = 1; y<33; y++){
z = 100 - (x+y);
if(((x + y + z) == 100) && (x*15 + y*9 + z) == 300){
printf("So trau dung: %d",x);
printf("\nSo trau nam: %d",y);
printf("\nSo trau gia: %d\n\n",z);
}
}
}
}
Vậy từ 100^3 bước lặp ban đầu, ta đã giảm còn 32*19 = 608 bước lặp. Kết quả chương trình cũng sẽ như trên nhưng với thời gian thực hiện nhanh hơn đáng kể.
Cảm ơn bạn đã đọc bài viết! Chúc bạn học tốt nhé!@@
[XEM THÊM NHIỀU BÀI VIẾT LẬP TRÌNH C/C++ TẠI ĐÂY]
XÊM THÊM Cách tìm UCLN và BCNN Thuật toán đếm số lượng chữ số của số nguyên dương n Thuật toán tính dãy số Fibonacci Bài toán chuẩn hóa xâu ký tự
.