Program C# do drukowania liczb ciągu Fibonacciego

Podejście rekurencyjne

Ciąg Fibonacciego – ciąg liczb naturalnych określony rekurencyjnie w sposób następujący: Pierwszy wyraz jest równy 0, drugi jest równy 1, każdy następny jest sumą dwóch poprzednich. Formalnie: Kolejne wyrazy tego ciągu nazywane są liczbami Fibonacciego.

Napiszmy teraz program w języku C# do drukowania liczb ciągu Fibonacciego. Program będzie prosił użytkownika o podanie, ile liczb ciągu chce wydrukować, a następnie wyświetli odpowiednią ilość liczb z ciągu Fibonacciego.

Oto przykładowy kod:

using System;

class Fibonacci
{
    static void Main()
    {
        Console.Write("Podaj liczbę elementów ciągu Fibonacciego do wydrukowania: ");
        int liczbaElementow = int.Parse(Console.ReadLine());

        for (int i = 0; i < liczbaElementow; i++)
        {
            Console.WriteLine($"{i + 1}: {FibonacciNumber(i)}");
        }
    }

    static int FibonacciNumber(int n)
    {
        if (n <= 1)
            return n;
        return FibonacciNumber(n - 1) + FibonacciNumber(n - 2);
    }
}

Ten program korzysta z rekurencji do obliczania liczby Fibonacciego na danej pozycji. Gdy użytkownik uruchomi program, zostanie poproszony o wprowadzenie liczby, która określi, ile liczb ciągu Fibonacciego zostanie wyświetlonych. Program następnie wydrukuje te liczby wraz z ich pozycją w ciągu.

Warto zauważyć, że dla bardzo dużych wartości może to być proces czasochłonny, ponieważ rekurencyjne obliczanie liczb Fibonacciego jest nieefektywne dla dużych liczb. W takich przypadkach lepiej stosować inne metody, takie jak dynamiczne programowanie. Dla test wpiszcie np. 100, a zobaczycie efekt.

Alternatywny sposób – techniki programowania dynamicznego

Zdecydowanie istnieją bardziej efektywne metody obliczania liczb ciągu Fibonacciego niż podejście rekurencyjne. Jednym z najbardziej efektywnych sposobów jest użycie techniki programowania dynamicznego. W programowaniu dynamicznym, zamiast wielokrotnego obliczania tych samych wartości (jak w przypadku rekurencji), obliczone wartości są zapisywane (często w tablicy), dzięki czemu każda liczba Fibonacciego jest obliczana tylko raz.

Oto przykład programu w C#, który używa tej metody:

using System;

class Fibonacci
{
    static void Main()
    {
        Console.Write("Podaj liczbę elementów ciągu Fibonacciego do wydrukowania: ");
        int liczbaElementow = int.Parse(Console.ReadLine());

        long[] fibNumbers = new long[liczbaElementow];
        if (liczbaElementow > 0)
        {
            fibNumbers[0] = 0;
            Console.WriteLine($"1: {fibNumbers[0]}");
        }
        if (liczbaElementow > 1)
        {
            fibNumbers[1] = 1;
            Console.WriteLine($"2: {fibNumbers[1]}");
        }

        for (int i = 2; i < liczbaElementow; i++)
        {
            fibNumbers[i] = fibNumbers[i - 1] + fibNumbers[i - 2];
            Console.WriteLine($"{i + 1}: {fibNumbers[i]}");
        }
    }
}

W tym kodzie, tablica fibNumbers jest używana do przechowywania i ponownego wykorzystywania obliczonych wartości. Program najpierw inicjalizuje dwa pierwsze elementy ciągu, a następnie każda kolejna liczba Fibonacciego jest obliczana jako suma dwóch poprzednich i zapisywana w tablicy.

Ta metoda jest znacznie bardziej wydajna, szczególnie dla dużych liczb, ponieważ unika problemu powtarzających się obliczeń, który występuje w podejściu rekurencyjnym. Programowanie dynamiczne jest znakomitym wyborem, gdy potrzebujemy efektywnie obliczać wartości, które zależą od wcześniej obliczonych wyników.

Alternatywny sposób – metoda iteracyjna

Inny efektywny i dydaktycznie interesujący sposób obliczania liczb ciągu Fibonacciego to metoda iteracyjna. Ta metoda polega na obliczaniu kolejnych liczb ciągu poprzez iterowanie i aktualizowanie wartości dwóch zmiennych, które przechowują ostatnie dwie liczby ciągu. Jest to znacznie szybsze niż rekurencyjne podejście, ponieważ nie wymaga wywoływania funkcji rekurencyjnej, co jest kosztowne pod względem zasobów.

Oto przykład implementacji metody iteracyjnej w języku C#:

using System;

class Fibonacci
{
    static void Main()
    {
        Console.Write("Podaj liczbę elementów ciągu Fibonacciego do wydrukowania: ");
        int liczbaElementow = int.Parse(Console.ReadLine());

        long a = 0, b = 1, c;

        for (int i = 0; i < liczbaElementow; i++)
        {
            if (i <= 1)
                c = i;
            else
            {
                c = a + b;
                a = b;
                b = c;
            }
            Console.WriteLine($"{i + 1}: {c}");
        }
    }
}

W tym przykładzie, dwie zmienne a i b przechowują dwie ostatnie liczby ciągu Fibonacciego. Na każdym etapie pętli obliczana jest nowa liczba c jako suma a i b, a następnie wartości a i b są aktualizowane. To podejście jest szczególnie użyteczne, gdy chcemy obliczyć dużą liczbę liczb Fibonacciego, ponieważ jest bardzo efektywne pod względem czasowym i pamięciowym.

Metoda iteracyjna jest świetnym przykładem, jak proste zmiany w podejściu do problemu mogą znacząco zwiększyć wydajność algorytmu, co jest kluczową lekcją w nauczaniu informatyki i programowania.