x-kom hosting

Przekazywanie tablicy w funkcji rekurencyjnej

Przejdź do rekomendowanej odpowiedzi Autor: rafalluz ,
kamil-magic
utworzono
utworzono (edytowane)

Witam, 

 

mam nastepujacy problem: chce napisac rekurencyjnie funkcje ktora zwroci mozliwa najkrotsza droge z szachownicy 7x7 z zadanego miejsca poruszajac sie krolem. 

 

Mialem nastepujacy 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, 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])
{

    tab[w][k] = true;

    if (tab[4][4])
    {

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

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


        }
        tab[w][k] = false;
    }
        return mini;

}

Stworzylem sobie tablice typu bool o wymierach N+2, krawedzi oznaczylem jako true, czyli zajete. Przekazuje do tej funkcji taka tablice z false na polach szachownicy i true wszedzie dookola. W momencie kiedy dochodze do momentu kiedy nie mozna wykonac juz ruchu, funkcja cofa ostatni i idzie dalej inna droga. 

 

Wydaje mi sie, ze problemem jest to, ze tablice zawsze sa przekazywane przez referencje - czyli dzialam caly czas na jednej tablicy, do ktorej mam adres. W momencie kiedy dochodze do  jakakolwiek rozwiazania i wracam do instancji nizej aby wykonac inna wersje tej drogi to tablica na ktorej wtedy operuje zawiera juz ta wczesniejsza droge z dojsciem do srodka. 

 

Nie wiem czy dobrze to interpretuje, nie prosze o gotowy kod tylko wyjasnienie mi tej kwestii jak to ma dzialac. 

 

Z gory dziekuje!

rafalluz
komentarz
komentarz

Przekazując tablicę jako parametr, tak naprawdę przekazujesz wskaźnik na jej pierwszy (zerowy) element + informacje o rozmiarze. Przekazywanie przez wartość tworzy kopię przekazanej wartości na zakres wywołania funkcji, ale po wyjściu z niej masz taką wartość, jak pierwotnie. Czyli jak przekażesz int x = 42, zmienisz w funkcji 43 i wyjdziesz z funkcji, to masz dalej 42.

 

ALE

 

Gdy przekażesz int* x (wskaźnik), gdzie wartość przypisana pod adresem x jest 42, zmienisz w funkcji wartość pod tym adresem na 43 i wyjdziesz, to dalej będziesz miał 43 pod tym adresem.

 

Czyli kluczowe jest, że żadna kopia całej tablicy nie jest robiona z automatu, by szybko cofnąć zmiany. Jedynie kopia wskaźnika, ale to bez znaczenia, bo wskaźnika do tablicy i tak nie zmieniasz.

 

Co więc zrobić? Dwie opcje:

 

1)Własnoręcznie twórz kopie tablicy przy każdym wywołaniu, pamiętając o ich kasowaniu, gdy nie są potrzebne. Niezalecane, gdy rekurencja jest głęboka, bo mnożenie się tych tablic zajmie mnóstwo pamięci

 

2)Olej rekurencję jawną i trzymaj informację o dodanych ruchach w odpowiedniej strukturze danych (stosie). Wtedy masz jedną tablicę, a na stos wrzucasz w odpowiedniej formie dane o ostatnim ruchu. Jak wejdziesz w "ślepą uliczkę", to ściągniesz odpowiednią ilość danych ze stosu i cofniesz zapisane w nich zmiany.

  • Dobra wypowiedź 1
kamil-magic
komentarz
komentarz

Dziekuje bardzo za szeroka odpowiedz, czyli reasumujac nie da sie zrobic rekurencji jawnej bez kopii tablic? 

  • Rekomendowana odpowiedź
rafalluz
komentarz
komentarz

W opcji 2) nie robisz pełnej kopii, tylko minimalną informację o tym, jaki ruch wykonałeś w danym wywołaniu (np. współrzędne). Jest to trochę bardziej złożone, ale efektywniejsze. Cykl wygląda mniej więcej tak:

 

Sprawdź, czy spełniono warunek stopu

Jak nie, to oblicz nowy ruch, zapisz ruch w tablicy i dodaj informacje o ruchu na stos.

Jak ruch jest niedozwolony/nieoptymalny, ściągnij ze stosu informację o ruchu i wymaż z tablicy

Wróć do punktu 1

 

Nawet jawnie nie musisz wołać rekurencyjnie, bo de facto stos to załatwia. Możesz te kroki opakować jakąś pętlą while i będzie.

Wciąż szukasz rozwiązania problemu? Napisz teraz na forum!

Możesz zadać pytanie bez konieczności rejestracji - wystarczy, że wypełnisz formularz.

×
×
  • Dodaj nową pozycję...

Powiadomienie o plikach cookie

Strona wykorzystuje pliki cookies w celu prawidłowego świadczenia usług i wygody użytkowników. Warunki przechowywania i dostępu do plików cookies możesz zmienić w ustawieniach przeglądarki.