I dette problem har vi tre pinde (1, 2 og 3). På pind 1 er anbragt et antal (n) cirkulære skiver, alle med forskellig diameter, og således at enhver skive altid er mindre end skiven lige under den. Opgaven går nu ud på at flytte skiverne fra pind 1 til pind 3 under overholdelse af følgende regler:
program hanoi;
var
n: integer;
procedure flyt(n, i, j: integer);
{Flytter n skiver fra pind nr. i til pind nr. j}
var
via: integer;
begin
if n=1 then
flyts(i,j) {kan løses direkte}
else begin
via:= 6-i-j; {via-pindens nummer}
flyt(n-1,i,via); {løsning af delproblem
1}
flyts(i,j);
{flytning af nederste skive}
flyt(n-1,via,j); {løsning af delproblem
2}
end;
end; {flyt}
procedure flyts(i, j: integer);
{udskrive flytningen}
var
x: integer;
begin
writeln(i); {frapind}
writeln(j); {tilpind}
readln(x); {pause}
end;
begin
readln(n); {antal skiver}
flyt(n,1,3); {start løsningen}
end.
| S:
Q:
|
lokale variable
... Gammel Q Returadresse ... Parametre |
Som det ses af ovenstående, vil vi bruge Q til at udpege vores activation-record med.
Før en procedure kaldes skal man altså anbringe parametrene
på stakken med kommandoen TILS.
Dernæst kaldes proceduren med HSUB.
Proceduren skal indledes med instruktioner, der giver Q og S de rigtige
værdier.
Selve procedurens instruktioner udføres.
Procedure afsluttes med instruktioner, der reetablerer Q og S.
Der vendes tilbage til kaldsstedet med HRET.
Efter procedurekaldet fjernes parametrene igen fra stakken.
; start:
n = 0
IND n
; flyt(n,1,3)
HENT n
TILS
; 1. par
HENT #1
TILS
; 2. par
HENT #3
TILS
; 3. par
HSUB flyt
STOP
| S: | 3
1 n |
Efter kaldet af flyt er stakken sådan ud:
| S: | Returadresse
3 1 n |
De to første linjer af flyt (se nedenfor) gemmer Q på stakken:
| S: | Gammel Q
Returadresse 3 1 n |
De to næste linjer lader Q pege på vores activation-record
(frame):
| S: Q: | Gammel Q
Returadresse 3 1 n |
Endelig gør de to næste linjer plads til den lokale variabel:
| S:
Q: |
Via (lokal var)
Gammel Q Returadresse 3 1 n |
Placeringen af de enkelte parametre og variable beskrives nu ud fra Q. F. eks. kan n hentes til A med instruktionen: HENT Q+4, og der gemmes i Via med instruktionen GEM Q+255.
HENT Q+4
; hent n
SUB #1
HNUL if1
; if n=1 then
HOP else1
if1:
; flyts(i,j)
HENT Q+3
; hent i
TILS
; 1. par
HENT Q+2
; hent j
TILS
; 2. par
HSUB flyts
FRAS
; afstak parametre
FRAS
HOP end1
else1:
; flyt(n-1,i,6-i-j);
HENT Q+4
; n
SUB #1
; n-1
TILS
; 1. par
HENT Q+3
; i
TILS
; 2. par
HENT #6
SUB Q+3
SUB Q+2
GEM Q+255
; via
TILS
; 3. par
HSUB flyt
FRAS
; afstak parametre
FRAS
FRAS
; flyts(i,j)
HENT Q+3
; hent i
TILS
; 1. par
HENT Q+2
; hent j
TILS
; 2. par
HSUB flyts
FRAS
; afstak parametre
FRAS
; flyt(n-1,6-i-j,j);
HENT Q+4
; n
SUB #1
; n-1
TILS
; 1. par
HENT Q+255 ; via
TILS
; 2. par
HENT Q+2
; j
TILS
; 3. par
HSUB flyt
FRAS
; afstak parametre
FRAS
FRAS
end1: HENTQ
GEMS
; genskab s
FRAS
GEMQ
; genskab gl. q
HRET
| S: Q: | Gammel Q
Returadresse 3 1 n |
Efter de to næste instruktioner har stakken følgende udseende:
| S: | Returadresse
3 1 n |
Og efter HRET ser stakken sådan ud:
| S: | 3
1 n |
Vi mangler blot at afstakke parametrene for at have fjernet alle spor
af procedurekaldet.
flyts:
HENTQ
TILS
; q gemmes
HENTS
GEMQ
; q peger på frame
SUB #1
GEMS
; lokal var (x) på stak
UD Q+3
; udskriv i
UD Q+2
; udskriv j
IND Q+255
; pause
HENTQ
GEMS
; genskab s
FRAS
GEMQ
; genskab gl. q
HRET