برج هانوی با جاوااسکریپت

هدف این مقاله معرفی راه حل جاوااسکریپتی برای مسأله برج هانوی می باشد. در مسأله برج هانوی شما باید تعدادی دیسک را از یک برج به برج دیگر انتقال دهید بدون اینکه حلقه بزرگتر روی حلقه کوچکتر قرار گیرد. این مسأله یک الگوریتم بازگشتی دارد.

یک الگوریتم بازگشتی برای برج هانوی

الگوریتم بازگشتی شناخته شده برای مسأله برج هانوی می تواند بوسیله تابع جاوااسکریپت زیر پیاده سازی شود:

ورودی الگوریتم چهار پارامتر عددی زیر می باشد:

1.n: تعداد دیسکها

2.from: برجی که دیسکها برروی آن قرار دارند.

3.to: برجی که دیسکها باید بر روی آن قرار گیرند.

4.via: برجی که بعنوان واسط بین دو برج from و to عمل می کند.

بطور معمول (اگر برجها را 0،1و2 نامگذاری کنیم) ، صدا زدن اولیه برای n دیسک به این صورت می باشد : (Hanoi(n,0,1,2.

یک الگوریتم بازگشتی سعی می کند که مسأله را به مسأله های کوچکتری تبدیل کند(نمونه هایی از مسأله اصلی ولی با اندازه کوچکتر) سپس راه حل مسأله بزرگتر را با استفاده از رها حل مسأله کوچکتر پیدا کند. 

الگوریتم بازگشتی برج هانوی بر پایه این مشاهده واقع شده که n -1 دیسک بالایی از برج from (به همراه دو برج دیگر) مسآلهکوچکتری از مسآله اصلی است و بنابراین می تواند با صدا زدن( Hanoi(n-1, 0,1,2 حل شود.

اینکار دیسک ها را به برج وسط (1) با استفاده از برج واسط (2) انتقال می دهد. بعد از این ما می توانیم با صدا زدن Hanoi(n-1,1,2,0) ، n امین دیسک را از برج 0 به برج 2 انتقال داده و سپس تمام n-1 دیسک از برج وسط را با استفاده از برج 0 به آخرین برج انتقال دهیم .

مدیریت کردن انیمیشن در جاوااسکریپت مشکل است

معمولاً کد انیمیشن می تواند از توابع جاوااسکریپتی ()setIntervalیا ()setTimeoutاستفاده کند اما اینکا چندان ساده نیست. فرض کنید در کد بالا، تابع ()moveDiskبا استفاده از ()setIntervalصدازده شده است. 

یک مشکل بوجود می آید زیرا کدی که تابع را صدا زده به اجرا شدن ادامه می دهد و با انیمیشن تداخل پیدا می کند. یک راه حل اینست که اجرای کد تا کامل شدن اجرای انیمیشن به خواب رود اما جاوااسکریپت یک مکانیزم تأخیر واقعی ندارد.

به نظر می رسد که انیمیشن های جاوااسکریپت از این الگو تبعیت می کنند : اگر انیمیشن را شروع کردی دیگر هیچ کاری نکن. برای الگوریتم برج هانوی می خواهیم تابع ()moveDisk را صدا بزنیم و انیمیشن را اجرا کنیم و منتظر شویم تا ()moveDisk بعدی صدازده شود و انیمیشن را اجرا کنیم و به همین ترتیب. اما با انیمیشن جاوااسکریپت ما مجبوریم که الگوی زیر را دنبال کنیم: ()moveDisk را اجرا کن، ()moveDisk بعدی را اجرا کن و به همین ترتیب. به عبارت دیگر هر اجرای ()moveDisk هنگامی که کامل شد باید صداکننده ()moveDisk بعدی باشد. برای پیاده سازی این سناریو از stack استفاده می کنیم. استفاده از استک ترتیب اجرای ()moveDisk را حفظ می کند.

کد زیر پیاده سازی استک را نشان می دهد:

بعد از صدازدن Hanoi() ، callStack یک ورودی برای هر ()moveDisk خواهد داشت. پردازش این ورودی ها بر عهده تابع ()moveDisk می باشد. این تابع یک ورودی از callStackبرمی دارد و یک شیء به نام moveInfo برای ارسال اطلاعات به تابع ()animateMove می سازد. انیمیشن با کد ;(myTimer = setInterval(animateMove,speed); شروع می شود.

کد زیر مربوط به تابع ()animateMove می باشد:

تابع ()animateMove یک دیسک را به بالا سپس راست یا چپ سپس پایین حرکت می دهد و در آخر ()moveDisk بعدی را صدا می زند. توجه کنید که قبل از صدازدن ()moveDisk تایمر با استفاده از کد (clearInterval(myTimer کنسل شده است تا از استفاده نادرست این تابع از شیء moveInfo اجتناب شود.