برج هانوی غیر بازگشتی

بنام خدا.

روش غیر بازگشتی برای حل مساله برج هانوی اینطور بود که مثلا برای 4دیسک باید ابتدا همه دیسک های روی آن را برمیداشتیم و در ستون کمکی قرار میدادیم .بعد دیسک چعارم را منتقل میکردیم و در آخر دیسک های میله کمکی را به میله مقصد منتقل میکردیم.

در روش غیربازگشتی(اینجا)برای حل مساله برای هرتعداد دیسک ، باید ابتدا مساله را برای دیسک های کمتر حل کرده باشیم... 

دانلود برنامه برج هانوی ترتیبی

در این روش ابتدا مساله برای یک دیسک انجام میشود.سپس در حرکت دوم ، دو حرکت به حرکت قبلی اظافه میشود.یکی قبل و یکی بعد.این نشان میدهد که حرکتی که در حل مساله برا یک دیسک انجام داده بودیم،در مرحله دوم بعنوان حرکت اصلی فرض شده است.همچنین در حرکات بعدی هم به بعد و قبل حرکت های شماره فرد، دوخانه اظافه میکنیم بطوریکه حرکت خانه فرد یک حرکت کمکی برای دو خانه دیگر فرض شود. 

 برای درک بیشتر مساله حل شده را برای 4 خانه نشان میدهم: 

honoi for n disks, move from 1 to 3:

1 disks:                     1,3
2 disks:        1,2    =   1,3    =    3,2
 3 disks:1,3= 1,2=3,2=1,3= 3,1= 3,2=1,2 

با توجه به این حرکت ها، میتوان مساله هانوی را بصورت عملیات رشته ای حل کرد.یعنی حرکت ها را در یک آرایه یا رشته قرار دهیم و روی آن ویرایش انجام دهیم.البته استفاده از لیست پیوندی بهتر است.اینجا از لیست پیوندی استفاده شده.
برای حل بکمک لیست پیوندی ابتدا یک کلاس برای حرکت طراحی میکنیم که نشان میدهد این  حرکت چه مبدا و مقصدی دارد: 

class move
{
friend class honoi;

public:
 int  from;
 int  to;
 move *next;
 move *prew;

 move(int,int);
 } 

سپس اشیاء از نوع این کلاس را بکمک یک کلاس دیگر لیست میکنیم.ای همان کلاس هانوی است.تابعی که مسئول انجام عملیات رشته ای است،در تابع اصلی به تعداد دیسک ها صدا زده میشود. و در آن برای دیسک های بیشتر از یکی ،یک شمارنده لیست حرکات را طی میکند و برای حرکات با شماره فرد،دو شئ جدید به دو طرف حرکت فرد در لیست اظافه میشود.برای راحت تر انجام شدن این کار بهتر است لیست دوطرفه باشد. 

   int  count=0;  //counter for nodes( move ) in list (honoi)

   move *p=first,*q=first;
   while(p!=NULL)
   {
    count++;
    q=p;
    p=p->next;

    if(count%2==1)
    {
     move *l=new move(q->from,other(q->from,q->to));
     move *r=new move(other(q->from,q->to),q->to);

     if(q==first)
     {
      first->prew=l;
      l->next=first;
      q->next->prew=r;
      r->next=q->next;
      q->next=r;
      r->prew=q;
      first=l;
     }//if q
     else
     {
      q->prew->next=l;
      l->prew=q->prew;
      q->prew=l;
      l->next=q;
      q->next->prew=r;
      r->next=q->next;
      q->next=r;
      r->prew=q;
     }//else
    }//if count%2
   }//while p
  }//else disks

     }

و در پایان این لیست بکمک پیمایش چاپ میشود.و البته بهمراه چاپ در صفحه نمایش،حرکات در  

 یک فایل متنی نیز ذخیره میشوند. 

دانلود برنامه برج هانوی ترتیبی