Non-Recursive Hanoi

Standard

A lot of people can think about how to do the Non-recursive Hanoi algorithm.

There is a Binary Solution(Binary Solution), and a version of a non-recursive on Wikipedia in others sites.

My algorithm was based on:

Hanoi Non-Recursive Solution (Wikipedia)

Moves Hanoi

The Algorithm:

Input: Number of disks(n = number of disks)
Output: Movements of Hanoi Tower

for ( i <- 1,...,2^n -1 )


if( n == even number)


if( i == odd number )
moveright();

else
movenormal();

else

if( i == oddnumber)
moveleft();

else
movenormal();

About the functions:

moveright();

This function moves the smaller disk in right direction.

moveleft();

This function moves the smaller disk in left direction.

movenormal();

This function moves the non-smaller disk in a movement that not involves the smaller disk.

The functions moveright() and moveleft() can be proved by induction.

Advertisements