6

using System;
using System.Collections.Generic;
using System.Diagnostics;

class Zadanie6
{
    static void Main()
    {
        int numerAlbumu = 35736; 
        int n = Math.Min(40, (int)Math.Round(numerAlbumu / 100.0)); // Ograniczenie do 40 dla rekurencji
        
        Console.WriteLine("=== Obliczanie ciągu Fibonacciego ===");
        Console.WriteLine($"Dla n = {n} (wyliczone z numeru albumu {numerAlbumu})");
        Console.WriteLine();

        // Test rekurencyjny
        TestujAlgorytm("Rekurencyjny", () => {
            long kroki = 0;
            long wynik = FibonacciRekurencyjnie(n, ref kroki);
            return (wynik, kroki);
        });
        
        // Test memoizacji
        TestujAlgorytm("Memoizacja", () => {
            long kroki = 0;
            long wynik = FibonacciMemo(n, ref kroki);
            return (wynik, kroki);
        });
        
        // Test iteracyjny
        TestujAlgorytm("Iteracyjny", () => {
            long kroki = 0;
            long wynik = FibonacciIteracyjnie(n, ref kroki);
            return (wynik, kroki);
        });
    }

    static void TestujAlgorytm(string nazwa, Func<(long wynik, long kroki)> algorytm)
    {
        try
        {
            Console.WriteLine($"[{nazwa}] Rozpoczęcie obliczeń...");
            var stoper = Stopwatch.StartNew();
            var (wynik, kroki) = algorytm();
            stoper.Stop();
            
            Console.WriteLine($"Wynik: {wynik}");
            Console.WriteLine($"Liczba kroków: {kroki}");
            Console.WriteLine($"Czas: {stoper.Elapsed.TotalMilliseconds} ms");
            Console.WriteLine();
        }
        catch (Exception ex)
        {
            Console.WriteLine($"Błąd: {ex.Message}");
        }
    }

    // Wersja rekurencyjna z licznikiem kroków
    static long FibonacciRekurencyjnie(int n, ref long licznikKrokow)
    {
        licznikKrokow++; // Zliczamy każde wywołanie funkcji
        if (n < 0) throw new ArgumentException("n nie może być ujemne");
        if (n <= 1) return n;
        return FibonacciRekurencyjnie(n - 1, ref licznikKrokow) 
             + FibonacciRekurencyjnie(n - 2, ref licznikKrokow);
    }

    // Wersja z memoizacją z licznikiem kroków
    static long FibonacciMemo(int n, ref long licznikKrokow)
    {
        if (n < 0) throw new ArgumentException("n nie może być ujemne");
        return FibonacciMemoHelper(n, new Dictionary<int, long>(), ref licznikKrokow);
    }

    static long FibonacciMemoHelper(int n, Dictionary<int, long> pamiec, ref long licznikKrokow)
    {
        licznikKrokow++; // Zliczamy każde wywołanie funkcji
        if (n <= 1) return n;
        if (pamiec.TryGetValue(n, out long wartosc)) return wartosc;
        
        long wynik = FibonacciMemoHelper(n - 1, pamiec, ref licznikKrokow) 
                   + FibonacciMemoHelper(n - 2, pamiec, ref licznikKrokow);
        pamiec[n] = wynik;
        return wynik;
    }

    // Wersja iteracyjna z licznikiem kroków
    static long FibonacciIteracyjnie(int n, ref long licznikKrokow)
    {
        licznikKrokow++; // Krok: sprawdzenie warunku wejściowego
        if (n < 0) throw new ArgumentException("n nie może być ujemne");
        
        licznikKrokow++; // Krok: sprawdzenie warunku n <= 1
        if (n <= 1) return n;

        long poprzedni = 0;
        long obecny = 1;
        licznikKrokow += 2; // Kroki: przypisania początkowych wartości

        for (int i = 2; i <= n; i++)
        {
            licznikKrokow++; // Zliczamy każdą iterację pętli
            
            long nowy = poprzedni + obecny;
            poprzedni = obecny;
            obecny = nowy;
            
            licznikKrokow += 3; // Kroki: obliczenia i przypisania
        }
        
        licznikKrokow++; // Krok: zwracanie wyniku
        return obecny;
    }
}