Fórum studentů MFF UK

Tak napřed si připravit data z těch souborů do ptřebnejch polí. To jsem dělal ukládáním koncertů do spojáku, na každej koncert navěsit název písničky, město dát do matice vzdáleností a přiřadit mu číslo od 1 do 20, písničku s časem zahešovat. Pak projít ten spoják koncertů a u každýho koncertu spočítat délku (po jednom průchodu už mám všechny písničky nahešovaný, tak znám jejich dýlky) a pak pro každý město a den vybrat nejdelší koncert.
Vedle toho na města spustit třeba floyd-warschalla.
Uvolnit pamět.
Udělat si výše zmíněnou trojrozměrnou tabulku.
A začínám vyplňovat:
Jednu for cyklama přes všechny dny, přes všechny města, přes všechny kilometry.
V prvním kroku začínám ve dni 1, v praze, a na nula kilometrech. Udělám for cyklus přes všechny města (včetně toho, kde teď jsem) a uložím to pole indexovanýho [den+1, město_do_kteryho_jdu, kilometry navýšený o vzdálenost kterou jsem urazil/může zůstat i stejný] hodnotu navýšenou o to, co v danej den a pro daný město dokážu slyšet. Pokud tam už něco je, tak vyberu samozřejmě to, co má větší hodnotu.

Na konci prohledám ve dni 92 všechny města a všechny možný kilometry.
Vyhledávání cesty zpátky:
Položka toho trojrozměrnýho pole bude záznam, kterej bude mít nejen celkovej čas, ale i město, odkud sem přišel. Pak to jednoduše proskáču až do dne 1.

Zdar,
nenašla by se nějaká dobrá duše, která by ten algoritmus vyžívající trojrozměrnou tabulku blíž popsala??? Asi si to jen nedokážu představit jak by to vypadalo...
Dík...

Ba co líp, bylo to exponenciální podle počtu koncertů .. nevim proč ale tabulka města*dni se mi už nevešla do paměti .. moje řešení by si nepustilo ani moje pravnouče

No jestli to bylo exponenciální tak, že si zkoušel pro každej den všechny města, ve kterejch se hraje, tak by ses k výsledku nedostal ani kdyby se počítače každej rok 2x zrychlovali a pár let před smrtí to pustil na tom nejlepším, ne?

zatraceně až teď mi došlo, že sem všechno cpal do 20kB místo MB .. aspon že vim, že je to za 3 .. btw co je tak špatnýho na exponenciálnim prohledávání do hloubky

postup pres 3-rozmernou tabulku v dynamickem programovani je spravny. Naopak naprosto chybny je postup pres hledani do hloubky (backtracking), za coz mi dal trojku a mohl jsem byt rad. Topfer je ale hodny clovek, na teorii se snazi najit neco, cemu rozumite. Jen je potreba mluvit jasne a formulovat presne.

Já sem měl celkem dobrej pocit a měl jsem to se složitostí O(počet kilometrů x počet dní x počet měst x počet měst) řešený přes dynamický programování - hlavní nástroje trojrozměrný pole [den,mesto,kilometr] s longem celkovy_cas a bytem odkud, matice nejkratších vzdáleností mezi městama a pole [mesto,den] obsahující délku nejlepšího koncertu a jeho název. Ale správností si budu jistej, až mi to potvrdí na ústním, doufejme že Holan xD (btw. novej účes i tričko, všimli jste si? )

Zadával Holan, úloha koncert
http://forum.matfyz.info/viewtopic.php? ... cert#p8270
http://www.martinvseticka.eu/index.php? ... se&page=40
nikde není vyloženě napsané řešení .. má někdo nějaké vyloženě dobré?
ještě pamět byla omezená na 20 MB místo 5MB .. odpovídá přesně na tabulky z návodu k řešení, byla trochu pozměněna čísla