Vitajte na stránke krúžku programovania pre začiatočníkov na gymnáziu Jura Hronca v Bratislave
Novinky | Pascal | Úlohy | Prográmky | Algoritmy | Linky
Na tomto mieste budú pribúdať realizované programy algoritmického charakteru Prvá algoritmická vec, ktorú som vám predstavoval. Binárne vyhladavanie nám slúži napríklad na zistenie prítomnosti dákeho čísla v utriedenom poli v čase log n. Vyfarbovanie mapy za účelom hľadania počtu ostrovou a ich označovania. K dispozícii sú aj nejaké vzorové mapy (mapa1, mapa2, mapa3, mapa4). Program je dobre okomentovaný a nie je vôbec zložitý. Je v ňom použitý algoritmus prehľadávania do hĺbky, ktorý ma časovú zložitosť lineárne závislú od veľkosti ostrova, v ľudskej reči je to Šíkra*Výška mapy (štandardné značenie N*M). Ďalšia realizácia prehľadávania do hĺbky. Na prácu týchto programov potrebujete bludiská, tie sú tu: bludisko1, bludisko2, bludisko3, bludisko4. V týchto bludiskách vieme riešiť nasledujúce úlohy - v prvom programe, ktorý je plnohodnotne okomentovaný, máme zisťovať existenciu cesty z našej počiatočnej pozície k pokladu (a tu je k dispozícii pedagogická verzia zobrazujúca pohyb a postup prehľadávania - najlepšie ozrejmí fungovanie programu). V našom druhom programe sme dostali za úlohu zistiť vzdialenosť medzi pokladom a nami, čo sme opäť realizovali pomocou prehľadávania do hĺbky - tu. Ešte treba podotknúť, že pokiaľ na prvú úlohu môžeme označiť náš algoritmus za optimálny, v tej druhej úlohe to neplatí, existuje oveľa lepší postup, ako to naprogramovať, pretože prehľadávanie do hĺbky robí veľa vecí zbytočne. Časom si tento postup samozrejme ukážeme, je o niečo zložitejší. Okrem iného sme sa bavili aj o triediacich algoritmoch a predstavili si možno najrýchlejší z nich (aspoň sa za taký v smrteľníckych kruhoch považuje) - Quicksort. Tu si ho môžete stiahnuť implementovaný. Treba samozrejme vedieť ako pracuje, to môžete dostatočne pedagogicky nájsť v tomto materiáli (posledné tri stránky), poprípade na tomto webe. Tu je zadanie úlohy so slovenskou dedinou a krčmou, ktorú sme robili v januári pred olympiádou. Vzorák nie je, ale môžete pozrieť sem na úlohu číslo 1 a potom sem, je to rovnaký, len v niečom zložitejší príklad. Naprogramovaný zásobník a fronta. Z grafových algoritmov: Prehľadávanie do hĺbky, keď si graf pamätáme v matici (N na druhú), a pre každý vrchol zoznam jeho okolia (N+M). Tu je aj verzia, ktorá vypisuje nájdenú cestu. Ďalej sme si spomínali, ako pracovať s disjunktnými množinami (to sú také, ktoré majú prázdny prienik). Na to nám slúži Union-Find, ktorý máte naprogramovaný tu a popísaný v materiáli nižšie. Venovali sme sa aj problému hľadania najkratšej cesty v neohodnotenom grafe, na čo je najvhodnejšie prehľadávanie do šírky, pracujúce v peknom čase N+M. Tu je verzia vypisujúca aj trasu, takže pozrite. Toto je asi najťažšia vec, ktorú sme robili alebo budeme robiť. Pokračovalo sa Dijkstrovým algoritmom, ktorý hľadá najkratšiu (najlacnejšiu) cestu v ohodnotenom grafe. Ukazovali sme si ho na programe pracujúcom s cestnou mapou Slovenska, stiahnute tu. A ešte samozrejme dáta, bez nich to nepôjde, sú k dispozícii tu. Dijkstrov algoritmus v obyčajnej implementácii dosahuje zložitosť N na druhú, sú ale aj iné implementácie, dočítate sa o nich napríklad na liahni. Na konci sme sa ešte dostali k princípu ťaháku, spomínal sa príklad menom Parlament a ako ho efektívne riešiť. To je obsiahnuté v tomto programe - mantinelová verzia/nemantinelová. Riešenie úlohy s depami zo záverečnej súťaže. Tu je link na materiál k teórii grafov.
Vytvoril Zemčo, garl(at)azet(dot)sk, ICQ# = 233685327