[Pascal] Ciekawy program na zaliczenie...

0

Ostatnio na zaliczenie miałem takie ciekawe zadanie na 5, którego nie zabardzo umiałem i umiem rozwiązać dlatego zrobiłem tylko na 4... :( Dobra ale do rzeczy. Ma się tabelę 15x15 i wypełnia się ją liczbami losowymi! z jakiegoś zakresu (np od 1 do 5, lub innym) i trzeba znaleźć drogę o najmniejszej wartości sumy liczb zawartych w polu przez które sie przechodzi z komórki (1,1) do komórki (15,15) a następnie ją wypisać... Można się poruszać o jedną komórkę w poziomie i pionie.

Ma ktoś pomysł na ten program, pomysł, nie rozwiązanie, nie gotowiec!

0

może sprawdzać wartości następnych możliwych ruchów i przechodzić na pole o najmniejszej możliwej wartości do tego poruszać się albo w lewo albo w dół... ale to chyba nie tak by wyszło.

0123456 algorytm <ort>najkrutszej </ort>drogi: poruszamy się od 0 na pole o kolejnej wartości
1234567 tylko, że ta losowa tablica trochę komplikuje.
2345678
3456789
456789X

0

rekurencyjne wołanie siebie dla 4 sąsiadów z pamiętaniem ścieżki i "kosztu".
po dojściu sprawdzam czy osiągnąłem mniejszy koszt niż wcześniej
być może istnieje dowcipniejszy sposób, takie podejście powinno też zadziałać
parę wierszy, ale jakiej złożoności należy oczekiwać?

0

No właśnie w tym problem, że sor nie dał żadnym wskazówek, mówił,że trzeba mieć SPOSÓB, a nie sprawdzać każdą drogę. Najlpeszym wyjściem też mi się wydawało jest szukanie sąsiedniego pola o najmniejszej wartości i to by się sprawdzało dla 99%, bo ten sposób obala taki przypadek:
user image

Żółta trasa odpada...

0

oczywiście że to jest zły sposób, bo niskie wartości z 'dalszej' drogi od danego punktu mogą rekompensować drogi koszt drogi do niego.
a może jakieś wyznaczniki ? :P myślę również, że w jakiś sposób mogła by się przydać tablica wartości sum z wszystkich kolumn, wierszy, i ukośnie również / .
a tak poza tym to ciekawy problem, zauważcie że nawet dla człowieka znalezienie rozwiązania nie jest oczywiste.

0

Chyba na pierwszy rzut oka powinno się odrzucić sposób polegający tylko na sprawdzaniu minimalnego sąsiada. Ale intuicja to mniej niż dowód.

chym, parę trywialnych wniosków:
minimalna długość ścieżki to N+1, oczywiście że nie musi to być najtańsze rozwiązanie.
macierz jest nieujemna, czyli minimalny koszt to t[1,1]+t[n,n]+"cóś"
czy "cóś" może być zerem? (zabawa polega na minimalizacji "cósia")
może, i wcale nie wymaga to zer w całej tablicy (poza t[1,1] i t[n,n])

tak na czuja to jest to jakoś podobne do problemu szukania podciągu o maksymalnej sumie

ciekawe, na ile sposobów można przejść od [1,1] do [n,n]?
na początek to właśnie pobadam

0

Na mój gust, rozwiązanie to potraktowanie tej tablicy jako grafu i zastosowanie algorytmu Dijkstry (czyli wyszukania najkrótszej (oczywiście z uwzględnieniem "wag") ścieżki).

0

Dokladnie o tym myslalem, bylo to troche dawno bo chyba na drugim semestrze ale mnie sie zdaje ze tych algorytmow na szukanie najkrotszej drogi bylo kilka. Poszperaj.

0

Nauczyciel raz juz dał na lekcji taki program do zorbienia, nikt nie miał pomysłu, a nauczyciel nie dał wskazówek... Te liczby mogą być z każdego zakresu również od 0. Przecież dobry program powinien działać dla każdego zakresu lokowanych w tablicę liczb.

Intrygujące zadanie co? :D

mgr.Dobrowolski, po magister (mgr) nie stawia się kropki :)

0

na pewno nie trzeba sprawdzać wszystkich dróg do końca, bo po przejściu 1szej w ten sposób, mogę przy następnej w pewny momencie sprawdzić:
'mając już taką sumę, nawet idąc najkrótszą możliwą stąd drogą zakładając że po drodze będą najniższe z możliwych wartości, otrzymana suma całkowita będzie większa od sumy z najlepszego jak do tej pory (czyli z 1szego) wyniku'

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