Turnurile din Hanoi

Divide et Impera

"Divide și Stăpânește" - o tehnică fundamentală în proiectarea algoritmilor.

Conceptul General

Metoda Divide et Impera (D&I) este o tehnică de rezolvare a problemelor care constă în descompunerea unei probleme complexe în subprobleme mai simple, de același tip.

Aceste subprobleme sunt rezolvate independent (adesea recursiv), iar soluțiile lor sunt apoi combinate pentru a obține soluția problemei originale.

Cei 3 pași esențiali:

  1. Divide: Împarte problema în subprobleme mai mici.
  2. Stăpânește: Rezolvă subproblemele recursiv. Dacă sunt suficient de mici, rezolvă-le direct (cazul de bază).
  3. Combină: Unește soluțiile subproblemelor pentru a forma soluția finală.
Problema Mare
Subproblema 1
Subproblema 2
Aplicarea D&I la Turnurile din Hanoi

Pentru a muta n discuri de pe tija A (Sursă) pe tija C (Destinație), folosind tija B (Intermediar), logica este următoarea:

1

Mută n-1 discuri

De pe A pe B, folosind C ca intermediar.

2

Mută discul n

De pe A pe C (discul cel mai mare).

3

Mută n-1 discuri

De pe B pe C, folosind A ca intermediar.