Metoda Divide et Impera – Problema Turnurilor din Hanoi

Prezentare generala:
Divide et Impera se bazează pe principiul descompunerii problemei în două sau mai multe subprobleme (mai ușoare), care se rezolvă, iar soluția pentru problema inițială se obține combinând soluțiile subproblemelor. De multe ori, subproblemele sunt de același tip și pentru fiecare din ele se poate aplica aceeași tactică a descompunerii în (alte) subprobleme, până când (în urma descompunerilor repetate) se ajunge la probleme care admit rezolvare imediată.

Nu toate problemele pot fi rezolvate prin utilizarea acestei tehnici. Se poate afirma că numărul celor rezolvabile prin “divide et impera” este relativ mic, tocmai datorită cerinței ca problema să admită o descompunere repetată.

Divide et impera este o tehnică ce admite o implementare recursivă. Principiul general prin care se elaborează algoritmi recursivi este: “ce se întâmplă la un nivel, se întâmplă la orice nivel” (având grijă să asigurăm condițiile de terminare). Așadar, un algoritm prin divide et impera se elaborează astfel: la un anumit nivel avem două posibilități:

1. s-a ajuns la o problemă care admite o rezolvare imediată (condiția de terminare), caz în care se rezolvă și se revine din apel;
2. nu s-a ajuns în situația de la punctul 1, caz în care problema curentă este descompusă în (două sau mai multe) subprobleme, pentru fiecare din ele urmează un apel recursiv al funcției, după care combinarea rezultatelor are loc fie pentru fiecare subproblemă, fie la final, înaintea revenirii din apel.

Legenda acestei probleme spune că Brahma a fixat pe Pământ trei tije de diamante şi pe una din ele a pus în ordine crescătoare 64 de discuri de aur de dimensiuni diferite, cu discul cel mai mare jos. Singura operaţiune permisă călugărilor era mutarea a câte unui singur disc de pe o tijă pe alta, astfel încât niciodată să nu se pună un disc mai mare peste unul mai mic. Legenda spune că atunci când călugării vor muta toate cele 64 de discuri respectând regulile de maa sus, atunci va veni sfârşitul lumii. Presupunând că în fiecare secundă se mută un disc, lucrând fără întrerupere, cele 64 de discuri nu pot fi mutate nici în 500 de miliarde de ani de la începutul acţiunii!

Vom considera trei tije verticale notate Stânga, Mijloc, Dreapta. Pe tija Stânga se găsesc aşezate n discuri de diametre diferite, în ordinea descrescătoare a diametrelor, privind de jos în sus. Iniţial, tijele Mijloc şi Dreapta sunt goale. Să se afişeze toate mutările prin care discurile de pe tija Stânga se mută pe tija Mijloc, în aceeaşi ordine, respectând următoarele reguli:
• la fiecare mişcare se mută un singur disc
• un disc mai mare nu poate fi plasat peste un disc cu diametrul mai mic
• un disc mai mare nu poate fi plasat peste un disc cu diametrul mai mic


#include "stdio.h"
#include "conio.h"
void scrie(char a, char b)
{
  printf("Muta discul de pe %c pe %c\n",a,b);
}

void muta(int n, char a, char b, char c)
{
  if(n == 1)
  {
    scrie(a,b);
    return 1;
  }
  else
  {
    muta(n-1,a,c,b);
    scrie(a,b);
    muta(n-1,c,b,a);
  }
}

void main(void)
{
  printf("Introdu numarul de turnuri: ");
  scanf("%d", &n);
  muta(n,"S","M","D");
  getch();
}

Leave a Reply

Your email address will not be published. Required fields are marked *

20 − 3 =

Time limit is exhausted. Please reload CAPTCHA.