Rozkład na sumę liczb Fibonacci’ego

Każdą liczbę naturalną większą od 2 można rozłożyć na sumę różnych dodatnich liczb Fibonacci’ego, na przykład 20 = 13+5+2. Rozkład taki nie zawsze jest jednoznaczny, mamy bowiem choćby 10 = 8+2 = 5+3+2. Dla większych liczb ilość możliwości ich rozkładu może być naprawdę pokaźna (choć oczywiście zawsze skończona). Spróbujmy rozwiązać następujący problem: na ile sposobów można rozłożyć w ten sposób daną liczbę naturalną?

Na pewno zależy to od zakresu tej liczby, więc założymy, że nie przekracza ona miliarda. W takim razie wystarczy się ograniczyć do liczb od F₂ = 1 do F₄₄ = 701408733. Liczby F₀ = 0 oraz F₁ = 1 odrzucamy, zaś F₄₅ jest większa od miliarda.

Mamy więc 43 liczby-klocki do dyspozycji: gdybyśmy chcieli na ślepo badać ich wszystkie możliwe układy (złożone z różnych liczb), byłoby ich 2⁴³ = 8796093022208. To dużo za dużo, a zatem musimy wymyślić sposób, jak maksymalnie ograniczyć ilość rozważanych zestawów liczb. Z pomocą przyjdzie nam algorytm z powrotami, odpowiednio dopasowany do naszych potrzeb.

Potrzebne nam będą dwie tablice liczb całkowitych: F oraz sF. Pierwsza z nich spełnia warunek F[i] = F_i, a druga sF[i] = F₂ + F₃ + … + F_i. (Zakres indeksu i był określony wcześniej.) Ponadto będziemy używać zmiennej list zawierającej listę indeksów liczb Fibonacci’ego – kandydatów do rozkładu (w kolejności malejącej) – na początku pustą. Prócz tego wykorzystamy zmienną cnt – licznik uzyskanych rozkładów (na początku równy zero).

Podstawowym elementem algorytmu będzie rekurencyjna funkcja test(N,maxF), gdzie N jest rozkładaną liczbą (lub tym, co z niej zostało po dotychczasowym częściowym rozkładzie), zaś maxF to indeks największej liczby Fibonacci’ego, jaką możemy od tej pory użyć w rozkładzie. Zadaniem tej funkcji jest dokonanie próby rozkładu N kolejno przy użyciu liczb Fibonacci’ego o indeksach od 2 do maxF jako największych liczb w rozkładzie.

W celu optymalizacji algorytmu dodajemy dwa warunki. Po pierwsze, jeśli ta „największa” liczba o indeksie i jest tak mała, że sF[i] jest mniejsze od N, to nie ma co liczyć na rozkład, bo sF[i] to suma wszystkich liczb Fibonacci’ego o indeksach nie większych od i. W tym przypadku trzeba przejść do kolejnej, większej wartości indeksu (a więc i większej liczby Fibonacci’ego). Po drugie, jeśli F[i] jest większe od N, to nie zmieści się w jej rozkładzie i trzeba zakończyć działanie tej instancji funkcji test (bo pętla zmierza w kierunku coraz większych wartości F[i]).

Jeśli wyczerpaliśmy całą liczbę N, to zwiększamy wartość licznika rozkładów o jeden. W przeciwnym razie wywołujemy funkcję test(N-F[i],i-1), bo liczbę F[i] wykorzystaliśmy już w tym rozkładzie, a każda kolejna powinna od niej być mniejsza.

Funkcja test powinna wyglądać tak:

test(N,maxF)
   for i=2 to maxF do
      if F[i]>N 
         return 
      if N<=sF[i]
         push(list,i)
         if N==F[i]
            cnt++
         else
            test(N-F[i],i-1)
         pop(list,i)

Funkcje push i pop odpowiednio dodają i usuwają element na końcu listy.

Po inicjalizacji opisanych wyżej tablic i zmiennych powinniśmy wykonać instrukcje:

maxF = 44;
while F[maxF]>=N do
   maxF--
test(N,maxF)
print cnt

Pętla while znajduje największy indeks liczby Fibonacci’ego mniejszej od N – właśnie od takiej liczby powinniśmy zacząć nasz algorytm.

Powrót do Algorytmy wykładnicze

Algorytmika