الگوریتم و کد برج های هانوی در ++C

 

tower of hanoi solution

مساله ی برج های هانوی (towers of Hanoi) از مساله های معروف در زمینه ی اگوریتم های بازگشتی است که در آن تعدادی دیسک را باید ازمیله ای به میله ی دیگر منتقل کرد.

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

مسآله: همه ی دیسک ها را باید به یک میله ی خالی منتقل کنید.

قوانین:

۱-هنگام حرکت دادن دیسکها هیچ دیسکی روی دیسک کوچکتر از خود قرار نگیرد.

۲-درهر بار حرکت دادن دیسک ها نمیتوان بیش از یک دیسک را منتقل کرد.

حل: فرض کنیم n دیسک داریم و میله ها را origin , middle , destination مینامیم که ابتدا دیسکها در origin قرار دارند وباید به destination منتقل شوند. فرض کنیم (H(n تابعی باشد که این کار را انجام میدهد n دیسک را به روش زیر منتقل میکنیم:

۱-با(H(n-1  ابتدا n-1 دیسک بالایی از میله ی origin را به middle منتقل میکنیم.

۲-آخرین دیسک موجود در origin را به destination منتقل میکنیم.

۳-با(H(n-1  درآخر n-1 دیسک موجود در میله ی origin را به destination منتقل میکنیم.

پس داریم:(H(n)=H(n-1)+1+H(n-1 یعنی H(n)=2H(n-1)+1

کد این مساله به زبان سی پلاس پلاس( ++C):

جالب است بدانیم که جواب تابع  بازگشتی در این مساله برابر است با: hanoi(n)=(2^n)-1 یعنی تابع به اندازه ی hanoi(n)=(2^n)-1 فراخوانی میشود, پس با انجام

همین تعداد حرکت دیسکها از origin  به destination  منتقل میشوند.

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)

۱۶ comments

Leave a Reply

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