خانه / کد / الگوریتم برج هانوی و پیاده سازی آن در C

الگوریتم برج هانوی و پیاده سازی آن در C

برج هانوی معمایی است که از ۳ میله و N حلقه یا دیسک با اندازه های متفاوت تشکیل شده می‌شود. حل این معما دو شرط دارد:

۱- در هر انتقال تنها یک حلقه را می توان انتقال داد.
۲- در هیچ کدام از میله ها هیچ وقت نمی توان یک حلقه بزرگتر را بر روی یک حلقه کوچکتر قرار داد.

راه حل

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

اگر فقط یک دیسک باشد آنگاه آن را به میله مورد نظر انتقال می دهیم.

اگر n>1 باشد برای این کار n-1 دیسک بالای میله ۱ را به میله ۲ انتقال می دهیم. حالا دیسک پایینی میله ۱ را ثابت باقی می ماند. حال دیسک باقی مانده در دیسک ۱ را به میله ۱ انتقال می دهیم. سرانجام بار دیگر به صورت بازگشتی الگوریتم را فراخوانده تاn-1 دیسک میله ۲ را به ۳ منتقل کند.
اکنون موفق شدیم n دیسک را از میله ۱ به ۳ منتقل کنیم.

درباره ی آریـان پــور

سلام . آریــان پور هستم . از نویسندگان میکروپـدیا .. علاقه مــند به برنامه نویسی و طراحی وب و شبکه ! دیدگاه ها و نظرات شما دوستان بررسی میشه و باعث دلگرمـی برای نوشتن مطالب بهتر و به روزتر . در تماس باشید با : aryanpour [at] micropedia [dot] ir با مـا همراه باشید ..

همچنین ببینید

کد تبدیل ماتریس خلوت (اسپارس) به ماتریس معادل در ++C

ماتریس های خلوت یا اسپارس گونه ای از داده ساختارها هستند که مقادیر پرارزش (غیر …

۱۳ دیدگاه ها

  1. کریسمس مبارک

    سلام اگه بخوایم سه یا چهار دیسک رو به میله c انتقال بدیم درحالی که در هر جابه جایی هر دیسک فقط به میله ی کناریش بتونه متنقل بشه چی؟ نتونستم کدی براش پیدا کنم کسی میتونه راهنماییم کنه؟

  2. سلام، کد مربوط به برج هانوی یا لینک دانلوش روی وب نیست.چه طور میتونم دانلودش کنم؟

  3. سلام خسته نباشید
    استاد ما گفته با stack این برج هانوی رو بنویسیم میشه کمک کنین چطور بنویسم؟
    خیلی ممنون.

  4. i did not get whole the program can you give me mor explaination plzzz

  5. عالیییییی!!!!!
    خیلییییی ممنون!!

  6. سلام استاد ما گفته الگوریتم برج هانوی را برای ۵ حلقه بنویسید تو رو خدا تا چهار شنبه جوابشو بدین وگرنه جریمه میشم

  7. سلام.در این قسمت کد void tower(int,char,char,char); چرا به تابع مقدار char یا int دادیم.البته استدلال من ایه که توی چند خط پایینی ازش استفاده کردیم.منظورم اینجاستtower(ndisk,’A’,’B’,’C’);
    ولی وقتی به استادم گفتم قبول نکرد و گفت یه دلیل دیگه داره.هرچقدر فکر کردم دلیلشو نفهمیدم.ممکنه راهنماییم کنید؟با سپاس

    • سلام ..
      تابع tower در قسمت void tower(int,char,char,char); تعریف شده است و در قسمت tower(ndisk,’A’,’B’,’C’); فراخوانی شده است .
      مقادیری که به عنوان ورودی گرفته int که همان ndisk ماست تعداد حلقه هایی که می خواهیم جابه جا کنیم را از ورودی می خواند .
      سه مقدار دیگه که از نوع char هستند و در قسمت فراخوانی ‘A’ و ‘B’ و ‘C’ نامیده شده اند نام پایه یا ستون برج ماست ( برج هانوی ۳ ستون دارد ) .
      موفق باشید ..

  8. سلام.خیلی ممنون که برنامرو گذاشتید.اگه لطف کنید راجع به خط system یه توضیح بدید.ممنون

    • سلام ..
      خواهش می کنم .
      این قسمت از کد که درون system مقدار cls را نوشته ایم باعث پاک شدن صفحه نمایش می شود .
      تا داده های جدید را در صفحه نمایش و حالا اون محیط cmd مشاهده کنیم .

  9. از اینکه این برنامه رو گذاشتین خیلی خیلی ممنون
    ولی اگر ممکنه یه توضیح مختصری هم درباره اینکه هر خط از این برنامه چه گاری رو انجام میده هم بزارید…
    استاد گیرداده بیایین توضیح بدین… 🙂
    ممنون

    • خواهش می کنم ، خوشحالم که به کارتون اومده ..
      سه خط اول که کتابخونه ها و هدرفایل های مورد نیاز برای استفاده ی توابعی مثل ()getch را فراخوانی کرده ایم .
      خط چهارم تابع tower را تعریف کردیم که تعداد دیسک و نام ستون های برج را به عنوان ورودی می گیرد .
      در تابع main تعداد دیسکی که می خواهیم قرار دهیم را از ورودی دریافت می کند و با نام ۳ ستون برجمون تابع tower را فراخوانی می کند .
      تابع tower هم که با توجه به توضیحاتی که اول پست داده شده اگر یک دیسک داشته باشیم آن را جابه جا می کنیم و حالات جابه جایی را چاپ می کنیم .
      اگر بیش از دیسک داشتیم تابع را همانطور که میبینین فراخوانی می کنیم . که در آن src ستون مبدا ما dest ستون مقصد و aux هم ستون میانی است .
      موفق باشین …

      • ممنون اقای اریا پور تونستم کد رو ببینم. اقای اریا پور مشه روی همین سور کد ها تغیراتی ایجاد کنید که. هر دیسک برای جابه جایی تنها بتونه به میله ی کناری خودش منتقل شه.مثلا دیسک میله ی اول ابتدا به میله ی دوم منتقل شود و بعد همان دیسک از روی میله ی دوم به میله ی سوم منتقل شود.ممنون میشم به سوالم پاسخ بدین

پاسخ دهید

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

پاسخ عبارت زیر را وارد کنید: *