Bài toán Đong nước môn Trí Tuệ Nhân Tạo

tiger86love102 · 14-10-2008, 03:18 PM

Chắc nhiều bạn đã học qua hoặc đang học môn Trí Tuệ Nhân Tạo. Một bài toán điển hình của môn này là bài toán "Đong nước".

Cho hai bình rỗng X và Y, đổ qua đổ lại làm sao cho đong đc Z lít nước. VD như cho VX = 5 và VY = 7 và z = 4.

Ý tưởng:
Múc đầy bình 7
Trút hết qua bình 5 cho đến khi 5 đầy.
Đổ hết nước trong bình 5
Đổ hết nước còn lại từ bình 7 sang bình 5
Múc đầy bình 7
Trút hết qua bình 5 cho đến khi bình 5 đầy.
Phần còn lại chính là số nước cần đong.

Gọi lượng nước chứa trong bình X là x (0<=x<=VX)
Gọi lượng nước chứa trong bình Y là y (0<=y<=VY)
Điều kiện đầu của bài toán là : x = 0 và y=0
Điều kiện kết thúc của bài toán sẽ là : x = z hoặc y = z

Bài toán đc giả dựa theo ba luật chính như sau:
(L1) Nếu bình X đầy thì đổ hết nước trong bình X đi.
(L2) Nếu bình Y rỗng thì đổ đầy nước vào bình Y.
(L3) Nếu bình X không đầy và bình Y không rỗng thì hãy trút nước t? bình Y sang bình X (cho đến khi bình X đầy hoặc bình Y hết nước).
Bài toán cần có điều kiện số nước cần đong là một bội số của ước số chung lớn nhất của thể tích hai bình.
z = n x USCLN(VX, VY) (với n nguyên dương)

Áp dụng với bài toán VD trên sẽ cho in ra:
Vx = 3, Vy = 4 và z = 2
Ban đầu : x = 0, y = 0
Luật (L2) -> x = 0, y = 4
Luật (L3) -> x = 3, y = 1
Luật (L1) -> x = 0, y = 1
Luật (L3) -> x = 1, y = 0
Luật (L2) -> x = 1, y = 4
Luật (L3) -> x = 3, y = 2

Ý tưởng là như vậy

Bài giải có thể viết bằng nhiều loại ngôn ngữ khác nhau mà vẫn rất ngắn gọn mà hay.
Lập trình trên C hay Pascal mình tàm tạm, mình đã làm bằng C++ nhưng còn lỗi lung tung, chạy không như mình mong muốn.

Bạn nào rành C++ hướng dẫn mình chút ít EXP để giải bài này bằng C++ nhé.
Mình đã học qua C++ nhưng lâu quá rồi ko dùng, ko chắc nhớ đc bao nhiêu nữa.
Mình muốn làm lại bài này bằng nhiều loại ngôn ngôn ngữ, tích lũy thêm kiến thức.
Tiện thể mình mong bạn nào rành về VB chỉ giáo mình luôn nhé. Mình thích làm bằng VB lắm, nhưng chẳng còn nhớ bao nhiêu nữa.
Mong các bạn giúp đỡ.

rox_rook · 14-10-2008, 04:06 PM

- Cậu post cái bài lỗi của cậu lên xem

! Suy nghĩ cả bài thì tui không có thời gian, cậu cứ đưa giải thuật mà cậu nghĩ rùi tui viết bằng C++ cho cậu !

Mình muốn làm lại bài này bằng nhiều loại ngôn ngôn ngữ, tích lũy thêm kiến thức.

Cậu học chắc 1 ngôn ngữ = cậu học 10 ngôn ngữ mà chỉ ở mức độ biết ! Chỉ tốn thời gian học syntax chứ chả được gì, cậu học lập trình chứ không học ngôn ngữ !

tiger86love102 · 15-10-2008, 06:03 PM

