Towers of Hanoi: Difference between revisions
Content deleted Content added
→[[C plus plus|C++]]: Point to C++ instead of C plus plus |
m →[[Java]]: Use Java header instead |
||
Line 144:
hanoiM' (n-1) c b a
==
public void move(int n, int from, int to, int via) {
|
Revision as of 23:42, 9 November 2007
Towers of Hanoi is a programming puzzle. It lays out a problem which Rosetta Code users are encouraged to solve, using languages and techniques they know. Multiple approaches are not discouraged, so long as the puzzle guidelines are followed. For other Puzzles, see Category:Puzzles.
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
#include <stdio.h> void move(int n, int from, int to, int via) { if (n > 0) { move(n - 1, from, via, to); printf("Move disk from pole %d to pole %d\n", from, to); move(n - 1, via, to, from); } } int main() { move(4, 1,2,3); return 0; }
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" ; : move-disk ( v t f n -- v t f ) dup 0= if drop exit then 1- >R rot swap R@ ( t v f n-1 ) recurse rot swap 2dup cr ." Move disk from " execute ." to " execute 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 ;
Haskell
Most of the programs on this page use an imperative approach (i.e., print out movements as side effects during program execution). Haskell favors a purely functional approach, where you would for example return a (lazy) list of movements from a to b via c:
hanoi :: Integer -> a -> a -> a -> [(a, a)] hanoi = hanoi' [] where hanoi' k 0 _ _ _ = k hanoi' k n a b c = hanoi' ((a,b):(hanoi' k (n-1) c b a)) (n-1) a c b
Here hanoi' uses an accumulator argument for the "following" moves.
One can use this function to produce output, just like the other programs:
hanoiIO n a b c = foldl (>>) (return ()) $ map f $ hanoi n a b c where f (x,y) = putStrLn $ "Move " ++ show x ++ " to " ++ show y
Or, instead one can of course also program imperatively, using the IO monad directly:
hanoiM :: Integer -> IO () hanoiM n = hanoiM' n 1 2 3 where hanoiM' 0 a b c = return () hanoiM' n a b c = do hanoiM' (n-1) a c b putStrLn $ "Move " ++ show a ++ " to " ++ show b hanoiM' (n-1) c b a
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)
Ruby
def hanoi n,a='left',b='middle',c='right' return if n==0 hanoi (n-1),a,c,b puts "Move from #{a} to #{b}" hanoi (n-1),c,b,a end
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