bài lập trình ngựa đi tuần

/* CHUONG TRINH LAP TRINH C "NGUA DI TUAN"
tac gia: LE VAN HUNG
lop: K52A3
chuyen nganh: TOAN TIN UNG DUNG
*/
#include<conio.h>
#include<stdio.h>
#include<math.h>
#define n 8
int h[n][n];
int a[n]={2,1,-1,-2,-2,-1,1,2};
int b[n]={1,2,2,1,-1,-2,-2,-1};
void khoi_tao()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
h[i][j]=0;
}
}
}
//void in_mang()
//{
//for(int i=0;i<n;i++)
//{
// printf("%d ",a[i]);
//}
//}
void in_matran()
{
for(int i=1;i<=n;i++)
{
for(int j =1;j<=n;j++)
{
printf("%5d",h[i][j]);
}
printf("\n");
}
}
void ngua_tuan(int i,int x,int y)//buoc thu i,toa do x, toa do y
{
int u,v;
for(int k=0;k<n;k++)
{
u=x+a[k];
v=y+b[k];
if(1<=u&&u<=n&&1<=v&&v<=n&&h[u][v]==0)
{
h[u][v]=i;
if(i==n*n){in_matran();getch();}
else {ngua_tuan(i+1,u,v); h[u][v]=0;}

}

}

}
int main()
{
printf("\n\t CHAO MUNG BAN DA DEN VOI BAI LAP TRINH CUA TUI\n");
khoi_tao();
//h[][]=?;
ngua_tuan(2,1,1);
//in_mang();
getch();
return 0;
}
note: bài có đúng một chỗ là ngựa chưa nhảy được 1 ô "chỗ ấy mấy hôm trước khi mình gửi cho nhân thì nhân đã sửa thành công rùi" ,các bạn chỉ cần chú ý chỗ in đậm màu xanh cuối cùng là ok sửa đi cái là xong thui

hunghanam đã viết:

