D_felfelak
پنج شنبه 24 اسفند 1391, 14:51 عصر
هشت وزير
اشکال در برنامه هشت وزير
برنامه ی هشت وزير رو نوشتم
اما با اينکه فکر ميکنم الگوريتم درست هست اما بعضی حالات وزير ها ميتونند هم ديگر رو بزنند
و و هزار بار هم اجرا کردم اکثراً شش يا هفت وزير رو ميچينه و حتی يه بار هم به هشت نميرسه!!!
سعی کردم برنامه رو تعميم پذير برای بيش از هشت وزير داشته باشم
اما الا" مقصودم برای هشت ها هست
شی گرايی و طراحی الگوريتم و ساختمان داده رو هنوز نگذرورندم!
#include <iostream>
#include <cstdlib>
#include
<ctime>
using namespace std;
const int N = 8;
struct miiin
{
int x;
int y;
int
minimum;
bool sahih;
};
int ghadremotlagh (int);
int min (int, int );
void firast_dast (
int [N + 1][N + 1]);
miiin mini ( int [N + 1][N + 1], const int [N +
1][N + 1]);
void boardchange ( int [N + 1][N + 1], const miiin);
void dast
( int [N + 1][ N + 1 ] , const int [N + 1][N + 1] );
int main()
{
srand ( time (0));
int board [N + 1][N +
1];
int dastresy [N + 1][N + 1];
char natije [N + 1][N +
1];
for (int i = 0; i <= N; i++)
for (int j = 0; j <=
N; j++)
{
board [i][j]=
0;
natije[i][j] = 'o';
}
firast_dast( dastresy );
int harekat = 0 ;
miiin
min;
bool mojodi, negah;
for ( int i = 1 ; i <= N ;
i++)
{
mojodi = false;
negah =
true;
for (int i = 1; negah , i < N + 1;
i++)
for (int j = 1; negah, j < N + 1;
j++)
if ( board[i][j] == 0
)
{
mojodi =
true;
negah =
false;;
}
if ( mojodi )
{
min = mini(
dastresy , board );
if ( min.sahih == true
)
{
harekat
++;
board [ min.x] [min.y] =
1;
boardchange ( board , min
);
dast ( dastresy ,
board);
natije[min.x][min.y] =
'X';
}
else
cout
<< "\aEROR: meghdar x va y namotabar hast!!!\n";
}
else
{
cout << "Adam
movafghiat\n";
break;
}
cout
<< "harekat = " << harekat << "\n";
}
cout << harekat;
for (int i = 1; i < N+1;
i++)
{
for (int j = 1; j < N+1;
j++)
cout << natije [i][j] <<
"\t";
cout << "\n\n";
}
cout <<
"\n\n\n\n\n\n\n";
for (int i = 1; i < N+1; i++)
{
for (int j =
1; j < N+1; j++)
cout << board [i][j] <<
"\t";
cout << "\n\n";
}
cout << "\n\n\n\n\n\n\n";
for (int i = 1; i < N+1; i++)
{
for (int j =
1; j < N+1; j++)
cout << dastresy [i][j] <<
"\t";
cout << "\n\n";
}
cin.get();
cin.get();
return 0;
}
int ghadremotlagh ( int x )
{
if ( x >= 0
)
return x;
else
return x * -1;
}
int min ( int x , int y )
{
if ( x < y )
return
x;
else
return y;
}
void firast_dast ( int x [N + 1][N + 1] )
{
for (int i = 1; i <= N ;
i++)
{
for (int j = 1; j <= N ;
j++)
{
x [i][j] = 2 * N -
1;
int k1 = ghadremotlagh( 8 - i
);
int k2 = ghadremotlagh ( 8 - j
);
int k3 = ghadremotlagh ( 1 - i
);
int k4 = ghadremotlagh ( 1 - j
);
x [i][j] += min ( k1 , k2
);
x [i][j] += min ( k3 , k4
);
x [i][j] += min ( k1,
k4);
x [i][j] += min ( k3,
k2);
}
}
}
miiin mini ( int x [N + 1][N + 1] , const int board [N + 1][N + 1]
)
{
miiin y[ N * 4 + 1];
int negah = 0 ;
miiin
returno;
returno.minimum = N * N;
for (int i = 1; i <= N ; i++)
for (int j = 1; j <=
N ; j++)
if ( board [i][j] ==
0)
{
if ( returno.minimum > x
[i][j])
{
negah =
0;
returno.minimum
=x[i][j];
returno.x =
i;
returno.y=
j;
}
else if ( returno.minimum == x [i][j])
{
y[negah].x =
i;
y[negah].y=
j;
negah++;
}
}
if ( negah == 0 )
{
if ( returno.x <=
N && returno.x >= 1 && returno.y <= N
&& returno.y >=
1)
{
returno.sahih =
true;
return
returno;
}
else
{
returno.sahih
= false;
return
returno;
}
}
else
{
int
rando = rand () % negah;
returno.x =
y[rando].x;
returno.y = y[rando].y;
if (
returno.x <= N && returno.x >= 1 && returno.y
<= N && returno.y >=
1)
{
returno.sahih =
true;
return
returno;
}
else
{
returno.sahih
= false;
return returno;
}
}
}
void boardchange ( int board [N + 1][N + 1] , const miiin minimum
)
{
for (int i = 1; i < N + 1;
i++)
{
board [ minimum.x][i] = 1;
board [
i ][minimum.y] = 1;
}
int x[4], y[4] ;
for (int i = 0; i < 4;
i++)
{
x[i] = minimum.x;
y[i]
= minimum.y;
}
while
(true)
{
x[0]++;
y[0]++;
if
( x[0] <=8 && y[0] <= 8 )
board [ x[0] ] [
y[0] ] = 1;
else
break;
}
while
(true)
{
x[1]--;
y[1]--;
if
( x[1] >= 0 && y[1] >= 0 )
board [ x[1] ] [
y[1] ] = 1;
else
break;
}
while
(true)
{
x[2]++;
y[2]--;
if
( x[2] <= 8 && y[2] >= 0 )
board [ x[1] ] [
y[2] ] = 1;
else
break;
}
while
(true)
{
x[3]--;
y[3]++;
if
( y[3] <= 8 && x[3] >= 0 )
board [ x[1] ] [
y[2] ] = 1;
else
break;
}
}
void dast ( int dast[N + 1][ N + 1 ] , const int board [N + 1][N + 1]
)
{
for (int i = 1; i <= N ; i++)
for (int j = 1;
j <= N ; j++)
{
dast [i][j] =
0;
//S mohasebe ye harekat ofoghi va
amodi
for (int shomarande = 1; shomarande <= N ;
shomarande++)
{
if ( board
[i][shomarande] == 0 && shomarande != j
)
++dast [i][shomarande];
if ( board [shomarande][j] == 0 &&
shomarande != i)
++dast
[shomarande][j];
}
//E mohasebe
ye harekat ofoghi va amodi
//S movarab
int x[4] , y[4] ;
for (int w = 0; w < 4;
w++)
{
x[w] =
i;
y[w] =
j;
}
while
( true
)
{
x[0]++;
y[0]++;
if
( x[0] <=8 && y[0] <= 8
)
{
if ( board [
x[0] ][ y[0] ] == 0 )
++dast [ x[0] ] [
y[0]
];
}
else
break;
}
while
(true)
{
x[1]--;
y[1]--;
if
( x[1] >= 0 && y[1] >= 0
)
{
if ( board [
x[1] ][ y[1] ] == 0 )
++dast [ x[1] ] [
y[1]
];
}
else
break;
}
while
(true)
{
x[2]++;
y[2]--;
if
( x[2] <= 8 && y[2] >= 0
)
{
if ( board [
x[2] ][ y[2] ] == 0 )
++dast [ x[2] ] [
y[2]
];
}
else
break;
}
while
(true)
{
x[3]--;
y[3]++;
if
( y[3] <= 8 && x[3] >= 0
)
{
if ( board [
x[3] ][ y[3] ] == 0 )
++dast [ x[3] ] [
y[3]
];
}
else
break;
}
}
}
اشکال در برنامه هشت وزير
برنامه ی هشت وزير رو نوشتم
اما با اينکه فکر ميکنم الگوريتم درست هست اما بعضی حالات وزير ها ميتونند هم ديگر رو بزنند
و و هزار بار هم اجرا کردم اکثراً شش يا هفت وزير رو ميچينه و حتی يه بار هم به هشت نميرسه!!!
سعی کردم برنامه رو تعميم پذير برای بيش از هشت وزير داشته باشم
اما الا" مقصودم برای هشت ها هست
شی گرايی و طراحی الگوريتم و ساختمان داده رو هنوز نگذرورندم!
#include <iostream>
#include <cstdlib>
#include
<ctime>
using namespace std;
const int N = 8;
struct miiin
{
int x;
int y;
int
minimum;
bool sahih;
};
int ghadremotlagh (int);
int min (int, int );
void firast_dast (
int [N + 1][N + 1]);
miiin mini ( int [N + 1][N + 1], const int [N +
1][N + 1]);
void boardchange ( int [N + 1][N + 1], const miiin);
void dast
( int [N + 1][ N + 1 ] , const int [N + 1][N + 1] );
int main()
{
srand ( time (0));
int board [N + 1][N +
1];
int dastresy [N + 1][N + 1];
char natije [N + 1][N +
1];
for (int i = 0; i <= N; i++)
for (int j = 0; j <=
N; j++)
{
board [i][j]=
0;
natije[i][j] = 'o';
}
firast_dast( dastresy );
int harekat = 0 ;
miiin
min;
bool mojodi, negah;
for ( int i = 1 ; i <= N ;
i++)
{
mojodi = false;
negah =
true;
for (int i = 1; negah , i < N + 1;
i++)
for (int j = 1; negah, j < N + 1;
j++)
if ( board[i][j] == 0
)
{
mojodi =
true;
negah =
false;;
}
if ( mojodi )
{
min = mini(
dastresy , board );
if ( min.sahih == true
)
{
harekat
++;
board [ min.x] [min.y] =
1;
boardchange ( board , min
);
dast ( dastresy ,
board);
natije[min.x][min.y] =
'X';
}
else
cout
<< "\aEROR: meghdar x va y namotabar hast!!!\n";
}
else
{
cout << "Adam
movafghiat\n";
break;
}
cout
<< "harekat = " << harekat << "\n";
}
cout << harekat;
for (int i = 1; i < N+1;
i++)
{
for (int j = 1; j < N+1;
j++)
cout << natije [i][j] <<
"\t";
cout << "\n\n";
}
cout <<
"\n\n\n\n\n\n\n";
for (int i = 1; i < N+1; i++)
{
for (int j =
1; j < N+1; j++)
cout << board [i][j] <<
"\t";
cout << "\n\n";
}
cout << "\n\n\n\n\n\n\n";
for (int i = 1; i < N+1; i++)
{
for (int j =
1; j < N+1; j++)
cout << dastresy [i][j] <<
"\t";
cout << "\n\n";
}
cin.get();
cin.get();
return 0;
}
int ghadremotlagh ( int x )
{
if ( x >= 0
)
return x;
else
return x * -1;
}
int min ( int x , int y )
{
if ( x < y )
return
x;
else
return y;
}
void firast_dast ( int x [N + 1][N + 1] )
{
for (int i = 1; i <= N ;
i++)
{
for (int j = 1; j <= N ;
j++)
{
x [i][j] = 2 * N -
1;
int k1 = ghadremotlagh( 8 - i
);
int k2 = ghadremotlagh ( 8 - j
);
int k3 = ghadremotlagh ( 1 - i
);
int k4 = ghadremotlagh ( 1 - j
);
x [i][j] += min ( k1 , k2
);
x [i][j] += min ( k3 , k4
);
x [i][j] += min ( k1,
k4);
x [i][j] += min ( k3,
k2);
}
}
}
miiin mini ( int x [N + 1][N + 1] , const int board [N + 1][N + 1]
)
{
miiin y[ N * 4 + 1];
int negah = 0 ;
miiin
returno;
returno.minimum = N * N;
for (int i = 1; i <= N ; i++)
for (int j = 1; j <=
N ; j++)
if ( board [i][j] ==
0)
{
if ( returno.minimum > x
[i][j])
{
negah =
0;
returno.minimum
=x[i][j];
returno.x =
i;
returno.y=
j;
}
else if ( returno.minimum == x [i][j])
{
y[negah].x =
i;
y[negah].y=
j;
negah++;
}
}
if ( negah == 0 )
{
if ( returno.x <=
N && returno.x >= 1 && returno.y <= N
&& returno.y >=
1)
{
returno.sahih =
true;
return
returno;
}
else
{
returno.sahih
= false;
return
returno;
}
}
else
{
int
rando = rand () % negah;
returno.x =
y[rando].x;
returno.y = y[rando].y;
if (
returno.x <= N && returno.x >= 1 && returno.y
<= N && returno.y >=
1)
{
returno.sahih =
true;
return
returno;
}
else
{
returno.sahih
= false;
return returno;
}
}
}
void boardchange ( int board [N + 1][N + 1] , const miiin minimum
)
{
for (int i = 1; i < N + 1;
i++)
{
board [ minimum.x][i] = 1;
board [
i ][minimum.y] = 1;
}
int x[4], y[4] ;
for (int i = 0; i < 4;
i++)
{
x[i] = minimum.x;
y[i]
= minimum.y;
}
while
(true)
{
x[0]++;
y[0]++;
if
( x[0] <=8 && y[0] <= 8 )
board [ x[0] ] [
y[0] ] = 1;
else
break;
}
while
(true)
{
x[1]--;
y[1]--;
if
( x[1] >= 0 && y[1] >= 0 )
board [ x[1] ] [
y[1] ] = 1;
else
break;
}
while
(true)
{
x[2]++;
y[2]--;
if
( x[2] <= 8 && y[2] >= 0 )
board [ x[1] ] [
y[2] ] = 1;
else
break;
}
while
(true)
{
x[3]--;
y[3]++;
if
( y[3] <= 8 && x[3] >= 0 )
board [ x[1] ] [
y[2] ] = 1;
else
break;
}
}
void dast ( int dast[N + 1][ N + 1 ] , const int board [N + 1][N + 1]
)
{
for (int i = 1; i <= N ; i++)
for (int j = 1;
j <= N ; j++)
{
dast [i][j] =
0;
//S mohasebe ye harekat ofoghi va
amodi
for (int shomarande = 1; shomarande <= N ;
shomarande++)
{
if ( board
[i][shomarande] == 0 && shomarande != j
)
++dast [i][shomarande];
if ( board [shomarande][j] == 0 &&
shomarande != i)
++dast
[shomarande][j];
}
//E mohasebe
ye harekat ofoghi va amodi
//S movarab
int x[4] , y[4] ;
for (int w = 0; w < 4;
w++)
{
x[w] =
i;
y[w] =
j;
}
while
( true
)
{
x[0]++;
y[0]++;
if
( x[0] <=8 && y[0] <= 8
)
{
if ( board [
x[0] ][ y[0] ] == 0 )
++dast [ x[0] ] [
y[0]
];
}
else
break;
}
while
(true)
{
x[1]--;
y[1]--;
if
( x[1] >= 0 && y[1] >= 0
)
{
if ( board [
x[1] ][ y[1] ] == 0 )
++dast [ x[1] ] [
y[1]
];
}
else
break;
}
while
(true)
{
x[2]++;
y[2]--;
if
( x[2] <= 8 && y[2] >= 0
)
{
if ( board [
x[2] ][ y[2] ] == 0 )
++dast [ x[2] ] [
y[2]
];
}
else
break;
}
while
(true)
{
x[3]--;
y[3]++;
if
( y[3] <= 8 && x[3] >= 0
)
{
if ( board [
x[3] ][ y[3] ] == 0 )
++dast [ x[3] ] [
y[3]
];
}
else
break;
}
}
}