برج هانوی
حل مسئله برج هانوی به روش غیربازگشتی

این مسئله علاوه بر روش تابع بازگشتی راه حلهای غیربازگشتی نیز دارد. در بالا به این نتیجه رسیدیم که بهترین راه حل برای جابجا کردن n دیسک ۲n - ۱ حرکت نیاز دارد. در نتیجه مرتبه راه حلهای آن در بهینه‌ترین حالت، چه بازگشتی و چه غیربازگشتی، از مرتبه (O(2n خواهد بود. اما آنچه که راه حل بازگشتی و غیربازگشتی را از هم متمایز می‌کند مرتبه فضای مصرفی آن است. حل بازگشتی مسئله، فراخوانی‌های تو در تو و فضای پشته از مرتبه (O(n نیاز دارد. در حالی که می‌توان با استفاده از روش غیربازگشتی این مرتبه را به (O(1 کاهش داد. البته این مسئله تنها دلیل بررسی روش غیربازگشتی نیست. تبدیل مرتبه مصرف فضا از (O(n به (O(1 زمانی که مرتبه اجرایی الگوریتم (O(2n است چندان قابل توجه نیست. دلیل دیگر می‌تواند این باشد که برخی زبانهای برنامه‌نویسی از فراخوانی بازگشتی توابع پشتیبانی نمی‌کنند و مجبور به استفاده ار روش‌های غیربازگشتی هستند. اما دلیل اصلی این است که با بررسی این روش‌ها تمرین کوچکی برای تبدیل الگوریتمهای بازگشتی به غیربازگشتی انجام می‌دهیم.
تا کنون چندین روش مختلف جهت پیاده‌سازی غیربازگشتی حل مسئله برج هانوی ارائه شده‌است، که ما در اینجا دو روش را معرفی کرده، و تنها یکی از آن‌ها را به‌طور کامل بررسی می‌کنیم. توجه داشته باشید که همه جزئیات حل مسئله به صورت دقیق و مشروح مطرح نمی‌شود، و استدلال قسمتی از نتیجه‌گیری‌ها به عنوان تمرین به شما واگذار می‌شود.
روش اول:
حل مسئله برج هانوی را می‌توان معادل پاسخ دادن به این سؤال دانست که: در هر مرحله کدام دیسک به کدام میله منتقل می‌شود؟
کدام دیسک؟
استدلال ۲ می‌گوید که اولین حرکت همیشه با دیسک ۱ است. استدلال ۳ می‌گوید حرکت بعدی با دیسکی غیر از دیسک ۱ است. استدلال ۴ می‌گوید این دیسک نمی‌تواند بزرگترین دیسک موجود در بالای میله‌ها باشد. پس در مرحله بعدی دیسک y جابجا خواهد شد؛ و بالاخره حرکت بعدی باز هم با دیسک ۱ است (چرا؟).
پس با بررسی منطقی خود به این نتیجه رسیدیم که دیسک ۱ و دیسکی که بزرگترین دیسک در آن مرحله نیست، به صورت متناوب جابجا می‌شوند. مراحل با شماره فرد برای دیسک ۱، و مراحل با شماره زوج برای دیسک y.
کدام میله؟
فرض کنیم دیسک ۱ روی میله A قرار داشته باشد و آن را به میله C منتقل کنیم. در مرحله بعدی دیسک y جابجا می‌شود؛ و در مرحله بعد باز هم دیسک ۱ باید جابجا شود. حال اگر این دیسک را به میله A بازگردانیم، به نوعی کار اضافی و بازگشت به عقب انجام داده‌ایم. برای آشکار شدن این موضوع کافی است مسئله برج هانوی را با دو دیسک حل کنید، و در حرکت دوم دیسک ۱، آن را به میله‌ای بازگردانید که از آن آمده بود. پس می‌توان گفت در حرکتهای متوالی، دیسک شماره ۱ به میله‌ای حرکت می‌کند که از آن به میله فعلی خود نیامده است. این مسئله نه تنها در مورد دیسک ۱، که در مورد همه دیسکها صادق است؛ یعنی همه دیسکها در حرکتهای خود به سمت میله‌ای می‌روند که در حرکت قبلی خود از آن نیامده‌اند. اما لحاظ کردن این شرط برای این دیسکها لازم نیست. چرا که در هر مرحله، تنها یک انتخاب برای حرکت خود دارند.
تنها مسئله باقی‌مانده، میله مقصد دیسک ۱ در اولین حرکت خود است. زمانی که این دیسک اولین حرکت خود را انجام می‌دهد، نمی‌توان از استدلال فوق برای تشخیص میله مقصد استفاده کرد (چرا!؟). استدلال این قسمت را هم که چندان دشوار نیست به شما وا می‌گذاریم و تنها به بیان نتیجه می‌پردازیم: اگر n (تعداد دیسکها) زوج باشد، دیسک ۱ در اولین حرکت به میله کمکی (یعنی میله B)، و در غیراینصورت به میله مقصد (یعنی میله C) منتقل می‌کنیم.
به این ترتیب حل مسئله برج هانوی به صورت غیربازگشتی به صورت کامل پیاده‌سازی می‌شود. حال می‌دانیم که در هر مرحله کدام دیسک به کدام میله منتقل می‌شود. تعداد مراحل هم همواره برابر ۲n - ۱ است. پیاده‌سازی کد این الگوریتم را نیز به شما وا می‌گذاریم تا با کار روی آن به خوبی بر الگوریتم تشریح شده مسلط شوید.
روش دوم:
void hanoi (int nDisk, char start, char temp, char finish)
{
  int max = nDisk;
  char dest = finish;
  int disk = max;
  while(true)
  {
  while(disk> 0)
  {
  if(moving disk succeeds)
  {
  if(disk == max)
  {
  max--;
  if(max == 0)
  {
  return;
  }
  }
  dest = the final place of max;
  }
  else
  {
  dest = the alternative place between dest and the current place of disk;
  }
  disk--;
  }
  p and q = the places different of dest;
  disk = the smaller of the disks on top of p and q;
  dest = the place between p and q with greater disk on top;
  }
}
در پایان توجه داشته باشید که دو روش ذکر شده، تنها روش‌های پیاده‌سازی غیربازگشتی حل مسئله نیستند.
برنامه برج هانوی به زبان c:
# include <stdlib.h>
# include <conio.h>
# define COUNT 8

enum Bar{L,C,R};
struct disk{int Size,Color;};
struct stack{int i; disk *Disks;};
void transfer(int,Bar,Bar,Bar);
void init(); // Init bars
void MoveDisk(Bar from,Bar to);
void DrawBars();
stack Bars[3]={ {0,{0}} ,{0,{0}}, {0,{0}} };
int main(void)
{
 textmode(C4350);
 clrscr();
 init();
 DrawBars();
 transfer(COUNT,L,R,C);
 getch();
 return 0;
}
char ConvertBarEnum2Char(Bar E){
 char r=0;
 switch (E) {
 case L: r='L'; break;
 case C: r='C'; break;
 case R: r='R'; break;
 }
 return r;
}

void msg(Bar from,Bar to){
 gotoxy(25,4);
 textattr(15|16*0);
 cprintf("Press anykey to move from %c to %c",ConvertBarEnum2Char(from),ConvertBarEnum2Char(to));
 gotoxy(37,5);
 cprintf("Esc = Exit");
}

void transfer(int n,Bar from,Bar to,Bar temp){
if(n>0){
 transfer(n-1,from,temp,to);
 msg(from, to);
 MoveDisk(from,to);
 transfer(n-1,temp,to,from);
 }
}
void init(){
Bars[L].Disks=new disk[COUNT];
for(int i=0;i<COUNT;i++){
Bars[L].Disks[i].Size=COUNT-i+1;
Bars[L].Disks[COUNT-i-1].Color=i+1;
}
Bars[L].i=COUNT-1;

Bars[R].Disks=new disk[COUNT];
for(i=0;i<COUNT;i++){
Bars[R].Disks[i].Size=0;
Bars[R].Disks[i].Color=0;
}
Bars[R].i=-1;

Bars[C].Disks=new disk[COUNT];
for(i=0;i<COUNT;i++){
Bars[C].Disks[i].Size=0;
Bars[C].Disks[i].Color=0;
}
Bars[C].i=-1;
}

void MoveDisk(Bar from,Bar to){
char kb=getch();
if(kb==27) exit(1);
Bars[to].Disks[++(Bars[to].i)]= Bars[from].Disks[(Bars[from].i)--];
clrscr();
DrawBars();
}
void me(){
char c;
for(int i=0;str[i];i++){
c=i%14+1;
if(c==1)c=2;
textattr(c|16);
cprintf("%c",str[i]);
}
}

void DrawBars(){
int n=0;
for(int j=0;j<3;j++){
for(int i=0;i<=Bars[j].i;i++){
gotoxy(1+j*27,24-i);
textattr(Bars[j].Disks[i].Color|16*0);
for(n=0;n<28 && n-13<Bars[j].Disks[i].Size ;n++){
if(n<14-Bars[j].Disks[i].Size)
cprintf("%s"," ");
else
cprintf("%s","ـ");
}
}
textattr(15|16*0);
for(n=0;n<15;n++){
gotoxy(1+j*27+13,n+10);
cprintf("%s",";");
}
}
gotoxy(5,28);
me();
}
نمونه‌ای از برج هانوی
حل مسئله برج هانوی با ۴ دیسک
حل مسئله برج هانوی با ۳ دیسک
ترتیب فراخوانی‌ها برای اجرا شدن دستور
درختی که ترتیب اجرای دستورها را نشان می‌دهد