hien_hien_1112
New Member
Đây là bài tâp trí tuệ nhân tạo:
Cho 2 bình có dung tích lần lượt là m và n (lit). Với nguồn nước không hạn chế, dùng 2 bình trên để đong k lit nước.
Mình dùng thuật toán tìm kiếm theo chiều rộng. Code như sau:
#include
#include
enum boolean {false, true};
/*************************** CAU HINH **************************************/
typedef struct CauHinh
{ int Truoc, x, y, SHDinh; };
/*************************** CAU TRUC MOT NUT ******************************/
class Nodes
{
public:
CauHinh Info;
Nodes *Link;
Nodes() {};
Nodes(CauHinh& temp, Nodes *next = NULL)
{ Info = temp; Link = next; }
};
/*************************** HANG DOI (QUEUE) ******************************/
class List
{
protected:
Nodes *LTop;
public:
List() { LTop = NULL; }
// Ham tra ve dia chi nut dau danh sach
Nodes *getLTop() { return LTop; }
// Kiem tra xem danh sach co rong ko?
boolean isEmpty()
{
if (LTop==NULL) return true;
else return false;
}
// Nap mot phan tu vao Queue
void pushQueue(CauHinh& temp)
{
Nodes *p = new Nodes(temp, LTop);
LTop = p;
}
// Day mot phan tu ra khoi Queue
CauHinh popQueue();
// Ham tra ve dia chi nut co SHDinh = n
Nodes *timDinh(int& n);
// Ham kiem tra mot cau hinh co thuoc danh sach hay ko?
Nodes *checkL(int& z, int& t);
// Ham noi danh sach L2 vao danh sach L1
void addList(List& L2);
};
// Day mot phan tu ra khoi Queue
CauHinh List:
opQueue()
{
Nodes *p = LTop;
while (p->Link != NULL) p = p->Link;
if (LTop->Link == NULL) LTop = NULL;
CauHinh temp = p->Info;
delete p;
return temp;
}
// Ham tra ve dia chi nut co gia tri SHDinh = n
Nodes *List::timDinh(int& n)
{
Nodes *p = LTop;
while (p != NULL || p->Info.SHDinh != n) p = p->Link;
return p;
}
// Ham kiem tra mot cau hinh co thuoc danh sach hay ko?
Nodes *List::checkL(int& z, int& t)
{
Nodes *p = LTop;
while (p != NULL || (p->Info.x != z && p->Info.y != t))
p = p->Link;
return p;
}
// Ham noi danh sach L2 vao danh sach L1
void List::addList(List& L2)
{
Nodes *p = LTop;
while (p->Link !=NULL) p = p->Link;
p->Link = L2.LTop;
}
/*************************** BAI TOAN DONG NUOC ****************************/
int m, n, k;
// Cac thao tac do nuoc:
void doNuoc(CauHinh u, CauHinh& v, int& i)
{
switch (i)
{
case 1: { v.x = n; v.y = u.y; }
case 2: { v.x = u.x; v.y = m; }
case 3: { v.x = 0; v.y = u.y; }
case 4: { v.x = u.x; v.y = 0; }
case 5:
{
if (u.x + u.y <= m) { v.x = 0; v.y = u.x + u.y; }
else { v.x = u.x + u.y - m; v.y = m; }
}
case 6:
{
if (u.x + u.y <= n) { v.x = u.x + u.y; v.y = 0; }
else { v.x = n; v.y = u.x + u.y -n; }
}
}
}
// IN KET QUA
void inKetQua(List& Mo, List& Dong, CauHinh& v)
{
Mo.addList(Dong);
cout<<"("<
int temp = v.Truoc;
while (temp != 0)
{
Nodes *p = Mo.timDinh(temp);
cout<<" <-- ("<Info.x<<", "<Info.y<<")";
temp = p->Info.Truoc;
}
}
// TIM KIEM RONG
void BrFS(CauHinh& temp)
{
List Mo, Dong;
Mo.pushQueue(temp);
while (!Mo.isEmpty())
{
CauHinh u = Mo.popQueue();
Dong.pushQueue(u);
int dinh = u.SHDinh;
for (int i = 1; i <= 6; i++)
{
CauHinh v;
doNuoc(u,v,i);
if (Mo.checkL(v.x,v.y) != NULL && Dong.checkL(v.x,v.y) != NULL)
{
v.Truoc = dinh;
dinh++;
v.SHDinh = dinh;
Mo.pushQueue(v);
if (v.x == k || v.y == k)
{
inKetQua(Mo,Dong,v);
break;
}
}
}
}
cout<<" Khong thanh cong !";
}
/*************************** HAM MAIN **************************************/
int main()
{
clrscr();
CauHinh xp;
cout<<"Nhap m, n, k: ";
cin>>m>>n>>k;
xp.Truoc = 0; xp.x = 0; xp.y = 0;
xp.SHDinh = 1;
BrFS(xp);
getch();
return 0;
}
Các pro giúp mình cai nha. Thanks![/SIZE]
Cho 2 bình có dung tích lần lượt là m và n (lit). Với nguồn nước không hạn chế, dùng 2 bình trên để đong k lit nước.
Mình dùng thuật toán tìm kiếm theo chiều rộng. Code như sau:
#include
#include
enum boolean {false, true};
/*************************** CAU HINH **************************************/
typedef struct CauHinh
{ int Truoc, x, y, SHDinh; };
/*************************** CAU TRUC MOT NUT ******************************/
class Nodes
{
public:
CauHinh Info;
Nodes *Link;
Nodes() {};
Nodes(CauHinh& temp, Nodes *next = NULL)
{ Info = temp; Link = next; }
};
/*************************** HANG DOI (QUEUE) ******************************/
class List
{
protected:
Nodes *LTop;
public:
List() { LTop = NULL; }
// Ham tra ve dia chi nut dau danh sach
Nodes *getLTop() { return LTop; }
// Kiem tra xem danh sach co rong ko?
boolean isEmpty()
{
if (LTop==NULL) return true;
else return false;
}
// Nap mot phan tu vao Queue
void pushQueue(CauHinh& temp)
{
Nodes *p = new Nodes(temp, LTop);
LTop = p;
}
// Day mot phan tu ra khoi Queue
CauHinh popQueue();
// Ham tra ve dia chi nut co SHDinh = n
Nodes *timDinh(int& n);
// Ham kiem tra mot cau hinh co thuoc danh sach hay ko?
Nodes *checkL(int& z, int& t);
// Ham noi danh sach L2 vao danh sach L1
void addList(List& L2);
};
// Day mot phan tu ra khoi Queue
CauHinh List:
opQueue(){
Nodes *p = LTop;
while (p->Link != NULL) p = p->Link;
if (LTop->Link == NULL) LTop = NULL;
CauHinh temp = p->Info;
delete p;
return temp;
}
// Ham tra ve dia chi nut co gia tri SHDinh = n
Nodes *List::timDinh(int& n)
{
Nodes *p = LTop;
while (p != NULL || p->Info.SHDinh != n) p = p->Link;
return p;
}
// Ham kiem tra mot cau hinh co thuoc danh sach hay ko?
Nodes *List::checkL(int& z, int& t)
{
Nodes *p = LTop;
while (p != NULL || (p->Info.x != z && p->Info.y != t))
p = p->Link;
return p;
}
// Ham noi danh sach L2 vao danh sach L1
void List::addList(List& L2)
{
Nodes *p = LTop;
while (p->Link !=NULL) p = p->Link;
p->Link = L2.LTop;
}
/*************************** BAI TOAN DONG NUOC ****************************/
int m, n, k;
// Cac thao tac do nuoc:
void doNuoc(CauHinh u, CauHinh& v, int& i)
{
switch (i)
{
case 1: { v.x = n; v.y = u.y; }
case 2: { v.x = u.x; v.y = m; }
case 3: { v.x = 0; v.y = u.y; }
case 4: { v.x = u.x; v.y = 0; }
case 5:
{
if (u.x + u.y <= m) { v.x = 0; v.y = u.x + u.y; }
else { v.x = u.x + u.y - m; v.y = m; }
}
case 6:
{
if (u.x + u.y <= n) { v.x = u.x + u.y; v.y = 0; }
else { v.x = n; v.y = u.x + u.y -n; }
}
}
}
// IN KET QUA
void inKetQua(List& Mo, List& Dong, CauHinh& v)
{
Mo.addList(Dong);
cout<<"("<
int temp = v.Truoc;
while (temp != 0)
{
Nodes *p = Mo.timDinh(temp);
cout<<" <-- ("<
temp = p->Info.Truoc;
}
}
// TIM KIEM RONG
void BrFS(CauHinh& temp)
{
List Mo, Dong;
Mo.pushQueue(temp);
while (!Mo.isEmpty())
{
CauHinh u = Mo.popQueue();
Dong.pushQueue(u);
int dinh = u.SHDinh;
for (int i = 1; i <= 6; i++)
{
CauHinh v;
doNuoc(u,v,i);
if (Mo.checkL(v.x,v.y) != NULL && Dong.checkL(v.x,v.y) != NULL)
{
v.Truoc = dinh;
dinh++;
v.SHDinh = dinh;
Mo.pushQueue(v);
if (v.x == k || v.y == k)
{
inKetQua(Mo,Dong,v);
break;
}
}
}
}
cout<<" Khong thanh cong !";
}
/*************************** HAM MAIN **************************************/
int main()
{
clrscr();
CauHinh xp;
cout<<"Nhap m, n, k: ";
cin>>m>>n>>k;
xp.Truoc = 0; xp.x = 0; xp.y = 0;
xp.SHDinh = 1;
BrFS(xp);
getch();
return 0;
}
Các pro giúp mình cai nha. Thanks![/SIZE]