Problema saptamanii - Initializare (Solutie)

Cosmin
Cosmin Negruseri
03 septembrie 2010

Problema saptamanii curente a fost rezolvata de 13 cititori. Ea nu e asa dificila ca si problemele anterioare, dar e singura de vara asta care are o aplicatie practica.

Rezolvitori:

Andrei Grigorean, Radu Berinde, Andrei-Marius Teodorescu, Delia David, Andrei Dragus, Adrian Carcu, Ovidiu Gheorghioiu, Adrian Vladu, George Nachman, Laura Draghici, Paul Dan Baltescu, Mihai Feier si Mihai Calancea.

Solutie:
Notam umem sirul de U pozitii cu memoria neinitializata. Cum avem nevoie de operatii in timp constant am putea tine 1 sau 0 pe pozitia v din umem daca elementul v este in set sau nu. Din pacate memoria nu este initializata si astfel pot exista deja 0 si 1 prin sir care sa ne pacaleasca.

Pentru a scapa de problemele generate de memoria neinitializata folosim un al doilea sir, nmem, de lungime N ce il initializam pentru a verifica daca umem spune adevarul. La adaugarea unui nou element v in set, dupa ce au fost deja adaugate max elemente, il adaugam in nmem la final si pe pozitia v din umem punem valoarea max. Astfel putem testa daca un element este intradevar in set folosind conditia nmem[umem[v]] == v. Trucul e ca realizam o legatura bidirectionala care este reala pentru ca noi controlam sirul nmem.

Aveti aici niste cod in Python scris de George Nachman pe aceasta idee:

umem = newarray(U)
nmem = newarray(N)
max = 0

def contains(v):
  if v >= U:
    return False
  i = umem[v]
  if i >= max:
    return False
  return nmem[i] == v

def add(v):
  if contains(v):
    return
  umem[v] = max
  nmem[max] = v
  max += 1
Categorii: potw
remote content