Bezużyteczne programowanie - rzut oka na liczby Fibonacciego

W codziennej pracy programisty nieczęsto zdarza się okazja do wykonania czegoś naprawdę oryginalnego. Zmieniają się technologie, pojawiają się nowe narzędzia, lecz 99% zadań to wciąż „przewalanie danych z kąta w kąt” – wyciąganie danych z tej czy innej bazy, generowanie raportów, wyliczanie prowizji, integracja kontrahentów. Słowem – tworzenie aplikacji zaspokajających praktyczne wymagania klientów. W owej szarej rzeczywistości bardzo łatwo zapomnieć, że programowanie może być dobrą zabawą, a zaklepanie kilku linijek kompletnie niepraktycznego kodu może dać nieporównywalnie większą satysfakcję niż stworzenie kolejnego formularza wprowadzania faktury, choćby i w najnowszej technologii.

Dobrą odskocznią od codzienności mogą być zadanka z konkursów programistycznych, takich jak Potyczki Algorytmiczne, ACM ICPC, Olimpiada Informatyczna, Google CodeJam, Facebook HackerCup i wielu innych. Chciałbym w tym artykule omówić dwie takie łamigłówki. Wybrałem zadania związane z bardzo ciekawym ciągiem liczb Fibonacciego.

Liczby Fibonacciego to ciąg liczb naturalnych, którego pierwsze wyrazy wynoszą:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, …

Kolejne wyrazy ciągu powstają przez dodanie dwóch poprzednich. Formalnie ciąg możemy opisać wzorem:

Od momentu opublikowania wzoru w 1202 przez Leonarda Fibonacciego z Pizy, matematycy znaleźli wiele ciekawych zależności z nim związanych, jak choćby równanie Cassiniego:

Równanie to stoi u podstaw pewnego paradoksu geometrycznego. Kwadrat o boku dzielimy na kawałki jak na rysunku. Po ich poprzestawianiu uzyskujemy prostokąt o bokach równych oraz , którego pole jest różne od pola wyjściowego kwadratu! W zależności od parzystości , zyskujemy bądź tracimy jedną „kratkę”:

Liczby Fibonacciego często manifestują się w naturze. Dość powiedzieć, że sam Leonardo z Pizy odkrył je rozważając zagadnienie rozmnażania się królików. Można się także na nie natknąć zliczając ziarenka słonecznika. Z kolei dla coraz większych wartości stosunek do zbliża się do liczby , którą znano już w starożytności. Nazywana jest „złotą proporcją” lub „złotym podziałem” i jest odbierana przez ludzkie zmysły jako najbardziej przyjemny stosunek boków prostokąta. Ową proporcja weszła do kanonów piękna. Stosowano ją i w architekturze, i przy projektowaniu kart płatniczych oraz dowodów osobistych.

Więcej związków liczb Fibonacciego z naturą można zobaczyć w poniższej animacji:

„Złota proporcja” przypadkiem jest bardzo zbliżona do przelicznika kilometrów na mile. Jeśli akurat nie mamy pod ręką kalkulatora a potrzebujemy przeliczyć miarę odległości, możemy wspomóc się ciągiem Fibonacciego. Dla przykładu, odległość z Torunia do Łodzi wynosi 178 kilometrów. Zapisujemy tę wartość jako sumę wyrazów ciągu Fibonacciego, tj. . Każdy wyraz zastępujemy poprzednim w ciągu, co daje nam mil. W istocie odległość wynosi 109,36 mil. Różnica jest niewielka i do zgrubnych oszacowań możemy z powodzeniem używać powyższej metody.

Ale dość o ciekawostkach, przechodzimy do zadań. Na rozgrzewkę proponuję zadanie "Kongres" autorstwa Jakuba Radoszewskiego, z Potyczek Algorytmicznych 2006:

Na pierwszym kongresie Bajtockiego Towarzystwa Informatycznego uczestnicy zasiedli przy długim prostokątnym stole, wszyscy po tej samej stronie. Jeden z uczestników postawił pytanie, na ile sposobów siedzący mogą uścisnąć sobie dłonie bez wstawania od stołu – w trakcie jednego takiego przywitania, każdy uczestnik może uścisnąć dłoń co najwyżej jednego innego uczestnika, który musi być jego sąsiadem przy stole.

