Spis treści Strona wyżej: Coś dla matematyków Następna strona: Liczby pierwsze

Męczony do upadłego ciąg liczbowy oraz męczeni tym ciągiem uczniowie w szkołach rozmaitych niech spojrzą nań jeszcze raz za sprawą tego skromnego artykułu. Kąt, pod którym będziemy spoglądać pozwoli nam spojrzeć na to zagadnienie w świetle informatyki. Znany i lubiany ciąg liczb naturalnych zwany ciągiem Fibonacciego (tak, podwójne c) zadany jest tzw. wzorem rekurencyjnym: . Aby poznać n-ty wyraz ciągu, należy znać dwa poprzednie: (n-1)-szy i (n-2)-gi oraz dodać je do siebie. Musimy od czegoś zacząć, więc umawiamy się, że dwa początkowe wyrazy są znane i równe , . Teraz mamy ,  , , itd. Wypiszmy kilka początkowych wyrazów ciągu : 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, … Jak zatem wygląda funkcja rekurencyjna obliczająca n-ty wyraz tego ciągu w języku C# (w C++ i Java będzie tak samo)?

int F(int n)
{
    if (n == 0) return 1;
    else if (n == 1) return 1;
    else return F(n - 1) + F(n - 2);
}

Albo krócej przy użyciu operatora warunkowego:

int F(int n)
{
    return n < 2 ? 1 : F(n - 1) + F(n - 2);
}

Skoro mamy już odpowiednią metodę, to co dalej? Jak to co? Męczymy komputer. Niech jednostką czasu będzie tzw. tick, czyli jedna dziesiąta mikrosekundy.

Trzy proste obserwacje:

1. Wartości rosną z wyjątkiem F(46), więc to musi być błąd. Przekroczyliśmy zakres liczb typu int, gdzie maksymalną wartością jest 2147483647. Powinno być F(46) = 2971215073, a jest -1323752223 = 2971215073 – 4294967296, gdzie 4294967296 to 2 do potęgi 32. Zgadza się. Rzeczywiście przekroczyliśmy zakres liczby 32-bitowej ze znakiem. Objawia się to właśnie tak, że „wchodzimy na minus, ale od lewej”. OK, ale skoro to jest błąd wykonania programu to dlaczego kompilator go nie zgłasza? Dlaczego nie mamy wyjątku? Ano dlatego, że takie właśnie przepełnienia arytmetyczne nie są domyślnie sprawdzane. Oczywiście można to sprawdzanie włączyć poprzez umieszczenie naszych operacji wewnątrz specjalnego bloku checked { }.

No proszę. Tak, tylko że dodanie sprawdzania wydłuża czas wykonania.

Przy zastosowaniu sprawdzania OverflowException obserwujemy wydłużenie czasów średnio o jakieś 5%. Nie ma tragedii, ale warto o tym pamiętać.

2. Wartości F(n) rosną wykładniczo. Wykres z Excel-a poniżej.

Zaraz, zaraz. Skoro to jest funkcja wykładnicza, to dlaczego nie obliczymy jej od razu z jakiegoś wzoru w bardziej zwartej postaci, tylko bawimy się w jakieś rekurencje? Hmmm… Taki wzór oczywiście istnieje:

i pozwala obliczyć w niewielkim stałym czasie:

static double pwk = Math.Sqrt(5.0);
static double a = (1.0 + pwk) * 0.5;
static double b = (1.0 - pwk) * 0.5;
static double c = 1.0 / pwk;

int Fib(int n)
{
    return (int)((Math.Pow(a, n + 1) - Math.Pow(b, n + 1)) * c);
}

Skąd się wziął ten wzór? Istnieje cały dział matematyki dyskretnej zajmujący się szukaniem takich wzorów, czyli tzw. rozwiązywaniem rekurencji. Swoją drogą to dość ciekawy temat, bo znanych jest kilka metod postępowania, a nie na wszystkie rekurencje działają wszystkie te metody. Czy są rekurencje, których wzory ogólne nie są znane?

PS. Linia trendu nie kłamie. To nie przypadek, że , .

3. Czasy obliczeń rosną wykładniczo. Wykres z Excel-a poniżej.

Hmmm… To pewnie przez tą rekurencję. Algorytm musi obliczać ponownie już wcześniej obliczone wartości. A co by było gdyby je tak wpisać do tablicy i korzystać z już obliczonych?

int[] fib = new int[46];

int Fi(int n)
{
    if (fib[n] == 0)
        fib[n] = n < 2 ? 1 : Fi(n - 1) + Fi(n - 2);
    return fib[n];
}

Wartości funkcji zostały wpisane do tablicy. Programowanie dynamiczne jak ta lala. No to jedziemy z koksem.

Jak by powiedział Kapitan Bomba: „K***a, ale za*******amy że c**j”. Wniosek? Rekurencja „czysta”, bez wsparcia dodatkową pamięcią i bez programowania dynamicznego nadaje się tylko do śmietnika.

Ale moment. To jeszcze nie koniec. Po co nam w ogóle rekurencja? Zamieńmy to na zwykłą iterację!

fib[0] = fib[1] = 1;
for (int n = 2; n < 46; n++)
{
    fib[n] = fib[n - 1] + fib[n - 2];
}

Ale moment. Po co nam w ogóle tablica? Jeśli zaczniemy ciąg od zera, a nie od jedynki (tak, jak sugeruje też wzór ogólny, w którym musieliśmy poprawić n na n + 1), to okaże się, że obliczenia można wykonywać na bieżąco i mówimy w takich przypadkach, że algorytm może „pracować w miejscu” (tym miejscem są tutaj dwie zmienne f0 i f1):

int f0 = 1, f1 = 0;
for (int n = 0; n < 46; n++)
{
    Console.WriteLine(n % 2 == 0 ? f0 += f1 : f1 += f0);
}

Kosmita panie Kapitanie, co robić? Jak to co? Na*****alać!!!

Console.WriteLine(1);
Console.WriteLine(1);
Console.WriteLine(2);
Console.WriteLine(3);
Console.WriteLine(5);
Console.WriteLine(8);
Console.WriteLine(13);
Console.WriteLine(21);
Console.WriteLine(34);
Console.WriteLine(55);
Console.WriteLine(89);
Console.WriteLine(144);
Console.WriteLine(233);
Console.WriteLine(377);
Console.WriteLine(610);
Console.WriteLine(987);
Console.WriteLine(1597);
Console.WriteLine(2584);
Console.WriteLine(4181);
Console.WriteLine(6765);
Console.WriteLine(10946);
Console.WriteLine(17711);
Console.WriteLine(28657);
Console.WriteLine(46368);
Console.WriteLine(75025);
Console.WriteLine(121393);
Console.WriteLine(196418);
Console.WriteLine(317811);
Console.WriteLine(514229);
Console.WriteLine(832040);
Console.WriteLine(1346269);
Console.WriteLine(2178309);
Console.WriteLine(3524578);
Console.WriteLine(5702887);
Console.WriteLine(9227465);
Console.WriteLine(14930352);
Console.WriteLine(24157817);
Console.WriteLine(39088169);
Console.WriteLine(63245986);
Console.WriteLine(102334155);
Console.WriteLine(165580141);
Console.WriteLine(267914296);
Console.WriteLine(433494437);
Console.WriteLine(701408733);
Console.WriteLine(1134903170);
Console.WriteLine(1836311903);

Spis treści Strona wyżej: Coś dla matematyków Następna strona: Liczby pierwsze