Prodám výdělečný web ZelenyTiket.cz 1.2Mil/rok
Zobrazují se odpovědi 1 až 11 z 11

Úkol na informatiku

  1. Ahoj, dostali jsme zadání úkolu z informatiky a nikdo ze třídy netuší jak na to.
    Chtěl jsem se zeptat, zda by nám někdo neporadil? :)
    Jedná se o Python.
    Zadání:
    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.
    Předem díky všem za pomoc :)
    Já jdu zatím zkusit něco upravit, tak to sem kdyžtak za chvíli hodím na kontrolu :)
    Naposledy upravil Pavel Čermák : 29.05.2013 v 21:47

  2. Co se právě děje na Webtrhu?
  3. 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-...hp-pomoci-foru
    http://diskuse.jakpsatweb.cz/?action...9&topic=107573

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

  4. Citace Původně odeslal BumbleBeee Zobrazit příspěvek
    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-...hp-pomoci-foru
    http://diskuse.jakpsatweb.cz/?action...9&topic=107573

    Pokud jsem špatně pochopil o co jde, tak sorry a považuj tu zprávu za bezpředmětnou :D
    V PHP bych to asi nějak vymyslel, jde bohužel o to, že se jedná o Python.
    Přidám to do zadání, není to totiž patrné. Děkuji za reakci na odkazy mrknu, snad se mi povede to nějak převést do python verze :)

  5. Jednoduchá rada:
    Musíš to opravdu zkoušet až do n - 1? (kdyz je cislo n slozene tak a * b = n, v nejhorsim pripade a = b)
    Má smysl zkoušet všechna sudá čísla?

    Pokud se bude algoritmus opakovat, tak mrkni na termín Eratostenovo síto.

    Komplikovaná rada:
    Vygoogli si Rabin-Millerův test

  6. Od hrubého pohledu bych si tipnul, že zlepšení má být tzv. Eratosthenovo síto - tzn. while MoznyDelitel < n se prepise na while MoznyDelitel < sqrt(n) - nebo jak se to v pythonu zapise. Jde o to, ze neumusím testovat az do konce - když mám 25, tak stačí testovat do 5, potom se mocněnce obrátí.


  7. Tak se mi povedlo sesmolit nějaký algoritmus, který by měl počítat s tím, že pokud je dotyčné číslo n dělitelné (2,3,5,7,9) tak není prvočíslo. Ze začátku mi to házelo true všude, teď mi to nevypíše nic. Pomůžete mi nalézt chybu ?
    Kód:
    def prvocislo ( n ) :                 
        JePrvocislo = True
        delitele = [2,3,5,7,9] #seznam prvocisel, kterym kdyz to vydelime tak to neni prvocislo
        y = len(delitele)  #pocet polozek v seznamu
        x = 0 
        while x < y : #kdyz x je mensi nez pocet polozek v seznamu
            if n % delitele[x] == 0 : #pokud je n delitelne polozkou v seznamu s id x se zbytkem 0
            JePrvocislo = False #prvocislo to neni
            x = x + 1 #pricteme k id x (polozka seznamu 1) a jedeme znova
        return JePrvocislo
    Zkoušel sem místo funkce while použít for, ale tam se mi nepovedlo zadat parametr x < y, < to hlásilo jako chybu..
    Naposledy upravil Pavel Čermák : 29.05.2013 v 23:25

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

  9. Citace Původně odeslal Martin Schlemmer Zobrazit příspěvek
    Když kopírujete kód, zkopírujte přece i prázdné znaky; o to víc v Pythonu.
    kopírované je to i s tabulátory, ručně jsem to i upravoval před postnutím zde forum, po doplnění komentářů se to trošku rozházelo, omlouvám se

  10. Vložte to do [ CODE ] [ / CODE ] (bez mezer).

  11. Citace Původně odeslal Martin Schlemmer Zobrazit příspěvek
    Vložte to do [ CODE ] [ / CODE ] (bez mezer).
    Kód:
    def prvocislo ( n ) :                 
        JePrvocislo = True
        delitele = [2,3,5,7,9]
        y = len(delitele)
        x = 0
        while x < y :
            if n % delitele[x] == 0 :
                JePrvocislo = False
                x = x + 1
        return JePrvocislo


    ---------- Příspěvek doplněn 29.05.2013 v 23:53 ----------

    Tak už jsem nalezl chybu. Pro případ kdyby to někdo potřeboval, výsledný kód je:
    Kód:
    def prvocislo ( n ) :
        delitele = [2,3,5,7,9]
        JePrvocislo = "Toto je prvočíslo"
        if n not in delitele :
            y = len(delitele)
            x = 0
            while x < y :
                if n % delitele [x] == 0 :
                    JePrvocislo = "Toto není prvočíslo"
                x = x + 1
        return JePrvocislo
    Všem děkuji za podporu a snad vám to někdy oplatím :)
    Naposledy upravil Pavel Čermák : 30.05.2013 v 00:01

Hostujeme u Server powered by TELE3