Clasa a 7-a Lecția 13: Analiză amortizată (2)

Înregistrare video curs

Load video

YouTube

YouTube might collect personal data. Privacy Policy

ContinueDismiss

Problema Unific

Problema Unific a fost dată la OJI 2013 clasa a 7-a. Problema definește o procedură prin care două numere pot fi unificate, dacă au măcar o cifră în comun. Apoi cere să se aplice pe un vector unificări de elemente adiacente până ce nu se mai poate unifica nimic. Întotdeauna se va face prima unificare posibilă de la începutul vectorului.

Soluția forță brută este să căutăm prima pereche unificabilă de la începutul vectorului și să o unificăm. Apoi reluăm, de la începutul vectorului. Ea este pătratică, deci va depăși timpul pe teste mari.

O soluție mai bună este ca la momentul citirii unui număr nou să îl unificăm cu el dinainte, apoi rezultatul cu cel dinainte și tot așa până ce nu mai putem unifica. Apoi citim următorul număr și reluăm.

Ce complexitate are această soluție?

La prima vedere un număr nou poate fi unificat de cel mult n ori, ceea ce duce la o complexitate pătratică. Desigur că nu e așa. Deoarece fiecare număr poate fi adăugat o singură dată și eliminat o singură dată (prin unificare) rezultă că numărul de unificări este maxim 2n. Analiza amortizată ne spune că soluția este liniară în numărul de unificări.

O parte grea este unificarea propriu zisă. Deși algoritmul este clar, există destule cazuri particulare, iar implementarea dă suficiente bătăi de cap, așa încât mulți elevi au greșit-o la olimpiadă, denumind-o problemă tractor.

În realitate nu este chiar așa, ea putându-se implementa în circa 90 de linii de cod.

Implementare soluție

Subprograme cu parametri de ieșire

În problema de față ne poate fi folositoare o funcție care returnează valori folosind parametri de ieșire. Un parametru de ieșire reprezintă o variabilă care păstrează valoarea calculată în funcție și în afara ei. Am mai vorbit despre ei, dar poate este un moment bun să reluăm.

Știm să scriem subprograme cu parametri de intrare:

int subprogram (int variabila1, int variabila2) {}

Pentru a putea avea un parametru de ieșire, suntem vom declara acest parametru ca pointer:

int subprogram (int variabila1, int *variabila2) {}

Vom avea grijă ca oriunde folosim *variabila2 să păstram simbolul *.

Când chemăm subprogramul undeva, vom avea grijă să îi spunem compilatorului care este parametrul de ieșire:

a = subprogram (var1, &var2);

Simbolul & raportează adresa de memorie unde este stocată acea variabilă, astfel că, executarea programului va folosi adresele de memorie, nu valorile în sine din variabile. Așa se explică de ce trimitem parametrii comenzii fscanf() cu &, pentru ca funcția să poată returna variabilele modificate.

Iată un exemplu de program care folosește parametri de ieșire. Programul următor calculează suma și produsul a două numere într-un subprogram de tip int. Suma este returnată de către subprogram iar produsul de către parametrul de ieșire al subprogramului:

#include <stdio.h>
#include <stdlib.h>

int suma_produs(int a, int b, int *produs) {
    *produs = a * b;
    return a + b;
}

int main()
{
    FILE *fin, *fout;
    int nr1, nr2, suma, prod;

    fin = fopen("sp.in", "r");
    fscanf(fin, "%d%d", &nr1, &nr2);
    fclose(fin);

    suma = suma_produs(nr1, nr2, &prod);

    fout = fopen("sp.out", "w");
    fprintf(fout, "%d %d\n", suma, prod);
    fclose(fout);

    return 0;
}

Urmează sugestii de implementare. Le puteți ignora dacă doriți :-)

Programul principal

În programul principal:

• vom folosi o stivă în care vom păstra atâtea doar numere care nu mai pot produce o unificare. Să numim stiva num[];
• vom determina cea mai folosită cifră, prin încărcarea tuturor cifrelor într-un vector de frecvență. Să îl numim c[]. Pe măsură ce vom citi numerele la intrare, vom prelucra cifrele acestuia în vectorul c. Astfel rezolvăm punctul a al problemei;
• vom verifica dacă putem face o unificare. Vom verifica dacă stiva are cel puțin două elemente, și dacă da, vom apela o funcție care verifică dacă ultimele două elemente din stivă se pot unifica. Să numim această funcție unific(). Ea va avea antetul astfel: long long unific (long long a, long long b). Funcția ne va returna una din situațiile:
  • fie cele două numere se pot unifica și rezultă un nou număr, caz în care scoatem ultimele două numere din stivă și adăugăm noul număr; numărul de elemente din stivă scade cu unu.
  • fie cele două numere se pot unifica și dispar, caz în care pur și simplu scoatem ultimele două elemente din stivă; numărul de elemente din stivă scade cu 2.
  • fie cele două numere nu se pot unifica.
• doar în cazul în care ultimele două numere se pot unifica și rezultă un singur număr (primul din cele trei cazuri anterioare) vom continua procedura de unificare, verificând ultimele două numere pe stivă.

Subprogramul unific()

Antetul programului este:

