لگوریتم برج هانوی و پیاده سازی آن در C
برج هانوی معمایی است که از ۳ میله و N حلقه یا دیسک با اندازه های متفاوت . مطابق شکل زیر می خواهیم تمام N حلقه را از میله اول به یک میله دیگر انتقال دهیم. از میله سوم می توان به عنوان کمکی استفاده کرد
حل این معما دو شرط دارد:
۱- در هر انتقال تنها یک حلقه را می توان انتقال داد.
۲- در هیچ کدام از میله ها هیچ وقت نمی توان یک حلقه بزرگتر را بر روی یک حلقه کوچکتر قرار داد.
راه حل :
این مسئله با استفاده از الگوریتم بازگشتی حل می شود.
اگر فقط یک دیسک باشد آنگاه آن را به میله مورد نظر انتقال می دهیم.
اگر n>1 باشد برای این کار n-1 دیسک بالای میله ۱ را به میله ۲ انتقال می دهیم . حالا دیسک پایینی میله ۱ را ثابت باقی می ماند. حال دیسک باقی مانده در دیسک ۱ را به میله ۱ انتقال می دهیم . سرانجام بار دیگر به صورت بازگشتی الگوریتم را فراخوانده تاn-1 دیسک میله ۲ را به ۳ منتقل کند .
اکنون موفق شدیم n دیسک را از میله ۱ به ۳ منتقل کنیم .
