سلام
می شه این سوال رو حل کنید.
اگر در برج هانوی سکه های با شماره‌ی فرد و زوج به ترتیب در میله های ۱ و ۲ باشند، با حداقل حرکت‌ها می خواهیم همه سکه‌ها را در میله ۳ قرار دهیم چگونه این کار را می شود انجام داد ؟
اگه n حلقه‌ی فرد روی ۱ و n حلقه‌ی زوج روی ۲ باشه و بخوایم همه‌ی ۲n حلقه رو روی ۳ قرار بدیم، اول فرض میکنیم که مسئله برای n-1 تا حلقه‌ی بالایی روی میله های ۱ و ۲ حل شده باشه، یعنی در میله‌ی ۳ به تعداد ۲n-2 حلقه که شرایط مسئله‌ی برج هانوی رو ارضا میکنه قرار داره، اون وقت مسئله رو برای این دو حلقه‌ی باقی مانده در میله های ۱ و ۲ حل میکنیم. که باید حلقه‌ی کوچکتر رو روی حلقه‌ی بزرگتر قرار بدیم، بقیه‌ی کاری که از این جا به بعد باقی مانده کاملاً شبیه همان مسئله‌ی هانوی کلاسیک هست. یعنی باید ۲n-2 حلقه‌ی روی میله‌ی ۳ را به روی ۲ حلقه‌ی روی میله‌ی دیگر انتقال دهیم. بعد از این کار ۲n حلقه‌ی مرتب خواهیم داشت، سرانجام همه را به میله‌ی شماره ۳ منتقل میکنیم.
سلام
۵۴m4n3h عزیز فکر می کنم راه حلتون اگه درست فهمیده باشم، مشکل داره فرض کنید ۲n-2 سکه توی میله‌ی سوم داریم الان باید این ۲n-2 سکه رو به میله ای که اون دوتا سکه‌ی بزرگتر توش نیست انتقال بدیم تا میله‌ی ۳ خالی بشه و بتونیم اون دو تا سکه رو بذاریم اونجا.در حالی که سکه‌ی کوچیک روی سکه‌ی بزرگتر هست نمی تونیم سکه‌ی بزرگتر رو اول انتقال بدیم.در واقع سکه بزررگه گیر میفته!حتی اگه این مشکلم مثلاً با انتقال همزمان دو سکه حل میشد، الگوریتم از لحاظ حداقل جابجایی‌ها بهینه نیست.
یه راه حل به نظرم رسید که عرض میکنم:
فرض میکنیم n تا سکه‌ی زوج توی میله‌ی a داریم و m تا فرد توی b و این سکه‌ها همه پشت سر همن ؛ یعنی مثلاً همه‌ی اعداد از ۱ تا k و k یه عدد زوج هست ؛ یعنی بزرگترین سکه زوجه:
n-1 سکه رو از a به b انتقال و آخرین سکه رو می ذاریم روی c
n-1 سکه رو از b به a برمی گردونیم
m-1 سکه رو از b به a انتقال و آخرین سکه رو می ذاریم روی c روی سکه‌ی زوج بزرگتر
m-1 سکه رو از a به b برمی گردونیم
حالا (بعد از ۴ بار فراخوانی الگوریتم برج هانوی) الگوریتم اصلی رو برای n-1 و m-1 تکرار میکنیم.
البته اگر سکه‌ها پشت سر هم نباشن (که منطقاً نبایدم باشن) مقایسه هم لازم میشه که بسته به این که بدونیم در دنیای واقعی چه سکه هایی وجود داره یا نه عملیات اضافی رو اعمال می کنیم.
این یه نظر بود، همیشه ممکنه راه حل بهتری وجود داشته باشه.....
(۰۷ آذر ۱۳۸۹ ۰۳:۰۳ ب.ظ)raha نوشته شده توسط: سلام
۵۴m4n3h عزیز فکر می کنم راه حلتون اگه درست فهمیده باشم، مشکل داره فرض کنید ۲n-2 سکه توی میله‌ی سوم داریم الان باید این ۲n-2 سکه رو به میله ای که اون دوتا سکه‌ی بزرگتر توش نیست انتقال بدیم تا میله‌ی ۳ خالی بشه و بتونیم اون دو تا سکه رو بذاریم اونجا.در حالی که سکه‌ی کوچیک روی سکه‌ی بزرگتر هست نمی تونیم سکه‌ی بزرگتر رو اول انتقال بدیم.در واقع سکه بزررگه گیر میفته!
راه حلم درسته!
برای این که من نگفتم ۲n-2 سکه رو انتقال میدم به میله‌ی خالی! من گفتم: ۲n-2 حلقه‌ی روی میله‌ی ۳ را به روی ۲ حلقه‌ی روی میله‌ی دیگر انتقال دهیم! و در این صورت مسئله تبدیل میشه به همون هانوی کلاسیک!
(۰۷ آذر ۱۳۸۹ ۰۵:۰۰ ب.ظ)۵۴m4n3h نوشته شده توسط:دوست خوبم به اون دو تا سکه ای که روی هم گذاشتین فکر کنید، وقتی خواستید اون ۲n-2 سکه رو به قول خودتون از میله ی۳ بذارین روی دو تا میله‌ی دیگه، با این دو تا سکه که روی هم توی یکی از این میله هاست چی کار می کنین؟دقت کنید که این دو سکه از همه بزرگترن و نمیشه روی بقیه قرار بگیرن.(07 آذر ۱۳۸۹ ۰۳:۰۳ ب.ظ)raha نوشته شده توسط: سلام
۵۴m4n3h عزیز فکر می کنم راه حلتون اگه درست فهمیده باشم، مشکل داره فرض کنید ۲n-2 سکه توی میله‌ی سوم داریم الان باید این ۲n-2 سکه رو به میله ای که اون دوتا سکه‌ی بزرگتر توش نیست انتقال بدیم تا میله‌ی ۳ خالی بشه و بتونیم اون دو تا سکه رو بذاریم اونجا.در حالی که سکه‌ی کوچیک روی سکه‌ی بزرگتر هست نمی تونیم سکه‌ی بزرگتر رو اول انتقال بدیم.در واقع سکه بزررگه گیر میفته!
راه حلم درسته!
برای این که من نگفتم ۲n-2 سکه رو انتقال میدم به میله‌ی خالی! من گفتم: ۲n-2 حلقه‌ی روی میله‌ی ۳ را به روی ۲ حلقه‌ی روی میله‌ی دیگر انتقال دهیم! و در این صورت مسئله تبدیل میشه به همون هانوی کلاسیک!
به نظرتون راه حلی که من پیشنهاد کردم اشتباهه؟خوشحال می شم نظرتون رو بدونم.
(۰۷ آذر ۱۳۸۹ ۰۶:۳۴ ب.ظ)raha نوشته شده توسط: دوست خوبم به اون دو تا سکه ای که روی هم گذاشتین فکر کنید، وقتی خواستید اون ۲n-2 سکه رو به قول خودتون از میله ی۳ بذارین روی دو تا میله‌ی دیگه، با این دو تا سکه که روی هم توی یکی از این میله هاست چی کار می کنین؟دقت کنید که این دو سکه از همه بزرگترن و نمیشه روی بقیه قرار بگیرن.
به نظرتون راه حلی که من پیشنهاد کردم اشتباهه؟خوشحال می شم نظرتون رو بدونم.
اون دو تا حلقه از همه بزرگترند پس بهشون کاری نداریم! انگار که نیستن! ما میخوایم ۲n-2 تا حلقه‌ی دیگه بیان روی میله ای که اینا هستند!
راه حلتونم نخوندم هنوز! یه چند ساعت دیگه میام میخونم
(۰۷ آذر ۱۳۸۹ ۰۶:۵۱ ب.ظ)۵۴m4n3h نوشته شده توسط:(07 آذر ۱۳۸۹ ۰۶:۳۴ ب.ظ)raha نوشته شده توسط: دوست خوبم به اون دو تا سکه ای که روی هم گذاشتین فکر کنید، وقتی خواستید اون ۲n-2 سکه رو به قول خودتون از میله ی۳ بذارین روی دو تا میله‌ی دیگه، با این دو تا سکه که روی هم توی یکی از این میله هاست چی کار می کنین؟دقت کنید که این دو سکه از همه بزرگترن و نمیشه روی بقیه قرار بگیرن.
به نظرتون راه حلی که من پیشنهاد کردم اشتباهه؟خوشحال می شم نظرتون رو بدونم.
اون دو تا حلقه از همه بزرگترند پس بهشون کاری نداریم! انگار که نیستن! ما میخوایم ۲n-2 تا حلقه‌ی دیگه بیان روی میله ای که اینا هستند!
راه حلتونم نخوندم هنوز! یه چند ساعت دیگه میام میخونم
آهان پس شما بقیه‌ی سکه هایی که قبلاً توی این میله بودند رو میچینید رو این دو تا بزرگه !
خوب تا جایی که من میدونم توی این مسایل باید نظم دسته‌ها حفظ شه( زوج‌ها مرتب پیش هم فرد‌ها مرتب پیش هم) درسته که اون چیزی که ته همه‌ی سکه هاس از همه چه زوج چه فرد بزرگتره اما یه جور بی نظمی پیش میاد یعنی در حالی که هنوز سکه‌ها مرتب نیست ما میله ای داریم که مثلاً تا نصف زوج و فرده بعد همه زوج(در واقع زوج‌ها به ترتیب پیش هم نیستن) به فرض این که این مسئله هم مهم نباشه و شما تا آخر همه‌ی این سکه‌ها رو توی یکی از میله های ۱ یا ۲ مرتب کنید و بعد تازه تبدیلش کنین به هانوی، تعداد جابجایی‌ها بهینه نیست، به جون خودم خیلی زیاده
این الگوریتمی که من گفتم، مرتبه ش (n×(۴^n هست!
(۰۷ آذر ۱۳۸۹ ۰۳:۰۳ ب.ظ)raha نوشته شده توسط: یه راه حل به نظرم رسید که عرض میکنم:
فرض میکنیم n تا سکه‌ی زوج توی میله‌ی a داریم و m تا فرد توی b و این سکه‌ها همه پشت سر همن ؛ یعنی مثلاً همه‌ی اعداد از ۱ تا k و k یه عدد زوج هست ؛ یعنی بزرگترین سکه زوجه:
n-1 سکه رو از a به b انتقال و آخرین سکه رو می ذاریم روی c
n-1 سکه رو از b به a برمی گردونیم
m-1 سکه رو از b به a انتقال و آخرین سکه رو می ذاریم روی c روی سکه‌ی زوج بزرگتر
m-1 سکه رو از a به b برمی گردونیم
حالا (بعد از ۴ بار فراخوانی الگوریتم برج هانوی) الگوریتم اصلی رو برای n-1 و m-1 تکرار میکنیم.
چه طوری n-1 حلقه رو میذارید روی میله‌ی b در حالی که روی میله‌ی b (اون بالای بالاش!) حلقه به قطر ۱ قرار داره؟ از روش خاصی این وسط استفاده میکنید؟ (چون مستقیم که نمیشه!)
(۰۷ آذر ۱۳۸۹ ۱۰:۲۹ ب.ظ)۵۴m4n3h نوشته شده توسط: این الگوریتمی که من گفتم، مرتبه ش (n×(۴^n هست!
(۰۷ آذر ۱۳۸۹ ۰۳:۰۳ ب.ظ)raha نوشته شده توسط: یه راه حل به نظرم رسید که عرض میکنم:
فرض میکنیم n تا سکه‌ی زوج توی میله‌ی a داریم و m تا فرد توی b و این سکه‌ها همه پشت سر همن ؛ یعنی مثلاً همه‌ی اعداد از ۱ تا k و k یه عدد زوج هست ؛ یعنی بزرگترین سکه زوجه:
n-1 سکه رو از a به b انتقال و آخرین سکه رو می ذاریم روی c
n-1 سکه رو از b به a برمی گردونیم
m-1 سکه رو از b به a انتقال و آخرین سکه رو می ذاریم روی c روی سکه‌ی زوج بزرگتر
m-1 سکه رو از a به b برمی گردونیم
حالا (بعد از ۴ بار فراخوانی الگوریتم برج هانوی) الگوریتم اصلی رو برای n-1 و m-1 تکرار میکنیم.
چه طوری n-1 حلقه رو میذارید روی میله‌ی b در حالی که روی میله‌ی b (اون بالای بالاش!) حلقه به قطر ۱ قرار داره؟ از روش خاصی این وسط استفاده میکنید؟ (چون مستقیم که نمیشه!)
داشتیم دوست رند من ؟!
از همون طوری که شما اون ۲n-2 تا سکه رو گذاشتی تو c روی هم 
من وقتی میگم ۲n-2 تا حلقه رو میذاریم روی یه میله، در این حالت دیگه همه مرتب شدن! یعنی یکی در میون زوج و فرد شدن! و مسئله تبدیل شده به هانوی معمولی!
اگه شما هم انتقال رو مثل من انجام میدید، پس بعد از انتقال n-1 تا حلقه از a به b،ا ۲n-1 تا عنصر مرتب خواهید داشت و یه بزرگترین حلقه در یک میله‌ی دیگه!
و من نمیدونم چرا شما وقتی n-1 تا رو از a بردید به b و ۲n-1 تا حلقه‌ی مرتب تشکیل دادید، بعد n-1تاش رو بر میگردونید به b! خب کلاً همون جا هانوی رو حل کنید دیگه!
در ضمن، رند معنیش بد نیست؟
(۰۷ آذر ۱۳۸۹ ۱۱:۵۹ ب.ظ)۵۴m4n3h نوشته شده توسط: من وقتی میگم ۲n-2 تا حلقه رو میذاریم روی یه میله، در این حالت دیگه همه مرتب شدن! یعنی یکی در میون زوج و فرد شدن! و مسئله تبدیل شده به هانوی معمولی!می دونید از اول ما دو نفر دو دید مختلف به این مسئله داشتیم شما تنها رعایت کوچیک و بزرگی سکه‌ها براتون مهم بود وبه این مسئله که روی یه سری عدد زوج/فرد مرتب دارید یه سری اعداد متوالی رو می چینید اهمیت نمی دادید و من دو تا آرایه مرتب یکی زوج ودیگری فرد رو در نظر می گرفتم که میشه یکی رو ادامه‌ی دیگری قرار داد فقط باید ترتیب حفظ بشه و من چون با دید خودم راه حل شما رو می خوندم برداشت خودم رو داشتم یعنی از اولین پستتون تا آخری ۳ - ۴ تا الگوریتم متفاوت برداشت کردم! و توی همین آخرین پست فهمیدم که شما کلاً یه دید دیگه ای دارین .
اگه شما هم انتقال رو مثل من انجام میدید، پس بعد از انتقال n-1 تا حلقه از a به b،ا ۲n-1 تا عنصر مرتب خواهید داشت و یه بزرگترین حلقه در یک میله‌ی دیگه!
و من نمیدونم چرا شما وقتی n-1 تا رو از a بردید به b و ۲n-1 تا حلقه‌ی مرتب تشکیل دادید، بعد n-1تاش رو بر میگردونید به b! خب کلاً همون جا هانوی رو حل کنید دیگه!
در ضمن، رند معنیش بد نیست؟
بهر حال ممنون از وقتی که گذاشتین ؛ بحث خوبی بود.
راستی عزیزم رند اصلاً معنیش بد نیست .با توجه به برداشت یکی مونده به آخرم
فکر میکردم شما یه قسمت از راهتون با من مشترکه رند خودمونیش یعنی ناقلا بازم ممنون.
(۱۷ اردیبهشت ۱۳۹۰ ۰۸:۲۸ ب.ظ)Star Sky نوشته شده توسط: سلام خدمت همگیفکر کنم همون برج هانوی به روش بازگشتی باشه توی این لینک هست:
بنده کاربر جدید فروم هستم و با معرفی یکی از دوستان به اینجا اومدم
ممنون میشم اگه بنده رو راهنکایی بکنین
یه سوال درمورد برج هانوی دارم
برنامه تقسیم و غلبه برای برج های هانوی رو برام بنویسید
ممنون
![[تصویر: 23333_1_1379098441.gif]](https://img.manesht.ir/23333_1_1379098441.gif)
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۰۷ آذر ۱۳۸۹ ۱۱:۵۹ ب.ظ)۵۴m4n3h نوشته شده توسط: من وقتی میگم ۲n-2 تا حلقه رو میذاریم روی یه میله، در این حالت دیگه همه مرتب شدن! یعنی یکی در میون زوج و فرد شدن! و مسئله تبدیل شده به هانوی معمولی!رابطه بازگشتی این میشه :
اگه شما هم انتقال رو مثل من انجام میدید، پس بعد از انتقال n-1 تا حلقه از a به b،ا ۲n-1 تا عنصر مرتب خواهید داشت و یه بزرگترین حلقه در یک میله‌ی دیگه!
و من نمیدونم چرا شما وقتی n-1 تا رو از a بردید به b و ۲n-1 تا حلقه‌ی مرتب تشکیل دادید، بعد n-1تاش رو بر میگردونید به b! خب کلاً همون جا هانوی رو حل کنید دیگه!
در ضمن، رند معنیش بد نیست؟
کد:
T(n)=2T(n-1)+2T(n-2)+2سلام.
سوال خیلی قشنگی بود. یکم درمورد جوابم توضیح میدم. فکر کنم جوابم درست باشه ولی شاید بشه یکم ساده تر نوشت.
صرف نظر از زوج یا فرد بودن تعداد سکه ها ما n سکه داریم. اگه زوج باشن، که تعدادشون توی میله های ۱ و ۲ برابره و اگه فرد باشن، بزرگترین و کوچکترین سکه توی میله ۱ قرار میگیرن.
برای اینکه این n سکه رو روی میله ۳ مرتب کنیم (تابع رو (S(n فرض میکنیم.)، باید n-1 سکه رو روی میله ای که بزرگترین سکه روی اون قرار نداره مرتب کنیم و این حالت رو با (P(n-1 مشخص میکنم (چون بزرگترین سکه در این میله نیست پس سکه ای که در آخر میبایست روی بزرگترین سکه قرار بگیره در انتهای این میله هست. پس n-2 دیسک باید روی این دیسک قرار بگیرن.) و بعد اول بزرگترین سکه رو به میله ۳ انتقال بدیم (۱ حرکت) و بعد n-1 سکه مرتب رو روی اون قرار بدیم (با (H(n-1 حرکت که H معرف همون حالات برج هانوی معمولیه.)
دنباله P رو برای جمله mام به این شکل تعریف میکنم: m سکه داریم بطوری که سکه های زوج و فرد روی میله های جداگانه مرتب اند و با استفاده از یک میله کمکی مشابه برج هانوی میخواهیم این سکه هارو روی ستونی که بزرگترین سکه در اون قرار داره مرتب کنیم. پس نیاز به جابجایی بزرگترین سکه نداریم. چون بقیه سکه ها روی اون مرتب میشن. برای این مرتب سازی باید m-2 سکه رو روی میله کمکی مرتب کنیم به (S(m-2)+1+H(n-2 حرکت نیاز داریم. چون اول باید همه سکه ها بغی از دو سکه انتهایی رو به میله کمکه ببریم و بعد سکه یکی مونده به آخر رو روی سکه آخر قرار داده و بعد سکه هارو از میله کمکی به میله اولیه برگردونیم.
جواب مسئلمونو با فرمول مینویسم:
[tex]S_n=P_{n-1} H_{n-1} 1[/tex]
[tex]P_m=S_{m-2} H_{m-2} 1[/tex]
[tex]\Rightarrow S_n=S_{n-3} H_{n-1} H_{n-3} 2[/tex]
[tex]S_1=1[/tex]
[tex]S_2=2[/tex]
[tex]S_3=5[/tex]
[tex]P_m=S_{m-2} H_{m-2} 1[/tex]
[tex]\Rightarrow S_n=S_{n-3} H_{n-1} H_{n-3} 2[/tex]
[tex]S_1=1[/tex]
[tex]S_2=2[/tex]
[tex]S_3=5[/tex]
[tex]H_n=2H_{n-1} 1[/tex]
[tex]H_1=1[/tex]
[tex]H_1=1[/tex]
با عددگزاری و امتحان دستی مقدار های دنباله به ازای ۴ و ۵ به ترتیب ۱۱ و ۲۲ بدست اومد. میدونم توضیحاتم خوب نبود ولی فکر کنم جواب بهینه باشه.