Xtends’ Weblog

Ik zal hier het probleem van de torens van Hanoi beschouwen voor een willekeurig aantal schijven n, niet noodzakelijk gelijk aan 64. Voor kleine waarden van n kunnen we de oplossing van het probleem als volgt definiëren:Als n=1, verplaatsen we gewoon de enige schijf van de eerste naar de derde paal. Als n=2, verplaatsen we eerste de bovenste schijf van de eerste naar de tweede paal, dan de onderste schijf van de eerste naar de derde paal, en tenslotte de bovenste schijf van de tweede naar de derde paal.Het is niet zonder meer duidelijk hoe deze oplossingen voor kleine waarden van n moeten veralgemeend worden naar oplossingen voor grotere waarden van n (uiteindelijk 64). We veronderstellen dat we al weten hoe we het probleem van de torens van Hanoi met n-1 schijven moeten oplossen. Die veronderstelling maakt echter het algoritme voor het probleem met n schijven plots glashelder:

1. Verplaats eerst op correcte wijze de bovenste n-1 schijven van de eerste naar de tweede paal, waarbij nu de derde paal als hulppaal wordt gebruikt.

2. Verplaats de onderste schijf van de eerste naar de derde paal.

3. Verplaats op correcte wijze de bovenste n-1 schijven van de tweede naar de derde paal, waarbij de eerste paal nu als hulppaal wordt gebruikt.

Nu, hoeveel verplaatsingen van individuele schijven vergt dit algoritme nu in functie van het aantal schijven? Laat ons dit aantal a(n) noemen. Uit a(n)=2a(n-1)+1 en a(1)=1 volgt dat a(n)=2^n-1.

Voor de oorspronkelijke probleemstelling (n=64) moet er dus 2^64 – 1 keer een schijf verplaatst worden.

Natuurlijk, de 21e eeuw zou de 21e eeuw niet zijn als we hiervoor geen snellere oplossing voor vonden. Onderstaand Java-programma lost hetzelfde probleem op:

import tio.*;
class Hanoi {
  static int n,niveau,aanroepen;
  static int[] toestand;
 
  static int derdepaal(int vanpaal, int naarpaal) {
    return(3-vanpaal-naarpaal);
  }
  static void verplaats(int n, int vanpaal, int naarpaal) {
    int hulppaal;
    niveau++;
    aanroepen++;
    if(n>1) {
      hulppaal=derdepaal(vanpaal,naarpaal);
      verplaats(n-1,vanpaal,hulppaal);
      verplaats(1,vanpaal,naarpaal);
      verplaats(n-1,hulppaal,naarpaal);
    }
    else {
      System.out.print(toestand[0] + ” ” + toestand[1] + ” ” + toestand[2] + “      “);
      toestand[vanpaal]=toestand[vanpaal]-1;
      toestand[naarpaal]=toestand[naarpaal]+1;
      System.out.print(vanpaal + ” -> ” + naarpaal + “            “);
      System.out.print(toestand[0] + ” ” + toestand[1] + ” ” + toestand[2] + “      “);
      System.out.println(niveau);
    }
    niveau–;
  }
  static void main(String[] args) {
    System.out.println(“Geef het aantal schijven: “);
    n=Console.in.readInt();
    niveau=0;
    aanroepen=0;
    toestand=new int[3];
    toestand[0]=n;
    toestand[1]=0;
    toestand[2]=0;
    System.out.println(“palen      verplaatsing      palen      niveau      “);
    System.out.println(“—————————————————-”);
    verplaats(n,0,2);
    System.out.println(“”);
    System.out.println(“Aantal aanroepen was ” + aanroepen);
  }
}

Nu, naar uitvoering van de code vond ik makkelijk de oplossingen voor kleinere waarden van n. Toen ik het programma compile met n=64 .. Wel, ik startte het programma een uur geleden en het is nog steeds niet klaar. Wel vond ik een bepaald algoritme achter het aantal verplaatsingen in functie van de waarde n. Stel, a(n) stelt het aantal verplaatsingen voor en n is het aantal schijven: a(n)=(a(n-1)+1)*2. Hieronder het programma dat het aantal verplaatsingen voorstelt:

import tio.*;

class HoeveelAanroepen {
  public static void main(String[] args) {
    int n,i;
    double j;
    System.out.println(“Geef een getal.”);
    n=Console.in.readInt();
   
    System.out.println(“1:\t1″);
    j=2;
    for(i=2;i<=n;i++) {
      System.out.println(i+”:\t”+(j*2));
      j=j*2+1;
    }
  }
}

Hieruit volgt dus het onderstaande lijstje voor n = 64:

1: 1
2: 4
3: 10
4: 22
5: 46
6: 94
7: 190
8: 382
9: 766
10: 1534
11: 3070
…
60: 1.72938225691027046E18
61: 3.4587645138205409E18
62: 6.9175290276410819E18
63: 1.3835058055282164E19
64: 2.7670116110564327E19

In functie van de tijd ondervond ik het volgende (niet zozeer helemaal correct):

Per verplaatsing heeft het programma ~74,5ms nodig. Dus voor n=64 heeft het programma 2.7670116110564327E19 * 74,5 = 2,089093766E21 ms nodig. Dit is gelijk aan 66244728770 jaar = ~66miljard jaar. Toch al iets minder als 600 miljard jaar