سورس کد برج هانوی در سی شارپ Hanoi Tower

برج هانوی (Tower of Hanoi) یکی از مسائل تاریخی مشهور است که در مباحث طراحی الگوریتم به آن پرداخته می‌شود. تاریخچه و صورت مسئله آن مربوط به دوران های قدیم است. در سال های دور در محوطه معبدی سه میله الماسی قرار داشت که یکی از آن‌ها حاوی تعدادی دیسک طلایی بود. کاهنان معبد در تلاش بودند تا دیسک های طلائی را از آن میله به یکی دیگر از میله‌ها تحت شرایطی انتقال دهند، و باور داشتند که با تمام شدن انتقال دیسک هاعمر جهان نیز به پایان خواهد رسید! میله اولیه ۶۴ قرص داشت، که بر روی هم به‌طور نزولی بر اساس اندازه‌شان چیده شده‌بودند.

نمونه‌ای از برج هانوی

همانند شکل زیر سه میله داریم. یکی از میله‌ها میله مبدأ (A)، دیگری میله کمکی (B) و دیگری میله مقصد (C) است. هدف انتقال تمام دیسک‌ها از میله مبدأ به میله مقصد با رعایت شرایط زیر است:

  • در هر زمان فقط یک دیسک را می‌توان جابجا نمود.
  • نباید در هیچ زمانی دیسکی بر روی دیسک با اندازه کوچکتر قرار بگیرد.

 

برج هانوی Towers of Hanoi

حل مسئله

هدف ارائه الگوریتمی است که کمترین توالی حرکت‌ها را برای انتقال دیسک‌ها به ما بدهد. مثلاً اگر n=۲ باشد، توالی حرکت به صورت زیر است:

دیسک ۱ را به میله B منتقل می‌کنیم.
دیسک ۲ را به میله C منتقل می‌کنیم.
دیسک ۱ را به میله C منتقل می‌کنیم.

توجه داشته باشید که بر اساس قانون اول نمی‌توان به غیر از بالاترین دیسک هر میله، به دیسک دیگری از آن دسترسی پیدا کرد.

برای اینکه مسئله‌ای بتواند با روش بازگشتی حل شود باید یک ویژگی اساسی داشته باشد. مسئله اصلی قابل خرد شدن به زیر مسئله‌هایی از همان نوع مسئله اصلی باشد، به شرطی که اندازه زیر مسئله‌های ایجاد شده کمتر باشد. آنگاه می‌توان امیدوار بود که آن را به‌طور بازگشتی حل کرد! این ویژگی در مورد مسئله برج هانوی صدق می‌کند. ایده اصلی این است که توجهمان را به جای حرکت بالاترین دیسک، روی پایین‌ترین دیسک میله متمرکز کرده، و مراحل زیر را طی می‌کنیم:

n – ۱ دیسک بالایی را با شرایط ذکر شده و به کمک میله C به میله B منتقل می‌کنیم. بزرگترین دیسک را از میله مبدأ به میله مقصد حرکت می‌دهیم. n – ۱ دیسک را که هم اکنون در میله B هستند با شرایط داده شده به میله مقصد انتقال می‌دهیم. می‌بینیم که توانستیم عملیات جابجا کردن n دیسک را به دو عملیات مشابه ولی با اندازه کمتر و یک عملیات ساده تقسیم کنیم. واضح است که جابجا کردن n – ۱ دیسک راحتتر از جابجا نمودن n دیسک است.

تحلیل پيچيدگي زمانی مسئله‌ی برج هانوی

در حالت کلی می‌خواهیم بدانیم اگر تعداد دیسک‌ها n باشد، کمترین تعداد حرکت برای جابجا نمودن دیسک‌ها چقدر است؟

فرض کنید (T(n تعداد حرکت‌های لازم جهت انتقال n دیسک به مقصد باشد. بر اساس توضیحات فوق، تعداد (T(n−1 حرکت برای انتقال n−1 دیسک به میله‌ی کمکی، یک حرکت برای انتقال بزرگترین دیسک به میله‌ی مقصد و مجددا (T(n−1 حرکت برای انتقال n−1 دیسک موجود در میله‌ی کمکی به میله‌ی مقصد نیاز است. پس:

T(n)=2T(n−1)+1

با حل این رابطه‌ی بازگشتی به روش‌های ریاضی، به نتیجه‌ی زیر می‌رسیم:

T(n)=2n−1

مرتبه‌ی اجرایی این الگوریتم (O(2n است که چندان مرتبه‌ی مطلوبی به نظر نمی‌رسد. اما همانگونه که بحث شد، این روش حداقل تعداد حرکت‌های ممکن را می‌دهد؛ و هرگز نمی‌توان روش دیگری با مرتبه‌ی پایین‌تر برای حل آن یافت.

پیاده سازی مسئله برج هانوی بصورت بازگشتی در سی شارپ

برای پیاده سازی مسئله برج هانوی در #C از چندین کلاس استفاده شده است. که وظایف هر کلاس به ترتیب بصورت زیر است:

کلاس MoveCalculator : این کلاس با هدف تنها کار بر روی راه حل ایجاد شده است. حل مسئله بصورت بازگشتی است.

کلاس GameState : کلاس بالا لیستی از حرکت ها را باز می کند و GameState آنها را می سازد.

 

کلاس Move: این کلاس برای تعریف حرکت دیک ها ایجاد شده است.

فرم GameForm: فرم اصلی برنامه می باشد که توابع و کلاس ها در آن ایجاد می شود.

 

نمایش خروجی محصول

برج هانوی Towers of Hanoi

 

معرفی ویدئوی محصول

سورس کد برج هانوی بصورت در سی شارپ دارای دو قسمت حل به روش دستی و حل خود کار با استفاده از روش بازگشتی بصورت گرافیکی می باشد. این سورس کد به زبان سی شارپ #C در Microsoft Visual Studio 2013 نوشته شده است. این سورس کد توسط کارشناسان پی استور تست و اجرا شده است و مورد تایید پی استور می باشد. محصول دارای نشان ضمانت پی استور می باشد. برای دانلود سورس کد برج هانوی در سی شارپ Hanoi Tower به صورت گرافیگی، محصول را خریداری کنید. به محض خرید لینک دانلود در دسترس خواهد بود.

19,000 تومان

1 دیدگاه برای سورس کد برج هانوی در سی شارپ Hanoi Tower به صورت گرافیکی

  1. امتیاز 5 از 5

    programstore

    نظرات و دیدگاه های خود را با ما درمیان بگذارید.

دیدگاه خود را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

این سایت از اکیسمت برای کاهش هرزنامه استفاده می کند. بیاموزید که چگونه اطلاعات دیدگاه های شما پردازش می‌شوند.

اطلاعات فروشنده