Thứ Tư, 28 Tháng Chín 2022
Trang chủLập trìnhLập trình C/C++Bài toán trăm trâu trăm cỏ c++ - Cách giải

Bài toán trăm trâu trăm cỏ c++ – Cách giải

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:

Hệ phương trình trăm trâu trăm cỏ

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.

Kết quả bài toán trăm trâu trăm cỏ

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.

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ự
0 0 Phiếu bình chọn
Xếp hạng bài viết
BÀI VIẾT LIÊN QUAN
Đăng ký nhận thông báo
Thông báo email khi
guest
0 Bình luận
Không thể gửi email
Phản hồi nội tuyến

NÊN ĐỌC THÊM

Bạn muốn tìm kiếm gì?


0
Giáo sư! có thể ném gạch bên dưới nhé!x
()
x