Cảm ơn góp ý của bạn, căn bản cái gì mình cũng muốn biết, mà biết nhiều nhưng chẳng giỏi đc về một cái nhất định nào, khổ thế đấy.
Mình sẽ xem xét lại. Thank bạn!
Mình gõ code lên đây, bạn xem sai sót loằng ngoằng ở chỗ nào bạn sửa dùm mình nha, mình còn gà code lung tung bạn có cáu cũng đừng "tạt tai" mình nha, hj hj!

C++ Code:

Select All | Show/Hide

#include"iostream.h"
#include"conio.h"
#include"math.h"
#include"stdio.h"
int Vx,Vy,x,y,z,min,max,us;
void nhap()
{
\* nhập vào thể tích 2 bình Vx,Vy *\
do
{
cout<<"nhập vào thể tích bình x:";
cin>>Vx;
cout<<" nhập vao thể tích bình y:";
cin>>Vy;
} while ((Vx<0)||(Vy<0));
\* Theo điều kiện bài toán thì số lít nước cần đong phải là bội số của ước số chung lớn nhất của Vx và Vy. Tìm ước số chung lớn nhất của 2 bình x và y*\
min=Vx
if(Vx>Vy) min =Vy;
for(i=min;i<0;i--)
{
if(Vx % i ==0)||(Vy % i==0))
{
cout<<" in ra danh sách các ước số của bình x,y:";
cout<< i ;
}
}
\* còn lấy ước số chung lớn nhất thì em thủ thế này nhưng không dc *\
usln=1; \* ước số lớn nhất gán bằng 1 *\
for( i=0;i<vx;i++)
{
if (usln < i) i=usln;
cout<<"ước số lơn nhất là :"<<usln;
}
\*nhập vào thể tích nước cần đong(z), với điều kiện z phải là bội số chung của ước số chung lớn nhất của thể tích 2 bình vừa nhập vào *\
Do
{
cout<<"nhập vào lượng nước cần đong z :";
cin>> z;
} while(z % usln != 0);
}
void dong_nuoc()
{
x=0;y=0;
while((x!=z) ||(y!=z))
{
if(x=Vx) x=o;
cout<<" in giá trị của x :"<< x<<" giá trị của y:"<<y;
if(y=0) y=Vy;
cout <<" in giá trị của x :"<< x<<" giá trị của y:"<<y;
if(y>0)
{
min = Vx-x;
if((Vx-x)>y) min =y;
x=x+min;
y=y-min
}
cout<<" in giá trị của x :"<< x<<" giá trị của y:"<<y;
}
}
void main()
{
clrscr();
nhap();
dong_nuoc();
getch();
}

Đây là phần code mình viết nhưng chua chạy mong bạn sửa dùm mình nha, chỉ luôn cho mình viết sai ở đâu, share cho mình it EXP nha.
Nhanh chút bạn nha, mình nóng ruột lắm hj hj!
Thank bạn nhiều lắm!
Ôi lằng nhằng quá, cứ linh tinh thế nào ý, rối bù hết cả lên rồi, loạn rồi.
Bạn ơi mình mới nghĩ ra là:
Khi nhập vào Vx và Vy thỏa mãn điều kiện >0, khi nhập vào số nước cần đong z thì chạy luôn một hàm kiểm tra xem z có phải bội số của uscln của cả Vx và Vy ko?
Nếu ko thì dừng luôn và thông báo bài toán ko có lời giải.
Nếu có mới tiếp tục chạy hàm đong_nước.
Nói về hàm thì mình thuộc loại gà chưa ra khỏi trứng.
Bạn sửa luôn bài mình theo ý tưởng trên đc ko?
Bạn xem phương án nào hay chỉ giúp mình luôn nhé.
Thank bạn nhiều!

Đọc mấy bài giải thuật toán của rr trên 4r hồi tết mà nể quá, mặc dù đọc chẳng hiểu ji.
Trước rr học ở đâu vậy? Đỉnh wa.
Em tập tành bước vào lập trình, sẽ cố gắng, mong bác "gõ đầu" em nhiều nhiều nhé.
Thank!

