Warunek zakonczenia nieskonczonej rekurencji

2016-01-09 23:08

Rejestracja: 5 lat temu

Ostatnio: 4 lata temu

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

Pozostało 580 znaków

2016-01-09 23:13

Rejestracja: 14 lat temu

Ostatnio: 4 dni temu

0

Czy musisz to zrobić za pomocą rekurencji?


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
Nie musze, zrobilem to itereacyjnie. Bylo prosciej i lepiej bo bralem pod uwage polozenie poczatkowe i nie przechodzilem w ciemno wszystkich mozliwosci, ale chcialem wykonac ta implementacje w postaci rekurencyjnej dla treningu zeby zrozumiec mechanic rekurencji. - Janusz2000 2016-01-09 23:19

Pozostało 580 znaków

2016-01-09 23:22

Rejestracja: 14 lat temu

Ostatnio: 4 dni temu

0

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


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2016-01-09 23:56

Rejestracja: 5 lat temu

Ostatnio: 4 lata temu

0

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

Dzieki za pomoc!

Pozostało 580 znaków

2016-01-10 00:31

Rejestracja: 14 lat temu

Ostatnio: 4 dni temu

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.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2016-01-10 16:26

Rejestracja: 5 lat temu

Ostatnio: 4 lata temu

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.

Chyba mozna to zrobic bez tworzenia kopii tablicy w kazdym wywolaniu funkcji, chyba ostatnia instrukcja falsowania na razie nic nie robi tak naprawde. - Janusz2000 2016-01-10 16:30

Pozostało 580 znaków

2016-01-10 16:49

Rejestracja: 14 lat temu

Ostatnio: 4 dni temu

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

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2016-01-10 17:48

Rejestracja: 5 lat temu

Ostatnio: 4 lata temu

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.

A co do sprawdzania warunku () == true to tak po prostu mi zostalo po jakims kursie gdzie wymagano tego dla wiekszej swiadomosci tego co sie robi. - Janusz2000 2016-01-10 17:49

Pozostało 580 znaków

2016-01-10 17:49

Rejestracja: 14 lat temu

Ostatnio: 4 dni temu

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;


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
edytowany 2x, ostatnio: _13th_Dragon, 2016-01-10 17:58

Pozostało 580 znaków

2016-01-10 23:09

Rejestracja: 4 lata temu

Ostatnio: 4 lata temu

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

przecież wycofujemy się przed powrotem: tab[w][k]=false; - _13th_Dragon 2016-01-10 23:35

Pozostało 580 znaków

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