Ponieważ uczestnicy kongresu są informatykami teoretykami, poprosili Ciebie o napisanie programu, który policzy dla nich tę liczbę sposobów. Żeby nie operować dużymi liczbami wystarczy, jeżeli podasz im ostatnią cyfrę wyniku.

Napisz program który:

• wczyta ze standardowego wejścia liczbę uczestników kongresu,
• wyznaczy ostatnią cyfrę liczby różnych sposobów uścisków dłoni przez uczestników kongresu,
• wypisze wynik na standardowe wyjście.

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita , oznaczająca liczbę uczestników kongresu.

W pierwszym i jedynym wierszu wyjścia powinna znajdować się jedna cyfra – ostatnia cyfra szukanej liczby możliwych sposobów uścisków dłoni.

Dla danych wejściowych:

4

poprawną odpowiedzią jest:

5

Wszystkie prawidłowe ustawienia dla powyższego przykładu:

Oznaczmy przez funckję wyznaczającą wynik dla danego . Rozważmy osobę siedzącą z brzegu stołu. Może albo nie podać ręki nikomu, albo podać ją sąsiadującej osobie. W pierwszym przypadku „eliminujemy” osobę z dalszych rozważań i musimy wyznaczyć , czyli liczbę możliwych uścisków dla osób, i dodać tę wartość do wyniku.  W drugim przypadku „eliminujemy” dwie osoby i do wyniku dodajemy . Gdy przy stole siedzi tylko jedna osoba, to jedyną możliwością jest, że nikomu nie poda ręki. Jeśli siedzą dwie osoby, to albo nikt nikomu nie poda ręki, albo podadzą sobie nawzajem, co daje 2 konfiguracje. Daje nam to niemal dokładną definicję ciągu, lecz przesuniętą o jedną pozycję:

Zauważmy, że jako wynik działania programu mamy wyznaczyć tylko ostatnią cyfrę . Zwykle autorzy zadań wprowadzają takie ułatwienie, aby rozwiązujący skupił się na algorytmie, a nie zawracał sobie głowy zakresami zmiennych, które są ograniczone. Innymi słowy, z pewnością nie zmieści się w zmiennej typu long int, czym jednak nie musimy się przejmować.

Najbardziej naiwne rozwiązanie, jakie można sobie wyobrazić, to bezpośrednie przeniesienie powyższej definicji do funkcji rekurencyjnej:

int FibonacciReccurrent(int n) {
    if (n == 1)
        return 1;
    if (n == 2)
        return 2;
    else
        return (FibonacciReccurrent(n - 1) + FibonacciReccurrent(n - 2)) % 10;
}

Taki program da poprawne wyniki, jednak nawet na dzisiejszych superszybkich komputerach możemy nie doczekać się wyników dla . No, chyba, że ktoś należy do osób wyjątkowo cierpliwych. Dzieje się tak dlatego, że program liczy wielokrotnie to samo, a drzewo generowanych przez niego wywołań rekurencyjnych jest olbrzymie. Ów stan rzeczy możemy poprawić stosując technikę spamiętywania (memorization), która prowadzi nas do następującego kodu:

Dictionary<int, int> Cache = new Dictionary<int, int>();

int FibonacciReccurrent(int n) {
    int res = 1;
    if (n == 1)
        res = 1;
    else if (n == 2)
        res = 2;
    else if (Cache.ContainsKey(n))
        res = Cache[n];
    else {
        res = (FibonacciReccurrent(n - 1) + FibonacciReccurrent(n - 2)) % 10;
        Cache[n] = res;
    }

    return res;
}

Z punktu widzenia wydajności, to rozwiązanie jest jak najbardziej optymalne. Program, gdy raz już coś wyliczy, zapamiętuje to w słowniku Cache, odcinając w ten sposób całe ogromne poddrzewa wywołań rekurencyjnych. Jednak i ten kod polegnie dla dużych wartości , tym razem ze względu na limit systemu operacyjnego na głębokość zagnieżdżenia wywołań funkcji. Ostatecznie najbardziej eleganckie i najprostsze i tak okazuje się rozwiązanie iteracyjne:

