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:
n | 0 | 1 | 2 | 3 | 4 | 5 |
Dokłada Pi | 1 | 1 | 3 | 8 | ||
Dokłada Sigma | 1 | 2 | 5 | |||
Suma | 2 | 3 | 5 | 8 | 13 | 21 |
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
[1]
oznacza część całkowitą z wyniku dzielenia
przez 2.