Úkol na informatiku

Tenhle úkol spočívá opět ve vylepšení existujícího postupu (můžete samozřejmě i vymyslet svůj).

Jedná se o ověření prvočíelnosti. Váš postup dostane číslo, a má co nejrychleji rozhodnout, jestli je to číslo prvočíslem. Prvočíslo je takové přirozené číslo, které má právě dva různé dělitele, což tedy musí být 1 a číslo samo. Ty první jsou 2, 3, 5, 7, 11... další snadno najdete s pomocí přiloženého programu.

Jako základ uvádím pomalý postup, jednou s while-cyklem, jednou s for-cyklem, jednou jako vývojový diagram. Každá verze ale dělá totéž - je na vás, ze které budete vycházet, které nejlíp rozumíte.

Odevzdejte:

1) Vylepšený algoritmus (zdrojový kód, vývojový diagram, přesný slovní popis...) ověření prvočíselnosti.

2) Odhad složitosti: čemu bude úměrný počet kroků (např. dělení se zbytkem) algoritmu? Rozlište, jestli odhadujete průměrnou, nejhorší, nebo jakou složitost.

Dobrým nápadem můžete snížit nejhorší složitost přibližně na polovinu, dvěma způsoby, takže celkem na čtvrtinu. Tím ovšem algoritmus zůstane lineární (viz učební text - toto zrychlení by bylo možné dosáhnout i "hrubou silou", čtyřnásobně rychlejším počítačem). Ještě lepším nápadem můžete z algoritmu udělat rychlejší než lineární (za to bych dal bonusové body). Kromě toho můžete navíc výrazně zlepšit sice nikoliv nejhorší (ta zůstane stejná), ale průměrnou složitost - a i to se hodí.

Několik obecných námětů k přemýšlení umístím do učebního textu.

Výzhozí algoritmus k vylepšení:

Algoritmus spočívá v systematickém ověřování, že všechna čísla 2..n-1 NEJSOU děliteli n. Pokud tam nějaké je, n není prvočíslem.

def PrvocisloWhile ( n ) : # overeni prvociselnosti; n je cele cislo vetsi nez 1 (jinak neni co overovat)

JePrvocislo = True # na zacatku predpokladejme, ze je to prvocislo

MoznyDelitel = 2 # budeme postupne zkouset delitele, zacneme s dvojkou (jednicku netreba zkouset)

while MoznyDelitel < n : # delitel musi byt mensi nez n, az dosahne n, tak skoncime

if n % MoznyDelitel == 0 : # overeni delitelnosti (zbytek musi vyjit nulovy)

JePrvocislo = False # kdyz jsme nasli delitele, zapamatujeme si, ze to NENI prvocislo

MoznyDelitel = MoznyDelitel + 1 # zvysime hodnotu, v dalsim behu cyklu zkusime dalsiho delitele

return JePrvocislo # promenna JePrvocislo uchovava, jestli dane cislo je prvocislo nebo ne - a to je nase odpoved

def PrvocisloFor ( n ) : # tenhle program dela to same, ale for-cyklus nam dovoluje to zapsat strucneji

JePrvocislo = True

for MoznyDelitel in range(2, n) : # diky for-cyklu a funkci range() bude MoznyDelitel nabyvat hodnot 2..n-1

if n % MoznyDelitel == 0 :

JePrvocislo = False

return JePrvocislo

Vývojový diagram

Jak na to (například):

- Prostudujte algoritmus, pochopte, jak funguje.

- Zkuste ho provést ručně pro několik čísel, třeba 5, 6, 12, 13.

- Případně ho zkoušejte spouštět na počítači. Přidejte na vhodná místa "print (MoznyDelitel)" apod., abyste viděli, co se v algoritmu děje.

- Hledejte, co se počítá zbytečně. Má smysl zkoušet, jestli... 33 dělí 47? 16 dělí nějaké prvočíslo? 4 delí 9, když už jsme zkusili 3? Všímejte si přirozených urychlení, které používáte, když prvočíselnost ověřujete ručně. Zkuste z těchto urychlení udělat pravidlo a zapracovat ho do algoritmu.

Napsal BumbleBeee;955270

Celý jsem to nečetl...:) Nicméně třeba v PHP existuje spusta příkladů na spočítání prvočísel - viz http://www.odpovedi.cz/otazky/vypis-prvocisel-od-1-1000-v-php-pomoci-foru

http://diskuse.jakpsatweb.cz/?action=vthread&forum=9&topic=107573

Pokud jsem špatně pochopil o co jde, tak sorry a považuj tu zprávu za bezpředmětnou :D

Napsal Martin Schlemmer;955322

Když kopírujete kód, zkopírujte přece i prázdné znaky; o to víc v Pythonu.

Napsal Martin Schlemmer;955331

Vložte to do (bez mezer).