int FibonacciIterative(int n) {
    int a = 1, b = 2, tmp;

    for (int i = 2; i < n; ++i) {
        tmp = a;
        a = b;
        b = (a + tmp) % 10;
    }
    return b;
}

Tym razem nie mamy żadnego wywołania rekurencyjnego funkcji FibonacciIterative, a kolejne wyrazy ciągu wyznaczamy ad hoc, w pętli.

Do przebrniecia, prawda? Przejdźmy zatem do kolejnego zadania. Tym razem proponuję zadanie „Licytacja”, pochodzące z – nieistniejącego już – serwisu internetowego OPSS.

Dwóch matematyków Pi i Sigma spotkało się wieczorem na partyjce pokera. Ponieważ nie mieli pieniędzy, postanowili grać „na zapałki”. Pi miał przy sobie tylko niebieskie zapałki, a Sigma tylko zielone. Przed przystąpieniem do licytacji Pi wyłożył  swoich niebieskich zapałek, zaś Sigma dołożył  swoich zielonych. Pi zaczyna licytację. Licytują na zmianę. W każdym kroku licytacji zawodnik dorzuca tyle swoich zapałek, ile aktualnie jest zapałek przeciwnika w puli. Licytacja trwała dość długo i gracze nie mogli się doliczyć aktualnej liczby zapałek w puli. Wiedzieli jednak, ile razy każdy z nich dorzucał zapałki podczas licytacji.

Pomóż matematykom określić, ile zapałek jest w puli po  krokach licytacji. Ponieważ to matematycy, zadowoli ich znajomość reszty z dzielenia tej liczby (liczby zapałek po  krokach) przez ustaloną przez nich „magiczną” liczbę .

Pierwsza linia wejścia zawiera liczbę zestawów danych . W kolejnych wierszach wejścia znajdują się zestawy danych. Każdy z   zestawów danych składa się z jednego wiersza zawierającego liczby całkowite , oddzielone pojedynczą spacją . Liczby  określają kolejno liczbę niebieskich zapałek Pi oraz zielonych Sigmy znajdujących się w puli przed rozpoczęciem licytacji. Liczba  określa liczbę kroków licytacji. Liczba  to ustalona przez graczy „magiczna” liczba.

Dla każdego zestawu danych, wynikiem jest linia zawierająca jedną liczbę –resztę z dzielenia przez  liczby zapałek po  krokach licytacji, przy założeniu, że przed przystąpieniem do licytacji w puli znajduje się  niebieskich zapałek Pi oraz  zielonych zapałek Sigmy.

Przykład:

Dla danych wejściowych:

3

1 1 4 1000

5 6 7 1000

4 101 23 999

Poprawną odpowiedzią jest:

13

309

767

Rozważmy pierwszy zestaw z przykładowych danych. Zobaczmy, jak przebiegać będzie licytacja i ile zapałek znajduje się w puli po ruchach:

Ewidentnie, każda kolejna suma, to następny wyraz ciągu Fibonacciego.

Zapomnijmy na razie, że  i  mogą być liczbami innymi niż 1 i skupmy się na podstawowym przypadku. Wszak nie mogę podać całego rozwiązania na tacy i psuć zabawy tym, którzy skuszą się na samodzielne programowanie :)

Jeśli wynikiem ma być po prostu -ta liczba Fibonacciego modulo , to dlaczego nie policzyć jej w sposób analogiczny jak w poprzednim zadaniu? Otóż, poprzednio mieliśmy do wykonania maksymalnie 10000000 iteracji. Liczba ta może się wydawać duża w kontekście marzeń o stanie własnych finansów, jednak jeśli myślimy o liczbie operacji wykonywanych przez procesor, to jest to drobnostka. Laptop, na którym piszę te słowa, poradzi sobie z nimi w pół sekundy. Niestety limit z aktualnie omawianego zadania wynosi , co jest liczbą ponad 200 razy większą. Obliczenie wyniku dla jednego zestawu zajęłoby zatem około 100 sekund, a zestawów potencjalnie możemy mieć aż 1000, a nie jeden. Całościowe rozwiązywanie maksymalnego zadania zajęłoby ponad dobę. Zdecydowanie, musimy nauczyć się wyznaczać -tą liczbę Fibonacciego szybciej. Tylko jak?

