Diff for ''

Revision 118
Author:
black
Time:
2022-08-26 02:23
Revision 2
Author:
black
Time:
2025-04-01 20:18
Comment:
Smazat neplatnou nabídku práce
Deletions are marked like this. Additions are marked like this.
Line 1: Line 1:
Oficiální stránky [http://ktv.mff.cuni.cz/ katedry tělesné výchovy], konkrétní sporty viz. níže. # Vypracovani semestralky
Line 3: Line 3:
= Historický šerm =
* klub historického šermu se zaměřením na volný bojový šerm Duelanti od svatého Rocha přijímá nováčky
* cvičí se 2x týdně pondělí a středa od 20:00 v tělocvičně ZŠ Lupáčova, Olšanské náměstí Žižkov
* první měsíc bývá zdarma, potom cca 500kč / měsíc, pro nováčky se na první půlrok najde i nějaký ten meč
* kontakt: https://www.facebook.com/duelanti/
<{ForumPost(poster="aliandroo", timestamp=2010-11-27 02:40:05)}>
Potreboval bych pomoc s vypracovanim teto semestralky:
  
Mate-li zajem napiste mi [aliandro@seznam.cz](mailto:aliandro@seznam.cz)
  
Zadání
  
Úkolem je realizovat program, který dokáže vypočítat efektivní průchod labyrintem s diamanty.
  
Vstupem programu je mapa labyrintu. Mapa je předaná v textové podobě na standardním vstupu. Pro jednoduchost předpokládáme, že mapa má obdélníkový tvar. V mapě jsou naznačené diamanty (znaky *), nepřekonatelné zdi (znak #) a volné prostranství (znak mezera). Labyrint má jediný vchod v některé z obvodových zdí. Zadávání labyrintu probíhá po řádcích. Každý řádek vstupu představuje jeden řádek mapy. Zadávání celého labyrintu je signalizováno koncem souboru (feof(stdin) je aktivní).
  
Výstupem programu je informace o tom, kolik diamantů lze z labyrintu odnést a dále informace o tom, kolik kroků v labyrintu je na to nejméně potřeba. Předpokládáme, že se můžeme pohybovat pouze ve směru vlevo/vpravo/nahoru/dolů, kde každý pohyb (o jedno políčko) je právě jeden krok. Cesta vždy začíná a končí vstupem do labyrintu.
  
Program musí být schopen detekovat nesprávný vstup. Pokud je zadaná neplatná mapa, program vypíše chybové hlášení a ukončí se. Formát chybového hlášení je zřejmý z ukázek níže. Za chybu je považováno:
  
    *
      v zadání labyrintu byly jiné znaky než mezera, hvězdička, křížek a odřádkování,
    *
      labyrint není obdélníkového tvaru,
    *
      labyrint není obehnán zdí,
    *
      do labyrintu není žádný vstup nebo naopak více než jeden vstup,
    *
      v labyrintu je celkem více než 20 diamantů (pro jednoduchost předpokládáme toto omezení).
  
Program je testován v omezeném prostředí. Je omezena doba běhu i dostupná paměť. Doba běhu je nastavena tak, aby vyhovělo i řešení hrubou silou bez heuristik. Výjimkou je bonusový test, který řešení bez alespoň základní heuristiky (zahazování neperspektivních průchodů) nezvládne časově.
Nápověda
  
    *
      Nejprve si spočtěte matici vzdáleností mezi jednotlivými diamanty a mezi vstupem a diamanty. Zde se hodí algoritmus procházení do šířky (BFS) ve variantě semínkového vyplňování (seed fill).
    *
      Sestavte cestu, která začíná a končí vstupním bodem a prochází všemi diamanty. Takových cest existuje mnoho (počet_diamantů faktoriál), postupně vypočtěte jejich délky (vzdálenosti znáte z matice vzdáleností vypočtené v předchozím bodě) a určete nejkratší z nich.
    *
      Pro vygenerování všech možných cest budete potřebovat rekurzi.
    *
      Může se stát, že některé diamanty nebudou dostupné, takové musíte z výpočtu cest vyloučit.
    *
      Popsané řešení (hrubou silou) není příliš rychlé. Proto je volen malý rozsah úlohy (do 20 diamantů), aby výpočet skončil v rozumné době. Řešená úloha (nalezení nejkratší cesty mezi diamanty) je optimalizační variantou problému obchodního cestujícího (TSP - traveling salesman problem). Úloha TSP patří mezi tzv. NP-úplné problémy, tedy problémy, pro které neznáme efektivní algoritmus jejich řešení. Úlohy tohoto typu dokážeme řešit pouze zkoušením všech možností, což mívá vysokou operační složitost (zde například faktoriální). Řešení bývá možné urychlit heuristikami, kdy se preferují perspektivní řešení (zde např. krátké cesty), naopak neperspektivní možnosti řešení (zde např. velmi dlouhé cesty) se buď vůbec nepočítají nebo se odkládají na později.
    *
      Referenční řešení používá dvě jednoduché heuristiky - pokud v průběhu vytváření cesty mezi diamanty zjistí, že cesta je delší než dosavadní nalezené minimum, dále již cestu nedokončuje a začne vytvářet cestu jinou. Druhou možností je preference cesty směrem k nejbližšímu diamantu (při vytváření cesty se první zkusí nejbližší diamant). Tím se program relativně brzy dostane k rozumné délce cesty (ale pozor - takto nalezená cesta nemusí být nejkratší). Výhodné je obě popsané heuristiky spojit.
  
Ukázka práce programu:
Line 9: Line 47:
= Plavání =
* matfyzáčtí plavci nejsou žádný B-čka: [http://plavani.matfyz.cz]
* v [[SCUK|sportovním centru Univerzity Karlovy]] v hodinách pro veřejnost za 80 Kč na ISIC - [http://bazen-hostivar.717.cz/ Plavecký bazén Hostivař] - neoficiální, přesto stále aktualizované stránky
* Plavecký bazén na Výstavišti [http://www.incheba.cz/bazen zde]
* [http://www.pspodoli.cz/ plavárna v Podolí]
** možnost plaváni ve vnitřním krytém bazénu i ve vnějším, který je přes zimu vyhřívaný (kolem 27 stupňů)
** k dispozici je v ceně také pára (aka mokrá sauna)
* ostatní na [http://www.koupani.cz/koupani/]
    Zadejte mapu:
    # ######
    # * *#
    # * #
    ########
    Diamantu: 3
    Delka cesty: 14
    
    Zadejte mapu:
    ##############
                 #
    ############ #
    #* #
    ##############
    Diamantu: 1
    Delka cesty: 50
    
    Zadejte mapu:
    ##################### ######
    #* # #
    ############ # #############
    # # # #
    # ############ # ######### #
    # *# # #
    # ############## # #########
    # # #
    # ######################## #
    #* * * #
    ############################
    Diamantu: 5
    Delka cesty: 148
    
    Zadejte mapu:
    #############
    #*# * # * #*#
    # # # # # # #
    # * # * # * #
    ###### ######
    Diamantu: 7
    Delka cesty: 46
    
    Zadejte mapu:
    ############################
    # * * #
    # ######## #
    # * # * # #
    # # ###### #
    # * * #
    # ############ * #
    # # * * # #
    # # * * # #
    # * ############ * #
    # * #
    ###################### #####
    Diamantu: 10
    Delka cesty: 86
    
    Zadejte mapu:
    #############
    # * # #
    # # #
    # # *#
    ###### ######
    Diamantu: 1
    Delka cesty: 12
    
    Zadejte mapu:
    ##### #######
    # #
    # #
    # *#
    ###### ######
    Nespravny vstup.
    
    Zadejte mapu:
    #############
    # #
    # a #
    # *#
    ###### ######
    Nespravny vstup.
    
Line 18: Line 130:
= Squash =
* centrum [http://www.squashe.cz/index.php?mm=hastal Haštal] - [http://www.squashe.cz/index.php?mm=hastal&s=2 ceny] pro studenty 130,- za kurt a hodinu (Pá, So, Ne večer dokonce 110,-)
* [http://www.mybox.cz/squash-holesovice/ Squash Holešovice] - z Nádraží Holešovice cca 5min na zastávku Maniny (tram #12), [http://www.mybox.cz/squash-holesovice/cenik.htm ceny] pro studenty 130,- za kurt a hodinu
Line 22: Line 131:
* [http://www.squasharbes.cz/Default.aspx/ Squash Arbes] - Arbesovo náměstí, pro informatiky blízko ze školy, studentská cena 170,- za kurt a hodinu <{/ForumPost}>
Line 24: Line 133:
= Bruslení =
* zimní stadion [http://www.nikolajka.eu/ Nikolajka] - Anděl
** cena: 40,- Kč
** - mnoho lidí
* stadion na [http://www.stvanice.cz/ Štvanici]
** cena: 80,- Kč
** + kulturní zážitek
* stadion pri OC[http://www.icearena.cz/index.php Letnany]
** cena: 80,- Kč
** + kvalita ledu
** + servis
** - vzádlenost od Troje
* [http://www.incheba.cz/main.php?pageid=56 malá sportovní hala] na pražském výstavišti
** cena: 50,- Kč
** + dostupnost z Troje
** - žádný bufet ani automat
* bruslení [http://supermapy.centrum.cz/map.php?ql=&qlc=-1&bbox=3460802.697119341:5552560.1201646095-3462552.697119341:5553950.037860082&mapsize=1&poi=2,6,7,8&stred=0:0&origin=&sid=&okoli=&search_flag=6 v mrtvém rameni Vltavy] :)
** + stačí zajít na Palmovku a odtud seběhnout k vodě
** + cena :)
** - závislost na počasí
* [http://www.praha13.cz/ruzne/stadion/ školní zimní stadion Bronzová] (metro B, stanice Lužiny)
** cena: 30,- Kč za hodinu, 50,- Kč za 3 hodiny
** - v sezóně 2005/2006 mimo provoz
* stadion [http://www.hckobra.cz/ HC Kobra Praha]
** cena: 60,- Kč
** otevřeno pro veřejnost: So, Ne - 13:15 až 15:15
** - vzdálenost (viz [http://www.mapy.cz/?query=Loc:%2050%C2%B01'53.17%22N,14%C2%B025'38.8%22E&zoom=16&mapType=base&centerX=133089632&centerY=135753376#centerX=133087791@centerY=135753054@typ=base@zoom=15@vizType=none@vizIds=none mapa])
** - hodně lidí