rox_rook · 16-10-2008, 09:52 AM

- Tui tự học là chính, hiện tại trên trường tui chỉ mới lấy lớp OOP with C++ thôi. Với lại ở đây thầy cô chẳng giúp nhiều cho cậu, cái chính vẫn là cậu thôi.
- Bây giờ tui đang trong lớp nên không giúp cậu nhiều được, tranh thủ break time nên vào search web tí thôi.
- Nhìn cách cậu code tui nghĩ cậu dùng VC++ 6.0 hoặc TC++, và nếu cậu thực sự muốn học C++ thì tui đề nghị cậu không xài 2 thằng này. Lý do thì đơn giản thôi, tui không thích đọc và viết code non-standard.
- Download Code::Block IDE, hoặc DevCpp IDE, hoặc Microsoft Visual C++ 2008 Express Edition hoặc KDevelop IDE. Một trong 4 thằng này đều ok. Cậu down về và install đi rùi tính tiếp nhé

! Good luck

tiger86love102 · 16-10-2008, 11:39 AM

Ý! Uhm mình sẽ tiếp thu ý kiến của bạn. Có nhiều cái mình chưa biết, mình sẽ học hỏi sau.
Bạn xem bài tập cho mình luôn với, mình nóng ruột quá.
Bạn sửa luôn dùm mình với nha.
Chừng nào còn chưa có đc lời giải thỏa đáng cho bài toán này mình còn khó chịu wa, bạn giúp mình với nha.
Đang măm măm trưa nè, nuốt hổng trôi.
Thank muck!

Tiger ngồi há hốc mồm, nước dãi chảy ròng ròng, lim dim con mắt, ngóng dài cổ... chờ rox_rock help. :(

Mình viết lại thế này, máy lỗi ko chạy thử đc, các bạn kiểm tra dùm mình nhé.
Coi có ji ko ổn cho mình chút ý kiến.
Thank all!

C++ Code:

Select All | Show/Hide

#include ”iostream.h”
#include “stdio.h”
#include “conio.h”
#include “math.h”
Int Vx,Vy,x,y,z,USCLN,a,b,k;
Void Nhap()
{
Do{
Cout<<”\n Nhap vao the tich binh 1 Vx: ”;
Cin>>Vx;
Cout<< “\n Nhap vao the tich binh 2 Vy: ”;
Cin>>Vy;
} While((Vx<0) &&(Vy<0));
a=Vx; b=Vy;
While((a!= 0)&&(b != 0))
{
If(a>=b)
a - = b;
Else
b - = a;
}
If(a = = 0)
USCLN = b
Else
USCLN = a;
\* Bài toán chỉ có được lời giải khi số lít nước cần đong là bội số của ước số chung lớn nhất của thể tích hai bình: z=n*USCLN(Vx,Vy) (Với n là số nguyên dương) *\
Do{
Cout<< “\n Nhap vao z lit nuoc can dong: ”;
Cin>> z;
} While ((z % USCLN) != 0);
}
Void Dong_nuoc()
{
x=0; y=0;
While((x != z)&&(y != z))
}
If(x = = Vx)
{
x = 0;
Cout<< “ \nL1: ”<<“x: ”<<x<<“ ”<<“y: ”<<y;
}
If (y = = 0)
{
y = Vy;
Cout<< “\nL2: ”<<“x: ”<<x<<“ ”<<“y: ”<<y;
}
If (y > 0)
{
{
If ((Vx - x)<y)
k = (Vx - x);
Else
k = y;
}
x = x + k;
y = y – k;
Cout<< “\nL3: ”<<“x : ”<<x<<“ ”<<“y: ”<<y;
}
}
}
Void main()
{
Clrscr();
Nhap();
Dong_nuoc();
Getch();
}

rox_rook · 20-10-2008, 11:27 AM

