SemiRafista Temat założony przez niniejszego użytkownika |
[C] Skoczek szachowy » 2015-01-27 03:03:20 WItam. Napisałem program którego celem jest rekurencyjne znalezienie takiej sekwencji ruchów skoczka szachowego, by odwiedzić wszystkie pola, nie powtarzając żadnego z nich. Otóż na codzień piszę w C++, ale na zaliczenie potrzebowałem tego zadania w C, z którym jakoś nie mogę sobie poradzić :( Uprzejmie proszę o sprawdzenie kodu i wskazanie ewentualnych błędów. #include <stdio.h> #include <stdlib.h> #include <stdbool.h>
void Zeruj_Tablice( int ** tab, int n ) { for( int i = 0; i < n; i++ ) { for( int j = 0; j < n; j++ ) { tab[ i ][ j ] = 0; } } }
void Drukuj( int ** tab, int n ) { for( int i = 0; i < n; i++ ) { for( int j = 0; j < n; j++ ) printf( "%3d", tab[ i ][ j ] ); printf( "\n" ); } }
bool Sprawdz_Ruch( int nr_przypadku, int x, int y, int ** tab, int n ) { bool temp = false; switch( nr_przypadku ) { case 1: if( tab[ x + 1 ][ y + 2 ] == 0 && x + 1 >= 0 && x + 1 < n && y + 2 >= 0 && y + 2 < n ) temp = true; break; case 2: if( tab[ x + 2 ][ y + 1 ] == 0 && x + 2 >= 0 && x + 2 < n && y + 1 >= 0 && y + 1 < n ) temp = true; break; case 3: if( tab[ x + 2 ][ y - 1 ] == 0 && x + 2 >= 0 && x + 2 < n && y - 1 >= 0 && y - 1 < n ) temp = true; break; case 4: if( tab[ x + 1 ][ y - 2 ] == 0 && x + 1 >= 0 && x + 1 < n && y - 2 >= 0 && y - 2 < n ) temp = true; break; case 5: if( tab[ x - 1 ][ y + 2 ] == 0 && x - 1 >= 0 && x - 1 < n && y + 2 >= 0 && y + 2 < n ) temp = true; break; case 6: if( tab[ x - 2 ][ y + 1 ] == 0 && x - 2 >= 0 && x - 2 < n && y + 1 >= 0 && y + 1 < n ) temp = true; break; case 7: if( tab[ x - 2 ][ y - 1 ] == 0 && x - 2 >= 0 && x - 2 < n && y - 1 >= 0 && y - 1 < n ) temp = true; break; case 8: if( tab[ x - 1 ][ y - 2 ] == 0 && x - 1 >= 0 && x - 1 < n && y - 2 >= 0 && y - 2 < n ) temp = true; break; } return temp; }
void Wykonaj_Ruch( int nr_przypadku, int x, int y, int ** tab, int nr_ruchu ) { switch( nr_przypadku ) { case 1: tab[ x + 1 ][ y + 2 ] = nr_ruchu; x = x + 1; y = y + 2; break; case 2: tab[ x + 2 ][ y + 1 ] = nr_ruchu; x = x + 2; y = y + 1; break; case 3: tab[ x + 2 ][ y - 1 ] = nr_ruchu; x = x + 2; y = y - 1; break; case 4: tab[ x + 1 ][ y - 2 ] = nr_ruchu; x = x + 1; y = y - 2; break; case 5: tab[ x - 1 ][ y + 2 ] = nr_ruchu; x = x - 1; y = y + 2; break; case 6: tab[ x - 2 ][ y + 1 ] = nr_ruchu; x = x - 2; y = y + 1; break; case 7: tab[ x - 2 ][ y - 1 ] = nr_ruchu; x = x - 2; y = y - 1; break; case 8: tab[ x - 1 ][ y - 2 ] = nr_ruchu; x = x - 1; y = y - 2; break; } }
void Cofnij_Ruch( int nr_przypadku, int x, int y, int ** tab ) { switch( nr_przypadku ) { case 1: tab[ x ][ y ] = 0; x = x - 1; y = y - 2; break; case 2: tab[ x ][ y ] = 0; x = x - 2; y = y - 1; break; case 3: tab[ x ][ y ] = 0; x = x - 2; y = y + 1; break; case 4: tab[ x ][ y ] = 0; x = x - 1; y = y + 2; break; case 5: tab[ x ][ y ] = 0; x = x + 1; y = y - 2; break; case 6: tab[ x ][ y ] = 0; x = x + 2; y = y - 1; break; case 7: tab[ x ][ y ] = 0; x = x + 2; y = y + 1; break; case 8: tab[ x ][ y ] = 0; x = x + 1; y = y + 2; break; } }
void Rekurencja( int nr_ruchu, int x, int y, int ** tab, int n ) { if( nr_ruchu == n * n ) Drukuj( tab, n ); else for( int i = 1; i <= 8; i++ ) { if( Sprawdz_Ruch( i, x, y, tab, n ) == true ) { Wykonaj_Ruch( i, x, y, tab, nr_ruchu ); Rekurencja( nr_ruchu + 1, x, y, tab, n ); if( nr_ruchu == n * n ) return 0; } else { Cofnij_Ruch( i, x, y, tab ); nr_ruchu--; } } }
int main() { int n; int ** tab; printf( "Podaj n - wielkosc szachownicy (n x n): \n" ); scanf( "%d", & n ); tab = malloc( sizeof( int * ) * n ); for( int i = 0; i < n; i++ ) tab[ i ] = malloc( sizeof( int ) * n ); int x, y; printf( "Podaj poczatkowa pozycje skoczka (x - kolumna, y - wiersz)\n" ); scanf( "%d", & x ); scanf( "%d", & y ); Zeruj_Tablice( tab, n ); Rekurencja( 1, x, y, tab, n ); free( tab ); return 0; }
|
|
stryku |
» 2015-01-27 05:28:48 Ciężko Ci będzie znaleźć kogoś kto będzie sprawdzał algorytm Twojego programu. Mi na pierwszy rzut oka trafiły się wycieki pamięci masz takie coś tab = malloc( sizeof( int * ) * n ); for( int i = 0; i < n; i++ ) tab[ i ] = malloc( sizeof( int ) * n );
free( tab );
Więc zwalniasz tylko jeden wymiar. Powinieneś zwalniać wszystko co zaalokowałeś, więc tab = malloc( sizeof( int * ) * n ); for( int i = 0; i < n; i++ ) tab[ i ] = malloc( sizeof( int ) * n );
for( int i = 0; i < n; i++ ) free( tab[ i ] );
free( tab );
Powinno być lepsze |
|
SemiRafista Temat założony przez niniejszego użytkownika |
» 2015-01-27 16:00:26 Dzięki, to był jeden z problemów, ostatecznie udało mi się uporać :) Pozdrawiam. |
|
« 1 » |