Wskazówka:
Algorytm binarny(x, k) opiera się na następującym pomyśle: jeśli liczba x jest nie mniejsza od 1/2, to jej pierwszą cyfrą dwójkową po przecinku musi być 1. Jeśli teraz pomnożymy liczbę x przez 2, to odpowiada to przesunięciu całego rozwinięcia o jedno miejsce w lewo. Druga po przecinku cyfra liczby x to pierwsza cyfra po przecinku 2x, czyli możemy ją wyznaczyć podobnie jak poprzednio: sprawdzając, czy jest większa lub równa 1/2. Oczywiście musimy najpierw pominąć stojącą przed przecinkiem część całkowitą — odejmujemy zatem 1, jeśli liczba przekroczyła 1 w czasie mnożenia.

Bardzo podobną technikę stosujemy w algorytmie trojkowy(x, k). Tutaj pierwsza cyfra po przecinku powinna być równa 2, jeśli liczba x jest nie mniejsza od 2/3, 1 — jeśli x należy do przedziału [1/3, 2/3), a 0 — jeśli x jest mniejsze od 1/3. Następnie dokonujemy przesunięcia w lewo, mnożąc liczbę przez 3, po czym usuwamy z niej część całkowitą. Istotną różnicą jest to, że teraz część całkowita liczby może wynosić 0, 1 lub 2, zatem musimy odjąć 1 lub 2, zależnie od potrzeby:

dla i=1, 2, ..., k wykonuj
jeżeli y ≥ 2/3
wypisz „2”
jeżeli y ≥ 1/3 oraz y < 2/3
wypisz „1”
jeżeli y < 1/3
wypisz „0”
y ← y * 3
jeżeli y≥2
y ← y – 2
jeżeli y≥1
y ← y – 1

Zamiast ostatnich czterech wierszy — odpowiadających pomijaniu części całkowitej — można było w oryginalnym algorytmie napisać tak:

jeżeli y≥2
y ← y – 1
jeżeli y≥1
y ← y – 1

Jeśli liczba będzie większa niż 2, algorytm najpierw odejmie 1, a następnie zauważy, że liczba wciąż jest większa niż 1, i odejmie znów jedynkę. Warto jeszcze wspomnieć, że gdyby luki nie narzucały konstrukcji algorytmu, można byłoby użyć krótszego zapisu:

dopóki y≥1 wykonuj
y ← y – 1

Miałoby to ten sam efekt: odrzucenie z liczby y jej części całkowitej.
Powrót do pytań