Algoritmy I

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.

#include <stdio.h> int main(){ float x,x1,x2,odchylka; printf("Zadejte cislo pro odmocneni: "); scanf("%f",&x); printf("Zadejte maximalni odchylku:"); scanf("%f",&odchylka); x2=1; do { x1 = x2; x2 = (x1 + x/x1) / 2; } while (abs(x1 - x2)> odchylka); printf("Odmocnina je %f",x2); return 0; }

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:

#include <stdio.h> #include <math.h> int main(){ float x,n; printf("Zadejte cislo pro odmocneni: "); scanf("%f",&x); printf("Zadejte exponent:"); scanf("%f",&n); printf("Mocnina je %f", exp((1/n)*log(x));); return 0; }

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:

int i = 1 ; // Rad cislice int Cislo=nejakecislo; // Prevadene cislo int Zaklad=zakladsoustavy; // na jakou soustavu prevadime int Cislice[n]; // Vektor prevedenych cislic, n je pocet cifer na ktery se prevadi while (Cislo) { Cislice [i] = Cislo % Zaklad ; Cislo = Cislo / Zaklad ; i++; } // V poli Cislice[1] az Cislice[n] jsou ulozeny hodnoty cislic v obracenem poradi

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