Acest articol face parte dintr-o serie de articole dedicate implementării de algoritmi clasici în Microsoft Excel 365.
Sursa de inspirație este site-ul: https://app.codility.com/programmers/lessons/1-iterations/binary_gap/
Doar puțină teorie
Iterațiile sau structurile de control clasice includ:
- IF cu sintaxa pseudocod: dacă condiție atunci acțiune_adevăr altfel acțiune_fals
- FOR cu sintaxa pseudocod: for variabilă in interval_de_valori acțiune
- WHILE cu sintaxa pseudocod: while condiție acțiune
În Excel în schimb nu există nici FOR nici WHILE implementată ceea ce face oarecum diferită abordarea. O simulare a unui FOR este întâlnită uneori prin utilizarea funcției SEQUENCE() combinată cu funcția SCAN() sau REDUCE(). De exemplu dacă am avea un pseudocod de tipul: pentru fiecare număr de la 1 la 9 adunați numărul cu suma numerelor anterioare. Exemplu:
Problema supusă rezolvării este BinaryGap
Aceasta presupune transformarea unui număr zecimal în număr binar după care trebuie determinate numărul maxim de secvențe de 0 care apar în numărul binar, urmate de valoarea 1.
În exemplu este prezentat numărul 9 care în binar este 1001 și care are un număr de 2 de 0 consecutivi urmați de valoarea 1. În numărul 32 care este în binar: 100000 numărul de 0 nu este urmat de 1 ceea ce înseamnă că rezultatul va fi 0.
Problema de pe Codility oferă un set de numere de test [1..2,147,483,647]. Doar că în Excel ultimul număr zecimal care poate fi transformat în binar este numărul 511, de la 512 încolo obținem eroarea #NUM!
În imagine propuneri de rezolvare.
Menționez că localizarea pe calculatorul meu este localizarea în română ceea ce face ca separatorii de formule să fie ; (punct și virgulă) nu , (virgula).
Ca să transform numărul în binar folosesc funcția DEC2BIN(). Funcția din celula B2 este: =DEC2BIN(A2)
Dacă aș dori să văd câți de 0 sunt în total în număr în D2 am introdus funcția LEN() pentru a determina lungimea șirului rezultat în binar și SUBSTITUTE() pentru a înlocui numerele de 1 cu nimic. Funcția din D2 este: =LEN(B2)-LEN(SUBSTITUTE(B2;”0″;””)).
Dacă ar trebui să determin doar numărul maxim de 0 consecutivi atunci folosesc în E2 funcția: =MAX(SCAN(0;MID(B2;SEQUENCE(LEN(B2));1); LAMBDA(a;v; IF(v=”1″; 0; a+1))))
În care:
SCAN() scanează un array de valori rezultat prin descompunerea valoare cu valoare a numărului binar din B2 pe baza lungimii sale SEQUENCE(LEN(B2)). Funcția SCAN() are nevoie de o funcție LAMBDA pentru calculul valorii finale. În Lambda avem variabilele a – acumulator, și v- valoarea curentă. Dacă valoarea curentă este 1 ca text, pentru vă provine din MID(), atunci acumulatorul va lua valoarea 0, altfel va lua valoarea iterată cu 1. La final aplic un MAX() pentru a determina exact care este cea mai mare secvență de valori 0.
Pentru numărul 401 care în binar este 110010001 rezultatul SCAN() este:
În exemplul lui 401 voi obține valoarea finală 3.
Dacă dorim să răspundem corect la problemă și să numărăm doar valorile 0 care sunt urmate de 1 atunci formula se complică puțin.
În F2 am introdus o funcție LET() ca să pot scrie mai puține caractere. Scopul în algoritmi este să ai un cod cât mai optim și poate mai puține caractere într-o formulă / cod.
=LET(bloc; MID(B2;SEQUENCE(LEN(B2));1); zu; IF(RIGHT(B2)=”0″;0;1); cate; MAX(SCAN(0; bloc; LAMBDA(a;v; IF(v=”1″; 0; a+1)))); conc; CONCAT(zu;”-„;cate); IF(zu=0;0;cate))
În această funcție am introdus variabila zu pentru a determina dacă la finalul șirului este sau nu valoarea 1. Această abordare are în schimb o eroare de logică pentru că nu tratează excepțiile în care avem totuși valori 0 urmate de 1 în numărul binar și se finalizează cu valoarea 1. Exemplu este numărul 486 care se termină cu 0 dar are 2 de 0 în interior urmați de valoarea 1.
Variantele cu emulare de FOR sunt interesante și pot duce la soluții destul de frumoase. Doar că în rezolvarea problemelor mai complexe de Excel important este să ai formule cât mai reduse ca dimensiune pentru a asigura un optim de execuție dar și pentru a face mai ușor depanarea formulelor. În acest sens propun o metodă de rezolvare fără iterații explicite.
Formula din B46 este: =MAX(LEN(DROP(TEXTSPLIT(B46;1);;-1)))
În care:
TEXTSPLIT() – împarte numărul binar în funcție de fiecare apariție a valorii 1 rezultând vectori cu număr de coloane diferite:
În cazul în care numărul splitat nu conține nici un 0 vom vedea o listă de celule vide.
În cazul în care în ultima coloană a fiecărui vector avem valoarea 0 înseamnă că secvența de 0 nu este urmată de valoarea 1.
DROP() – este utilizat pentru a elimina excepția când la final-ul vectorului avem valoarea 0. Elimină ultima celulă din rezultat.
LEN() – numără pentru fiecare celulă rămasă în vector cât de lungă este secvența de 0 rezultatul intermediar fiind de forma:
MAX() extrage din lista de valori valoarea maximă a numărului de 0 consecutivi urmați de valoarea 1.
În Google Spreadsheets nu există funcția TEXTSPLIT() dar există o funcție SPLIT() care nu funcționează asemănător cu cea din Excel.
Cam asta ar fi. Sper să fie util cuiva.
Valy Greavu - Live Blog 