Hanojski stolpiči

 

Rešujemo naslednji problem: dani so trije stebri, a, b in c. Na stebru a je n obročev. Vsi obroči so različne velikosti. Problem je poiskati zaporedje operacij, s katerimi prenesemo vse obroče na steber c. Prenašati smemo samo po en obroč naenkrat. Steber b lahko uporabljamo kot pomožno vmesno odlagališče.  Dodatna omejitev je, da morajo biti vedno obroči na vsakem stebru urejeni po velikosti. To pomeni, da se ne sme pojaviti večji obroč na manjšem.

Rešitev za prenos treh obročev:

1. prenesi najmanjši obroč iz a na c
2. prenesi srednji obroč iz a na b
3. prenesi najmanjši obroč iz c na b
4. prenesi največji obroč z a na c
5. prenesi najmanjši obroč z b na a
6. prenesi srednji obroč z b na c
7. prenesi najmanjši obroč z a na c

Splošna rešitev:

V splošnem lahko rešitev problema za n obročev sestavimo iz treh faz:

 

1. faza: Premesti zgornjih (n-1) obročev s stebra a na steber b; pri tem lahko uporabljaš steber c kot pomožno odlagališče.
2. faza: Prenesi preostali obroč z a na c
3. faza:  Premesti (n-1) obročev z b na c; pri tem lahko uporabljaš steber a kot pomožno odlagališče.

 

Program in rekurzivna funkcija

#include <iostream>
using namespace std;

void hanoi (int  n, char zacetni, char odlagalisce, char koncni)
{

  if (n > 0)
  {
    hanoi(n-1,zacetni,koncni,odlagalisce);

    cout << "Prenesi obroc iz stebra " <<zacetni << " na steber " << koncni << endl;

    hanoi(n-1,odlagalisce, zacetni, koncni);
   }

}


void main()
{
  int N;

  cout << "Vpisi stevilo stolpičev? ";

  cin >> N;

  hanoi(N,'A','B','C');

  system("pause");
}

ANIMACIJA REŠITVE