Warunek zakonczenia nieskonczonej rekurencji

0

Witam,

staram sie napisac program, ktory zwraca najkrotsza droge krola z podanego pola szachownicy do jego pola srodkowego dla szachownicy 7x7 (jego pole srodkowe to bedzie (3,3) ).

Mam taki kod:

const int N=7;
int dx[] = {1,0,1,-1,-1,0,-1,1};
int dy[] = {1,1,0,-1,0,-1,1,-1};


bool czyWolne(int w, int k, int i) // funkcja sprawdza czy nie wyszlismy poza szachownice
{
    if ( (w + dx[i] < N) and (w + dx[i] >=0) and (k + dy[i] < N) and (k + dy[i] >=0) )return true;
    else return false;

}
int przejdz(int w, int k, int odleglosc, int mini) // (wiersz z ktorego startuje krol, kolumna, obecna liczba ruchow, najmniejsza obecna liczba ruchow ) 
{
    if (odleglosc >= mini) { return mini; } // jesli liczba krokow do srodka jest wieksza od najmniejszej obecnej drogi to zakoncz instancje 

    if ( (w == 3) and (k == 3) ) // doszlismy do srodka, sprawdzamy czy nasza droga jest obecnie najkrotsza 
    {
        if (odleglosc < mini)
        {
            mini = odleglosc;

        }
        return mini;
    }
    else
    {
        for (int i=0; i<8; i++)
        {

            if (czyWolne(w, k, i) == true)
            {
                return przejdz(w + dx[i], k+ dy[i], odleglosc+1, mini); // wykonujemy ruchy z tablicy ruchow, zwiekszamy licznik ruchow
            }
        }

    }  


} 

Bylbym bardzo wdzieczny za wskazanie jak taka rekurencja mialaby wygladac. Mam chyba problem z operowaniem rekurencja, ktora jest nieskonczona i przerwanie jej w odpowiednim momencie.

Pozdrawiam

0

Czy musisz to zrobić za pomocą rekurencji?

0

W takim razie musisz zaznaczyć pole jako zajęte po wejściu na niego i odznaczyć przy wycofaniu się.

0

Rozumiem, tak tez myslalem tylko liczylem ze jest jakas prostsza droga.

Dzieki za pomoc!

0

Jest kilka innych, nie wiem czy może być coś prostszego niż dodanie dwóch wierszy, ustawienie komórki na true po czym ustawienie komórki na false.

0

Zmodyfikowalem ten kod w nastepujacy sposob:

const int N=7;
int dx[] = {1,0,1,-1,-1,0,-1,1};
int dy[] = {1,1,0,-1,0,-1,1,-1};


bool czyWolne(int w, int k, int i, bool tab[N][N])
{
    if ( (w + dx[i] > N-1) or (w + dx[i] <0)  or (k + dy[i] > N-1) or (k + dy[i] < 0) )return false;
    if (tab[w+ dx[i]][k+dy[i]] == true) return false;
    else return true;

}

int przejdz(int w, int k, int odleglosc, int mini, bool tablica[N][N]) 
{
    bool tab[N][N];
    tab[N][N] = tablica[N][N];

    tab[w][k] = true;



    if ( tab[3][3] == true )
    {
        
        if (odleglosc < mini)
        {
            mini = odleglosc;

        }
        return mini;
    }
    else
    {
        for (int i=0; i<8; i++)
        {

            if (czyWolne(w , k, i, tab) == true)
            {
                return przejdz(w + dx[i], k+ dy[i], odleglosc+1, mini, tab);
            }
        }

        tab[w][k] = false;
        
    }



}

} 

Przy pierwszym wywolaniu przekazuje do funkcji tablice wypelniona falsami, potem wewnatrz kazdej funkcji jest tworzona kopia na ktorej dalej operuje funkcja. W przypadku skonczonej mozliwosci ruchow przechodzi calego fora i zaznacza element tablicy na false.

Nie dziala to jak powinno i nie widze na razie luki w moim rozumowaniu.

0
  1. W ten sposób tablicy nie skopiujesz teraz kopiujesz jeden element na dodatek znajdujący się poza tablicą.
  2. Nie twórz kopi tablicy, tylko przy wejściu zaznaczaj, przy wyjściu odznaczaj.
  3. ==true WTF?
  4. Zrób tablicę większą bool tab[N+2][N+2] zaznacz krawędzie jako true wtedy zamiast czyWolne(...) piszesz tab[w][k]
  5. Przenieś tą czy wolne do środka przejdz
0

Mam problem z ostatnim punktem, przenioslem sprawdzanie na poczatek, a potem wykonuje dopiero ruch:

const int N=7;
int dx[] = {1,0,1,-1,-1,0,-1,1};
int dy[] = {1,1,0,-1,0,-1,1,-1};

bool czyWolne(int w, int k, bool tab[N+2][N+2])
{
        if(tab[w][k]) return false;
        else return true;

}
int przejdz(int w, int k, int odleglosc, int mini, bool tab[N+2][N+2])
{
    if (czyWolne(w , k, tab))
        tab[w][k] = true;

    if (tab[3][3])
    {
        if (odleglosc < mini)
        {
            mini = odleglosc;

        }
        return mini;
    }
    else
    {
        for (int i=0; i<8; i++)
        {
            return przejdz(w + dx[i], k+ dy[i], odleglosc+1, mini, tab);
        }
        tab[w][k] = false;
    }
}

 

Niestety prowadzi to do przepelnienia stosu.

2

To naprawdę straszne, nie stosuj żadnych rad bezmyślnie.

unsigned przejdz(int y,int x,unsigned dist,unsigned mindist,bool tab[N+2][N+2])
  {
   if(tab[w][k]) return mindist;
   if(tab[3][3]) return dist;
   tab[w][k]=true;
   for(int dy=-1;dy<=1;++dy)
     {
      for(int dx=-1;dx<=1;++dx)
        {
         int tmp=przejdz(w+dx,k+dy,dist+1,mindist,tab);
         if(mindist>tmp) mindist=tmp;         
        }
     }
   tab[w][k]=false;
   return mindist;
  }

coś się zagalopowałem - zmienione;

0

hej, tez sie wlasnie ucze rekurencji i trafilem na ten temat. A czy to nie bedzie przypadkiem tak, ze tablica jest zawsze przekazywana przez referencję skutkiem czego kolejne wywolania beda miec szczatki poprzednich i beda sie wypelnialy az do wypelnienia calej tablicy nim przejda wszytkie możliwości? Ten ostatni kod nie dziala (przynajmniej mi), jezeli autor tematu przerobil to tak żeby dzialalo to prosze o wstawke

1 użytkowników online, w tym zalogowanych: 0, gości: 1