- Tui thành thật sorry cậu nhưng quả thật quên mất thread này.
- Nhưng cậu chưa biết hoàn cảnh tui ra sao mà cậu đã chửi tui là quá đáng !!!
- Cậu thấy 2 ngay qua tui toàn online từ 10h30-11h tối bên này, tui đi làm về thì chỉ lên coi được 1 tí, nếu bài nào ngắn đơn giản thì tui giúp chứ còn bài làm thực sự thì làm sao tui đọc cho nổi, tui làm từ 9h sáng đến 10h30 tối lận cậu à ! Cậu phải thông cảm cho tui chứ !
- Tui hứa với cậu tui giúp thì tui nhất định sẽ giúp, do tui chưa sắp xếp thời gian được thôi. Chứ tui có phải làm kiêu làm dáng với cậu thì tui được gì ?
- Thôi thì dù gì lỗi cũng của tui, do tui quên để ý.
- Còn đây là bài giải tui dựa theo giải thuật cậu mà làm :

C++ Code:

Select All | Show/Hide

#include <iostream>
using namespace std;
void nhapTheTichXYVaLuongNuoc( int& Vx, int& Vy, int& luong_nuoc )
{
do {
cout << "Nhap the tich ( Vx, Vy ) dieu kien : vX < Vy and vX, Vy > 0 :\n";
cin >> Vx >> Vy;
}
while( ( Vx < 0 ) || ( Vy < 0 ) || Vx >= Vy );
cout << "Nhap luong nuoc can dong : ";
cin >> luong_nuoc;
}
bool tonTaiLoiGiai( int ucln_cua_VxVy, int luong_nuoc_can_dong )
{
if( ( luong_nuoc_can_dong % ucln_cua_VxVy ) == 0 )
{
return true;
}
return false;
}
int uocChungLonNhat( int x, int y )
{
if( y == 0 )
return x;
else
return uocChungLonNhat( y, x % y );
}
void inLuongNcTrongThung( int Vx, int Vy )
{
cout << "\n + Binh X hien tai chua : " << Vx;
cout << "\n + Binh Y hien tai chua : " << Vy;
cout << "\n";
}
int thucHienDongNuoc( int Vx, int Vy, int luong_nuoc_can_dong )
{
int binh_x = 0;
int binh_y = 0;
int buoc = 1;
do {
if( binh_x == Vx )
{
cout << "\n -> Buoc thu " << buoc << "\n";
cout << "( L1 ) : Neu binh X day, thi do het nc binh X di ";
binh_x = 0;
buoc++;
inLuongNcTrongThung( binh_x, binh_y );
}
else if( binh_y == 0 )
{
cout << "\n -> Buoc thu " << buoc << "\n";
cout << "( L2 ) : Neu binh Y rong thi do day nc vao binh Y ";
binh_y = Vy;
buoc++;
inLuongNcTrongThung( binh_x, binh_y );
}
else if( binh_x != Vx && binh_y != 0 )
{
cout << "( L3 ) Neu binh X khong day va binh Y khong rong thi trut nc \n"
<< "tu binh Y sang binh X cho den khi binh X day hoac binh Y het nuoc";
while( binh_x < Vx && binh_y != 0 )
{
cout << "\n -> Buoc thu " << buoc << "\n";
buoc++;
if( binh_y >= Vx )
{
int tam = binh_x;
binh_x = Vx;
binh_y -= Vx - tam;;
}
else // else if( binh_y < Vx )
{
binh_x += binh_y;
binh_y = 0;
}
inLuongNcTrongThung( binh_x, binh_y );
}
cin.get();
}
}
while( binh_x != luong_nuoc_can_dong && binh_y != luong_nuoc_can_dong );
if( binh_x == luong_nuoc_can_dong )
return Vx;
else
return Vy;
}
int main()
{
int the_tich_binh_x;
int the_tich_binh_y;
int luong_nuoc;
nhapTheTichXYVaLuongNuoc( the_tich_binh_x, the_tich_binh_y, luong_nuoc );
int ucln_cuaXY = uocChungLonNhat( the_tich_binh_x, the_tich_binh_y );
cout << "ucln_cuaXy = " << ucln_cuaXY << "\n";
if( tonTaiLoiGiai( ucln_cuaXY,luong_nuoc ) == true )
{
int thung_chua_luong_nuoc = thucHienDongNuoc( the_tich_binh_x, the_tich_binh_y, luong_nuoc );
cout << "\n Thung chua luong nuoc can dong la thung co the tich = "
<< thung_chua_luong_nuoc << "\n";
}
else
{
cout << "\n Khong ton tai loi giai. Chuong trinh ket thuc \n";
}
return 0;
}

