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:
î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.
De data aceasta mi-a dat greu! :) De aceea am decis să împart articolul despre numerele Fibonacci în două părți: una pentru problema FibFrog și a doua pentru Ladder. Pentru cititorii care au reușit să urmărească aceste serii complicate de programare funcțională în Excel, poate au observat că în articole sunt vehiculate permanent aceleași funcții, doar cu construcții și cazuri de utilizare diferite.
Pentru acest articol vă propun o metodă de rezolvare a problemei FibFrog de pe site-ul Codility: https://app.codility.com/programmers/lessons/13-fibonacci_numbers/. Trebuie știut că la data publicării acestui articol, nici un instrument de AI nu poate rezolva problema corect în Excel.
Să începem ca de obicei cu …
Un pic de teorie
Sunt foarte multe materiale de studiu pentru numerele Fibonacci pe Internet, ele stârnind interesul multor autori datorită aplicabilității pe scară largă a acestei secvențe.
Secvența Fibonacci este o succesiune recursivă definită de relația de recurență:
F(n)=F(n−1)+F(n−2)
unde F(0)=0 și F(1)=1. Aceasta are multiple aplicații în informatică, inclusiv în algoritmi de optimizare, structuri de date (heap Fibonacci), analiza complexității algoritmilor (divide et impera) și generarea de chei criptografice. Secvența este, de asemenea, utilizată în probleme de programare dinamică și este strâns legată de numărul de aur, având proprietăți logaritmice utile în analiza complexității algoritmilor.
Una din cele mai interesante metode de a calcula șirurile de numere este dată de formula:
Pentru a implementa această formulă în Excel utilizăm cu precădere funcția SQRT() pentru calculul radical și SEQUENCE() pentru valoarea lui n.
Având în vedere că în rezolvarea problemei am nevoie permanentă de această construcție introduc în acest articol funcția _fFibonacciSir() cu parametrul N pe care o voi reutiliza ulterior.
Funcția DROP o utilizez pentru a elimina prima linie din șir, în așa fel încât să rămân cu o singură valoare 1 în rezultat.
În același timp o variație a acestei probleme este verificarea dacă un număr face parte dintr-un șir Fibonacci. Pentru a rezolva acest aspect introduc funcția _fFibonacciIS() cu paramentrul N, în care N este oricare număr natural pe care doresc să-l testez.
Această funcție returnează valorile TRUE sau FALSE și reutilizează funcția _fFibonacciSir() pentru a calcula secvențele lui N. construcția _n1+1 din parametrul funcției este pentru a corecta problemele numerelor mici: 0, 1. În rezolvarea problemei 0 nu este considerat parte a acestei secvențe, chiar dacă în realitate el este primul număr. În versiunile viitoare voi aduce corecții dar în rezolvarea problemei am nevoie ca 0 să nu fie luat în seamă.
Un alt aspect important în aceste șiruri este raportul sau numărul de aur denumit φ (phi). Acest raport este întâlnit frecvent în lumea care ne înconjoară. Valoarea lui după al 14 element al șirului este 1,61803.
Problema FibFrog sau Salturile Fibonacci prin matrice
Fără a insista pe idioțeniile politice care spamează rețelele sociale, matricile în Excel au o putere deosebită de calcul vectorial și reprezintă o cale elegantă de a rezolva diferite tipuri de probleme.
FibFrog este o problemă care combină elemente din teoria numerelor (șirul Fibonacci) și grafuri. Scopul este să determini numărul minim de sărituri pe care o broască trebuie să le facă pentru a traversa un râu reprezentat de o serie de frunze și apă. Avem un șir binar A (de exemplu, [0, 1, 0, 0, 0, 1, 0]), unde: 1 reprezintă o frunză și 0 reprezintă apă. Broasca poate sări doar pe frunze (pe pozițiile marcate cu 1).
Dificultatea problemei este dată de restricția că lungimile săriturilor sunt restricționate la valor care aparțin șirului Fibonacci (F), adică {1, 2, 3, 5, 8, ...}.
Broasca începe la poziția -1 (deci înainte de prima frunză) și trebuie să ajungă după ultima poziție a șirului (pe N, unde N este lungimea șirului). Obiectivul principal este calcularea numărului minim de sărituri necesare pentru a traversa complet șirul de frunze și apă.
Dacă broasca nu poate traversa folosind sărituri din șirul Fibonacci, rezultatul trebuie să fie -1. Pentru a înțelege mai bine problema, cele mai bune explicații le-am găsit în sursa de mai jos.
În B4 am descompus șirul dat în B2 cu funcția: =–TEXTSPLIT(B1;;”,”) apoi în A4 am calculat secvența de poziții a fiecărei frunze cu start de la 0: =SEQUENCE(ROWS(B4#);;0)
În D4 am calculat secvența de numere corespondent pozițiilor din A4 prin reutilizarea funcției _fBibonacciSir() definită anterior. M-am raportat la numărul maxim de poziții și am filtrat doar numerele care răspund criteriului: =LET(fib; _fFibonacciSir(MAX(A4#)); FILTER(fib; fib<=MAX(A4#)))
În E4 am calculat poziția frunzelor prin filtrarea vectorului Poz din A4 cu valorile 1 de pe vectorul A din B4. Ca să răspund cerințelor problemei, am adugat valoarea -1 ca fiind malul de start și valoarea maximă din poziții ca fiind malul destinație. =VSTACK(-1;FILTER(A4#;B4#=1);MAX(A4#)+1). În VSTACK() am adăugat 3 termen: valoarea -1, valorile filtrate din poziții și maxim poziții +1.
Cheia problemei este în H3 unde am proiectat o matrice RxC în care antet de coloane și linii sunt valorile frunzelor rezultate în E4. Formula utilizată este:
în care un rol deosebit îl are funcția recursivă fScanCol care apelează funcția creată anteriror: _fFibonacciIS(). Rolul său este de a păsta în matrice doar valorile din șirul Fibonacci.
Variabila diff este utilizată pentru a genera matricea ințială prin care scad valorile corespondente din vectorul arr pe toate combinațiile posibile. Ca să pot afișa antetele matricei (linii și coloane) am folosit o combinație de VSTACK() cu HSTACK().
A doua cheie este în H13 unde am extras toate combinațiile optime de salturi.
Chiar dacă pare complicată, formula nu face decât să aducă valorile din antetul de linie și coloană specifice valorilor rezultat de pe fiecare coloană. Cheia este valoarea -1 din variabila poz care caută valoarea specifică de jos în sus pe vector-ul _hc care este de fapt prima coloană din matrice. colc este un artificiu care rulează scan-ul în matrice de fapt, coloană cu coloană. Nu aveam cum să rulez funcția BYCOL() pentru că nu o pot integra în SCAN(). Ca să păstrez doar pozițiile în forma start;final am utilizat două funcții DROP() prin care am eliminat prima și ultima linie din rezultat. Ca să pot vedea valorile tabelar am implemententat variabila splited care folosește artificiul de splitare linie cu linie.
Rezultatul final al funcției din H13 este identic cu cel din K13, unde am făcut de fapt reunificarea pentru a putea parcurge aceste valori cu scopul de a le extrage pe cele care îndeplinesc criteriul cerut.
Aparent cea mai grea chestie a fost să găsesc calea de a scoate doar perechile corecte de salturi. Pentru asta am încercat diferite abordări dar în final am ajuns tot la un SCAN() pe care l-am implementat în N13:
În această formulă parcurg vectorul K13# și descompun fiecare valoare F1-F2 pentru a o compara cu cele anterioare. Acumulatorul (a) este reprezentat permanent de combinația câștigătoare anterioară. Dacă valoarea de pe prima combinație nu este un număr atunci rezultatul funcției este -1 așa cum cere problema.
Toate funcțiile și calculele intermediare integrate vor duce la formula finală:
în care nu am mai folosit funcțiile definite la început ci le-am introdus ca recursive în această formulă pentru a evita erorile de a nu avea funcțiile definite / salvate.
Cam atât pentru această parte. Voi reveni cu un video pas cu pas pentru explicații suplimentare și cu partea a doua în viitor.
Având în vedere că nu am prea multă teorie nu mai facem o secțiune separată pentru această componentă. Amintim doar că Algoritmul Euclidean este utilizat pentru calcularea celui mai mare divizor comun (GCD) al două numere printr-un proces iterativ sau recursiv de împărțiri succesive; însă, în combinație cu alte metode, poate ajuta la testarea primalității sau la factorizarea numerelor. Detalii foarte faine despre algoritm găsiți la adresa: https://ro.wikipedia.org/wiki/Algoritmul_lui_Euclid
Problema ChocolatesByNumbers
Ai N bucăți de ciocolată aranjate într-un cerc. Numeri aceste bucăți de la 0 la N-1. Începi să mănânci bucăți de ciocolată de la bucata numerotată 0. După ce mănânci o bucată, sari peste M bucăți și mănânci următoarea (adică sari la bucata 0 + M mod N, și tot așa).
Întrebarea este: Câte bucăți de ciocolată vei mânca în total până când te întorci la o bucată pe care ai mai mâncat-o înainte?
Parametrii:
N: Numărul total de bucăți de ciocolată (N ≥ 1).
M: Numărul de bucăți peste care sari după ce mănânci o bucată (M ≥ 1).
Exemplu:
Să considerăm cazul în care:
N = 10 (ciocolată aranjată în cerc cu 10 bucăți)
M = 4 (sari peste 4 bucăți după ce mănânci una)
Secvența bucăților mâncate va fi: 0 → 4 → 8 → 2 → 6 → 0. Vei mânca 5 bucăți de ciocolată înainte să te întorci la bucata 0.
Observații:
Vei mânca fiecare bucățică o singură dată înainte de a reveni la o bucățică deja consumată.
Problema are o legătură cu cel mai mare divizor comun (GCD) dintre N și M.
Rezolvare în Excel
Pas cu pas în rezolvarea problemei, concret începem de la C5 care calculează restul împărțirii numărului N la secvența de numere componente. În felul acesta pentru valorile 0 identificăm divizorii. Procedăm la fel pentru numărul M în celula D5. Ca să aflăm divizorii filtrăm secvența de numere componente pentru toate valorile 0. În felul acesta obținem în E5 si F5 divizorii celor două numere. În G5 căutăm cel mai mare număr comun din cele două șiruri după care indexăm lista divizorilor cu valoarea rezultat și obținem astfel valoarea 2. În context în I5 calculăm numărul N împărțit la cel mai mare divizor comun.
Nu mi-a luat foarte mult timp rezolvarea, dar am fost oarecum dezamagit de mine când am aflat că în Excel există built-in funcția GCD() care returnează exact valoarea mea din H5. În același timp funcția GCD() permite calcularea divizorului comun al mai multor numere. Toată problema se rezumă acum la formula:
=A2/GCD(A2;B2)
De multe ori spun că dacă nu suntem suficient de bine pregătiți riscăm să pierdem foarte mult timp reinventând roata… în cazul acesta roata pătrețelelor de ciocolată. :)
Exemple practice?
Problema se aplică cu succes rezolvării tuturor problemelor ciclice: planificarea reviziei unor mașini de pe un lanț de producție sau în vânzări, planificarea campaniilor de marketing sau promoțiilor specifice.
Problema CommonPrimeDivisors
Această problemă face parte tot din categoria problemelor care implică divizori comuni și numere prime. Scopul acestei probleme este de a determina dacă două numere împărtășesc aceiași divizori primi.
Avem doi vectori de numere întregi, A și B, ambele de lungime N. Pentru fiecare pereche de numere A[i] și B[i], trebuie să verifică, dacă aceștia au exact aceiași divizori primi. Dacă da, se returnează valoarea 1 pentru acea pereche, iar dacă nu returnăm valoarea 0. Rezultatul final este numărul total de perechi de numere care au aceiași divizori primi.
Parametrii:
A și B: doi vectori de lungime N cu numere întregi pozitive.
Exemplu:
Să presupunem că:
A = [15, 10, 9]
B = [75, 30, 5]
Analiza pentru fiecare pereche:
Pentru A[0] = 15 și B[0] = 75:
Divizorii primi ai lui 15 sunt 3 și 5.
Divizorii primi ai lui 75 sunt 3 și 5.
Cei doi au exact aceiași divizori primi → răspunsul este 1.
Pentru A[1] = 10 și B[1] = 30:
Divizorii primi ai lui 10 sunt 2 și 5.
Divizorii primi ai lui 30 sunt 2, 3 și 5.
Aceștia nu au exact aceiași divizori primi → răspunsul este 0.
Pentru A[2] = 9 și B[2] = 5:
Divizorii primi ai lui 9 sunt 3.
Divizorii primi ai lui 5 sunt 5.
Nu împărtășesc aceiași divizori primi → răspunsul este 0.
Rezultatul final al problemei este 1 pentru vă avem o singură pereche care împarte aceeași divizori primi.
Rezolvare în Excel
Ca să putem rezolva un pic mai simplu și mai rapid propun două funcții noi, ca rezultat al cercetărilor din articolele anterioare.
Funcția fPrim() – calculează dacă un număr este prim sau compus. Pentru managementul numelor și funcțiilor eu folosesc Excel Labs, un proiect Microsoft Garage.
Funcția are parametrul n care este numărul pe care dorim să-l verificăm. După care se calculează radicalul din acest număr și se realizează un secvență din 2 în 2 a valorilor rezultat. După care calculăm un fel de mod în variabila unmod prin care aflăm restul pe secvențe întregi.
Funcția fPrime() – care determină toate valorile prime de la 2 până la un anumit număr specificat.
în această funcție nu am reiterat fPrime() descris anterior ci am făcut o variabilă recursivă ftPrim care înglobează textul funcției. În această funcție pornesc secvența generată de la 5 la care concatenez valorile 2 și 3 cu ajutorul funcției VSTACK{} în așa fel încât să am șirul complet de la 2 încolo.
Rezolvarea problemei în Excel
Rezolvarea aceasta este pentru prima pereche de numere.
În C2 determinăm cel mai mare divizor comun, apoi în D2 calculăm restul împărțirii la cele două numere. În F2 și I2 aplicăm funcția fPrime() descrisă anterior pentru a calcula toate numerele prime de la 2 la numărul N și M, iar pentru fiecare din ele calculăm restul împărțirii numărului N și M la numerele prime rezultate, obținând astfel valorile 0 pentru divizori, după care filtrez cei doi vectori rezultat în H2 și K2.
Dacă cele două rezultate sunt egale obțin valoarea 1. Dacă nu obțin o valoare între 0 și 1. Pentru valorile date tabelul rezultat este format din valorile. Ceea ce înseamnă că numărând valorile 1 vom obține o singură valore.
1 0,598701901 0,409665529
Funcția finală integrată pentru a rezolva această problemă:
Valy Greavu - Live Blog 