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

je prázdný
a
b

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

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 ...


Titul doručujeme za 3 pracovní dny
Vaše cena s DPH:  211
+
-
ks
rozbalKdy zboží dostanu
rozbalVýhodné poštovné: 39Kč
rozbalOsobní odběr zdarma
Doporučená cena:  249 Kč
15%
naše sleva
7
bo za nákup

ukázka z knihy ukázka

Titul je dostupný ve formě:
tištěná forma elektronická forma

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
Kniha je zařazena v kategoriích
Radek Pelánek - další tituly autora:
Zážitkové výukové programy Zážitkové výukové programy
Pelánek, Radek
Cena: 184 Kč
Jak to vyřešit? -- Logické úkoly a hry Jak to vyřešit?
Pelánek, Radek
Cena: 212 Kč
Modelování a simulace komplexních systémů -- Jak lépe porozumět světu Modelování a simulace komplexních systémů
Pelánek, Radek
Cena: 352 Kč
Hlavolamikon Hlavolamikon
Pelánek, Radek
Cena: 169 Kč
Hlavolamikon Hlavolamikon
Pelánek, Radek
Cena: 93 Kč
Programátorská cvičebnice Programátorská cvičebnice
Pelánek, Radek
Cena: 121 Kč
 
Zákazníci kupující knihu "Programátorská cvičebnice" mají také často zájem o tyto tituly:
Algoritmy v jazyku C a C/ -- 2., rozšířené a aktualizované vydání Algoritmy v jazyku C a C/
Prokop, Jiří
Cena: 211 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í - online prodej knih


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