Zadání semestrálního projektu Algoritmy I. zimní semestr 2010 doc. Mgr. Jiří Dvorský, Ph.D. 3. listopadu 2010
Verze zadání 22. října 2010 25. října 2010 3. listopadu 2010
První verze Opraveno odsazení prvního řádku odstavce v ukázce sedmého příkladu Opraven ukázkový výpočet ve čtvrtém příkladu.
Obecné pokyny 1. Celkem je k dispozici 7 zadání příkladů. 2. Každý student dostane přidělen jeden příklad. Na mém webu je zveřejněn seznam studentů a jim přiřazených zadání. Kdo by se tam případně nenašel, nechť mě neprodleně kontaktuje emailem. 3. Termín odevzdání prezenční studium kombinované studium
17. prosince 2010 ve 23:59 17. prosince 2010 ve 23:59
4. Projekt odevzdáváte emailem svému cvičícímu. Kombinovaní studenti svému tutorovi – doc. Dvorský. 5. Programy budou zpracovány jako projekt Visual Studia 2010. 6. Než projekt odešlete, ve Visual Studiu jej „vyčistěteÿ – menu Build, pak Clean Solution. Takto vyčištěný projekt zabalte do Zip archivu. Ostatní archivy, speciálně Rar, nemá školní poštovní server nějak rád. Vyčištění je nezbytné, protože přílohy mailu obsahující spustitelné soubory nejsou doručovány. 7. Upozorňuji, že nestačí jen program odevzdat, ale je nutné své řešení před cvičícím/tutorem obhájit. Jinak řečeno, pokud program od někoho opíšete, necháte si napsat, a nebudete tušit co se v programu děje, je s Vámi zle. Obhajoby budou probíhat v termínech určených Vaším cvičícím ve zkouškovém období. Obhajoby projektů studentů kombinované formy studia budou probíhat s tutorem. 1
8. Dále připomínám, že minimální počet bodů je za funkční program tj. za program, který lze spustit a který poskytuje správný výsledek. Pokud nebude Váš program funkční, nemáte nárok na ani minimální počet bodů.
2
1. zadání – Postfixový kalkulátor Vaším úkolem je vytvořit program, který bude vyhodnocovat aritmetický výraz zadaný v postfixové notaci. Podrobný popis postfixového způsobu zápisu aritmetického výrazu najdete na webu http://cs.wikipedia.org/wiki/Postfixov% C3%A1_notace. V postfixové notaci operátory následují za operandy. Například sčítání čísel běžně zapisujeme jako 3 + 4. Této formě zápisu říkáme infixová notace. V postfixové notaci se stejný výraz zapíše jako 3 4 +. Jestliže provádíme více operací, je operátor umístěn za druhý operand, takže výraz 3 − 4 + 5 zapsaný v infixové notaci bude v postfixové notaci zapsán jako 3 4 − 5 +. Nejprve odečteme 4 od 3 a posléze přičteme 5. U postfixové notace odpadá nutnost používání závorek používaných v infixové notaci. Výraz 3 + 4 ∗ 5 se v postfixové notaci zapíše jako 3 4 5 ∗ +, kdežto výraz (3 + 4) ∗ 5 se zapíše jako 3 4 + 5 ∗. Interpretry postfixové notace jsou zásobníkového typu. Operandy jsou ukládány na zásobník, když má být provedena operace, jsou její operandy vyzvednuty ze zásobníku a výsledek je uložen zpět na zásobník. Vyhodnocování postfixové notace je tudíž velice jednoduché. V praxi používáte podobně konstruovaný jazyk asi téměř denně – na postfixovém zápisu celých programů je založen jazyk PostScript a hlavně jeho následovník PDF. Algoritmus pro vyhodnocování postfixových výrazů lze popsat asi takto: dokud není konec vstupu opakuj přečti další element jestliže je přečtený element číslo ulož jej na zásobník jinak element musí být operand předpoklad: operand potřebuje n operandů vyber ze zásobníku horních n hodnot jestliže je v zásobníku méně než n hodnot CHYBA jinak vypočti výsledek operace ulož výsledek operace na zásobník konec cyklu jestliže na zásobníku zbyla jen jedna hodnota je to výsledek výpočtu jinak CHYBA -- uživatel zadal příliš hodnot Elementem je myšleno číslo nebo znak operátoru.
Poznámky • Ve Vašem projektu předpokládejte, že se budou používat jen operátory definované v tabulce 1. • Pro vyhodnocení výrazu budete potřebovat zásobník, jeho popis je uveden ve skriptech a lze jej nalézt i na Wikipedii. Předpokládejte, že bude stačit zásobník na maximálně 100 prvků. 3
Výraz a b + a b a b * a b / a b % a b ^ a f
Význam a+b a−b a·b a/b a mod b ab celá část čísla a
Tabulka 1: Operátory • Ukázkové příklady pracují pro jednoduchost s celými čísly, Vás program by měl pracovat s čísly s plovoucí řádovou čárkou, např. typu double. • Váš program musí umět reagovat na nesprávně zadané výrazy. Nemusí jejich správnost jakkoliv kontrolovat dopředu, ale musí být schopen detekovat chyby při vyhodnocování výrazu. Například chci vyhodnocovat součet a v zásobníku naleznu jen jednu hodnotu. V tom okamžiku se program nesmí zhroutit, ale musí vypsat chybové hlášení, že se očekávala další hodnota, ale zásobník je prázdný. • Vyhodnocovaný výraz se bude zadávat z klávesnice, celý výraz najednou na řádku. • Načtený řádek je potřeba rozdělit na jednotlivé části tj. na operandy (čísla) a operátory. K rozdělení použijte funkci strtok , popis této funkce naleznete na adrese http://msdn.microsoft.com/en-us/library/2c8d19sb.aspx. • V další fázi potřebujete řetězce reprezentující operandy (čísla) převést na typ double. K tomu požijte funkci atof , popis této funkce naleznete na adrese http://msdn.microsoft.com/en-us/library/hc25t012.aspx. • Operátor f vypočte celou část ze svého operandu, pro implementaci tohoto operátoru použijte funkci floor , popis této funkce naleznete na adrese http://msdn.microsoft.com/en-us/library/x39715t6.aspx.
Příklad Běžný, infixový výraz 5 + (1 + 2) ∗ 4 − 3 může být přepsán do postfixové notace jako 5 1 2 + 4 ∗ + 3 −. Výraz je počítán zleva doprava.
4
Vstup 5 1 2 +
Operace Ulož operand Ulož operand Ulož operand Sečti
Zásobník 5 5, 1 5, 1, 2 5, 3
4 *
Ulož operand Vynásob
5, 3, 4 5, 12
+
Sečti
17
3 -
Ulož operand Odečti
17, 3 14
Popis
Vyber dvě hodnoty (1, 2), zpracuj a ulož výsledek (3) Vyber dvě hodnoty (3, 4), zpracuj a ulož výsledek (12) Vyber dvě hodnoty (5, 12), zpracuj a ulož výsledek (17) Vyber dvě hodnoty (17, 3), zpracuj a ulož výsledek (14)
Když je výpočet hotov, na vrcholu zásobníku je uložen výsledek, v tomto případě 14.
5
2. zadání – Písemné násobení Předpokládejme, že na vstupu Vašeho programu jsou dvě čísla typu int . Vaším úkolem je zobrazit postup jejich písemného násobení, čili jak se tato čísla vynásobí na papíře ručně pod sebou.
Příklad 12 105 ----60 00 12 ----1260
nebo
12 105 ----60 120 ----1260
12 -145 -----60 48 12 ------1740
-145 -12 -----290 145 -----1740
Při vypisování na obrazovku je třeba dbát na správné formátování postupných mezivýsledků, tak aby Vám jednotlivé cifry pod sebou lícovaly! Bez tohoto lícování bude program hodnocen jako nevyhovující.
Poznámky • Předpokládejte vždy správný vstup. Nezabývejte se ošetřováním nesprávně zadaných hodnot. • Předpokládejte, že součin obou činitelů bude opět číslo typu int , jinak řečeno, že nedojde k přetečení. • Je třeba ovšem dát pozor při formátování na znaménka minus. • Při násobení nulou si můžete vybrat, kterou alternativu implementujete, zda s řádkem nul nebo bez něj.
6
3. zadání – Eratosthenovo síto Vaším úkolem je naprogramovat klasický algoritmus pro nalezení všech prvočísel z daného intervalu. Tento algoritmus je znám od starověku a za autora je pokládán matematik a filozof Eratosthénés z Kyrény. Princip algoritmu je velice jednoduchý a spočívá v postupné eliminaci násobků čísel z posloupnosti přirozených čísel tak, že nakonec v ní zůstanou jen prvočísla. Postup lze zapsat neformálně takto: 1. Zapíšeme do posloupnosti všechna přirozená čísla od 2 do zvoleného n. Čísla 0 a 1 nejsou považována za prvočísla. 2. První neoznačené číslo v posloupnosti je prvočíslo. Toto číslo si označíme. 3. Z posloupnosti vyškrtáme všechny jeho násobky. 4. Pokud je v posloupnosti nějaké neoznačené číslo, pokračuj bodem 2.
Příklad Pro n = 20 je postup výpočtu zobrazen v tabulce 2. Z tabulky je dále vidět, že počínaje číslem 5 již nedojde k žádnému vyškrtávání násobků, protože případné násobky již byly vyloučeny jako násobky čísel nižších, například 15 bylo vyloučeno√jako násobek čísla 3. Obecně √ nemusíme odstraňovat násobky čísel větších než n, v našem případě 5 > 20. 2
3
2
3
2
2
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
5
označíme číslo 2 a vyloučíme jeho násobky 7 9 11 13 15
17
19
3
5
označíme číslo 3 a vyloučíme jeho násobky 7 11 13
17
19
3
5
označíme číslo 5 a vyloučíme jeho násobky 7 11 13
17
19
20
Tabulka 2: Eratosthenovo síto V programu můžeme reprezentovat posloupnost nejjednodušeji polem logických hodnot. Jednotlivá čísla v posloupnosti nereprezentují hodnoty prvků v poli, ale indexy v tomto poli. Hodnota true pak znamená, že číslo odpovídající danému indexu je stále zařazeno v posloupnosti. Na hodnotu false prvek nastavíme při jeho vyškrtnutí z posloupnosti. Dále pro zjednodušení implementace se v poli ponechávají prvky s indexy 0 a 1, které označíme ihned jako vyškrtnuté, false . Další možností je zachytit čísla ze zpracovávané posloupnosti jako jednotlivé bity v čísle například typu int . Předpokládejme, že typ int má délku 32 bitů. Potom budou čísla 0 až 31 reprezentována jako bity 0 až 31 prvního prvku pole čísel typu int . Čísla 32 až 63 budou uložena jako bity 0 až 31 druhého prvku pole čísel typu int a tak dále. Dojde tedy k osminásobnému snížení paměťových nároků.
7
Vaším úkolem je realizovat Eratosthenovo síto právě tímto způsobem. Váš program dostane jako vstupní parametr horní mez intervalu a na výstup vypíše všechna prvočísla z toho intervalu.
Poznámky • Předpokládejte vždy správný vstup. Nezabývejte se ošetřováním nesprávně zadaných hodnot. • Předpokládejte, že maximální přípustná hodnota n je rovna 220 . Tudíž budete potřebovat pole čísel int délky 32768, za předpokladu, že číslo typu int má délku 32 bitů. Toto pole si můžete nadeklarovat dopředu a při vlastním výpočtu si pak jen pamatovat, že v tomto okamžiku počítáme prvočísla například jen do hodnoty 100.
8
4. zadání – Výpočet editační vzdálenosti dvou textů Na vstupu jsou dány dva neprázdné řetězce a a b. Vaším úkolem je vypočítat tzv. editační vzdálenost těchto dvou řetězců. Editační vzdáleností můžeme měřit vzdálenost, odlišnost, dvou řetězců. V případě editační vzdálenosti je vzdálenost definována jako počet operací smazání znaku, vložení znaku a záměny znaku tak, aby se jeden řetězec transformoval na druhý. Výpočet můžeme popsat následujícím způsobem. Máme dány dva řetězce a = a1 a2 . . . am a b = b1 b2 . . . bn . Editační vzdálenost di,j předpony délky i řetězce a a předpony délky j řetězce b můžeme vypočítat jako1 : di−1,j + 1 di,j−1 + 1 di,j = min (1) di−1,j−1 + 1 pokud ai 6= bj di−1,j−1 pokud ai = bj pro 1 ≤ i ≤ m a 1 ≤ j ≤ n. První hodnota odpovídá vymazání j-tého znaku z prvního řetězce, druhá hodnota odpovídá vložení znaku na (j − 1)-ní pozici do prvního řetězce, třetí hodnota odpovídá výměně j-tého a i-tého znaku. Čtvrtá hodnota se uplatní jen v případě, že jsou znaky v obou řetězcích shodné. Na konci hodnota dmn udává editační vzdálenost řetězců a a b. Dále je pochopitelně definováno: d0,0
=
0
di,0
= i, pro 1 ≤ i ≤ m
d0,j
= j, pro 1 ≤ j ≤ n
Z předchozího textu je patrné, že celý výpočet můžeme implementovat jako rekurzivní funkci, kde výpočet hodnoty dmn se rozpadne na výpočet hodnot dm−1,n , dm,n−1 , případně dm−1,n−1 a tak dále, až k definovaným koncovým hodnotám d0,0 atd.
Příklad Hodnota dij udává editační vzdálenost mezi prvními i znaky řetězce a a prvními j znaky řetězce b. Tuto hodnotu však neumíme vypočítat přímo, ale vypočteme ji na základě znalostí vzdáleností mezi prvními i − 1 znaky řetězce a a prvními j − 1 znaky řetězce b. Tímto způsobem postupně redukujeme problém až na úroveň případů, kdy je hodnota známa přímo, například pro d0,0 = 0. Předpokládejme, že a = abcabba a b = cbabac, odtud m = 7 a n = 6. Editační vzdálenost těchto dvou řetězců se bude počítat jako hodnota d7,6 d6,6 + 1 d7,5 + 1 d7,6 = min d6,5 + 1 protože a7 6= b6 tj. a 6= c Editační vzdálenost celých řetězců a a b je jinak řečeno rovna editační vzdálenosti prvních 7 znaků řetězce a a prvních 6 znaků řetězce b. Hodnotu d6,6 1 Předponou
délky i řetězce a se myslí prvních i znaků od začátku řetězce.
9
můžeme dále rozložit na d6,6
d5,6 + 1 d6,5 + 1 = min d5,5 + 1
protože a6 6= b6 tj. b 6= c
Dále můžeme rozepsat hodnotu d7,5 jako d6,5 + 1 d7,4 + 1 d7,5 = min d6,4 protože a7 = b5 tj. a = a Dále bychom postupovali výpočtem hodnot d5,6 , d6,5 , d5,5 , znovu hodnotu d5,6 , d7,4 , d6,4 . . . Tabulka 3 schematicky znázorňuje postup výpočtu hodnoty d7,6 . Výsledná editační vzdálenost je pak uložena v buňce na řádku 6 a sloupci 7. řetězec b c a b a b c
j 6 5 4 3 2 1 0
6 5 4 3 2 1 0 0
5 4 3 2 2 1 1 1 a
4 3 2 2 1 2 2 2 b
3 3 3 2 2 2 3 3 c
4 3 3 2 3 3 4 4 a
4 3 2 3 3 4 5 5 b
4 3 3 4 4 5 6 6 b
4 3 4 4 5 6 7 7 a
i řetězec a
Tabulka 3: Výpočet editační vzdálenosti
Poznámky • Předpokládejte vždy správný vstup. Nezabývejte se ošetřováním nesprávně zadaných hodnot, v tomto případě řetězcem nulové délky.
10
5. zadání – Rozklad na součet Fibonacciho čísel Napište program, který vypíše rozklad daného přirozeného čísla z intervalu 1 až 10000 na součet Fibonacciho čísel. Fibonacciho čísla jsou zadána rekurzivním předpisem: F0
=
1
F1
=
1
Fn
= Fn−1 + Fn−2 pro n ≥ 2
Jinak řečeno první dvě Fibonacciho čísla jsou rovna jedné, další jsou vždy součtem dvou předchozích. Začátek posloupnosti těchto čísel vypadá následovně: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, . . . Pro přirozená čísla platí věta, která říká, že každé přirozené číslo lze zapsat jako součet jistých Fibonacciho čísel. Po spuštění programu, uživatel zadá číslo a Váš program vytiskne příslušný rozklad. Ukázky výstupu z Vašeho programu: 1 = 1 2 = 2; 3 = 3 4 = 3 + 1 5 = 5 6 = 5 + 1 7 = 5 + 2 8 = 8 9 = 8 + 1 6263 = 4181 + 1597 + 377 + 89 + 13 + 5 + 1 10000 = 6765 + 2584 + 610 + 34 + 5 + 2
Poznámky • Předpokládejte vždy správný vstup. Nezabývejte se ošetřováním nesprávně zadaných hodnot. • Dále pro rozklad přirozeného čísla pomocí Fibonacciho čísel platí, že se v tomto rozkladu nevyskytují dvě bezprostředně po sobě jdoucí Fibonacciho čísla. Důvod je zřejmý. Kdyby se v rozkladu taková dvě čísla vyskytovala, tak by se jejich součet rovnal dalšímu Fibonaccimu číslu. Tento fakt Vám může sloužit pro kontrolu, že máte výpočet správně. Takže například rozklad čísla 5 je jedině samotné číslo 5, nikoliv 3 + 2. Stejně tak se v rozkladu vyskytuje každé Fibonacciho číslo právě jednou. Tudíž obdobně rozklad čísla 4 je možný pouze jako 3 + 1 nikoliv jako 2 + 2. V tomto směru můžete namítnout, že se ve Fibonacciho posloupnosti vyskytují dvě čísla stejná, první dvě jedničky. Při kódování se z uvedené posloupnosti uvažuje pouze jedna jednička, jinak by byl rozklad neproveditelný. Ony dvě jedničky jsou výchozí hodnoty pro výpočet celé posloupnosti • Fibonacciho čísla potřebná v programu si můžete vždy na začátku vypočítat nebo načíst ze souboru nebo napevno uložit do pole jako konstanty – toto nechám na Vás.
11
6. zadání – Rozklad na prvočinitele Napište program, který vypíše rozklad daného přirozeného čísla z intervalu 2 do 10000, včetně, na prvočinitele. Po spuštění programu, uživatel zadá číslo a Váš program vytiskne příslušný rozklad. Ukázky rozkladů jsou v následující tabulce. Znak ^ označuje mocninu, například 2^3 znamená „dvě na třetíÿ. 2 = 2^1 3 = 3^1 4 = 2^2 5 = 5^1 6 = 2^1 * 3^1 7 = 7^1 8 = 2^3 9 = 3^2 10 = 2^1 * 5^1 11 = 11^1 12 = 2^2 * 3^1 ..... 1768 = 2^3 * 13 * 17 ..... 10000 = 2^4 * 5^4
Poznámky • Předpokládejte vždy správný vstup. Nezabývejte se ošetřováním nesprávně zadaných hodnot. • K rozkladu čísel do 10000 potřebujete znát prvočísla do 10000. Tato si můžete vždy při spuštění programu vypočítat nebo si je načíst ze souboru nebo je mít v programu zadána napevno pomocí pole – toto nechám na Vás. • Seznam prvočísel je k dispozici na http://en.wikipedia.org/wiki/ List_of_prime_numbers
12
7. zadání – Formátování textového souboru V tomto příkladu je Vaším úkolem jednoduché formátování textu. Na vstupu je textový soubor. Tento soubor obsahuje odstavce textu, každý odstavec je uložen jako jediný, velmi dlouhý řádek. Tento dlouhý řádek je nutno rozdělit, zalomit, na více řádků (vložením konců řádků) tak, aby délka zalomeného řádku nepřesahovala stanovenou délku. Pro zalamování platí tato pravidla: 1. První řádek odstavce je odsazen třemi mezerami. Další zalomené řádky se neodsazují. 2. Řádky lze zalamovat pouze v mezislovních mezerách. 3. Interpunkční znaménka se nesmí objevit na začátku řádku. Například tečku ze větou je potřeba zalomit s celým přecházejcím slovem. Odstavec po zalomení řádků bude tedy zarovnán doleva, první řádek bude odsazen o tři mezery a pravý okraj bude „zubatýÿ. Zalomené odstavce ve výstupním souboru oddělte jedním prázným řádkem.
Příklad Předpokládejme, že na vstupu je následující odstavec textu2 : Lorem ipsum dolor sit amet, consectetur adipiscing elit. Quisque lacinia placerat pharetra. Fusce quis mi sapien. Morbi non eleifend libero. Mauris mattis egestas dui, at tincidunt eros rutrum eget. Donec nulla orci, fringilla in consectetur tempus, laoreet id mauris. Vivamus sagittis dapibus mi, in feugiat neque semper eget. Stanovená délka řádku bude 30. Po naformátování bude odstavec vypadat takto: Lorem ipsum dolor sit amet, consectetur adipiscing elit. Quisque lacinia placerat pharetra. Fusce quis mi sapien. Morbi non eleifend libero. Mauris mattis egestas dui, at tincidunt eros rutrum eget. Donec nulla orci, fringilla in consectetur tempus, laoreet id mauris. Vivamus sagittis dapibus mi, in feugiat neque semper eget. Shodou okolností vyšel poslední řádek přesně na požadovaných 30 znaků, což ale nemusí nastat vždy. 2 Pochopitelně
na papíře je nutné řádky zalomit, v textovém souboru to bude řádek jeden.
13
Poznámky • Předpokládejte, že řádek s kompletním odstavcem nebude delší než 10000 znaků. • Odstavce jsou ve vstupním textovém souboru odděleny jedním či více prázdnými řádky. • Předpokládejte, že délka zalamovaných řádků bude vždy větší než délka slova tj. nemusíte řešit situaci, kdy jednotlivé slovo bude delší než délka zalamovaného řádku. Můžete pro jednoduchost předpokládat, že tato délka bude vždy větší než 20. • Jméno vstupního a výstupního textového souboru, délka zalamovaných řádků se bude zadávat z klávesnice.
14