long long unific (long long a, long long b)

Acesta va returna rezultatul unificării a două numere, a și b. Rezultatul poate avea unul dintre următoarele valori:

• numărul rezultat prin unificare;
• -1, dacă dispar ambele numere;
• -2, dacă nu se unifică.

Vom implementa procedura descrisă în cerință. Pentru a simplifica calculele, vom defini 2 vectori de frecvență, unul pentru fiecare număr. În va[10] vom salva cifrele numărului a și în vb[10] vom salva cifrele numărului b. Putem crea o altă funcție, care să calculeze acești vectori sau o putem face aici.

De asemenea, vom avea nevoie să calculăm cea mai mare putere a lui 10, mai mică sau egală cu a, respectiv cu b. Să le notăm pa și pb.

Vom parcurge cei doi vectori de frecvență, va și vb și vom vedea dacă găsim cel puțin o cifră comună. Dacă da, atunci trebuie să creăm noul număr. Pentru că există posibilitatea ca după unificare, ambele numere să nu mai aibă nici o cifră, vom crea noul a și noul b. Apoi vom verifica dacă oricare dintre cele două numere noi sunt diferite de 0. Dacă sunt diferite de 0, va trebui să construim numărul din nou.

Pentru a calcula noul a sau noul b, vom crea altă funcție, să o numim nrnou().

Subprogramul nrnou()

Antetul programului este:

long long nrnou (long long a, long long p10, int v[], int *nrcf)

Acesta va returna noul număr și numărul lui de cifre în parametrul de ieșire *nrcf. Explicația parametrilor este următoarea:

• a: numărul din care se elimină cifrele;
• pa: puterea cea mai mare a lui 10 care încape în a, inițial;
• v[]: vectorul de frecvență al cifrelor rămase în noul număr. La apelare va fi de fapt vectorul va[] sau vb[], pe care îl vom folosi pentru calcule;
• nrcf: numărul de cifre al noului număr (se calculeaza și returnează).

Modul de calcul ar trebui să fie deja evident. Câtă vreme sunt cifre în numărul a, vom calcula prima cifră cu ajutorul puterii pa și vom elimina prima cifră din a. Dacă cifra există în vectorul de frecvență o adăugăm la numărul nou construit. Vom actualiza numărul de cifre pentru noul număr.

Atenție, tot aici trebuie să ajustăm noul număr când singurele cifre rămase sunt 0.

Problema MaxArea

Problema MaxArea a fost dată la concursul Shumen pentru juniori în 2015.

Rezolvarea folosește o stivă, similar cu problemele Tower sau MaxP. Vom memora o stivă de dreptunghiuri de înălțimi din ce în ce mai mari. Când adăugăm o înălțime h vom închide toate dreptunghiurile de înălțimi mai mari de pe stivă. Apoi depunem pe stivă dreptunghiul curent.

Avem două cazuri, dacă dreptunghiul curent este de înălțime strict mai mare vom crea un nou dreptunghi pe stivă de lățime 1 + lățimea însumată a dreptunghiurilor eliminate. Altfel, în caz de egalitate, vom mări lățimea dreptunghiului din vârful stivei cu același număr, 1 + lătimea însumată a dreptunghiurilor eliminate.

De remarcat că problema cere citirea a un milion de întregi de 5 cifre. Incluzând separatorul, spațiu, aceasta înseamnă circa 6MB. Soluția fiind O(n), la fel ca și citirea, este clar că ea va fi dominată ca timp de citire. De aceea este important să nu citim cu fscanf(), ci cu fgetc() (parsing în limbajul olimpicilor).

Observație: spre finalul numerelor pe stivă se vor afla foarte multe înălțimi egale. O optimizare ar fi, deci, să grupăm acele înălțimi. În loc de o înălțime putem stoca o pereche (h, ap) unde ap ne spune numărul de apariții ale acelei înălțimi. Când adăugăm o înălțime egală la stivă vom aduna de fapt 1 la ap. Astfel mărimea stivei rămâne mică.

Problema Skyline

Problema Skyline este o problemă clasică. Cere să se găsească dreptunghiul de arie maximă într-un skyline, unde un skyline este linia lăsată de zgârie-nori. Cu alte cuvinte o secvență de dreptunghiuri aliniate cu axa Ox.

Rezolvarea folosește o stivă, similar cu problemele Tower sau MaxP. Vom memora o stivă de dreptunghiuri de înălțimi din ce în ce mai mari. Când adăugăm un dreptunghi de înălțime h vom închide toate dreptunghiurile de înălțime mai mare de pe stivă, având grijă să le înlocuim cu un dreptunghi egal cu suma lungimilor lor și de înălțime egală cu h.

Complexitatea este O(n) prin analiză amortizată și O(n) memorie.

Temă 13

Să se rezolve următoarele probleme (program C trimis la NerdArena):

• Unific dată la OJI 2013 clasa a 7-a
• MaxArea dată la Shumen Juniori 2015
• Skyline problemă clasică de analiză amortizată

Tema opțională

Să se rezolve următoarele probleme (program C trimis la NerdArena):

• Dreptunghi1 problemă clasică de analiză amortizată

Accesează rezolvarea temei 13