načítání...
nákupní košík
Košík

je prázdný
a
b

Programátorská cvičebnice - Radek Pelánek

-15%
sleva

Kniha: Programátorská cvičebnice
Autor:

Chcete-li být skutečně dobrým programátorem, nevyhnete se opakovanému řešení různě obtížných úloh – jenom opakovaný trénink z vás udělá opravdového mistra. Kde ale najít ta ...
Kniha teď bohužel není dostupná.

»hlídat dostupnost

hodnoceni - 0%hodnoceni - 0%hodnoceni - 0%hodnoceni - 0%hodnoceni - 0%   celkové hodnocení
0 hodnocení + 0 recenzí

Specifikace
Nakladatelství: Computer press
Rok vydání: 2012-10-10
Počet stran: 176
Rozměr: 167 x 225 mm
Úprava: 175 stran : ilustrace
Vydání: 1. vyd.
Vazba: brožovaná lepená
Doporučená novinka pro týden: 2012-42
ISBN: 9788025137512
EAN: 9788025137512
Ukázka: » zobrazit ukázku
Popis

Chcete-li být skutečně dobrým programátorem, nevyhnete se opakovanému řešení různě obtížných úloh – jenom opakovaný trénink z vás udělá opravdového mistra. Kde ale najít ta správná zadání, nápady a myšlenky, jejichž přetváření do podoby funkčního programu odvede požadovanou práci a posune vás blíže k metě zkušeného programátora? S Programátorskou cvičebnicí by to neměl být problém. Zkušený autor, který prošel programováním od základů přes roli studenta až na druhou stranu barikády a začal své poznatky předávat méně znalým, vám v knize nabízí ucelený soubor zajímavých zadání programátorských úloh. Ty jsou přehledně rozděleny do tematických oblastí, přičemž u každé je uvedeno ohodnocení její obtížnosti. V textu najdete základní rady, jak úlohy řešit, a detailní řešení k některým vypracovaným cvičením. Kniha se zaměřuje na široké spektrum programátorů: inspiraci v ní najdou nejen začátečníci a pokročilí, ale i profesionálové, kteří v ní mohou vyhledat zajímavá zadání, na nichž si procvičí a zopakují své znalosti. S publikací si mimo jiné vyzkoušíte: * Číselné řady a posloupnosti * Kombinatorická cvičení * Grafické úlohy a fraktály * Vytváření šifer a jejich prolamování * Logické problémy nejen s šachovnicí * Sudoku, Sokoban, Tetris, Piškvorky a řadu dalších her O autorovi: Radek Pelánek vystudoval Fakultu informatiky Masarykovy univerzity. V současnosti na této fakultě působí jako docent a proděkan pro studijní programy. Kniha vychází z jeho dlouhodobých zkušeností s výukou programování a s organizováním programátorských soutěží. Je autorem pěti knih a řady odborných článků. ([algoritmy v příkladech])

Předmětná hesla
Zákazníci kupující knihu "Programátorská cvičebnice" mají také často zájem o tyto tituly:
Algoritmy Algoritmy
Wróblewski, Piotr
Cena: 343 Kč
Algoritmy v jazyku C a C/ -- 2., rozšířené a aktualizované vydání Algoritmy v jazyku C a C/
Prokop, Jiří
Cena: 211 Kč
Java nástroje -- Nástroje pro PLATFORMU JAVA tm Java nástroje
Hynar, Martin
Cena: 25 Kč
 
Recenze a komentáře k titulu
Zatím žádné recenze.


