حل مساله برج هانوی

برج هانوی
[FONT=Tahoma, Arial, Helvetica, sans-serif]مساله «برج هانوی» از سه میله با نام های A و B و C تشکیل می شود که n
دیسک با قطر های مختلف ( و ارتفاع های یکسان ) در میله ها قرار دارند. در
ابتدای کار تمام دیسک ها به صورت مرتب شده بر اساس قطرشان ( طوری که کم
قطرترین دیسک بالاترین و بزرگ ترین دیسک پایین ترین باشد ) روی میله A قرار دارند.[/FONT]

​

[FONT=Tahoma, Arial, Helvetica, sans-serif]یک
حرکت «مجاز» در این مساله برداشتن بالاترین دیسک از یک میله( میله مبدا )و
قرار دادن آن در میله ای دیگر( میله مقصد ) است بطوری که هیچ گاه یک دیسک
روی دیسکی با قطر کوچکتر قرار نگیرد. با این وصف ، یک حرکت را می توان با
دو حرف بزرگ انگلیسی نمایش داد که حرف اول میله مبدا و حرف دوم میله مقصد
است. برای مثال حرکت AB یعنی برداشتن بالاترین دیسک میله A و قرار دادن آن روی تمام دیسک های میله B ( در صورت وجود ). دقت کنید که حرکت AB تنها زمانی مجاز است که میله A حداقل یک دیسک داشته باشد و بعلاوه یا میله B خالی باشد یا قطر بالاترین دیسک میله A ( که جابجا می شود ) از قطر بالاترین دیسک میله B کمتر باشد.[/FONT]

[FONT=Tahoma, Arial, Helvetica, sans-serif]با شروع از حالتی که تمام دیسک ها بصورت مرتب در میله ی A قرار دارند ( نظیر شکل بالا )، بازی هنگامی تمام می شود که تمام دیسک ها به همین ترتیب در میله B قرار بگیرند ( و میله های A و C خالی باشند ) یا تمام دیسک ها به همین ترتیب در میله ی C قرار بگیرند ( و میله های A و B خالی باشند ).[/FONT]

[FONT=Tahoma, Arial, Helvetica, sans-serif]هوشنگ
برای حل کردن این معما ، الگوریتم زیر را در پیش می گیرد. او ابتدا یک
جایگشت از تمام 6 حرکت موجود در نظر می گیرد ( مثلا جایگشت CB ، AC ، BA ، BC ، AB ، CA
از چپ به راست ) ، سپس در هر مرحله سمت چپ ترین حرکت مجاز از حرکات این
جایگشت را انجام می دهد. علاوه بر این ، او هبچ وقت دوست ندارد یک دیسک را
در دو حرکت متوالی جابجا کند و از این رو اگر یک حرکت ( بعد از حرکت اول )
از مقصد حرکت قبلی آغاز شود ، او این حرکت را غیر مجاز تلقی می کند. برای
مثال اگر جایگشت نمونه ی گفته شده را روی میله های شکل در نظر بگیریم ،
اولین حرکت هوشنگ AB خواهد بود ( چرا که CA بدلیل خالی بودن میله C غیر مجاز است ) و حرکت دوم او AC خواهد بود: CA غیر مجاز است چون C هنوز خالی است؛ AB غیر مجاز است چون دیسک با قطر 2 را نمی توان روی دیسک با قطر 1 ( که در حرکت اول به B منتقل شده ) قرار داد؛ BC نیز غیر مجاز است چرا که دیسک رویی B در حرکت قبلی تکان خورده و هوشنگ دوست ندارد یک دیسک را در 2 حرکت متوالی جابجا کند و از این رو سمت چپ ترین حرکت مجاز ، AC است![/FONT]

[FONT=Tahoma, Arial, Helvetica, sans-serif]می
توان اثبات کرد که الگوریتم هوشنگ همیشه پایان می یابد! آنچه از شما
خواسته می شود این است که با دانستن تعداد دیسک ها و استراتژی هوشنگ(
جایگشتی از 6 حرکت ممکن )، مشخص کنید که هوشنگ چند جابجایی انجام می دهد
تا بازی تمام شود.[/FONT]

[FONT=Tahoma, Arial, Helvetica, sans-serif]ورودی[/FONT]

[FONT=Tahoma, Arial, Helvetica, sans-serif]در سطر اول ورودی ، تعداد تست داده می شود. سپس هر تست در 2 خط داده می ش.د که خط اول تنها یک عدد n را داشته و در خط دوم یک جایگشت از حرکات ممکن بصورت 6 رشته 2 حرفی ( معتبر و دو به دو متمایز) داده می شود.[/FONT]

[FONT=Tahoma, Arial, Helvetica, sans-serif]خروجی[/FONT]

[FONT=Tahoma, Arial, Helvetica, sans-serif]به ازای هر تست ورودی ، در یک سطر تعداد حرکاتی که هوشنگ می کند را بنویسید.[/FONT]

[FONT=Tahoma, Arial, Helvetica, sans-serif]محدودیت ها[/FONT]

[FONT=Tahoma, Arial, Helvetica, sans-serif]می دانیم که N<=۱ و N<=۳۰ و جواب خروجی هیچ تستی از 10 به توان 18 بیشتر نبست.[/FONT]

دانلود برنامه سوال

دانلود فایل PDF مساله