Hanojski stolpi

Hanoiski stolpi je stara matematična igra. Imamo 3 palice na katere premikamo plošče, naloga je da prenesemo plošče iz prve na zadnjo tako, da nikoli ne preložimo večjo ploščo na manjšo ploščo - premikamo lahko samo po 1 ploščo naenkrat.

n : a » b

zadevo rešujemo tako, da poizkušamo nalogo razbiti na manjše podprobleme

najočitnejši podproblem je ta, da želimo premakniti največjega iz 1. na 2. palico - če jo želimo premakniti torej ne sme biti na 1. noben obroček razen največjega ker drugače največjega ne moremo dvigniti in na 2. ne sme biti nobenega, ker drugače nanj ne moremo premakniti največjega - torej želimo vse razen največjega premakniti na zadnjo palico

     |       |       |
     |       |      ###
  #######    |     #####
--------------------------

torej rešujemo problem, kako premakniti n-1 iz a na c ( n-1 : a » c)

ko rešimo ta problem imamo problem enega - premakni iz a -> b (1 : a » b)

potem želimo premakniti vse iz c na b - (n-1 : c » b)

Algoritem

Psevdokoda

static public void hanoi (char A, char B, char C, int n)
{
  if (n>0)  //robni primer
  {
    hanoi(A,C,B,n-1);
    izpis A -> B
    hanoi(C,B,A,n-1);
  }
}

Praktična izvedba v Javi

public class HanoiRek {
  public static void main (String[] args) {
    hanoi(3, 'A', 'B', 'C');
  }
 
  private static void hanoi (int n, char a, char b, char c) {
    if (n==1)
      System.out.println("Prestavi obroc s palice "+a+" na palico "+c);
    else {
      hanoi(n-1, a, c, b);
      hanoi(1, a, b, c);
      hanoi(n-1, b, a, c);
    }
  }
}

Povezave

• Wikipedija (sl)