Algoritmusok
Három különböző algoritmust beszéltünk meg. Az elsőt a szakkörösök találták ki, a másik kettőt "megtanultuk".
1. Mohó algoritmus
Fibonacci eljárását azért hívjuk mohónak, mert minden lépésben a lehető legnagyobb reciprokértéket veszi hozzá a felbontáshoz, majd a maradékkal dolgozik tovább.
A mohó algoritmus legfeljebb
$p$ darab törtből álló felbontást ad, de a nevezők nagyon nagyra nőhetnek. Például az
$\frac{5}{121}$ tört egyiptomi alakja mohó algoritmussal számolva:
$\frac{5}{121}=
\frac{1}{25}+
\frac{1}{757}+
\frac{1}{763309}+
\frac{1}{873960180912}+
\frac{1}{1527612795642093418846225}$
mohó(p,q):
p’ := p; q’ := q
Ciklus amíg p’ > 0
a következő tört: 1/n, ahol 1/n <= p’/q’ < 1/(n-1)
p’ := p’n – q’; q’ := q’n
p’/q’ egyszerűsítése
Ciklus vége
2. Párosítós algoritmus
Kiindulunk a
$\frac pq = \frac 1q + \frac 1q + \ldots + \frac 1q$
felbontásból, és fokozatosan megszüntetjük az egyenlő nevezőket. Az egyezések megszüntetése a következő módon történik:
$
\frac 1q + \frac 1q =
\frac 2q = \left\{
\begin{array}{ll}
\displaystyle{\frac {1}{\frac q2}} & , \mathrm{ha }q\mathrm{ ps}
\\
\displaystyle{\frac {1}{\frac {q+1}2}+\frac {1}{\frac {q(q+1)}2}} & , \mathrm{ha }q \mathrm{ ptln}
\end{array}
$
A párosítási lépés nem növeli a felbontásban szereplő törtek számát és bizonyítható, hogy véges lépésben minden egyezést kiküszöböl. Így legfeljebb
$p$ tört összegére bontottuk az eredetit. Az egyezések keresése hatékonyan elvégezhető, ha a lista elemeit nagyság szerint rendezve tároljuk.
párosító(p,q):
lista := [q, q,…, q] (p darab)
Ciklus amíg van két egyenlő nevező (értékük q)
lista := lista – [q,q]
Ha q páros
akkor lista := lista + [q/2]
különben lista := lista + [(q+1)/2, q(q+1)/2]
Elágazás vége
Ciklus vége
A felbontás nevezői a lista elemei
3. Golomb algoritmusa
A 3. sorban meghatározott $s$ érték a
$p’$ multiplikatív inverze (mod $q’$). Látható, hogy a legnagyobb előforduló nevező legfeljebb $q(q-1)$ lehet. $s$ képzési szabálya miatt $p’$ és $q’$ relatív prím marad.
golomb(p,q):
p’ := p; q’ := q
Ciklus amíg p’ > 1
a következő tört: 1/(sq’), ahol p’s=q’r+1 (0<s<q’)
q’ := s; p’ := r
Ciklus vége
az utolsó tört: p’/q’
Kódok
