1. Learn
    2. /
  2. 课程
    3. /
  3. Structuri de date și algoritmi în Python
Connected

道练习

Șirul Fibonacci

În acest exercițiu, vei implementa șirul Fibonacci, care apare frecvent în natură. Șirul arată astfel: "0, 1, 1, 2, 3, 5, 8…". Vei crea o implementare recursivă a unui algoritm care generează acest șir.

Primele două numere sunt 0 și 1, iar restul reprezintă suma celor două numere precedente.

Putem defini acest șir recursiv astfel: \(fib(n)=fib(n-1)+fib(n-2)\), cu \(fib(0)=0\) și \(fib(1)=1\), unde \(n\) este poziția \(n\) în șir.

În primul pas, vei implementa Fibonacci folosind recursivitatea. În al doilea pas, vei îmbunătăți soluția prin programare dinamică, salvând rezultatele subproblemelor în variabila cache.

说明 1/2

undefined XP
  • 1
    • Definește cazul de bază.
    • Apelează recursiv funcția fibonacci().
  • 2
    • Verifică dacă valoarea există în cache.
    • Salvează rezultatul în cache pentru a evita recalcularea lui mai târziu.