حل مسالهی برج هانوی با ++C
در محوطه معبدی در آسیای دور سه میله الماسی قرار داشت که یکی از آنها حاوی تعدادی قرص طلایی بود. کاهنان معبد در تلاش بودند تا قرصهای طلائی را از آن میله به یکی دیگر از میلهها تحت شرایطی انتقال دهند، و باور داشتند که با تمام شدن انتقال قرصها عمر جهان نیز به پایان خواهد رسید! میله اولیه ۶۴ قرص داشت، که بر روی هم به طور نزولی بر اساس اندازهشان چیده شدهبودند (منبع ویکی پدیا). این میله ها و قرص ها به برج هانوی معروف شده اند. برای انتقال قرص ها دو قانون وجود داشت.
قانون اول: در هر لحظه فقط می توان یک قرص را جا به جا کرد.
قانون دوم: در هیچ لحظه ای نباید قرصی با اندازه ی بزرگ تر بر روی قرصی با اندازه کوچک تر قرار بگیرد.
هدف حل مساله ی برج هانوی پیدا کردن روشی با کمترین تعداد جا به جایی قرص هاست. برای مثال اگر تعداد قرص ها دو عدد باشد، با سه حرکت می توان این کار را انجام داد و این سه حرکت عبارت اند از:
حرکت قرص کوچک از میله A به میله B
حرکت قرص بزرگ از میله A به میله C
حرکت قرص کوچک از میله B به میله C
برای حل این گونه مسائل می توانیم از روش تقسیم و حل استفاده کنیم. مسائلی که با روش تقسیم و حل و یا با روش بازگشتی قابل حل هستند باید دارای دو خاصیت زیر باشند:
۱- قابل تقسیم به مسائل دیگری باشند.
۲- اندازه ی مسائل به دست آمده ی جدید از مساله ی اولیه کوچک تر باشد.
حال سعی می کنیم مساله ی برج هانوی را به روش بازگشتی حل کنیم. فرض کنید n قرص بر روی میله ی اولیه وجود دارد و شما راه حلی برای انتقال ۱ – n قرص از یک میله به میله ی دیگر را می دانید. بنابراین کافیست ۱ – n قرص بالایی را به روشی که از قبل می دانید به میله ی B منتقل کنید. سپس قرص nام را به میله ی C منتقل کنید و در نهایت ۱ – n قرص را از میله ی B به میله ی C انتقال دهید. این الگوریتم برای ۵ = n در تصویر زیر نشان داده شده است.
بنابراین، در این الگوریتم مساله ی اصلی هانوی به دو مساله ی هانوی با اندازه کوچک تر تقسیم شد. در نتیجه با حل بازگشتی مسائل کوچک تر مساله ی اولیه به طور کامل حل خواهد شد. الگوریتم بالا را به زبان ++C می توان به این صورت نوشت.
#include<iostream> using namespace std; void hanoi ( int nDisk, char start, char temp, char finish ) { if ( nDisk == 1 ) cout <<start <<" --> " <<finish <<endl; else { hanoi ( nDisk - 1, start, finish, temp ); cout <<start <<" --> " <<finish <<endl; hanoi ( nDisk - 1, temp, start, finish ); } } int main(){ int n; cin >> n; hanoi(n,'A','B','C'); return 0; }
و خروجی این برنامه به ازای ۴ = n برابر است با:
به ازای تعداد قرص های اولیه متفاوت، تعداد حرکات برای حل مساله به سادگی قابل محاسبه است. و این تعداد برابر ۲n – 1 می باشد. بنابراین پیچیدگی زمانی این الگوریتم (O(2n است. که با وجود بالا بودن میزان پیچیدگی زمانی، بهترین الگوریتمی است که برای این مساله وجود دارد. برای درک بهتر پیچیدگی زمانی این الگوریتم از این مثال استفاده می کنیم. فرض کنید کاهنان معبد با همکاری یکدیگر در هر دو ثانیه یک قرص را جابجا می کردند، ۱۱۶۹ میلیون میلیون سال طول می کشید تا تمام ۶۴ قرص را به میله ی سوم منتقل کنند.
قهرمان دنیای خودت باش!
مطالب زیر را حتما مطالعه کنید
حسگرها و فناوریهای پوشیدنی و کاربردهای آنها در پزشکی
آشنایی با نمودار رابطهای (ER)
درخت دودویی
ساختمان داده درخت
مدار منطقی – گیت های منطقی
مدار منطقی-جبر بول
1 Comment
Join the discussion and tell us your opinion.
دیدگاهتان را بنویسید لغو پاسخ
برای نوشتن دیدگاه باید وارد بشوید.
kheli mamnon babate maghale jalebeton