Strona Piotr Kotarski

Strona główna

Algorytmy

Algorytmy klasyczne

Największy wspólny podzielnik
"Sito Erastotenesa" - znajdowanie liczb pierwszych
Rozkład liczb na czynniki pierwsze
Obliczanie pierwiastków - algorytm Newtona-Raphsona

Największy wspólny podzielnik - algorytm Euklidesa
program demonstracyjny euklides.zip (217kB)

Jest to jeden z najstarszych, znanych od starożytności algorytmów. Został on opisany w wydanym przez Euklidesa 13-tomowym podręczniku do matematyki p.t. "Elementy" ok 300pne. Algorytm dotyczy znalezienia największego wspólnego dzielnika dwóch liczb całkowitych. W oryginale wyglądało to tak:
a) masz dwie liczby a i b, przy czym a>b,
b) dopóki a≥b wykonuj działanie a:=a-b,
c) jeżeli a<b i a≠0 to zamień miejscami a i b, i wróć do punktu b),
d) jeżeli a=0 to wynikiem jest aktualna wartość b.

W praktycznej realizacji odejmowanie zastępujemy resztą z dzielenia (operacja "modulo"), nie trzeba również wstępnie porządkować zmiennych, gdyż w pierwszym przebiegu pętli i tak to nastąpi.
NWD
```
Function Nwd(a, b : LongInt) : LongInt;
var     r:  LongInt;
begin   while b<>0 do
        begin   r:=a mod b;
                a:=b;
                b:=r;
        end;
        Nwd:=a;
end;
```
do góry
"Sito Erastotenesa" - znajdowanie liczb pierwszych
program demonstracyjny pierwsze.zip (262kB)

Jest to algorytm również znany od starożytności. Dotyczy znalezienia liczb pierwszych w pewnym, ograniczonym zakresie liczb. Zasada jest następująca:
- Tworzymy zbiór liczb naturalnych większych od jedności, tj. {2, 3, 4 ...} (np. jako tablicę).
- Z tego zbioru, wybieramy najmniejszą - czyli 2 (jest ona liczbą pierwszą) - i wykreślamy wszystkie jej wielokrotności większe od niej samej, to jest 4, 6, 8, 10, ...
- Z pozostałych liczb wybieramy najmniejszą niewykreśloną liczbę - 3 - i usuwamy wszystkie jej wielokrotności większe od niej samej: 6, 9, 12, 15, ..., przy czym nie przejmujemy się tym, że niektóre liczby (na przykład 6 czy 12) będą skreślane więcej niż raz.
- Z pozostałych liczb wybieramy najmniejszą niewykreśloną i wykreślamy wszystkie jej wielokrotności większe od niej samej...
- Procedurę tę powtarzamy teoretycznie do nieskończoności, w praktyce można skończyć, gdy kolejna wybrana liczba pierwsza jest równa lub większa od pierwiastka z maksymalnej liczby zbioru.
- Dla danej liczby n wszystkie niewykreślone liczby mniejsze od n są liczbami pierwszymi.
sito Erastotenesa
```
const max=1000;

var tab:array[2..n] of Boolean;

Procedure Kasowanie;
var i:Integer;
begin   for i:=2 to n do
        tab[i]:=True;
end;

Procedure Sito;
var     n,k:Integer;
begin   n:=2;
        repeat
            if tab[n] then
            begin
                k:=2*n;
                while k<=max do
                begin
                    tab[k]:=false;
                    k:=k+n;
                end;
            end;
            n:=n+1;
       until n*n>max;
end;
```
do góry
Rozkład liczb na czynniki pierwsze
program demonstracyjny pierwsze.zip (262kB)

Rozkład liczby x na czynniki pierwsze polega na sprawdzaniu podzielności tej liczby przez kolejne liczby piewsze k. Ponieważ program "nie zna" liczb pierwszych sprawdzamy podzielność dla ciągu liczb k = 2, 3, 5, 7, 9, ... (dalej kolejne nieparzyste).
Jeżeli liczba x jest podzielna przez k to:
a) k zapisujemy na liście czynników,
b) x modyfikujemy: x:=x div k,
c) powtarzamy sprawdzenie podzielności x przez k.
Proces można zakończyć, gdy k*k>x, gdyż takie wartości na pewno nie będą czynnikami liczby x.
Jeżeli w wyniku poprzednich obliczeń wartość x>1, to jest ona ostatnim czynnikiem.

Procedura Rozklad otrzymuje dwa parametry:
x - dana liczba,
i - ilość czynników.
Czynniki zapisywane są do tablicy.

Oczywiście, można wyniki wyprowadzać inaczej, np. na ekran lub do pliku. Nie zmienia to istoty algorytmu.
Rozkład liczby na czynniki
```
var     czynniki:array[1..100]of LongInt;

procedure Rozklad(x:LongInt; var i:Integer);
var     k:LongInt;
begin   i:=1;
        k:=2;
        repeat
            while (x mod k)=0 do
            begin
                 czynniki[i]:=k;
                 i:=i+1;
                 x:=x div k;
            end;
            if k=2 then k:=3 else k:=k+2;
        until k*k > x;
        if x>1 then
        begin
            czynniki[i]:=x;
            i:=i+1;
        end;
end;
```
do góry
Obliczanie pierwiastków - algorytm Newtona-Raphsona
Jest to przykład eleganckiego i bardzo efektywnego algorytmu iteracyjnego. Służy do obliczenia pierwiastka kwadratowego (lub innego) z liczby rzeczywistej. Polega na znajdowaniu kolenych przybliżeń pierwiaska na podstawie poprzednich przybliżeń.

Załóżmy, że

Wzór ten jest słuszny dla kwadratu o boku y i polu x. Problem więc polega na znalezieniu boku kwadratu o polu x.

Załóżmy, że mamy prostokąt o jednym boku równym (dowolna, dodatnia liczba). Aby jego pole było równe x, to drugi bok musi być równy .

Oczywiste jest, że jest pierwiastkiem, jeżeli te boki są równe. W ogólnym przypadku tak nie jest, więc musimy obliczyć kolejne przybliżenie. Wyznaczamy je jako średnią arytmetyczną boków prostokąta. Tak otrzymujemy znany wzór iteracyjny:

Pierwsze przybliżenie może być dowolne, np równe x.
Przykładowo dla y₀=x=100:
```
0  100,0000000000000
1   50,5000000000000
2   26,2400990099010
3   15,0255301199868
4   10,8404346730269
5   10,0325785109606
6   10,0000528956427
7   10,0000000001399
8   10,0000000000000
```
Na przykładzie widać dużą zbieżność iteracji, co jest główną zaletą tego algorytmu. Po znalezieniu pierwszych poprawnych cyfr, ich ilość podwaja się w każej iteracji.

W praktycznych realizacjach algorytmu N-R w systemach cyfrowych (komputery, kalkulatory) pierwsze przybliżenie wyznacza się korzystająć z wewnętrznej, dwójkowej, zmiennoprzecinkowej reprezentacji liczby. Najprościej jest podzielić cechę liczby przez 2, np:

x = 1,5625 * 2⁶ = 100

y₀ = 1,5625 * 2³ = 12,5

Jak widać niżej, rozwiązanie jest znacznie szybsze!
```
0   12,5000000000000
1   10,2500000000000
2   10,0030487804878
3   10,0000004646115
4   10,0000000000000
```
Algorytm N-R można uogólnić na pierwiastki wyższych stopni, stosując następujące wzory iteracyjne:

pierwiastek sześcienny:

pierwiastek k-tego stopnia:
do góry