۰
subtitle
ارسال: #۱
مسئله ای از برج هانوی
سلام
می شه این سوال رو حل کنید.
اگر در برج هانوی سکه های با شماره‌ی فرد و زوج به ترتیب در میله های ۱ و ۲ باشند، با حداقل حرکت‌ها می خواهیم همه سکه‌ها را در میله ۳ قرار دهیم چگونه این کار را می شود انجام داد ؟
می شه این سوال رو حل کنید.
اگر در برج هانوی سکه های با شماره‌ی فرد و زوج به ترتیب در میله های ۱ و ۲ باشند، با حداقل حرکت‌ها می خواهیم همه سکه‌ها را در میله ۳ قرار دهیم چگونه این کار را می شود انجام داد ؟
۰
ارسال: #۲
RE: سوال: برج هانوی
اگه n حلقه‌ی فرد روی ۱ و n حلقه‌ی زوج روی ۲ باشه و بخوایم همه‌ی ۲n حلقه رو روی ۳ قرار بدیم، اول فرض میکنیم که مسئله برای n-1 تا حلقه‌ی بالایی روی میله های ۱ و ۲ حل شده باشه، یعنی در میله‌ی ۳ به تعداد ۲n-2 حلقه که شرایط مسئله‌ی برج هانوی رو ارضا میکنه قرار داره، اون وقت مسئله رو برای این دو حلقه‌ی باقی مانده در میله های ۱ و ۲ حل میکنیم. که باید حلقه‌ی کوچکتر رو روی حلقه‌ی بزرگتر قرار بدیم، بقیه‌ی کاری که از این جا به بعد باقی مانده کاملاً شبیه همان مسئله‌ی هانوی کلاسیک هست. یعنی باید ۲n-2 حلقه‌ی روی میله‌ی ۳ را به روی ۲ حلقه‌ی روی میله‌ی دیگر انتقال دهیم. بعد از این کار ۲n حلقه‌ی مرتب خواهیم داشت، سرانجام همه را به میله‌ی شماره ۳ منتقل میکنیم.
۰
ارسال: #۳
سوال : برج هانوی
سلام.
سوال خیلی قشنگی بود. یکم درمورد جوابم توضیح میدم. فکر کنم جوابم درست باشه ولی شاید بشه یکم ساده تر نوشت.
صرف نظر از زوج یا فرد بودن تعداد سکه ها ما 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 حرکت نیاز داریم. چون اول باید همه سکه ها بغی از دو سکه انتهایی رو به میله کمکه ببریم و بعد سکه یکی مونده به آخر رو روی سکه آخر قرار داده و بعد سکه هارو از میله کمکی به میله اولیه برگردونیم.
جواب مسئلمونو با فرمول مینویسم:
با عددگزاری و امتحان دستی مقدار های دنباله به ازای ۴ و ۵ به ترتیب ۱۱ و ۲۲ بدست اومد. میدونم توضیحاتم خوب نبود ولی فکر کنم جواب بهینه باشه.
سوال خیلی قشنگی بود. یکم درمورد جوابم توضیح میدم. فکر کنم جوابم درست باشه ولی شاید بشه یکم ساده تر نوشت.
صرف نظر از زوج یا فرد بودن تعداد سکه ها ما 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]
با عددگزاری و امتحان دستی مقدار های دنباله به ازای ۴ و ۵ به ترتیب ۱۱ و ۲۲ بدست اومد. میدونم توضیحاتم خوب نبود ولی فکر کنم جواب بهینه باشه.
۰
ارسال: #۴
سوال: برج هانوی
سلام
۵۴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 تکرار میکنیم.
البته اگر سکه‌ها پشت سر هم نباشن (که منطقاً نبایدم باشن) مقایسه هم لازم میشه که بسته به این که بدونیم در دنیای واقعی چه سکه هایی وجود داره یا نه عملیات اضافی رو اعمال می کنیم.
این یه نظر بود، همیشه ممکنه راه حل بهتری وجود داشته باشه.....
۵۴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 تکرار میکنیم.
البته اگر سکه‌ها پشت سر هم نباشن (که منطقاً نبایدم باشن) مقایسه هم لازم میشه که بسته به این که بدونیم در دنیای واقعی چه سکه هایی وجود داره یا نه عملیات اضافی رو اعمال می کنیم.
این یه نظر بود، همیشه ممکنه راه حل بهتری وجود داشته باشه.....
ارسال: #۵
RE: سوال: برج هانوی
(۰۷ آذر ۱۳۸۹ ۰۳:۰۳ ب.ظ)raha نوشته شده توسط: سلام
۵۴m4n3h عزیز فکر می کنم راه حلتون اگه درست فهمیده باشم، مشکل داره فرض کنید ۲n-2 سکه توی میله‌ی سوم داریم الان باید این ۲n-2 سکه رو به میله ای که اون دوتا سکه‌ی بزرگتر توش نیست انتقال بدیم تا میله‌ی ۳ خالی بشه و بتونیم اون دو تا سکه رو بذاریم اونجا.در حالی که سکه‌ی کوچیک روی سکه‌ی بزرگتر هست نمی تونیم سکه‌ی بزرگتر رو اول انتقال بدیم.در واقع سکه بزررگه گیر میفته!
راه حلم درسته!
برای این که من نگفتم ۲n-2 سکه رو انتقال میدم به میله‌ی خالی! من گفتم: ۲n-2 حلقه‌ی روی میله‌ی ۳ را به روی ۲ حلقه‌ی روی میله‌ی دیگر انتقال دهیم! و در این صورت مسئله تبدیل میشه به همون هانوی کلاسیک!
ارسال: #۶
RE: سوال: برج هانوی
این الگوریتمی که من گفتم، مرتبه ش (n×(۴^n هست!
چه طوری n-1 حلقه رو میذارید روی میله‌ی b در حالی که روی میله‌ی b (اون بالای بالاش!) حلقه به قطر ۱ قرار داره؟ از روش خاصی این وسط استفاده میکنید؟ (چون مستقیم که نمیشه!)
(۰۷ آذر ۱۳۸۹ ۰۳:۰۳ ب.ظ)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 تا حلقه رو میذاریم روی یه میله، در این حالت دیگه همه مرتب شدن! یعنی یکی در میون زوج و فرد شدن! و مسئله تبدیل شده به هانوی معمولی!
اگه شما هم انتقال رو مثل من انجام میدید، پس بعد از انتقال n-1 تا حلقه از a به b،ا ۲n-1 تا عنصر مرتب خواهید داشت و یه بزرگترین حلقه در یک میله‌ی دیگه!
و من نمیدونم چرا شما وقتی n-1 تا رو از a بردید به b و ۲n-1 تا حلقه‌ی مرتب تشکیل دادید، بعد n-1تاش رو بر میگردونید به b! خب کلاً همون جا هانوی رو حل کنید دیگه!
در ضمن، رند معنیش بد نیست؟
اگه شما هم انتقال رو مثل من انجام میدید، پس بعد از انتقال n-1 تا حلقه از a به b،ا ۲n-1 تا عنصر مرتب خواهید داشت و یه بزرگترین حلقه در یک میله‌ی دیگه!
و من نمیدونم چرا شما وقتی n-1 تا رو از a بردید به b و ۲n-1 تا حلقه‌ی مرتب تشکیل دادید، بعد n-1تاش رو بر میگردونید به b! خب کلاً همون جا هانوی رو حل کنید دیگه!
در ضمن، رند معنیش بد نیست؟
ارسال: #۸
RE: سوال: برج هانوی
(۰۷ آذر ۱۳۸۹ ۱۱:۵۹ ب.ظ)۵۴m4n3h نوشته شده توسط: من وقتی میگم ۲n-2 تا حلقه رو میذاریم روی یه میله، در این حالت دیگه همه مرتب شدن! یعنی یکی در میون زوج و فرد شدن! و مسئله تبدیل شده به هانوی معمولی!می دونید از اول ما دو نفر دو دید مختلف به این مسئله داشتیم شما تنها رعایت کوچیک و بزرگی سکه‌ها براتون مهم بود وبه این مسئله که روی یه سری عدد زوج/فرد مرتب دارید یه سری اعداد متوالی رو می چینید اهمیت نمی دادید و من دو تا آرایه مرتب یکی زوج ودیگری فرد رو در نظر می گرفتم که میشه یکی رو ادامه‌ی دیگری قرار داد فقط باید ترتیب حفظ بشه و من چون با دید خودم راه حل شما رو می خوندم برداشت خودم رو داشتم یعنی از اولین پستتون تا آخری ۳ - ۴ تا الگوریتم متفاوت برداشت کردم! و توی همین آخرین پست فهمیدم که شما کلاً یه دید دیگه ای دارین .
اگه شما هم انتقال رو مثل من انجام میدید، پس بعد از انتقال n-1 تا حلقه از a به b،ا ۲n-1 تا عنصر مرتب خواهید داشت و یه بزرگترین حلقه در یک میله‌ی دیگه!
و من نمیدونم چرا شما وقتی n-1 تا رو از a بردید به b و ۲n-1 تا حلقه‌ی مرتب تشکیل دادید، بعد n-1تاش رو بر میگردونید به b! خب کلاً همون جا هانوی رو حل کنید دیگه!
در ضمن، رند معنیش بد نیست؟
بهر حال ممنون از وقتی که گذاشتین ؛ بحث خوبی بود.
راستی عزیزم رند اصلاً معنیش بد نیست .با توجه به برداشت یکی مونده به آخرم
فکر میکردم شما یه قسمت از راهتون با من مشترکه 
رند خودمونیش یعنی ناقلا بازم ممنون.
ارسال: #۹
RE: سوال: برج هانوی
(۰۷ آذر ۱۳۸۹ ۱۱:۵۹ ب.ظ)۵۴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
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close