Ukázka / obsah
Přepis ukázky
3 Pocˇı ́ta ́nı ́ s cˇı ́sly U ́ cˇel vy ́pocˇtu ̊ je vhled, nikoliv cˇı ́sla. R. Hamming Tato kapitola obsahuje na ́meˇty na prˇı ́klady, ktere ́ majı ́ velmi jednoduche ́ vstupneˇ-vy ́stupnı ́ chova ́nı ́: vesmeˇs pouze nacˇtou cˇı ́sla a na vy ́stup opeˇt dajı ́ cˇı ́sla. Pocˇı ́ta ́nı ́ s cˇı ́sly pro veˇtsˇinu lidı ́ nenı ́ tak atraktivnı ́ jako trˇeba grafika, logicke ́ u ́lohy nebo hry. Nicme ́neˇ prˇı ́klady s cˇı ́sly jsou vhodne ́ jako u ́vodnı ́ cvicˇenı ́, protozˇe k nim stacˇı ́ velmi ma ́lo znalostı ́ o syntaxi konkre ́tnı ́ho jazyka. Veˇtsˇinou vystacˇı ́me s celocˇı ́selny ́mi promeˇnny ́mi, cykly, funkcemi a prˇı ́padneˇ jednorozmeˇrny ́mi poli. Veˇtsˇina uvedeny ́ch zada ́nı ́ navı ́c ilustruje zajı ́mave ́ vlastnosti cˇı ́sel cˇi algoritmu ̊, prˇı ́padneˇ se k u ́loha ́m va ́zˇou zajı ́mave ́ souvislosti, jako naprˇı ́klad historicke ́ zajı ́mavosti nebo nevyrˇesˇene ́ otevrˇene ́ proble ́my. Pokud o teˇchto souvislostech vı ́me, i jednoduche ́ pocˇı ́ta ́nı ́ s cˇı ́sly dosta ́va ́ na zajı ́mavosti. 3.1 Hra ́tky s cˇı ́sly Na ́pad: 1 Ko ́dova ́nı ́:1 Styl u ́lohy:Jednoduche ́ cvicˇenı ́ na za ́kladnı ́ procvicˇenı ́ pra ́ce s celocˇı ́selny ́mi promeˇnny ́mi a s cykly. Program nacˇte prˇirozene ́ cˇı ́slon a vypı ́sˇe vy ́sledek vy ́pocˇtu nad tı ́mto cˇı ́slem. Na ́meˇty na vy ́pocˇty: 1. soucˇet prvnı ́chn prˇirozeny ́ch cˇı ́sel, 2. faktoria ́l cˇı ́slan, tj. soucˇin prvnı ́ch n cˇı ́sel, 3. celou cˇa ́st odmocniny z cˇı ́slan, tj. nejveˇtsˇı ́ cele ́ x takove ́, zˇe x 2 ≤ n, 4. ciferny ́ soucˇet cˇı ́slan, 5. pocˇet jednicˇek obsazˇeny ́ch v cˇı ́sle n, 6. cˇı ́slon zapsane ́ pozpa ́tku, 7. informace o tom, zdan je platne ́ rodne ́ cˇı ́slo. 26 3. Pocˇı ́ta ́nı ́ s cˇı ́sly Doplnˇujı ́cı ́ komenta ́rˇ Toto cvicˇenı ́ slouzˇı ́ prˇedevsˇı ́m k procvicˇenı ́ cyklu ̊. Z tre ́ninkovy ́ch du ̊vodu ̊ je uzˇitecˇne ́ vyrˇesˇit stejny ́ u ́kol neˇkolika ru ̊zny ́mi zpu ̊soby. V rˇesˇenı ́ch na konci knihy je naprˇı ́klad uvedeno 5 mozˇnostı ́, jak zapsat rˇesˇenı ́ prvnı ́ho u ́kolu. U prˇı ́kladu ̊ 4.–7. spocˇı ́va ́ za ́kladnı ́ princip v procha ́zenı ́ jednotlivy ́ch cifer cˇı ́sla. Toho snadno dosa ́hneme tak, zˇe cˇı ́slo postupneˇ deˇlı ́me 10 a zkouma ́me zbytek po deˇlenı ́ 10 (operace modulo). 3.2 Posloupnosti Na ́pad:1-3 Ko ́dova ́nı ́:1-2 Styl u ́lohy:Procvicˇenı ́ pra ́ce s celocˇı ́selny ́mi promeˇnny ́mi, s cykly a prˇı ́padneˇ poli. Odhalte princip na ́sledujı ́cı ́ch posloupnostı ́ a pote ́ napisˇte pro kazˇdou z nich program, ktery ́ dostane na vstup cˇı ́slon a na vy ́stup vypı ́sˇe prvnı ́ch n cˇlenu ̊ dane ́ posloupnosti. 1. 1, 2, 3, 4, 5, 6, . . . 2. 1, 3, 5, 7, 9, 11, . . . 3. 1, 5, 9, 13, 17, 21, 25, 29, . . . 4. 1, 2, 4, 7, 11, 16, . . . 5. 1, 2, 4, 8, 16, 32, . . . 6. 1, 2, 6, 24, 120, . . . 7. 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, . . . 8. 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, . . . 9. 1, 2, 4, 7, 9, 12, 18, 24, 32, 38, 42, 50, 56, 64, 71, 73, 75, 81, . . . 10. 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, . . . 11. 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, . . . Doplnˇujı ́cı ́ komenta ́rˇ Principy posloupnostı ́ jsou na ́sledujı ́cı ́: 1. prˇirozena ́ cˇı ́sla, 2. licha ́ cˇı ́sla, tj. aritmeticka ́ posloupnost s krokem 2, 3. aritmeticka ́ posloupnost s krokem 4, 4. aritmeticka ́ posloupnost 2. stupneˇ – rozdı ́ly mezi cˇleny tvorˇı ́ aritmetickou posloupnost s krokem 1, tj. prˇirozena ́ cˇı ́sla, 5. mocniny dvojky, tj. geometricka ́ posloupnost s krokem 2, 3.3. Collatzu ̊v proble ́m 27 6. faktoria ́ly, 7. u ́seky prˇirozeny ́ch cˇı ́sel postupneˇ se prodluzˇujı ́cı ́ de ́lky, 8. prvocˇı ́sla, 9. dalsˇı ́ cˇlen vznikne tak, zˇe k aktua ́lnı ́mu cˇlenu prˇicˇteme pocˇet jeho deˇlitelu ̊, 10. popis prˇedchozı ́ho cˇlenu, dalsˇı ́ cˇlen dostaneme tak, zˇe prˇedchozı ́ cˇlen „prˇecˇteme nahlas“: „jedna jednicˇka“, „dveˇ jednicˇky“, „jedna dvojka, jedna jednicˇka“, 11. Golombova sebe-popisujı ́cı ́ posloupnost, neklesajı ́cı ́ rˇada kladny ́ch cˇı ́sel, jejı ́zˇn-ty ́ cˇlen rˇady uda ́va ́, kolikra ́t se opakuje cˇı ́slo n. Prvnı ́ch 6 posloupnostı ́ lze vyrˇesˇit jednodusˇe pomocı ́ jednoho for cyklu a neˇkolika celocˇı ́selny ́ch promeˇnny ́ch, dalsˇı ́ 3 posloupnosti vyzˇadujı ́ vnorˇene ́ cykly nebo pouzˇitı ́ pomocne ́ funkce. Z uvedeny ́ch posloupnostı ́ jsou nejna ́rocˇneˇjsˇı ́ dveˇ poslednı ́, i kdyzˇ i u nich je na ́rocˇne ́ prˇijı ́t prˇedevsˇı ́m na princip posloupnosti, programa ́torsky jsou vcelku prˇı ́mocˇare ́. V prˇı ́padeˇ posloupnosti s popisem prˇedchozı ́ho cˇlenu mu ̊zˇe by ́t vy ́hodneˇjsˇı ́ pracovat s cˇleny jako rˇeteˇzci spı ́sˇe nezˇ jako s cely ́mi cˇı ́sly. Golombova sebe-popisujı ́cı ́ rˇada vyzˇaduje pouzˇitı ́ jednorozmeˇrne ́ho pole. Mnoho dalsˇı ́ch zajı ́mavy ́ch na ́meˇtu ̊ na zada ́nı ́ lze najı ́t v internetove ́ encyklopedii celocˇı ́selny ́ch posloupnostı ́ (The On-Line Encyclopedia of Integer Sequences,oeis.org). V te ́to encyklopedii je uvedena take ́ rˇada doplnˇujı ́cı ́ch komenta ́rˇu ̊ a zajı ́mavostı ́. Zajı ́mavy ́m rozsˇı ́rˇenı ́m te ́to u ́lohy je automaticke ́ doplnˇova ́nı ́ rˇad – implementace „umeˇle ́ inteligence“, ktera ́ odhalı ́ princip posloupnosti a automaticky ji doplnı ́. Toto je rea ́lne ́ jen pro relativneˇ jednoduche ́ posloupnosti,jako je prvnı ́ch 5 uvedeny ́ch posloupnostı ́. I tak tato varianta prˇedstavuje u ́kol obtı ́zˇnosti 4–5. 3.3 Collatzu ̊v proble ́m Na ́pad:1 Ko ́dova ́nı ́:1 Styl u ́lohy:Programa ́torsky jednoduche ́ cvicˇenı ́, ktere ́ ilustruje velmi zajı ́mavy ́ proble ́m z teorie cˇı ́sel. Prˇedmeˇtem tohoto cvicˇenı ́ je matematicky ́ proble ́m, ktery ́ je zna ́m pod mnoha ru ̊zny ́mi na ́zvy – kromeˇ na ́zvu Collatzu ̊v proble ́m se mu ̊zˇete setkat te ́zˇ s oznacˇenı ́m3n+1proble ́m, Ulamu ̊v proble ́m, Syrakusky ́ proble ́m a spoustou dalsˇı ́ch jmen. Proble ́m se ty ́ka ́ na ́sledujı ́cı ́ho postupu: „vezmi prˇirozene ́ cˇı ́slo, pokud je sude ́, vydeˇl jej dveˇma, pokud je liche ́, vyna ́sob jej trˇemi a prˇicˇti jednicˇku; 28 3. Pocˇı ́ta ́nı ́ s cˇı ́sly tento postup opakuj, dokud nedostanesˇ cˇı ́slo jedna“. Program tedy vypada ́ na ́sledovneˇ: def collatz(n): while n != 1: print n if n % 2 == 0: n = n / 2 else: n = 3*n + 1 Ilustrujme postup na prˇı ́kladu. Pokud zacˇneme v cˇı ́sle 7, dostaneme na ́sledujı ́cı ́ posloupnost: 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Acˇkoliv je definice postupu jednoducha ́, vy ́sledne ́ chova ́nı ́ je velmi zajı ́mave ́. Jizˇ na prˇı ́kladu zacˇı ́najı ́cı ́m v cˇı ́sle 7 je videˇt, zˇe chova ́nı ́ vypada ́ docela „chaoticky“. A kdyzˇ zacˇneme cˇı ́slem 27, potrˇebujeme dokonce 111 kroku ̊, nezˇ se dostaneme na cˇı ́slo 1 a jako jeden z mezivy ́sledku ̊ dostaneme cˇı ́slo 9 232. Pru ̊beˇh teˇchto dvou posloupnostı ́ je graficky zna ́zorneˇn na obra ́zku 3.1. Kdyzˇ ma ́me takto definovany ́ postup, nabı ́zı ́ se na ́sledujı ́cı ́ ota ́zka. Platı ́, zˇe at’zacˇneme v libovolne ́m prˇirozene ́m cˇı ́sle, skoncˇı ́ posloupnost v jednicˇce? Tato ota ́zka cˇinı ́ uvedenou posloupnost zna ́mou, protozˇe nikdo totizˇ zatı ́m nezna ́ s jistotou odpoveˇd ’ . Collatzova (nebo te ́zˇ Ulamova) hypote ́za rˇı ́ka ́, zˇe odpoveˇd ’ na uvedenou ota ́zku je „ano“. Experimenta ́lneˇ bylo oveˇrˇeno, zˇe i pro velmi vysoka ́ cˇı ́sla se vy ́pocˇet nakonec dostane do jednicˇky, takzˇe veˇtsˇina lidı ́ veˇrˇı ́, zˇe hypote ́za platı ́. Nicme ́neˇ matematicky ́ du ̊kaz zatı ́m nema ́me a proble ́m je sta ́le otevrˇeny ́. V ra ́mci nasˇeho cvicˇenı ́ se nebudeme pousˇteˇt do rˇesˇenı ́ obtı ́zˇny ́ch matematicky ́ch proble ́mu ̊, ale vyuzˇijeme te ́ma k neˇkolika jednoduchy ́m programa ́torsky ́m cvicˇenı ́m: 1. Pro zadane ́ cˇı ́slo vypocˇı ́tejte posloupnost vygenerovany ́ch cˇı ́sel a tuto posloupnost zobrazte graficky (podobneˇ jako na obra ́zku 3.1 A). 2. Pro cˇı ́sla od 1 don vypocˇı ́tejte, kolik kroku ̊ potrˇebujeme, nezˇ se dostaneme do jednicˇky. Hodnoty vykreslete grafem – pro male ́n vypada ́ vy ́sledny ́ graf vcelku na ́hodneˇ, pro velke ́n se vsˇak objevı ́ zajı ́mava ́ struktura (viz obra ́zek 3.1 B). 3. Podobneˇ jako prˇedchozı ́ bod, nezobrazujte vsˇak pocˇet kroku ̊, ale maxima ́lnı ́hodnotu, na kterou v pru ̊beˇhu vy ́pocˇtu narazı ́me (naprˇ. pro zacˇa ́tek v cˇı ́sle 7 je touto maxima ́lnı ́ hodnotou 52). 4. Pro ktere ́ cˇı ́slo od 1 do 100 000 potrˇebujeme nejvı ́ce kroku ̊, nezˇ dospeˇjeme do jednicˇky? Jake ́ je maxima ́lnı ́ cˇı ́slo, ktere ́ se v prˇı ́slusˇne ́ posloupnosti objevı ́? 3.3. Collatzu ̊v proble ́m 29 Obra ́zek 3.1:Collatzu ̊v proble ́m – grafy 5. Rekordman je takove ́ cˇı ́slox, pro ktere ́ je pocˇet potrˇebny ́ch kroku ̊ veˇtsˇı ́ nezˇ pro jake ́kolivy < x. Posloupnost rekordmanu ̊ zacˇı ́na ́ 1, 2, 3, 6, 7, 9, 18, 25, 27, 54. Najdeˇte vsˇechny rekordmany do 100 000. 6. Vyzkousˇejte jine ́ funkce podobne ́ho typu a prozkoumejte jejich chova ́nı ́. Co se naprˇı ́klad stane, kdyzˇ vy ́raz3n + 1 nahradı ́me za 3n − 1? Pak uzˇ uvedena ́ hypote ́za neplatı ́ – kdyzˇ zacˇneme ve vhodne ́m cˇı ́sle, vy ́pocˇet se zacyklı ́ a nikdy se nedostane do jednicˇky. Najdeˇte takove ́ cˇı ́slo. Doplnˇujı ́cı ́ komenta ́rˇ Pokud bychom se chteˇli proble ́mem zaby ́vat pro vysoka ́ cˇı ́sla, bylo by smysluplne ́ snazˇit se program optimalizovat naprˇı ́klad pomocı ́ ukla ́da ́nı ́ mezivy ́- 30 3. Pocˇı ́ta ́nı ́ s cˇı ́sly sledku ̊. Pro hodnoty uvedene ́ v zada ́nı ́ (do 100 000) vsˇak bohateˇ stacˇı ́ prˇı ́mocˇare ́ rˇesˇenı ́ bez jaky ́chkoliv optimalizacı ́ – prosteˇ prˇepı ́sˇeme funkci pro pocˇı ́ta ́nı ́ posloupnosti a pak ji opakovaneˇ vola ́me. Pro graficke ́ zobrazenı ́ vy ́sledku ̊ mu ̊zˇeme vyuzˇı ́t knihovnu pro zobrazenı ́ grafu ̊, jezˇ je dostupna ́ ve veˇtsˇineˇ programovacı ́ch jazyku ̊. Klidneˇ ale mu ̊zˇeme pouzˇı ́t i beˇzˇny ́ tabulkovy ́ procesor, do ktere ́ho zkopı ́rujeme vy ́sledky nasˇeho programu. 3.4 Na ́hodna ́ procha ́zka Na ́pad:1-2 Ko ́dova ́nı ́:1-3 Styl u ́lohy:Jednoducha ́ cvicˇenı ́ s vyuzˇitı ́m genera ́toru na ́hodny ́ch cˇı ́sel. Na ́hodna ́ procha ́zka je postup spocˇı ́vajı ́cı ́ v mnoha opakovany ́ch na ́hodny ́ch krocı ́ch. Jde o jednoduchy ́ matematicky ́ princip, ktery ́ vsˇak dobrˇe modeluje mnoho rea ́lny ́ch jevu ̊ a je intenzivneˇ studova ́n v oblastech, jako je fyzika, finance nebo biologie. Pro u ́cˇel u ́vodnı ́ho programa ́torske ́ho cvicˇenı ́se zameˇrˇı ́me pouze na jednoduche ́ variace na toto te ́ma: 1. „Opilcova procha ́zka“ probı ́ha ́ na jednorozmeˇrne ́m pla ́nu velikosti n. Na leve ́m konci pla ́nu je domov, na prave ́m hospoda. Opilec se na zacˇa ́tku nacha ́zı ́ na poli cˇı ́slok. V kazˇde ́m kole se opilec s pravdeˇpodobnostı ́ p pohne smeˇrem k hospodeˇ a s pravdeˇpodobnostı ́1 − p smeˇrem domu ̊. Procha ́zka koncˇı ́, kdyzˇ opilec dorazı ́ do hospody nebo domu ̊. 2. „Na ́hodna ́ procha ́zka ve 2D“ probı ́ha ́ na mrˇı ́zˇce velikostin×n, zacˇı ́na ́me uprostrˇed, v kazˇde ́m kroku se pohneme se stejnou pravdeˇpodobnostı ́ na jednu ze 4 sousednı ́ch buneˇk. Procha ́zka koncˇı ́, kdyzˇ narazı ́me na kraj mrˇı ́zˇky. 3. Zjednodusˇene ́ „C ˇ loveˇcˇe, nezlob se“ se hraje na hracı ́m pla ́nu velikosti na pouze s 1 figurkou. Figurka se posunuje podle hodu ̊ kostkou, tj. podle na ́hodneˇ generovany ́ch cˇı ́sel od 1 do 6. Kdyzˇ padne cˇı ́slo 6, ha ́zı ́me znova a cˇı ́sla scˇı ́ta ́me. Figurka se posunuje o celkovy ́ soucˇet. Hra koncˇı ́, jakmile dorazı ́me na poslednı ́ pole, prˇicˇemzˇ se musı ́me trefit prˇesneˇ na poslednı ́ pole. Pokud se netrefı ́me, figurka stojı ́. Za ́kladnı ́ u ́kol pro vsˇechny varianty spocˇı ́va ́ v napsa ́nı ́ programu, ktery ́ pro zadane ́ parametry odsimuluje pru ̊beˇh procha ́zky a textoveˇ cˇi graficky jej zna ́zornı ́. Rozsˇirˇujı ́cı ́ u ́kol spocˇı ́va ́ v opakovane ́m spusˇteˇnı ́ simulace a vy ́pocˇtu pru ̊meˇrny ́ch charakteristik simulace: Jaka ́ je pro dane ́n,k,p pravdeˇpodobnost, zˇe opilec dorazı ́ do hospody? Jaka ́ je pru ̊meˇrna ́ de ́lka 2D procha ́zky na mrˇı ́zˇce n×n? Jak za ́visı ́ u zjednodusˇene ́ho „C ˇ loveˇcˇe, nezlob se“ de ́lka hry na velikosti pla ́nu? 3.5. Deˇlitelnost a prvocˇı ́sla 31 Doplnˇujı ́cı ́ komenta ́rˇ Jde o vyuzˇitı ́ za ́kladnı ́ch programa ́torsky ́ch konstrukcı ́, takzˇe u ́lohy nebudeme rozebı ́rat. Jen poznamenejme, zˇe minima ́lneˇ pro neˇktere ́ varianty lze uvedene ́ pru ̊meˇrne ́ charakteristiky vypocˇı ́tat i matematicky, tj. bez prova ́deˇnı ́ simulacı ́. C ˇ tena ́rˇ s matematicky ́mi ambicemi se tedy mu ̊zˇe pokusit odvodit prˇı ́slusˇny ́ vy ́sledek a pak jej pomocı ́ programu oveˇrˇit. Prˇı ́padneˇ je mozˇne ́ se zaby ́vat nejen pru ̊meˇrny ́mi hodnotami, ale i dalsˇı ́mi parametry prˇı ́slusˇny ́ch pravdeˇpodobnostnı ́ch distribucı ́, naprˇı ́klad media ́nem nebo rozptylem. 3.5 Deˇlitelnost a prvocˇı ́sla Na ́pad:2-3 Ko ́dova ́nı ́:1-3 Styl u ́lohy:Jednoducha ́ cvicˇenı ́ rˇesˇitelna ́ ru ̊zny ́mi algoritmicky ́mi prˇı ́stupy, na ktery ́ch lze ilustrovat rozdı ́ly v efektiviteˇ algoritmu ̊. Za ́kladnı ́ zada ́nı ́ spocˇı ́vajı ́ v tom, zˇe program nacˇte prˇirozena ́ cˇı ́sla a vypı ́sˇe informace souvisejı ́cı ́ s deˇlitelnostı ́ cˇi prvocˇı ́selnostı ́: 1. Vy ́pis vsˇech deˇlitelu ̊ cˇı ́slan. 2. Test prvocˇı ́selnosti cˇı ́slan. 3. Vy ́pis prvnı ́chn prvocˇı ́sel. 4. Vy ́pis nejveˇtsˇı ́ho spolecˇne ́ho deˇlitele cˇı ́sel n a m. 5. Hleda ́nı ́ „prvocˇı ́selny ́ch dvojcˇat“: program nacˇte cˇı ́slo n a najde nejmensˇı ́ p≥ n takove ́, zˇe p a p + 2 jsou obeˇ prvocˇı ́sla. Pokrocˇilejsˇı ́ ztva ́rneˇnı ́ te ́matu dostaneme za vyuzˇitı ́ bitmapove ́ (prˇı ́padneˇ textove ́) grafiky, kdy zakreslujeme distribuci prvocˇı ́sel graficky pomocı ́ takzvane ́ Ulamovy spira ́ly. Ta vznikne tak, zˇe si napı ́sˇeme vsˇechna cˇı ́sla „do sˇneka“ a potom vybereme pouze prvocˇı ́sla. Na obra ́zku 3.2. ma ́me takto zna ́zorneˇno prvnı ́ch 40 tisı ́c prˇirozeny ́ch cˇı ́sel, prvocˇı ́sla jsou cˇerneˇ. Podobny ́m zpu ̊sobem mu ̊zˇeme zna ́zornit trˇeba cˇı ́sla deˇlitelna ́ zadany ́m cˇı ́slem n. Doplnˇujı ́cı ́ komenta ́rˇ Prvocˇı ́sla jsou velmi zajı ́mavy ́ matematicky ́ objekt, protozˇe nejsou nijak striktneˇ pravidelna ́, ale prˇitom vykazujı ́ rˇadu dı ́lcˇı ́ch pravidelnostı ́. Tuto vlastnost prvocˇı ́sel na ́zorneˇ ilustruje Ulamova spira ́la, kterou objevil Stanislav Ulam v sˇedesa ́ty ́ch letech, kdyzˇ si cˇma ́ral po papı ́rˇe beˇhem nudne ́ prˇedna ́sˇky. Vy ́sledny ́ obra ́zek nema ́ zˇa ́dny ́ zjevny ́ rˇa ́d, nicme ́neˇ jsou na neˇm videˇt vy ́razne ́ „diagona ́ly“. S prvocˇı ́sly se take ́ va ́zˇe mnoho teˇzˇky ́ch a cˇasto i nevyrˇesˇeny ́ch 32 3. Pocˇı ́ta ́nı ́ s cˇı ́sly Obra ́zek 3.2:Ulamova spira ́la: ilustrace principu a spira ́la velikosti 200 × 200 matematicky ́ch proble ́mu ̊. Jeden takovy ́ zna ́my ́ proble ́m souvisı ́ s prvocˇı ́selny ́mi dvojcˇaty zmı ́neˇny ́mi v zada ́nı ́: Existuje nekonecˇneˇ mnoho prvocˇı ́selny ́ch dvojcˇat? Vy ́pis vsˇech deˇlitelu ̊ lze realizovat prˇı ́mocˇarˇe pomocı ́ jednohofor cyklu. Test prvocˇı ́selnosti mu ̊zˇeme udeˇlat prˇı ́mocˇarˇe spocˇı ́ta ́nı ́m deˇlitelu ̊. Program mu ̊zˇeme mı ́rneˇ optimalizovat, naprˇı ́klad tak, zˇe zkousˇı ́me deˇlit pouze dvojkou a lichy ́mi cˇı ́sly, a to jen do odmocniny zn. Jsou pochopitelneˇ mozˇne ́ i vy ́razneˇjsˇı ́ optimalizace – testova ́nı ́ prvocˇı ́sel je du ̊lezˇity ́ prakticky ́ proble ́m naprˇı ́klad v modernı ́ kryptografii. Pokrocˇilejsˇı ́ optimalizace ale jdou vysoce nad ra ́mec u ́vodnı ́ch programa ́torsky ́ch cvicˇenı ́. Vy ́pis prvocˇı ́sel mu ̊zˇeme udeˇlat dveˇma za ́kladnı ́mi zpu ̊soby, z tre ́ninkovy ́ch du ̊vodu ̊ je vhodne ́ implementovat oba dva. Prvnı ́ metoda je prosta ́ hruba ́ sı ́la. Procha ́zı ́me postupneˇ prˇirozena ́ cˇı ́sla a pro kazˇde ́ z nich zjistı ́me pomocı ́ vy ́sˇe popsane ́ho testu, zda je prvocˇı ́slem. Druha ́ metoda se nazy ́va ́ Eratosthenovo sı ́to a je ilustrova ́na na obra ́zku 3.3. Napı ́sˇeme si cˇı ́sla od 2 don, v kazˇde ́m kroku vzˇdy vybereme nejmensˇı ́ neoznacˇene ́ cˇı ́slo a oznacˇı ́me vsˇechny na ́sobky tohoto cˇı ́sla. Vsˇimneˇte si, zˇe v uvedene ́m obra ́zku jsou jizˇ po 4 krocı ́ch vy ́pocˇtu vsˇechna neoznacˇena ́ cˇı ́sla prvocˇı ́sla. Take ́ hleda ́nı ́ nejveˇtsˇı ́ho spolecˇne ́ho deˇlitele mu ̊zˇeme deˇlat vı ́ce zpu ̊soby. Za ́kladnı ́ rˇesˇenı ́ je opeˇt hruba ́ sı ́la: procha ́zı ́me sestupneˇ cˇı ́sla odn do 1 a zkou- 3.5. Deˇlitelnost a prvocˇı ́sla 33 sˇı ́me jimi deˇlitn i m, dokud nenajdeme spolecˇne ́ho deˇlitele. Lepsˇı ́ rˇesˇenı ́ je Euclidu ̊v algoritmus, ktery ́ je zalozˇen na pozorova ́nı ́, zˇeNSD(n,m) = NSD(m,n mod m), kde mod znacˇı ́ zbytek po deˇlenı ́. Tento vztah mu ̊zˇeme snadno prˇeve ́st na algoritmus vy ́pocˇtu, naprˇı ́klad pro cˇı ́sla 504 a 180 probı ́ha ́ vy ́pocˇet na ́sledovneˇ:NSD(504,180) = NSD(180,144) = NSD(144,36) = NSD(36,36) = NSD(36,0) = 36. Alternativnı ́ za ́pis stejne ́ho vy ́pocˇtu ukazuje tabulka 3.1. Euclidu ̊v algoritmus je vy ́razneˇ efektivneˇjsˇı ́ nezˇ naivnı ́ algoritmus, cozˇ jde snadno experimenta ́lneˇ oveˇrˇit. Prˇı ́klad slouzˇı ́ jako dobra ́ ilustrace rozdı ́lu ̊ mezi vy ́pocˇetnı ́ na ́rocˇnostı ́ ru ̊zny ́ch algoritmu ̊. Obra ́zek 3.3:Eratosthenovo sı ́to: prvnı ́ 4 kroky vy ́pocˇtu Tabulka 3.1:Euclidu ̊v algoritmus: prˇı ́klad krokn m 1504 180 2180 144 3144 36 536 36 636 0


       

internetové knihkupectví ABZ - online prodej knih


Knihy.ABZ.cz - knihkupectví online -  © 2004-2018 - ABZ ABZ knihy, a.s. TOPlist