Zpět na seznam článků     Číst komentáře (23)     Verze pro tisk

Algoritmy I

Autor: pr0ph3t   
26.2.2007

Popis nekolika algoritmy na ktere jsem v posledni dobe narazil - vypocet odmocnin bez pouziti funkce sqrt, prevody mezi ciselnymi soustavami.


Pod vlivem usertextu o PHP BruteForceru a par zvidavych dotazech na IRC jsem se rozhodl napsat tenhle usertext, protoze se muze najit par dalsich lidi, kterym by tyto algoritmy mohly v budoucnu pomoct.

Prvni dva z nich se tykaji vypoctu odmocniny cisel bez pouziti funkci jako je sqrt a podobne. Uplne prvnim je newtonova iteracni metoda, druhy je vlatne jen matematicke odvozeni.

Poslednim algoritmem je pak jako dodatek ke clanku o BruteForceru a k diskuzi pod nim, kde se par lidi zminilo o prevadeni, obecny algoritmus prevodu cisel mezi polyadickymi soustavami.


Newtonova iteracni metoda

Tato metoda je zalozena na generovani nekonecne rady cisel, v niz kazde dalsi je blize a blize hledane odmocnine.



Pokud by nekoho zajimal presny postup proc to tak je, tak ho odkazu na dukaz vypoctu zde:
http://www.fi.muni.cz/~xsmerk/ib001/
Pro zajemce o zapis v jinem jazyce je tu i odkaz na totez v pascalu
http://kozzak.chytrak.cz/skola/NEWTON.PAS


Matematicke vypocteni odmocniny bez pouziti funkce sqrt

Nejedna se o zadny konkretni algoritmus, ale spis o to uvedomit si ze odmocnina (i mocnina) se da vypocitat i pomoci logaritmu a exponentu. Pro vypocet urcite mocniny kladneho celeho cisla se pouziva vyrazu mocnina=exp(n*lnx). Jeho jednoduchou upravou dostaneme:



Upozornuji na nutnost pridat hlavickovy soubor math.h, protoze bez nej nejde pouzit funkci log (ktera, ac se to nezda nepocita dekadicky logaritmus ale prirozeny. Pro dekadicky je tu funkce log10() ).

Ve vypoctu se vyuziva toho ze n-ta odmocnina z x je x^1/n, proto je vysledny vyraz exp((1/n)*log(x)).


Prevody mezi soustavami

A na zaver algoritmus pro prevod mezi soustavami. Je sice strasne znamy, ale preci jen si ho neodpustim.

Nejdriv ale trochu obecne o ciselnych soustavach.

Nejznamejsi polyadickou soustavou je soustava desitkova. Cislo se v ni vyjadruje jako soucet mocnin deseti vynasobenych jednoduchymi souciniteli. Soucinitele mohou nabyt nektere z hodnot 0,1,...,9 a nazyvaji se cislice. Cislo A lze tedy napsat

A=a(n)*10^n + a(n-1)*10^(n-1) + ...... + a(1)*10^1 + a(0)*10^0

Podobne se cisla zapisuji i v jinych soustavach, jen misto desitek si vsude domyslete zaklad pozadovane soustavy (2 pro binarni, 16 pro hexadecimalni atd.)

A ted slibeny algoritmus pro prevod mezi soustavami:



Algoritmus je vhodne doplnit o prevraceni poradi vyslednych cislic v poli;)

Tot pro dnesek vse, za pripadne chyby, at uz pravopisne nebo logicke se predem omlouvam, a budu rad kdyz na ne upozornite v diskuzi pod textem. Urcite nejake najdete (dopisuju to ve tri rano ;).



Líbil se Vám článek?
Budeme potěšeni, pokud vás zaujme také reklamní nabídka

Social Bookmarking

     





Hodnocení/Hlasovalo: 3/1

1  2  3  4  5    
(známkování jako ve škole)