/* CHUONG TRINH LAP TRINH C "NGUA DI TUAN"
tac gia: LE VAN HUNG
lop: K52A3
chuyen nganh: TOAN TIN UNG DUNG
*/
#include
#include
#include
#define n 8
int h[n][n];
int a[n]={2,1,-1,-2,-2,-1,1,2};
int b[n]={1,2,2,1,-1,-2,-2,-1};
void khoi_tao()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
h[i][j]=0;
}
}
}
//void in_mang()
//{
//for(int i=0;i
//{
// printf("%d ",a[i]);
//}
//}
void in_matran()
{
for(int i=1;i<=n;i++)
{
for(int j =1;j<=n;j++)
{
printf("%5d",h[i][j]);
}
printf("\n");
}
}
void ngua_tuan(int i,int x,int y)//buoc thu i,toa do x, toa do y
{
int u,v;
for(int k=0;k
{
u=x+a[k];
v=y+b[k];
if(1<=u&&u<=n&&1<=v&&v<=n&&h[u][v]==0)
{
h[u][v]=i;
if(i==n*n){in_matran();getch();}
else {ngua_tuan(i+1,u,v); h[u][v]=0;}

}

}

}
int main()
{
printf("\n\t CHAO MUNG BAN DA DEN VOI BAI LAP TRINH CUA TUI\n");
khoi_tao();
//h[][]=?;
ngua_tuan(2,1,1);
//in_mang();
getch();
return 0;
}
note: bài có đúng một chỗ là ngựa chưa nhảy được 1 ô "chỗ ấy mấy hôm trước khi mình gửi cho nhân thì nhân đã sửa thành công rùi" ,các bạn chỉ cần chú ý chỗ in đậm màu xanh cuối cùng là ok sửa đi cái là xong thui

Cái lỗi đó là do khi khởi tạo duyệt ô đầu tiên Hưng nó chưa đánh dấu là đã duyêt nên ô đó đi qua rồi nhưng chưa được đánh số

h[x][y]=1;
ngua_tuan(2,x,y);

bài này cho kêt quả khi bắt đầu duyệt tại (1-1) hoặc (7-7).
Nhưng thử xp từ (1-4),(2-5),(4-3)... thì có lẽ là đơ máy mà vẫn chưa ra cái chi mô cả. Đã test trên Core i3 rùi mà ko dc j cả ,,hixxxxxxxx (CPU luôn là 100%)

uhm. Nếu muốn cho nó đi tuần với tất cả mọi ví trí thì tham khảo code này. Tất nhiên với input không tốt nó sẽ chạy lâu một chút vì độ phức tạp của bải toán này rất lớn. Tớ chỉ cho in một kết quả mà thui.

#include"iostream"

using std::cout;
using std::cin;
using std::endl;

int ok=0;

static int a[8]= {-2, -1, 1, 2, 2, 1, -1, -2};
static int b[8]= {-1, -2, -2, -1, 1, 2, 2, 1};
static int mark[8][8];

class Horse{
private:
int xCoordinate;
int yCoordinate;

public:
int init(){
for(int i=0; i<8; i++)
for(int j=0; j<8;j++)
mark[i][j]=0;
}

void select(){
mark[yCoordinate][xCoordinate]= 1;
}
void showValue(){
cout<<<" "<<
}

void unSelect(){
mark[yCoordinate][xCoordinate]= 0;
}

int testMark(int x, int y){
return mark[y][x];
}


void setValue(int x, int y){
xCoordinate= x;
yCoordinate= y;
}

void setValue(int i, Horse
horse){
xCoordinate= horse.xCoordinate + a[i];
yCoordinate= horse.yCoordinate + b[i];
}

void print(){
cout<<"("<<<", "<<<") ";
}


int testValue(int i){
if(xCoordinate+ a[i]>7 ||xCoordinate+ a[i] < 0||yCoordinate+ b[i]>7
|| yCoordinate+ b[i] < 0)return 0;
else if(testMark(xCoordinate+ a[i], yCoordinate+ b[i]))return 0;
else
return 1;

}

};


Horse horse[64];

void
result(){
int i;
for(i=0; i<64; i++)
horse[i].print();
cout<<"\n\n";
}

void
patrol(int i){// di tuan
if(ok)return;
int j;
for(j=0; j<8; j++)
if(horse[i].testValue(j)){
if(ok)return;
horse[i+1].setValue(j,horse[i]);
horse[i+1].select();
if(i+1== 63){result();ok=1;return ;}
patrol(i+1);
horse[i+1].unSelect();

}

}

int main(){

int x,y;

cout<<"Enter a current coordinate of
horse: (x,y)= ";
cin>>x>>y;
horse[0].setValue(x,y);
horse[0].init();
horse[0].select();
patrol(0);
system("pause");


}

cuongcnb đã viết:

uhm. Nếu muốn cho nó đi tuần với tất cả mọi ví trí thì tham khảo code này. Tất nhiên với input không tốt nó sẽ chạy lâu một chút vì độ phức tạp của bải toán này rất lớn. Tớ chỉ cho in một kết quả mà thui.

#include"iostream"

using std::cout;
using std::cin;
using std::endl;

int ok=0;

static int a[8]= {-2, -1, 1, 2, 2, 1, -1, -2};
static int b[8]= {-1, -2, -2, -1, 1, 2, 2, 1};
static int mark[8][8];

class Horse{
private:
int xCoordinate;
int yCoordinate;

public:
int init(){
for(int i=0; i<8; i++)
for(int j=0; j<8;j++)
mark[i][j]=0;
}

void select(){
mark[yCoordinate][xCoordinate]= 1;
}
void showValue(){
cout<<<" "<<
}

void unSelect(){
mark[yCoordinate][xCoordinate]= 0;
}

int testMark(int x, int y){
return mark[y][x];
}


void setValue(int x, int y){
xCoordinate= x;
yCoordinate= y;
}

void setValue(int i, Horse
horse){
xCoordinate= horse.xCoordinate + a[i];
yCoordinate= horse.yCoordinate + b[i];
}

void print(){
cout<<"("<<<", "<<<") ";
}


int testValue(int i){
if(xCoordinate+ a[i]>7 ||xCoordinate+ a[i] < 0||yCoordinate+ b[i]>7
|| yCoordinate+ b[i] < 0)return 0;
else if(testMark(xCoordinate+ a[i], yCoordinate+ b[i]))return 0;
else
return 1;

}

};


Horse horse[64];

void
result(){
int i;
for(i=0; i<64; i++)
horse[i].print();
cout<<"\n\n";
}

void
patrol(int i){// di tuan
if(ok)return;
int j;
for(j=0; j<8; j++)
if(horse[i].testValue(j)){
if(ok)return;
horse[i+1].setValue(j,horse[i]);
horse[i+1].select();
if(i+1== 63){result();ok=1;return ;}
patrol(i+1);
horse[i+1].unSelect();

}

}

int main(){

int x,y;

cout<<"Enter a current coordinate of
horse: (x,y)= ";
cin>>x>>y;
horse[0].setValue(x,y);
horse[0].init();
horse[0].select();
patrol(0);
system("pause");


}

Theo em thì code nào chả thế.Độ phức tạp là như nhau mà.