Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

[C] Skoczek szachowy

Ostatnio zmodyfikowano 2015-01-27 16:00
Autor Wiadomość
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.

C/C++
#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 ) //(x,y) - aktualne wspolrzedne skoczka
{
    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 ); //odlozenie pamieci dla tablicy reprezentujacej szachownice
    for( int i = 0; i < n; i++ ) //c.d.
         tab[ i ] = malloc( sizeof( int ) * n ); //c.d.
   
    int x, y;
    printf( "Podaj poczatkowa pozycje skoczka (x - kolumna, y - wiersz)\n" ); //przykladowo: prawy górny róg(8x8) to pole (x=8,y=1)
    scanf( "%d", & x );
    scanf( "%d", & y );
   
    Zeruj_Tablice( tab, n );
   
    Rekurencja( 1, x, y, tab, n ); //wywolanie glownej funkcji rekurencyjnej
   
    free( tab ); //zwolnienie miejsca w pamieci
   
    return 0;
}
P-125590
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ś
C/C++
tab = malloc( sizeof( int * ) * n ); //odlozenie pamieci dla tablicy reprezentujacej szachownice
for( int i = 0; i < n; i++ ) //c.d.
     tab[ i ] = malloc( sizeof( int ) * n ); //c.d.

/*...*/

free( tab ); //zwolnienie miejsca w pamieci

Więc zwalniasz tylko jeden wymiar. Powinieneś zwalniać wszystko co zaalokowałeś, więc

C/C++
tab = malloc( sizeof( int * ) * n ); //odlozenie pamieci dla tablicy reprezentujacej szachownice
for( int i = 0; i < n; i++ ) //c.d.
     tab[ i ] = malloc( sizeof( int ) * n ); //c.d.

/*...*/
for( int i = 0; i < n; i++ ) //c.d.
     free( tab[ i ] );

free( tab ); //zwolnienie miejsca w pamieci

Powinno być lepsze
P-125591
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.
P-125613
« 1 »
  Strona 1 z 1