System Fibonacciego zawiera na pozycjach cyfr zamiast potęg np. 10 liczby Fibonacciego przesunięte o 3 pozycje. Pozwala to uzyskać system zawierający tylko 0 i 1 oraz spełniający schemat
1) [1 0 0] = [0 1 1].
Liczba jest sumą dwu poprzednich, z których pierwsze są 0 i 1. W tym systemie pozycja jedności F_3=1.
Np. 9 = [1 0 0 0 1] = 1*8+0*5+0*3+0*2+1*1.
Na potrzeby faktoryzacji ignoruję fakt, że na każdej pozycji jest tylko 1 albo 0, dopuszczam dowolną naturalną wartość z zerem włącznie. Wtedy liczba w systemie Fibonacciego jest podzielna przez a, gdy jej zapis w systemie Fibonacciego M składa się tylko z a oraz zer. Gdy liczba nie jest podzielna przez a, resztę można umieścić w cyfrze najmniej znaczącej, np.
[3 0 3 0 4] = 3*8+0*5+3*3+0*2+4 = 3(8+3+1)+1 = 37
Dodawanie w systemie Fibonacciego sprowadza się do orowania cyfr, zaś gdy obie są ustawione, do mnożenia przez 2.
Szczególne przypadki cyfr najmniej znaczących (z definicji cyfr systemu):
[. 1 0 1] = [. 0 2 0] = 4
[. 0 1 0] = [. 0 0 2] = 2
Dla pozostałych pozycji mamy schematy, które się dodaje do aktualnych cyfr
2) [1 0 0 1] = [0 2 0 0]
3) [1 0 0 0 1] = [0 0 3 0 0]
Dowody
[1 0 0 1] = [0 1 1 1] = [0 1+1 0 0] = [0 2 0 0];
[1 0 0 0 1] = [0 1 1 0 1] = [0 0 2 1 1] = [0 0 2+1 0 0] = [0 0 3 0 0].
Pierwszy pomysł na faktoryzację z systemu Fibonacciego. Zapisuję liczbę N w tym systemie jako M_{}, następnie za pomocą uogólnień schematów 1) i 2)
[a 0 0] = [0 a a];
4) [a 0 0 a] = [0 2a 0 0]
przekształcam by uzyskać odpowiednią ustaloną wartość zamiast jedynek. np.
z liczby
[1 0 0 0 1 0 1 0 0 1]
można zrobić wartość podzielną przez 2
[0 0 3 0 0 0 0 2 0 0] = [3 0 0 0 0 2 0 0], przeniesienie reszty do cyfry jedności
[3 0 0 0 0 2 0 0] = [2 1 1 0 0 2 0 0] = [2 0 2 1 0 2 0 0] = [2 0 2 0 1 3 0 0] =
[2 0 2 0 0 4 1 0] = [2 0 2 0 0 2 3 2] = [2 0 2 0 0+2 0 1 2] = [2 0 2 0 2 0 0 4] =
[2 0 2 0 2 0 2 0]
lub przez 3:
[3 0 0 0 0 2 0 0] = [3 0 0 0 0 0 2 2] = [3 0 0 0 0 0 3 0]
Ale jak widać w przykładzie, występują nawroty. Zwłaszcza kłopotliwe są fragmenty [. a b 0 a .]
Zatem drugi pomysł. Chcąc uzyskać resztę z przedziału (2^(i-1), 2^i], przekształcamy liczbę do postaci Fibonacciego M_i tak, by zamiast jedynek były liczby 2^i, podwajając cyfry z pomocą 4)
[1 0 0 0 1 0 1 0 0 1] = [0 1 1 0 1 0 1 0 0 1] = [0 0 2+1 0 0 0 1 0 0 1] =
[2 1 1 0 1 0 0 1] = [2 0 2+1 0 0 0 0 1] = [2 0 2 1 1 0 0 1] = [2 0 2 0 2 1 0 1] =
[2 0 2 0 2 0 1 2] = [2 0 2 0 2 0 2 0] = (M_1)
[2 0 0 2 4 0 2 0] = [0 4 0 0 4 0 2 0] = [4 0 0 4 0 0 4] = (M_2)
[0 8 0 0 0 0 4] (M_3)
Jest to liniowe i nie ma nawrotów.
Jeśli teraz chcemy znaleźć resztę przez d<2^i, jest ona równa iloczynowi postaci
M_i *(2^i - d) + r ,
gdzie r jest resztą (cyfra jedności M_i lub M_i-2^i, gdy M_i ma ustawioną tę cyfrę ).
Ten drugi sposób jest dowodem na cechę podzielności przez d w systemie.
I znowu, działania na dużej liczbie zostały zastąpione działaniami na znacznie mniejszych, gdyż M_{i+1} ma co najmniej dwie cyfry mniej niż M_i, 2^i-d<2^{i-1), zaś reszta też jest mniejsza niż 2^{i-1}.
Pozostaje sposób konwersji N na postać Fibonacciego M_0. Chyba najbardziej opłacalny jest klasyczny szukania największej liczby Fibonacciego F_k nie większej niż N i odejmowanie. Jeśli chcemy zmniejszać N wcześniej, możemy odejmować kolejne liczby Fibonacciego, a kiedy F_k >N-\sum{F_{i<k}}, odejmujemy jeszcze 2, razem zostało odjęte F_{k+2}.
Wynika to z przekształceń
[1 1 . . . 1 1] = [1 0 1 . . . 0 1 0 0] lub [1 0 1 . . . 1 0 0 1]
w zależności od liczności jedynek. Uzyskane ciągi mają dokładnie jedną pozycję więcej. Brakuje dokładnie 2, by cały ten ciąg używając 1) stał się kolejną liczbą Fibonacciego, zyskując dodatkową pozycję. Z programowania dynamicznego lub rekursji ustawiamy kolejne jedynki M_0.
Brak komentarzy:
Prześlij komentarz