Próba pierwsza: nie wspominałem o tym wcześniej – teoria funkcji tworzących, na które teraz ani czas ani miejsce, pozwala wyprowadzić następujący jawny wzór (przy okazji, czy nie przypomina on „złotego podziału”?):

Niestety, jest to ślepa uliczka. Ze względu na konieczność wykonania dzielenia modulo, pierwiastkowania oraz potęgowania liczb niewymiernych, polegniemy z jednej strony na zakresie zmiennych typu double, a z drugiej na ich dokładności.

Próba numer dwa: rozważmy następujący iloczyn macierzy:

Zauważmy, że ogólnie:

Przemnożenie wektora złożonego z dwóch sąsiednich liczb Fibonacciego przez odpowiednio skonstruowaną macierz daje nam w wyniku wektor zawierający kolejną liczbę! Zatem, mnożąc wektor jedynek przez macierz podniesioną do potęgi, otrzymamy:

Czyli dokładnie to, co nam potrzebne.

No dobra, ale czym się różni -krotne mnożenie macierzy od iteracyjnego wyznaczania -tego wyrazu ciągu Fibonacciego? Dlaczego miałoby być szybsze? Otóż jesteśmy dopiero w połowie drogi. Aby rozwiązanie z macierzami stało się wydajniejsze, musimy zastosować algorytm szybkiego potęgowania (repeated squaring algorithm). Najlepiej wyjaśnić go na przykładzie. Zauważmy, że:

Zamiast 10 mnożeń wystarczą nam 4 (podniesienie do kwadratu, kolejne podniesienie do kwadratu, przemnożenie i podniesienie do kwadratu całości). Wystarczy spostrzec, że do wyznaczenia -tej potęgi danego wyrażenia musimy wyznaczyć potęgę[1] (wykonując jedno dodatkowe mnożenie, gdy jest nieparzyste) i wynik podnieść do kwadratu.

Algorytm sprawia, że zamiast mnożeń musimy ich wykonać . Dla tych, którym funkcja logarytmu nic nie mówi przypomnę ważne oszacowanie, tzw. „drugie twierdzenie matematyki stosowanej”, głoszące:

Logarytm z „dużo” równa się „mało” :)

Aby podnieść naszą macierz do potęgi będziemy musieli wykonać nie więcej niż 50 mnożeń, co da wydajnościowego kopa lepszego niż wymiana procesora na 100-rdzeniowy. Z taką wiedzą dokończenie implementacji zadania powinno stanowić formalność.

Podsumowanie

Omówiliśmy liczby Fibonacciego, poznając kilka ciekawostek na ich temat. Rozwiązując dwa przykładowe zadania, próbowaliśmy wyrazy ciągu wyznaczać metodą rekurencyjną, jak i iteracyjną. Poznaliśmy technikę spamiętywania. Przypomnieliśmy sobie algorytm szybkiego potęgowania. Podobało się? Choć od czasów studenckich, kiedy startowałem w wielu konkursach algorytmicznych, minęło już trochę czasu, to wciąż mnie to bawi. Jeśli Was też, to „lajkujcie”, komentujcie, mailujcie – będzie to dla mnie najlepszym sygnałem, że jest sens pisać podobne artykuły.

Garść linków

• https://oeis.org/A000045 - ciąg Fibonacciego w Encyklopedii ciągów liczbowych
• http://main.edu.pl/pl - archiwum zadań z Potyczek Algorytmicznych oraz Olimpiady Informatycznej
• http://uva.onlinejudge.org/ - archiwum zadań wszelakich, głównie z konkursów ACM
• http://pl.wikipedia.org/wiki/Z%C5%82oty_podzia%C5%82 – złoty podział
• http://uva.onlinejudge.org/external/117/11780.html - zadanie związane z użyciem ciągu Fibonacciego do przeliczania kilometrów na mile