Modele de algoritmi în #Excel – Fibonacci numbers (13.2) – Ladder

Acest articol este o continuare a articolului despre numerele Fibonacci: Modele de algoritmi în #Excel – Fibonacci numbers (13) – Partea 1 – FibFrog și prezintă o metodă de rezolvare a problemei Ladder de pe site-ul Codility: https://app.codility.com/programmers/lessons/13-fibonacci_numbers/ladder/

Odată rezolvată problema șirurilor Fibonacci explicată în articolul anterior, această problemă nu are nimic special, atât timp cât autorii problemei explică în detaliu modul de rezolvare.

Pe scurt, problema presupune calcularea numărului de combinații prin care se poate urca o scară de dimensiune N pâșind una sau două trepte.

Datele de intrare ale problemei sunt doi vectori A și B în care:

Vectorul A: Numărul de trepte pentru fiecare scară
Fiecare element A[i] din vectorul A reprezintă numărul de trepte pentru o anumită scară.
De exemplu, dacă A = [4, 3, 5], atunci avem trei scări:
Prima scară are 4 trepte
A doua scară are 3 trepte
A treia scară are 5 trepte
Practic, fiecare element al lui A definește dimensiunea unei scări pentru care trebuie să calculăm numărul de moduri în care putem ajunge în vârf.

Vectorul B: Modulo pentru fiecare scară
Fiecare element B[i] din vectorul B reprezintă valoarea modulo 2^B[i] care trebuie aplicată rezultatului.
Deoarece valorile Fibonacci cresc foarte rapid, trebuie să calculăm rezultatul modulo 2^B[i] pentru a evita depășirea limitelor numerice.
De exemplu, dacă B = [3, 2, 4], atunci:
Pentru prima scară, rezultatul trebuie modulo 2^3=8
Pentru a doua scară, rezultatul trebuie modulo 2^2=4

Rolul lui B este să controleze dimensiunea rezultatului final pentru fiecare scară, evitând numere prea mari.

Rezolvare problema în Excel

În care:

D2 – Care este maximul sir Fibonnaci +1
În problema Ladder, folosim Fibonacci(N+1) pentru că trebuie să numărăm modurile distincte de a urca scara.
Fibonacci(N+1) se bazează pe faptul că pentru a ajunge la treapta 𝑁 putem veni fie de la 𝑁 − 1 (1 pas), fie de la 𝑁 − 2 (2 pași).

E2 – Puterile lui 2 la valoarea lui B

F2 – Se calculeaza restul impartirii numarului Fibonaci rezultat la puterile lui B

Funcția _fFibonacciSir() a fost introdusă și explicată în articolul anterior.

Rezolvarea integrată a problemei printr-o singură formulă cu funcții recursive nesalvate anterior ar fi:

=LET(_a; A2:A6; _b; B2:B6;
     fReqFibSir; LAMBDA(n; (((1+SQRT(5))/2)^SEQUENCE(n)-((1-SQRT(5))/2)^SEQUENCE(n))/SQRT(5));
      fibocat; MAP(_a; LAMBDA(v; MAX(fReqFibSir(v+1))));
      PuteriB; MAP(_b; LAMBDA(v; 2^v));
      return; MOD(fibocat;PuteriB);
return)

în care locul funcției presalvate _fFibonacciSir() este luat de funcția recursivă: fReqFibSir.

De remarcat în această formulă faptul să în partea de return am aplicat MOD() pentru cei 2 vectori cu număr de elemente egale, fără a întâmpina nici un fel de eroare.

Cam atât pentru acest articol!

Sper să fie util cuiva!