Algoritmi rezolvați în C++: Șirul lui Fibonacci (Lecția 5.3)

Algoritmi rezolvați în C++: Șirul lui Fibonacci

Bună ziua și bun venit la lecția 5.3 a cursului nostru despre algoritmi rezolvați în limbajul de programare C++. În această lecție, vom explora unul dintre cei mai cunoscuți și fascinanți algoritmi matematici – Șirul lui Fibonacci.

Ce este Șirul lui Fibonacci?

Șirul lui Fibonacci este o secvență matematică în care fiecare termen este suma celor doi termeni precedenți. Începe cu 0 și 1, iar următorul termen este suma celor două termeni anterioare. Astfel, șirul începe astfel: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, și așa mai departe.

Implementarea algoritmului în limbajul C++

Pentru a implementa algoritmul Șirului lui Fibonacci în limbajul C++, putem folosi o abordare recursivă sau o abordare iterativă. Vom explora ambele metode în continuare.

Abordarea recursivă

În implementarea recursivă, vom defini o funcție care primește un număr n și returnează al n-lea termen din Șirul lui Fibonacci. Aceasta va fi o implementare simplă și elegantă, dar poate fi ineficientă pentru valori mari ale lui n, deoarece va calcula de mai multe ori aceeași valoare.

#include <iostream>

int fibonacci(int n)
{
    if (n <= 1)
        return n;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

int main()
{
    int n;
    std::cout <> n;
    std::cout << "Termenul " << n << " din Șirul lui Fibonacci este: " << fibonacci(n) << std::endl;

    return 0;
}

În această implementare, funcția “fibonacci” primește un număr n și verifică dacă acesta este mai mic sau egal cu 1. În caz afirmativ, returnează n. În caz contrar, se apelează recursiv funcția “fibonacci” pentru n-1 și n-2 și se returnează suma acestora.

Abordarea iterativă

Pentru a evita recalcularea termenilor, putem implementa Șirul lui Fibonacci folosind o abordare iterativă, care utilizează o buclă pentru a calcula fiecare termen în ordine.

#include <iostream>

int fibonacci(int n)
{
    if (n <= 1)
        return n;

    int a = 0, b = 1, fib = 0;
    for (int i = 2; i <= n; i++)
    {
        fib = a + b;
        a = b;
        b = fib;
    }

    return fib;
}

int main()
{
    int n;
    std::cout <> n;
    std::cout << "Termenul " << n << " din Șirul lui Fibonacci este: " << fibonacci(n) << std::endl;

    return 0;
}

În această implementare, funcția “fibonacci” primește un număr n și verifică dacă acesta este mai mic sau egal cu 1. În caz afirmativ, returnează n. În caz contrar, se folosește o buclă “for” pentru a calcula fiecare termen al Șirului lui Fibonacci în ordine, evitând astfel recalcularea.

Concluzie

Șirul lui Fibonacci este un algoritm matematic fascinant și util, care poate fi implementat în limbajul de programare C++ atât într-un mod recursiv, cât și într-un mod iterativ. Am explorat ambele abordări și am prezentat codul corespunzător. Este important să înțelegem că abordarea recursivă poate fi elegantă, dar poate fi ineficientă pentru valori mari ale lui n, în timp ce abordarea iterativă evită recalcularea termenilor și este mai eficientă.

Sperăm că această lecție v-a fost utilă și că acum aveți o înțelegere mai bună a modului în care puteți implementa Șirul lui Fibonacci în limbajul C++. Vă încurajăm să experimentați cu codul și să explorați mai multe despre acest algoritm fascinant. Vă mulțumim pentru atenție și vă așteptăm la următoarea lecție!