[[programovani-i|Programování I - cvičení]] ====== Domácí úlohy ====== Úlohy odevzdávejte do [[https://codex.ms.mff.cuni.cz/|CodExu]]. Na nejasnosti se prosím ptejte mailem, rád je upřesním. Úlohy mají vetšinou dva termíny. Při úspěšném odevzdání úlohy do prvního termínu můžete dostat plný počet bodů, při odevzdání mezi prvním a druhým termínem maximálně počet bodů specifikovaný pro druhý termín. Po uplnynutí druhého termínu žádné body za úlohu nedostanete. Výsledky jsou v tabulce [[lide#bodovani|bodování]]. Úvodní mezery ve výpisech vstupů a výstupů slouží pouze jako odsazení, nejsou součástí reálných dat. ===== Informace ===== Úlohy psané v Pascalu je možno nyní do CodExu odevzdávat pouze s příponou .pas a budou se vykovávat [[http://www.freepascal.org|FreePascalem]]. Borland Pascal a GNU Pascal se již nebudou používat. Pro vás to bude znamenat, že úlohy před odevzdáním musíte odladit ve FreePascalu. ===== Palindromní věta ===== * **Odevzdávání uzavřeno**, max. 2 body. * 1. termín: 13.11.2009 0:00, max. 2 body. * 2. termín: 20.11.2009 0:00, max. 1 bod. ==== Zadání ==== Úkolem je určit zda zadaný text je nebo není palindrom, tj. je stejný ať ho čteme popředu nebo pozpátku. Přitom se neberou v úvahu mezery mezi slovy. **Vstup:** ''TEXT'' ... string **Výstup:** ''TRUE/FALSE'' ... string Předpoklady pro vstupní slovo: může se skládat pouze z malá písmen anglické abecedy a mezer, je celé na jednom řádku, je dlouhé maximálně 100 znaků. Výstupem je ''TRUE'', pokud vstupní slovo je palindrom, jinak ''FALSE''. Vstupní slovo načtěte z klávesnice, výstup přijde na obrazovku. Samotný výpočet implementujte ve funkci tvaru: function palindrom(slovo:string) : boolean; Práci se vstupem a výstupem implementujte v hlavním bloku programu. Inspirace pro testování: [[http://www.cs.arizona.edu/icon/oddsends/palinsen.htm|mnoho palindromních vět]]. ==== Příklady ==== Vstup: radar Výstup: TRUE Vstup: abc def e dcb a Výstup: TRUE Vstup: abcdef Výstup: FALSE **Hint:** Procedura writeln(), kde parametrem je výraz typu boolean, vypíše TRUE nebo FALSE. Př. writeln(2 > 5) vypíše FALSE. ** Hint:** Pro uložení vstupího slova použijte typ string a slovo si zpracujte do příjemnějšího tvaru (buď před samotným testováním nebo v jeho průběhu). **Hint:** Uvažujte i okrajové případy, např. hodně krátké slovo. ==== Řešení ==== program palindrom; { Test if the given string is a palindromic sentence. Ie. it is the same when read from the beginning or from the end, assumming that spaces are ommited. Author: Bohumir Zamecnik Date: 2009/10/19 } function is_palindrom(text : string) : boolean; var n, {length of the input text} front, {pointer which scan the text from the beginning, 1..n} back {pointer which scan the text from the end} : integer; begin n := length(text); front := 1; back := n; {such a loop condition does correctly handle the case of when the remains only one character, which itself is considered palindromic} while (front < back) do begin {skip spaces} while (text[front] = ' ') do begin front := front + 1 end; while (text[back] = ' ') do begin back := back - 1 end; {test palindromicity for two opposite characters} if (text[front] <> text[back]) then begin {the two characters do not correspond, so this is definitely not a palindrom} is_palindrom := false; exit end; front := front + 1; {move the front scanner to the right} back := back - 1; {move the back scanner to the left} end; is_palindrom := true end; var text : string; begin readln(text); writeln(is_palindrom(text)); end. ===== Numerické integrování ===== * **Odevzdávání uzavřeno**, max. 3 body. * 1. termín: 13.11.2009 (0:00), max. 3 body. * 2. termín: 27.11.2009 (0:00), max. 1 bod. ==== Zadání ==== Úkolem bude spočítat přibližnou hodnotu určitého integrálu pevně dané funkce na daném intervalu. Ač to může vypadat složitě, je to docela jednoduché :) Takže žádný strach. Hodnota integrálu odpovídá ploše omezené funkcí, osou X a hranicemi intervalu. Použijeme maličko upravenou [[http://cs.wikipedia.org/wiki/Riemann%C5%AFv_integr%C3%A1l|Riemannovu metodu]], tedy plochu si rozkrájíme na úzké proužky, které budeme aproximovat pomocí obdélníků. Celková plocha pak bude součtem ploch těchto obdélníčků. Všechny obdélníčky budou stejně široké a jejich šířku (delta) bude možno zadat. Pro každý proužek budeme používat dva obdélníky, jejichž výšku (a tedy i plochu) zprůměrujeme. Jeden bude vysoký jako hodnota funkce v levém kraji prouku, druhý jako hodnota funkce v kraji pravém. Všimněte si, že jedna z hodnot se použije ve dvou po sobě následujících proužcích, můžete ji zkusit počítat pouze jednou. Pamatujte si mimo jiné: průběžný součet plošek, aktuální pozici na ose X. Funkce, která se bude vyhodnocovat: ''cos((x-2)*PI/2)+1'' Na celém R je spojitá, Riemannovsky integrovatelná a kladná. **Vstup:** ''A B n'' **Výstup:** ''plocha'' * A ... začátek intervalu * B ... konec intervalu * n ... počet proužků, na které se interval rozdělí (delta = |[A;B]| / n) * plocha ... přibližná hodnota integrálu na 4 desetinná místa (A, B, plocha je typu real, tj. racionální číslo, n je typu integer) Můžeme předpokládat, že A < B. Hlavní počítací funkce bude ve tvaru: function integral(a, b:real, n:integer) : real; **Tip:** všimněte si, že čím menší je delta, tím déle bude výpočet trvat, ale zase tím přesnější výsledek dostaneme. **Tip:** ''writeln(abc:2:4)'' zformátuje reálnou proměnnou abc na dvě celá místa a 4 desetinná místa. ==== Řešení ==== program riemann_integral; { Numericke integrovani spojite funkce na zadanem inervalu. Author: Bohumir Zamecnik Date: 2009/10/20 } const PI = 3.1415926535; {zadana funkce, ze ktere se pocita integral} function funkce(x:real) : real; begin funkce := cos((x - 2) * PI/2) + 1; end; function integral(a, b : real; n : integer) : real; var plocha : real; {castecny soucet plochy integralu} delta : real; {sirka jednoho prouzku} x : real; {aktualni pozice na ose X, mezi hranicemi A a B intervalu} {y_prechozi : real;} y1, y2 : real; swap : real; meze_prohozene : boolean; {meze jsou prohozene} begin meze_prohozene := false; if (a > b) then begin swap := a; a := b; b := swap; meze_prohozene := true; end; delta := (b - a) / n; x := a; plocha := 0; y1 := funkce(x); while (x <= b) do begin x := x + delta; y2 := funkce(x); plocha := plocha + ((y1 + y2) / 2) * delta; y1 := y2; end; if meze_prohozene then begin plocha := -plocha; {prohozene meze daji zaporny integral} end; integral := plocha; end; var a, b : real; {dolni a horni meze intervalu integrace} n : integer; {pocet aproximacnich prouzku} begin readln(a, b, n); writeln(integral(a, b, n):2:4); end. ===== Počet dní mezi dvěma daty ===== * **Odevzdávání uzavřeno**, max. 3 body. * 1. termín: 13.11.2009 (0:00), max. 3 body. * 2. termín: 27.11.2009 (0:00), max. 1 bod. * Platí detaily zadání z CodExu. ==== Zadání ==== Úkolem je spočítat počet dní, které uplynuly mezi dvěma zadanými daty. **Vstup:** ''DD MM RRRR DD MM RRRR'' * dvě data ve formátu ''DD MM RRRR'' za sebou na jednom řádku **Výstup:** ''N'' * ''N'' .. počet dní mezi zadanými dvěma daty jako přirozené číslo ==== Upřesnění ==== Je třeba vzít v úvahu, že rok nemá pokaždé 365 dní, ale občas je přestupný rok. V takovém roce je přidán 29. únor. Rok je přestupný, jestliže jeho číslo je dělitelné 4 a není dělitelné 100, nebo je dělitelné 400. Tedy např. roky 2000, 2400, 2004, 2008 jsou přestupné, ale 1900 nebo 2100 nejsou. Předpokládejme, že vstup je korektní. Počet dní je včetně prvního dne, ale poslední den intervalu se už nepočítá, tj. význam operace rozdíl je stejný jako u přirozených čísel. Uvažujte pouze [[http://cs.wikipedia.org/wiki/Gregori%C3%A1nsk%C3%BD_kalend%C3%A1%C5%99|gregoriánský kalendář]], tj. od roku 1582. ==== Příklady ==== Vstup: 1 1 2007 3 1 2007 Výstup: 2 Vstup: 2 2 2000 2 2 2001 Výstup: 366 ===== Frekvenční analýza textu ===== * **Odevzdávání uzavřeno**, max. 2 body. * 1. termín: 4.12.2009 (0:00), max. 2 body. * 2. termín: 11.12.2009 (0:00), max. 1 bod. ==== Zadání ==== Cílem je spočítat výskyty jednotlivých písmenek v zadaném textu. **Vstup:** ''TEXT'' * ''TEXT'' ... string **Výstup:** tabulka ve tvaru: ''písmenko: počet výstytů'' Počítejte jen malá písmena anglické abecedy, ostatní znaky ignorujte. Vypište pouze záznamy pro písmena s nenulovým výskytem. ==== Příklad ==== Vstup: Wenn ist das nunstruck git und slotermeyer? Ja! Beiherhund das oder die flipperwaldt gersput!? Výstup: a: 4 c: 1 d: 7 e: 10 f: 1 g: 2 h: 2 i: 5 k: 1 l: 3 m: 1 n: 6 o: 2 p: 3 r: 7 s: 6 t: 6 u: 5 w: 1 y: 1 **Hint:** funkce ''ord'' a ''chr'', pole. ===== Generování kombinací ===== * **Odevzdávání uzavřeno**, max. 4 body. * 1. termín: 4.12.2009 (0:00), max. 4 body. * 2. termín: 11.12.2009 (0:00), max. 1 bod. ==== Zadání ==== Kombinace bez opakování jsou neuspořádané K-prvkové podmnožiny z N-prvkové množiny (budeme uvažovat množinu čísel {1, ..., N}), kde K i N jsou kladná celá čísla a platí, že K je menší nebo rovno N. * **Vstup:** ''N K'' * ''N'' ... velikost množiny {1, ..., N} * ''K'' ... velikost podmnožin (kombinací) * **Výstup:** všechny kombinace velikosti K z {1, ..., N} * Každá kombinace bude na samostatném řádku. Prvky budou odděleny mezerami. Na pořadí prvků na řádku ani řádků samotných nezáleží. ==== Příklad ==== Vstup: 6 4 Výstup: 1 2 3 4 1 2 3 5 1 2 3 6 1 2 4 5 1 2 4 6 1 2 5 6 1 3 4 5 1 3 4 6 1 3 5 6 1 4 5 6 2 3 4 5 2 3 4 6 2 3 5 6 2 4 5 6 3 4 5 6 **Hint:** Použijte rekurzi. Mohlo by se hodit pole. Zkuste upravit datovou strukturu, abyste nemuseli zesložiťovat algoritmus. ===== Generování rozkladů čísla na sčítance ===== * **Zadáno v CodExu**, max. 3 body. * 1. termín: 11.12.2009 (0:00), max. 3 body. * 2. termín: 18.12.2009 (0:00), max. 1 bod. * UPDATE: **2. termín: 8.1.2010 (0:00), max. 1 bod.** ==== Zadání ==== * **Vstup:** ''N'' ... přirozené číslo (kladný integer) * **Výstup:** všechny možné rozklady N na součet přirozených čísel oddělené znaménkem +, každý na samostatném řádku ==== Příklad ==== Vstup: 4 Výstup: 1+1+1+1 1+1+2 1+2+1 1+3 2+1+1 2+2 2+1+1 3+1 4 Na pořadí sčítanců záleží, tj. 1+2 není to samé jako 2+1. Na pořadí řádků nezáleží. Můžete předpokládat, že N je omezeno konstantou, v tomto případě 20. Pro generování implementujte rekuzivní proceduru: { k ... k-ty scitanec (0..N-1), zbytek ... N - (suma prechozich scitancu) } procedure generuj(k, zbytek : integer); **Hint:** Použijte rekurzi. Mohlo by se hodit pole. ===== Faktoriál velkých čísel ===== * **Zadána v CodExu**, max. 3 body. * 1. termín: 18.12.2009 (0:00), max. 3 body. * 2. termín: 1.1.2010 (0:00), max. 1 bod. * UPDATE: **2. termín: 1.1.2010 (0:00), max. 3 body.** ==== Zadání ==== Spočítejte přesnou hodnotu faktoriálu čísla N. Můžete předpokládat, že N je menší než 100. ==== Příklad ==== Vstup: 8 Výstup: 40320 ===== Kalkulačka s dlouhými čísly ===== * **Zadáno v CodExu**, max. 4 body. * 1. termín: 25.12.2009 (0:00), max. 4 body. * 2. termín: 1.1.2009 (0:00), max. 1 bod. * UPDATE #1: 2. termín: 8.1.2010 (0:00), max. 4 body. * **UPDATE #2: 2. termín: 28.1.2010 (0:00), max. 4 body.** Přesné počítání s dlouhými celými čísly - operace sčítání, odčítání, násobení. Detaily zadání v CodExu. Autor úlohy: Michal Vaner. ==== Vstup ==== Na každém řádku standardního vstupu se nachází jeden výraz pro výpočet. Takový výraz sestává z jednoho čísla, znaménka operace (+, -, *) a druhého čísla. Vstup je ukončen výrazem, jehož znaménko je znak zavináč (''@''). ==== Výstup ==== Na standardním výstupu je očekáván řádek pro každý výraz, obsahující jedno celé číslo, které je výsledkem výrazu z odpovídajícího řádku na vstupu. Číslo nesmí obsahovat počáteční nuly (tedy, správně je 123, nikoliv 0123). Výjimku tvoří číslo 0, které má obsahovat právě jedinou číslici 0. ==== Příklad ==== Vstup: 123+456 10000000000000000-1 2*222222 0@1 Výstup: 579 9999999999999999 444444 0 ==== Předpoklady ==== * Žádné z čísel na vstupu ani výsledek žádného výrazu není větší než 10^50. * Čísla na vstupu i na výstupu budou nezáporná. * Budou existovat i vstupy, které budou používat jen jednu z operací (zde se nepočítá @ jako operace), takže i "neúplné" kalkulačky s jen některými operacemi získají nějaké body. ===== Cesta králem na šachovnici (délka) ===== * **Zadáno v CodExu**, max. 3 body. * 1. termín: 25.12.2009 (0:00), max. 3 body. * 2. termín: 1.1.2009 (0:00), max. 1 bod. * UPDATE: **2. termín: 8.1.2009 (0:00), max. 3 body.** Program bude hledat nejkratší cestu šachovým králem na šachovnici 8x8, kde na některá políčka nelze vstoupit. Vstup programu obsahuje popořadě: * počet překážek * souřadnice jednotlivých překážek (dvojice čísel v rozsahu 1..8) * souřadnice výchozího políčka * souřadnice cílového políčka Počet překážek je zapsán na samostatném řádku, souřadnice jsou vždy zapsány jako dvojice čísel na jednom řádku oddělená mezerou. Výstup je buď -1, pokud král na cílové políčko nemůže dojít NEBO počet kroků, které musí vykonat. Může se hodit algoritmus vlny. Autor úlohy: Tomáš Holan. ==== Příklad ==== Vstup: 1 2 1 1 1 2 2 Výstup: 1 ===== Odstavcovač ===== * **Zadáno v CodExu**, max. 3 body. * 1. termín: 1.1.2010 (0:00), max. 3 body. * 2. termín: 8.1.2010 (0:00), max. 1 bod. * UPDATE: **2. termín: 8.1.2009 (0:00), max. 3 body.** Zarovnání textu do odstavce dané šířky. Dělá něco podobného jako příkaz "zarovnání do bloku" nebo "justify" v officech. Téma: práce se soubory a s textovými řetězci. ==== Zadání ==== Na prvním řádku vstupního souboru ''odst.in'' se nachází jedno celé kladné číslo ''N''. Na dalších řádcích pokračuje text. Výstupem programu bude soubor ''odst.out''. V něm bude uložen stejný text, ale zformátovaný do odstavce šířky ''N''. == Formát odstavce == První slovo každého řádku se dotýká levého okraje odstavce (jeho první písmeno je v prvním sloupečku). Stejně tak, poslední slovo je zarovnané k pravému okraji (jeho poslední písmeno je v sloupečku ''N''). Mezi každými dvěma sousedními slovy je buď oddělovač řádku nebo jedna či více mezer. "Přebytečné" mezery se rozdělují rovnoměrně mezi všechny mezery na řádku odleva. (Tedy, když máme na řádku 3 slova a je mezi ně potřeba dostat 5 mezer, tak mezi 1. a 2. budou tři, mezi 2. a 3. dvě.) Pokud se na řádek nevejdou ani dvě slova, bude na něm jen jedno, zarovnané doleva a žádné mezery okolo nebudou. Poslední řádek je zarovnán pouze doleva, mezi každými dvěma sousedními slovy právě jedna mezera. Za slovo se považuje libovolná posloupnost znaků oddělená od zbytku buď novým řádkem nebo alespoň jednou mezerou. Tedy, text ''Ahoj, jak je?'' obsahuje 3 slova: ''Ahoj,'', ''jak'' a ''je?''. Autor úlohy: Michal Vaner. ==== Příklad ==== Vstup ze souboru ''odst.in'': 25 Tut, man, one fire burns out another's burning, One pain is lessen'd by another's anguish; Turn giddy, and be holp by backward turning; One desperate grief cures with another's languish: Take thou some new infection to thy eye, And the rank poison of the old will die. Výstup do souboru ''odst.out'': Tut, man, one fire burns out another's burning, One pain is lessen'd by another's anguish; Turn giddy, and be holp by backward turning; One desperate grief cures with another's languish: Take thou some new infection to thy eye, And the rank poison of the old will die. ===== Kontrola uzávorkování ===== * **Zadáno v CodExu**, max. 3 body. * 1. termín: 25.12.2009 (0:00), max. 3 body. * 2. termín: 1.1.2010 (0:00), max. 1 bod. * UPDATE: **2. termín: 8.1.2009 (0:00), max. 3 body.** Úložka na procvičení práce s řetězci, se soubory a se zásobníkem. ==== Zadání ==== Napište program, který umí pro zadanou posloupnost rozhodnout, zda je korektně uzávorkovaná či nikoliv. Tzn., že lze všechny závoky navzájem spárovat a že se závorky nikde vzájemně nekříží. Vstup programu bude v souboru ''zavorky.in''. Tento soubor obsahuje předem neznámý počet řádků, přičemž na každém řádku je vždy jedna posloupnost závorek. Všechny závorky jsou oddělené mezerou a za posledním řádkem je konec souboru. Výstupem programu je pro každou posloupnost odpověď ''true'', pokud byla korektně uzávorkovaná, nebo ''false'' pokud nebyla. Odpovědi by měl program psát na standardní výstup a na každém řádku by měla být vždy jen jedna odpověď. Aby nebylo zadání jednoduché, nemusí být závorky jednoznakové. Program by měl umět zpracovat následující dvojice závorek: ^Otevírací^Uzavírací^ |(|)| |[|]| |/*|*/| || |($|$)| |<<|>>| Můžete předpokládat, že na vyřešení stačí zásobník o 10.000 položkách typu ''string[2]''. Autor: Zbyněk Falt ==== Příklad ==== Vstup (soubor ''zavorky.in''): << $) >> << >> ($ $) [ ] ( ) /* << /* [ ] */ >> */ Výstup (standardní): false true Testovaci soubor (prejmenovat na zavorky.pas): [[http://mff.zamecnik.org/programovani/pascal/uzavorkovani/5.in|5.in]] [[http://mff.zamecnik.org/programovani/pascal/uzavorkovani/5.out|5.out]] ===== Sokoban ===== * **Zadáno v CodExu**, max. 2 body. * 1. termín: 25.12.2009 (0:00), max. 2 body. * 2. termín: 1.1.2010 (0:00), max. 1 bod. * UPDATE: **2. termín: 8.1.2009 (0:00), max. 2 body.** Nalezněte délku nejkratší cesty, kterou potřebuje skladník na přesun dané bedny. ==== Zadání ==== Ve skladišti o ploše 10x10 kostiček se na políčku ''[sx,sy]'' nachází skladník a na políčku ''[bx,by]'' bedna, kterou je potřeba dopravit na políčko ''[cx,cy]''. Kolem dokola skladiště jsou zdi, zdi-překážky mohou být i na některých políčkách uvnitř skladiště. Skladník se pohybuje v každém kroku vždy o jedno políčko doleva, doprava, nahoru nebo dolů, je-li před ním (ve směru pohybu) bedna a za ní volné místo, pak při pohybu bednu odstrčí na volné místo a sám se posune na její pozici, pokud na políčku, kam chce jít, je překážka nebo okraj skladiště, nebo pokud je tam bedna, za kterou je překážka nebo okraj skladiště, pohyb nelze provést. Napište program, který najde nejmenší počet kroků skladníka potřebný k dopravení bedny na cílové políčko. Pokud bednu na danou cílovou pozici nelze dopravit, vytiskne ''-1''. Vstup je zadán jako mapa, ve které každý znak určuje obsah políčka: |''.'' (tečka)|volné políčko| |''X''|překážka| |''S''|skladník| |''B''|bedna| |''C''|cílové políčko| Předpokládejte, že vstup je korektně zadán. Autor úlohy: Tomáš Holan ==== Příklad ==== Vstup: .......... .......... .......... .......... .......... CSB....... .......... .......... .......... .......... Výstup: 6 ===== Cesta draka po šachovnici ===== * **Zadána v CodExu**, max. 7 bodů. * 1. termín: 8.1.2009 (0:00), max. 7 bodů. * 2. termín: 14.1.2009 (0:00), max. 3 body. * UPDATE: **2. termín: 14.1.2009 (19:00), max. 5 bodů.** * za nepoužití fronty mohu strhnout 1 bod * za nepoužití recordu mohu strhnout další 1 bod ==== Zadání ==== Cílem programu je najít nejkratší cestu drakem na šachovnici ze daného zdrojového políčka na dané cílové políčko, nebo oznámit, že taková cesta neexistuje. Pohyb draka je kombinací pohybu obyčejného koně a "2-3-mílové věže". Na šachovnici se mohou vyskytovat i obsazená políčka, na která drak nemůže vstoupit. Šachovnice může mít obdélníkový tvar zadané velikosti ''MxN'' o maximálních rozměrech 15x20 políček. Je třeba kontrolovat meze souřadnic zadaných na vstupu, jestli patří do šachovnice, a také počet obsazených políček a případně ohlásit chybu a skončit. Souřadnice jsou v zadání zapsány ve formátu ''[x,y]'', kde ''x'' je z ''{1..M}'' a ''y'' je z ''{1..N}''. Obsazená políčka jsou očíslována od jedničky. Obsazená políčka nesmí ležet na počátečních a cílových souřadnicích. === Pohyb draka === V každém tahu si může vybrat, jestli táhne jako kůň nebo jako 2-3-mílová věž. Kůň chodí na relativně zadaná sousední políčka. 2-3-mílová vež může skákat horizontálně nebo vertikálně, dokud nenarazí na obsazené políčko nebo konec šachovnice. Pro jednoduchost testování správnosti zafixujeme následující pořadí tahů. Drak nejdříve projde tahy koně a pak tahy věže. Tahy koně projde v tomto pevném pořadí: ''[-1,-2], [-1,2], [-2,-1], [-2,1], [1,-2], [1,2], [2,-1], [2,1]''. Tahy 2-3-mílové věže projde v takovém pořadí, že jde nahoru, doprava, dolů a nakonec doleva, přitom prochází ve směru od sebe pryč. Nahoru a dovela skáče věž po třech políčkách, dolů a doprava po dvou políčkách. Tedy věž táhne: ''[0,-3], [2,0], [0,2], [-3,0]'' Pohyb draka může vypadat např. takto: ............... .......1....... ............... ............... .......1....... ......1.1...... .....1...1..... .1..1..0.1.1.1. .....1...1..... ......111...... ............... .......1....... ............... .......1....... ............... Hledáme jednu nejkratší cestu, ale může jich existovat víc. Kterou vybereme závisí na pořadí ve kerém procházíme sousední políčka. Proto jsme si pořadí tahů zafixovali. Následuje symbolicky zapsaný vstup a výstup. Texty ve složených jsou pouze komentáře. Ve vstupu/výstupu se nevyskytují. === Vstup === M N {rozměry šachovnice} X Y {souřadnice počáteční pozice draka} X Y {souřadnice cílové pozice draka} P {počet obsazených políček} X Y {souřadnice obsazeného políčka č. 1} X Y {souřadnice obsazeného políčka č. 2} ... X Y {souřadnice posledního obsazeného políčka} === Výstup === Pokud existuje zadaná cesta: X Y {souřadnice cílové pozice draka} X Y {souřadnice předposledního kroku na cestě draka} ... X Y {souřadnice druhého kroku na cestě draka} X Y {souřadnice počáteční pozice draka} Pokud neexistuje zadaná cesta: Cesta neexistuje. Pokud je vstup chybně zadán (jedno z toho): Chybny vstup (rozmery sachovnice). Chybny vstup (pocatecni policko). Chybny vstup (cilove policko). Chybny vstup (pocet obsazenych policek). Chybny vstup (obsazene policko). ==== Další informace v rámci tohoto cvičení ==== Pro řešení úlohy použijte algoritmus prohledávání do šířky. Která políčka navštívit řiďte nikoliv přímo obsahem šachovnice, ale frontou souřadnic dalších políček. Pro souřadnice použijte record. Použití fronty i recordu bude kontrolováno nikoliv CodExem, ale následně okem. Z ohodnocení CodExem může být v případě nepoužití fronty nebo recordu strženo pár bodů. Rád bych, abyste si tyto věci ozkoušeli. ==== Příklad ==== Vstup: 15 20 4 5 11 16 74 9 1 10 1 11 1 12 1 3 2 14 2 6 3 12 3 2 4 9 4 14 4 12 5 6 6 10 6 11 6 1 7 7 7 9 7 13 7 14 7 15 7 2 8 3 8 9 8 5 9 6 9 10 9 14 9 7 10 8 10 4 11 14 11 6 12 10 12 6 13 7 13 8 13 11 13 12 13 13 13 1 14 2 14 3 14 7 14 9 14 10 14 11 14 12 14 13 14 1 15 2 15 8 15 9 15 10 15 11 15 12 15 13 15 3 16 8 16 9 16 10 16 1 17 6 17 8 17 9 17 10 17 9 18 10 18 2 19 4 19 6 19 12 19 1 20 9 20 Výstup: 11 16 11 19 3 19 3 7 4 5 Šachovnice vypadá takto: |.|volné políčko| |#|obsazené políčko| |p|počáteční políčko| |c|cílové políčko| ........####... ..#..........#. .....#.....#... .#......#....#. ...p.......#... .....#...##.... #.....#.#...### .##.....#...... ....##...#...#. ......##....... ...#.........#. .....#...#..... .....###..###.. ###...#.#####.. ##.....######.. ..#....###c.... #....#.###..... ........##..... .#.#.#.....#... #.......#...... ==== Goodies ==== Při ladění by se vám mohla hodit šachovnice reprezentovaná maticí znaků. Pro převod máte k dispozici nástroj **boardConvert**: program boardConvert; { prevod mezi reprezentacemi sachovnice: matice policek <-> seznam objektu parametry: bez parametru: seznam objektu -> matice -r: matice -> seznam objektu pouziti: boardConvert -r < 01b.in > 01.in boardConvert < 01.in > 01b.in matice policek: znaku z mnoziny: [ '.' = prazdne policko '#' = obsazene policko 'p' = pocatecni policko 'c' = cilove policko ] seznam objektu: M N = rozmery sachovnice X Y = souradnice pocatecni pozice draka X Y = souradnice cilove pozice draka P = pocet obsazenych policek X Y = souradnice obsazeneho policka c. 1 X Y = souradnice obsazeneho policka c. 2 X Y = souradnice posledniho obsazeneho policka } const MaxSirkaSachovnice = 15; {osa X} MaxVyskaSachovnice = 20; {osa Y} type Souradnice = record x, y: integer end; var poziceFigurkyX, poziceFigurkyY : integer; pocatecniPoziceFigurky: Souradnice; cilovaPoziceFigurky: Souradnice; poziceObsazenehoPolicka: Souradnice; sirkaSachovnice, vyskaSachovnice : integer; pocetObsazenychPolicek : integer; i : integer; obsazeno : array[1..MaxSirkaSachovnice,1..MaxVyskaSachovnice] of boolean; procedure nactiSouradnice(var souradnice : Souradnice); begin readln(souradnice.x, souradnice.y); end; procedure coords2board; begin readln(sirkaSachovnice, vyskaSachovnice); for poziceFigurkyY := 1 to vyskaSachovnice do begin for poziceFigurkyX := 1 to sirkaSachovnice do begin obsazeno[poziceFigurkyX, poziceFigurkyY] := FALSE; end; end; nactiSouradnice(pocatecniPoziceFigurky); nactiSouradnice(cilovaPoziceFigurky); readln(pocetObsazenychPolicek); for i := 1 to pocetObsazenychPolicek do begin nactiSouradnice(poziceObsazenehoPolicka); obsazeno[poziceObsazenehoPolicka.x, poziceObsazenehoPolicka.y] := TRUE; end; writeln(sirkaSachovnice, ' ', vyskaSachovnice); for poziceFigurkyY := 1 to vyskaSachovnice do begin for poziceFigurkyX := 1 to sirkaSachovnice do begin if (obsazeno[poziceFigurkyX, poziceFigurkyY]) then write('#') else if (poziceFigurkyX = pocatecniPoziceFigurky.x) AND (poziceFigurkyY = pocatecniPoziceFigurky.y) then write('p') else if (poziceFigurkyX = cilovaPoziceFigurky.x) AND (poziceFigurkyY = cilovaPoziceFigurky.y) then write('c') else write('.') end; writeln end; end; procedure board2coords; var radek : string; sachovnice : array[1..MaxVyskaSachovnice] of string; begin readln(sirkaSachovnice, vyskaSachovnice); pocetObsazenychPolicek := 0; writeln(sirkaSachovnice, ' ', vyskaSachovnice); for poziceFigurkyY := 1 to vyskaSachovnice do begin readln(radek); sachovnice[poziceFigurkyY] := radek; if length(radek) = sirkaSachovnice then begin for poziceFigurkyX := 1 to sirkaSachovnice do begin case radek[poziceFigurkyX] of 'p': begin pocatecniPoziceFigurky.x := poziceFigurkyX; pocatecniPoziceFigurky.y := poziceFigurkyY; end; 'c': begin cilovaPoziceFigurky.x := poziceFigurkyX; cilovaPoziceFigurky.y := poziceFigurkyY; end; '#': Inc(pocetObsazenychPolicek); end; end; end else begin writeln('Chybny format tabulky sachovnice.'); exit; end; end; writeln(pocatecniPoziceFigurky.x, ' ', pocatecniPoziceFigurky.y); writeln(cilovaPoziceFigurky.x, ' ', cilovaPoziceFigurky.y); writeln(pocetObsazenychPolicek); for poziceFigurkyY := 1 to vyskaSachovnice do begin for poziceFigurkyX := 1 to sirkaSachovnice do begin case sachovnice[poziceFigurkyY][poziceFigurkyX] of '#': writeln(poziceFigurkyX, ' ', poziceFigurkyY); end; end end; end; var smerKonverze : (c2b, b2c); {TRUE = coords2board, FALSE = board2coords} begin smerKonverze := c2b; if ParamCount >= 1 then begin if ParamStr(1) = '-r' then smerKonverze := b2c; end; case smerKonverze of c2b: coords2board; b2c: board2coords; end; end. ===== Hodnost matice ===== * **Zadána v CodExu**, max. 6 bodů. * 1. termín: 28.1.2009 (0:00), max. 6 bodů. * UPDATE: 2. termín: 14.2.2009, max. 6 bodů. ==== Zadání ==== Spočítejte hodnost zadané celočíselné matice. Můžete předpokládat, že žádný rozměr matice nepřesáhne 1000 a že prvky matice se vejdou do datového typu ''longint''. === Vstup === Vstupní matici načtěte ze souboru s názvem ''matice.in''. Zápis matice je následující: n m a11 a12 ... a1m a21 . ... ... . ... an1 an2 ... anm ''n'' (1 ≤ n ≤ 1000) je počet řádků matice, ''m'' (1 ≤ ''m'' ≤ 1000) je počet sloupců matice. Následuje ''n'' řádků po ''m'' číslech (''aij''), které určují jednotlivé prvky matice. === Výstup === Na standardní výstup vypište spočítanou hodnost matice. === Rady === Použijte například algoritmus [[http://cs.wikipedia.org/wiki/Gaussova_elimina%C4%8Dn%C3%AD_metoda|Gaussovy eliminace]]. Řešení lze napsat na 100 řádek rozumného pascalovského kódu). Matici můžete reprezentovat pomocí typu record. Mohou se hodit procedury jako ''swapRows'', ''divideRow'', ''isZero'', případně ''readMatrix'' a ''writeMatrix'' které si můžete napsat. ==== Příklad ==== Vstup: 4 4 1 -2 0 4 3 1 1 0 -1 -5 -1 8 3 8 2 -12 Výstup: 2