Wątek przeniesiony 2019-01-24 14:28 z Kosz przez aurel.

algorytm zachłanny poszukiwania drogi

0

mając taką macierz NxN gdzie N = 5

5
2 3 4 2 5
5 2 1 2 2
2 4 2 2 3
1 2 2 4 3
3 2 1 2 3

muszę z lewego dolnego rogu dojść do prawego górnego rogu normalnie bym to zrobił

for(int i = 0; i < N; i++)
        {
            cout <<  i << " " << N-1-i << '\n';
        }

i droga by wyglądała

3 2 2 2 5

ale ze jest to algorytm zachłanny muszę poruszać się drogą po mniejszych wartościach np.

3 1 2 4 2 1 2 2 5

mając taki przepis proszę o pomoc w napisanu go w c++
1) ustawiasz start na [N - 1][0] => lewy, dolny róg.
2) sprawdzasz, który z kierunków zawiera miejszą wartość - czy w górę, czyli [N - 1 - 1][0], czy w prawo, czyli [N -1][1]
2a) może nastąpić przypadek, że po drodze dojdziesz do wiersza 0, albo kolumny N - 1. Od takiego momentu możliwy jest tylko ruch w prawo (dla wiersza 0), albo w górę (dla ostatniej kolumny), musisz to uwzględnić w algorytmie.
3) przestawiasz start na znaleziony w punkcie 2 indeks, i powtarzasz krok 2 póki nie dojdzie do [0][N - 1] => prawy, górny róg

0

No dobra, wiesz jak to rozwiązać - to dlaczego tego nie zapiszesz w kodzie?

0

Właśnie nie wiem jak to przełożyć na kod w c++, to prawda MasterBLB pomysł zaczerpnąłem od Ciebie, a że uczę się o algorytmie zachłannym bardzo pomógł mi post w którym brałeś udzial, prosiłbym o pomoc jeszcze raz nie za bardzo rozumiem te zapisy [N - 1][0] itp.. w sensie rozumiem ale nie wiem jak przełożyć je na kod

0

Pytanie pomocnicze, czym może być N w zaproponowanym rozwiązaniu?

0

tylko ze problem jest zupełnie inny niż koleżanki bo ona miała problem z otwarciem pliku mi natomiast zależy tylko na algorytmie a dokładniej pomocy w przelozeniu go na kod..
przemyslowiec N jest to wielkosc macierzy kwadratowej

rozumiem to zacząc w ten sposób:

int tab[100];
        for(int i=0;i<N;i++)
        {
            tab[0]=tablica[N-1][0];
            if(tablica[N-1-1][0]<tablica[N-1][1])
                cout<<tablica[N-1-1][0];
                else cout<<tablica[N-1][1];
        }
}

i wlasnie uwazam ze to co pisze jest bez sensu, a nie potrafie go lepiej przelozyc na poprawny kod dlatego proszę o pomoc...

1

Zauważ, że w tym kodzie:

        for(int i=0;i<N;i++)
        {
            tab[0]=tablica[N-1][0];
            if(tablica[N-1-1][0]<tablica[N-1][1])
                cout<<tablica[N-1-1][0];
                else cout<<tablica[N-1][1];
        }

N razy odwołujesz się do dokładnie tych samych pól tablicy. N się nie zmienia przecież.

0

Przez N oznaczyłem wielkość kwadratowej tablicy 2-wymiarowej NxN, od tego zacznijmy. W takim układzie indeksy wierszy oraz kolumn zawierają się w <0, N - 1> => stąd wspomniane w przepisie [N - 1][0] => lewy, dolny róg a to dlatego, że [N - 1][0] oznacza maksymalny możliwy wiersz oraz pierwszą kolumnę.

0

Zatem nalezało by zacząc od

for(int i=N-1;i>=0;i--)

i nie wiem czy druga pętla teraz jest potrzebna zaczynajaca od 0 czy może od razu warunek sprawdzający ?

0

Potrzebne jest coś w rodzaju wskaźnika na początkowy element oraz możliwe, iż dodatkowych zmiennych, tak abyś dla tablicy 5x5 mógł zrobić porównanie:
pointer[4 - 1][0] < pointer[4][1]? Jeśli tak to pointer nastaw na [4 - 1][0], jeśli nie to na [4][1]. I powtarzasz to aż pointer będzie wskazywał na [0][4]

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