Towers of Hanoi: Difference between revisions
Content added Content deleted
mNo edit summary |
(revert vandalism) |
||
Line 13: | Line 13: | ||
if Ndisks > 0 then |
if Ndisks > 0 then |
||
Hanoi(Ndisks - 1, Start_Peg, Via_Peg, End_Peg); |
Hanoi(Ndisks - 1, Start_Peg, Via_Peg, End_Peg); |
||
Put_Line("Move disk" |
Put_Line("Move disk" & Natural'Image(Ndisks) & " from " & Pegs'Image(Start_Peg) & " to " & |
||
Pegs'Image(End_Peg)); |
|||
Hanoi(Ndisks - 1, Via_Peg, End_Peg, Start_Peg); |
|||
end if; |
|||
end Hanoi; |
|||
begin |
|||
Hanoi(4); |
|||
end Towers; |
|||
==[[AppleScript]]== |
|||
[[Category:AppleScript]] |
|||
global moves --this is so the handler 'hanoi' can see the 'moves' variable |
|||
set moves to "" |
|||
hanoi(4, "peg A", "peg C", "peg B") |
|||
on hanoi(ndisks, fromPeg, toPeg, withPeg) |
|||
if ndisks is greater than 0 then |
|||
hanoi(ndisks - 1, fromPeg, withPeg, toPeg) |
|||
set moves to moves & "Move disk " & ndisks & " from " & fromPeg & " to " & toPeg & return |
|||
hanoi(ndisks - 1, withPeg, toPeg, fromPeg) |
|||
end if |
|||
return moves |
|||
end hanoi |
|||
==[[C plus plus|C++]]== |
|||
[[Category:C plus plus]] |
|||
'''Compiler:''' [[GCC]] |
|||
void move(int n, int from, int to, int via) { |
|||
if (n == 1) { |
|||
std::cout << "Move disk from pole " << from << " to pole " << to << std::endl; |
|||
} else { |
|||
move(n - 1, from, via, to); |
|||
move(1, from, to, via); |
|||
move(n - 1, via, to, from); |
|||
} |
|||
} |
|||
==[[E]]== |
|||
[[Category:E]] |
|||
def move(out, n, fromPeg, toPeg, viaPeg) { |
|||
if (n.aboveZero()) { |
|||
move(out, n.previous(), fromPeg, viaPeg, toPeg) |
|||
out.println(`Move disk $n from $fromPeg to $toPeg.`) |
|||
move(out, n.previous(), viaPeg, toPeg, fromPeg) |
|||
} |
|||
} |
|||
move(stdout, 4, def left {}, def right {}, def middle {}) |
|||
==[[Forth]]== |
|||
[[Category:Forth]] |
|||
With locals: |
|||
CREATE peg1 ," left " |
|||
CREATE peg2 ," middle " |
|||
CREATE peg3 ," right " |
|||
: .$ COUNT TYPE ; |
|||
: MOVE-DISK |
|||
LOCALS| via to from n | |
|||
n 1 = |
|||
IF CR ." Move disk from " from .$ ." to " to .$ |
|||
ELSE n 1- from via to RECURSE |
|||
1 from to via RECURSE |
|||
n 1- via to from RECURSE |
|||
THEN ; |
|||
Without locals, executable pegs: |
|||
: left ." left" ; |
|||
: right ." right" ; |
|||
: middle ." middle" ; |
|||
: print ( t f -- ) |
|||
CR ." Move disk from " execute ." to " execute ; |
|||
: move-disk ( v t f n -- v t f ) |
|||
dup 1 = if drop 2dup print exit then |
|||
1- >R |
|||
rot swap R@ ( t v f n-1 ) recurse |
|||
rot swap 2dup print |
|||
swap rot R> ( f t v n-1 ) recurse |
|||
swap rot ; |
|||
: hanoi ( n -- ) |
|||
1 max >R ['] right ['] middle ['] left R> move-disk drop drop drop ; |
|||
==[[Java]]== |
|||
[[Category:Java]] |
|||
public void move(int n, int from, int to, int via) { |
|||
if (n == 1) { |
|||
System.out.println("Move disk from pole " + from + " to pole " + to); |
|||
} else { |
|||
move(n - 1, from, via, to); |
|||
move(1, from, to, via); |
|||
move(n - 1, via, to, from); |
|||
} |
|||
} |
|||
==[[Perl]]== |
|||
[[Category:Perl]] |
|||
sub move { |
|||
my $n = shift; |
|||
my $from = shift; |
|||
my $to = shift; |
|||
my $via = shift; |
|||
if ($n == 1) { |
|||
print "Move disk from pole $from to pole $to.\n"; |
|||
} else { |
|||
move($n - 1, $from, $via, $to); |
|||
move(1, $from, $to, $via); |
|||
move($n - 1, $via, $to, $from); |
|||
}; |
|||
}; |
|||
==[[Pop11]]== |
|||
[[Category:Pop11]] |
|||
define hanoi(n, src, dst, via); |
|||
if n > 0 then |
|||
hanoi(n - 1, src, via, dst); |
|||
printf('Move disk ' >< n >< ' from ' >< src >< ' to ' >< dst >< '.\n'); |
|||
hanoi(n - 1, via, dst, src); |
|||
endif; |
|||
enddefine; |
|||
hanoi(4, "left", "middle", "right"); |
|||
==[[Python]]== |
|||
[[Category:Python]] |
|||
<pre> |
|||
def hanoi(ndisks, startPeg=1, endPeg=3): |
|||
if ndisks: |
|||
hanoi(ndisks-1, startPeg, 6-startPeg-endPeg) |
|||
print "Move disk %d from peg %d to peg %d" % (ndisks, startPeg, endPeg) |
|||
hanoi(ndisks-1, 6-startPeg-endPeg, endPeg) |
|||
hanoi(ndisks=4) |
|||
</pre> |
|||
==[[Seed7]]== |
|||
[[Category:Seed7]] |
|||
const proc: hanoi (in integer: disk, in string: source, in string: dest, in string: via) is func |
|||
begin |
|||
if disk > 0 then |
|||
hanoi(pred(disk), source, via, dest); |
|||
writeln("Move disk " <& disk <& " from " <& source <& " to " <& dest); |
|||
hanoi(pred(disk), via, dest, source); |
|||
end if; |
|||
end func; |
|||
==[[Toka]]== |
|||
[[Category:Toka]] |
|||
value| sa sb sc n | |
|||
[ to sc to sb to sa to n ] is vars! |
|||
[ ( num from to via -- ) |
|||
vars! |
|||
n 0 <> |
|||
[ |
|||
n sa sb sc |
|||
n 1- sa sc sb recurse |
|||
vars! |
|||
." Move a ring from " sa . ." to " sb . cr |
|||
n 1- sc sb sa recurse |
|||
] ifTrue |
|||
] is hanoi |
Revision as of 09:48, 9 June 2007
Towers of Hanoi
You are encouraged to solve this task according to the task description, using any language you may know.
You are encouraged to solve this task according to the task description, using any language you may know.
In this task, the goal is to solve the Towers of Hanoi problem with recursivity.
Ada
with Ada.Text_Io; use Ada.Text_Io; procedure Towers is type Pegs is (Left, Center, Right); procedure Hanoi (Ndisks : Natural; Start_Peg : Pegs := Left; Via_Peg : Pegs := Center; End_Peg : Pegs := Right) is begin if Ndisks > 0 then Hanoi(Ndisks - 1, Start_Peg, Via_Peg, End_Peg); Put_Line("Move disk" & Natural'Image(Ndisks) & " from " & Pegs'Image(Start_Peg) & " to " & Pegs'Image(End_Peg)); Hanoi(Ndisks - 1, Via_Peg, End_Peg, Start_Peg); end if; end Hanoi; begin Hanoi(4); end Towers;
AppleScript
global moves --this is so the handler 'hanoi' can see the 'moves' variable set moves to "" hanoi(4, "peg A", "peg C", "peg B") on hanoi(ndisks, fromPeg, toPeg, withPeg) if ndisks is greater than 0 then hanoi(ndisks - 1, fromPeg, withPeg, toPeg) set moves to moves & "Move disk " & ndisks & " from " & fromPeg & " to " & toPeg & return hanoi(ndisks - 1, withPeg, toPeg, fromPeg) end if return moves end hanoi
C++
Compiler: GCC
void move(int n, int from, int to, int via) { if (n == 1) { std::cout << "Move disk from pole " << from << " to pole " << to << std::endl; } else { move(n - 1, from, via, to); move(1, from, to, via); move(n - 1, via, to, from); } }
E
def move(out, n, fromPeg, toPeg, viaPeg) { if (n.aboveZero()) { move(out, n.previous(), fromPeg, viaPeg, toPeg) out.println(`Move disk $n from $fromPeg to $toPeg.`) move(out, n.previous(), viaPeg, toPeg, fromPeg) } } move(stdout, 4, def left {}, def right {}, def middle {})
Forth
With locals:
CREATE peg1 ," left " CREATE peg2 ," middle " CREATE peg3 ," right " : .$ COUNT TYPE ; : MOVE-DISK LOCALS| via to from n | n 1 = IF CR ." Move disk from " from .$ ." to " to .$ ELSE n 1- from via to RECURSE 1 from to via RECURSE n 1- via to from RECURSE THEN ;
Without locals, executable pegs:
: left ." left" ; : right ." right" ; : middle ." middle" ; : print ( t f -- ) CR ." Move disk from " execute ." to " execute ; : move-disk ( v t f n -- v t f ) dup 1 = if drop 2dup print exit then 1- >R rot swap R@ ( t v f n-1 ) recurse rot swap 2dup print swap rot R> ( f t v n-1 ) recurse swap rot ; : hanoi ( n -- ) 1 max >R ['] right ['] middle ['] left R> move-disk drop drop drop ;
Java
public void move(int n, int from, int to, int via) { if (n == 1) { System.out.println("Move disk from pole " + from + " to pole " + to); } else { move(n - 1, from, via, to); move(1, from, to, via); move(n - 1, via, to, from); } }
Perl
sub move { my $n = shift; my $from = shift; my $to = shift; my $via = shift; if ($n == 1) { print "Move disk from pole $from to pole $to.\n"; } else { move($n - 1, $from, $via, $to); move(1, $from, $to, $via); move($n - 1, $via, $to, $from); }; };
Pop11
define hanoi(n, src, dst, via); if n > 0 then hanoi(n - 1, src, via, dst); printf('Move disk ' >< n >< ' from ' >< src >< ' to ' >< dst >< '.\n'); hanoi(n - 1, via, dst, src); endif; enddefine;
hanoi(4, "left", "middle", "right");
Python
def hanoi(ndisks, startPeg=1, endPeg=3): if ndisks: hanoi(ndisks-1, startPeg, 6-startPeg-endPeg) print "Move disk %d from peg %d to peg %d" % (ndisks, startPeg, endPeg) hanoi(ndisks-1, 6-startPeg-endPeg, endPeg) hanoi(ndisks=4)
Seed7
const proc: hanoi (in integer: disk, in string: source, in string: dest, in string: via) is func begin if disk > 0 then hanoi(pred(disk), source, via, dest); writeln("Move disk " <& disk <& " from " <& source <& " to " <& dest); hanoi(pred(disk), via, dest, source); end if; end func;
Toka
value| sa sb sc n | [ to sc to sb to sa to n ] is vars! [ ( num from to via -- ) vars! n 0 <> [ n sa sb sc n 1- sa sc sb recurse vars! ." Move a ring from " sa . ." to " sb . cr n 1- sc sb sa recurse ] ifTrue ] is hanoi