- Code cậu viết còn yếu quá, bỏ dùng biến cục bộ đi, code cậu cũng chẳng phải standard C++. Tập viết theo standard để code portable !

tiger86love102 · 21-10-2008, 02:25 AM

Uhmm! code hay vậy ta.
Thành thật sorry cậu! Mình sai rồi.

sim · 08-02-2012, 08:11 PM

Cái này mình dựa sát vào ý tưởng giải thuật đầu đề nè:

C++ Code:

Select All | Show/Hide

#include <iostream>
#include <conio.h>
using namespace std;
int ucln(int, int);
int x, y;
int vx, vy;
int z;
int luat1();
int luat2();
int luat3();
int main()
{
cout << "Bai Toan Dong Nuoc" << endl;
cout << "Nhap dung tich binh X: ";
cin >> vx;
cout << "Nhap dung tich binh Y: ";
cin >> vy;
cout << "Nhap dung tich can dong: z = ";
cin >> z;
if (z % ucln(vx, vy) != 0)
{
cout << "Khong the dong duoc theo yeu cau!" << endl;
}
else
{
x = 0;
y = 0;
while (x != z && y != z)
{
luat1();
luat2();
luat3();
}
}
getch();
return 0;
}
int ucln(int a, int b)
{
if (a <= 0 || b <= 0)
return 1;
while (a % b != 0 && b % a != 0)
{
if (a > b)
a = a % b;
else
b = b % a;
}
return a > b ? b : a;
}
int luat1()
{
if (x == vx)
{
x = 0;
cout << "Luat L1 -> x = " << x << ", y = " << y << endl;
return 1;
}
return 0;
}
int luat2()
{
if (y == 0)
{
y = vy;
cout << "Luat L2 -> x = " << x << ", y = " << y << endl;
return 1;
}
return 0;
}
int luat3()
{
if (x < vx && y > 0)
{
if (y > vx - x)
{
y -= vx - x;
x = vx;
}
else
{
x += y;
y = 0;
}
cout << "Luat L3 -> x = " << x << ", y = " << y << endl;
return 1;
}
return 0;
}

tiendaotd · 08-02-2012, 09:08 PM

giải thuật hay phết.
code :

C++ Code:

Select All | Show/Hide

int vx, vy, z, x, y;
int nstep ;
queue<int> trace;
void read() {
cin >> vx >> vy >> z;
}
void solve() {
if(z % gcd(vx,vy) != 0){
cout << "-1";
return;
}
while(true){
if(x < vx && y > 0 ){
if(y > vx-x){
y -= (vx-x);
x = vx;
}
else {
x += y;
y = 0;
}
}
else {
if(x == vx) x = 0;
if(y == 0) y = vy;
}
nstep++;
trace.push(x); trace.push(y);
if(x == z || y == z){
cout << nstep << endl;
while(!trace.empty()){
cout << trace.front() ; trace.pop();
cout << " " << trace.front(); trace.pop();
cout << endl;
}
return;
}
}
}

input :

Code:

3 4 2

output :

Code:

chevalier90 · 13-10-2012, 05:35 PM

Có bác nào có code bài toán đong nước này bằng ngôn ngữ prolog không ? Cho mình xin với

Đề tài: Bài toán Đong nước môn Trí Tuệ Nhân Tạo

Các công cụ đề tài

Display

Bài toán Đong nước môn Trí Tuệ Nhân Tạo

Bài toán Đong nước môn Trí Tuệ Nhân Tạo

Quyền hạn của bạn