ارسال: #۱

۳۰ آبان ۱۳۸۹, ۰۵:۲۸ ب.ظ

Josephus پرسیده:

مسئله ای از برج هانوی

سلام
می شه این سوال رو حل کنید.

اگر در برج هانوی سکه های با شماره‌ی فرد و زوج به ترتیب در میله های ۱ و ۲ باشند، با حداقل حرکت‌ها می خواهیم همه سکه‌ها را در میله ۳ قرار دهیم چگونه این کار را می شود انجام داد ؟

ارسال: #۲

۰۲ آذر ۱۳۸۹, ۰۱:۳۵ ب.ظ

۵۴m4n3h پاسخ داده:

RE: سوال‌: برج هانوی

اگه n حلقه‌ی فرد روی ۱ و n حلقه‌ی زوج روی ۲ باشه و بخوایم همه‌ی ۲n حلقه رو روی ۳ قرار بدیم، اول فرض میکنیم که مسئله برای n-1 تا حلقه‌ی بالایی روی میله های ۱ و ۲ حل شده باشه، یعنی در میله‌ی ۳ به تعداد ۲n-2 حلقه که شرایط مسئله‌ی برج هانوی رو ارضا میکنه قرار داره، اون وقت مسئله رو برای این دو حلقه‌ی باقی مانده در میله های ۱ و ۲ حل میکنیم. که باید حلقه‌ی کوچکتر رو روی حلقه‌ی بزرگتر قرار بدیم، بقیه‌ی کاری که از این جا به بعد باقی مانده کاملاً شبیه همان مسئله‌ی هانوی کلاسیک هست. یعنی باید ۲n-2 حلقه‌ی روی میله‌ی ۳ را به روی ۲ حلقه‌ی روی میله‌ی دیگر انتقال دهیم. بعد از این کار ۲n حلقه‌ی مرتب خواهیم داشت، سرانجام همه را به میله‌ی شماره ۳ منتقل میکنیم.

ارسال: #۳

۱۷ اسفند ۱۳۹۰, ۰۶:۰۳ ق.ظ

Jooybari پاسخ داده:

سوال : برج هانوی

سلام.
سوال خیلی قشنگی بود. یکم درمورد جوابم توضیح میدم. فکر کنم جوابم درست باشه ولی شاید بشه یکم ساده تر نوشت.
صرف نظر از زوج یا فرد بودن تعداد سکه ها ما 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 حرکت نیاز داریم. چون اول باید همه سکه ها بغی از دو سکه انتهایی رو به میله کمکه ببریم و بعد سکه یکی مونده به آخر رو روی سکه آخر قرار داده و بعد سکه هارو از میله کمکی به میله اولیه برگردونیم.
جواب مسئلمونو با فرمول مینویسم:

$S_n=P_{n-1} H_{n-1} 1$

$P_m=S_{m-2} H_{m-2} 1$

$\Rightarrow S_n=S_{n-3} H_{n-1} H_{n-3} 2$

$S_1=1$

$S_2=2$

$S_3=5$

$H_n=2H_{n-1} 1$

$H_1=1$

با عددگزاری و امتحان دستی مقدار های دنباله به ازای ۴ و ۵ به ترتیب ۱۱ و ۲۲ بدست اومد. میدونم توضیحاتم خوب نبود ولی فکر کنم جواب بهینه باشه.

ارسال: #۴

۰۷ آذر ۱۳۸۹, ۰۳:۰۳ ب.ظ

raha پاسخ داده:

سوال‌: برج هانوی

سلام
۵۴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 پاسخ داده:

RE: سوال‌: برج هانوی

(۰۷ آذر ۱۳۸۹ ۰۳:۰۳ ب.ظ)raha نوشته شده توسط: سلام
۵۴m4n3h عزیز فکر می کنم راه حلتون اگه درست فهمیده باشم‌، مشکل داره فرض کنید ۲n-2 سکه توی میله‌ی سوم داریم الان باید این ۲n-2 سکه رو به میله ای که اون دوتا سکه‌ی بزرگتر توش نیست انتقال بدیم تا میله‌ی ۳ خالی بشه و بتونیم اون دو تا سکه رو بذاریم اونجا.در حالی که سکه‌ی کوچیک روی سکه‌ی بزرگتر هست نمی تونیم سکه‌ی بزرگتر رو اول انتقال بدیم.در واقع سکه بزررگه گیر میفته!

راه حلم درسته!
برای این که من نگفتم ۲n-2 سکه رو انتقال میدم به میله‌ی خالی! من گفتم‌: ۲n-2 حلقه‌ی روی میله‌ی ۳ را به روی ۲ حلقه‌ی روی میله‌ی دیگر انتقال دهیم! و در این صورت مسئله تبدیل میشه به همون هانوی کلاسیک!

ارسال: #۶

۰۷ آذر ۱۳۸۹, ۱۰:۲۹ ب.ظ

۵۴m4n3h پاسخ داده:

RE: سوال‌: برج هانوی

این الگوریتمی که من گفتم، مرتبه ش (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-2 تا حلقه رو میذاریم روی یه میله، در این حالت دیگه همه مرتب شدن! یعنی یکی در میون زوج و فرد شدن! و مسئله تبدیل شده به هانوی معمولی!
اگه شما هم انتقال رو مثل من انجام میدید، پس بعد از انتقال n-1 تا حلقه از a به b،ا ۲n-1 تا عنصر مرتب خواهید داشت و یه بزرگترین حلقه در یک میله‌ی دیگه!
و من نمیدونم چرا شما وقتی n-1 تا رو از a بردید به b و ۲n-1 تا حلقه‌ی مرتب تشکیل دادید، بعد n-1تاش رو بر میگردونید به b! خب کلاً همون جا هانوی رو حل کنید دیگه!

در ضمن، رند معنیش بد نیست؟

ارسال: #۸

۰۸ آذر ۱۳۸۹, ۰۱:۱۷ ق.ظ

raha پاسخ داده:

RE: سوال‌: برج هانوی

(۰۷ آذر ۱۳۸۹ ۱۱:۵۹ ب.ظ)۵۴m4n3h نوشته شده توسط: من وقتی میگم ۲n-2 تا حلقه رو میذاریم روی یه میله، در این حالت دیگه همه مرتب شدن! یعنی یکی در میون زوج و فرد شدن! و مسئله تبدیل شده به هانوی معمولی!
اگه شما هم انتقال رو مثل من انجام میدید، پس بعد از انتقال n-1 تا حلقه از a به b،ا ۲n-1 تا عنصر مرتب خواهید داشت و یه بزرگترین حلقه در یک میله‌ی دیگه!
و من نمیدونم چرا شما وقتی n-1 تا رو از a بردید به b و ۲n-1 تا حلقه‌ی مرتب تشکیل دادید، بعد n-1تاش رو بر میگردونید به b! خب کلاً همون جا هانوی رو حل کنید دیگه!

در ضمن، رند معنیش بد نیست؟

می دونید از اول ما دو نفر دو دید مختلف به این مسئله داشتیم شما تنها رعایت کوچیک و بزرگی سکه‌ها براتون مهم بود وبه این مسئله که روی یه سری عدد زوج/فرد مرتب دارید یه سری اعداد متوالی رو می چینید اهمیت نمی دادید و من دو تا آرایه مرتب یکی زوج ودیگری فرد رو در نظر می گرفتم که میشه یکی رو ادامه‌ی دیگری قرار داد فقط باید ترتیب حفظ بشه و من چون با دید خودم راه حل شما رو می خوندم برداشت خودم رو داشتم یعنی از اولین پستتون تا آخری ۳ - ۴ تا الگوریتم متفاوت برداشت کردم‌! و توی همین آخرین پست فهمیدم که شما کلاً یه دید دیگه ای دارین .
بهر حال ممنون از وقتی که گذاشتین ؛ بحث خوبی بود.
راستی عزیزم رند اصلاً معنیش بد نیست .با توجه به برداشت یکی مونده به آخرم Big Grin

فکر میکردم شما یه قسمت از راهتون با من مشترکه Smile

رند خودمونیش یعنی ناقلا Big Grin

بازم ممنون.

ارسال: #۹

۱۷ اسفند ۱۳۹۰, ۰۳:۴۴ ق.ظ

لهمشد پاسخ داده:

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

[/code]

موضوع‌های مرتبط با این موضوع...
موضوع:		نویسنده	پاسخ:	بازدید:	آخرین ارسال
	کمک به حل مسئله	Moha33	۰	۱,۴۲۰	۰۵ تیر ۱۴۰۰ ۰۹:۴۲ ق.ظ آخرین ارسال: Moha33
	کامپیوتر یا هنر، مسئله این است	arian_61	۲	۴,۸۴۴	۲۵ دى ۱۳۹۸ ۱۱:۳۱ ق.ظ آخرین ارسال: packationmachinery
	مسئله n_وزیر	Sanazzz	۲	۳,۵۹۰	۱۱ بهمن ۱۳۹۷ ۰۳:۰۳ ب.ظ آخرین ارسال: Sanazzz
	فروش کتاب ۳۰۰۰ مسئله حل شده شبکه فقط ۱۵۰۰۰ تومن کاملا نو	Maral93	۰	۱,۹۱۵	۲۵ مهر ۱۳۹۶ ۱۰:۴۰ ب.ظ آخرین ارسال: Maral93
	آزاد یا غیرانتفاعی یا پردیس؟ مسئله این است!	setayesh20	۰	۲,۳۱۳	۱۳ شهریور ۱۳۹۶ ۱۰:۵۷ ق.ظ آخرین ارسال: setayesh20
	مسئله Betweenness درس شبکه های اجتماعی	fo-eng	۱	۳,۱۸۴	۰۵ شهریور ۱۳۹۶ ۰۸:۰۷ ق.ظ آخرین ارسال: M.Amin.M
	مسئله ی ارضای محدودیت - سراسری ۸۹	ali.majed.ha	۴	۳,۸۲۷	۱۸ فروردین ۱۳۹۶ ۰۱:۵۳ ب.ظ آخرین ارسال: Saman
	مسئله کشیشان و آدمخواران	zahramousavi	۱	۲,۲۸۱	۰۴ اسفند ۱۳۹۵ ۱۲:۰۲ ب.ظ آخرین ارسال: zahramousavi
	سوال اول ۶۰۰ مسئله !	M a h d i	۳	۳,۵۰۸	۲۵ بهمن ۱۳۹۵ ۰۴:۵۹ ب.ظ آخرین ارسال: Behnam‌
	نظرتون در مورد کتاب ۶۰۰ مسئله از داده ساختارها و الگوریتم ها - دکتر قدسی ؟	tarane.68	۲۶	۳۵,۲۱۳	۲۵ بهمن ۱۳۹۵ ۱۲:۱۹ ب.ظ آخرین ارسال: taha_h

مسئله ای از برج هانوی

مسئله ای از برج هانوی

RE: سوال‌: برج هانوی

سوال : برج هانوی

سوال‌: برج هانوی

RE: سوال‌: برج هانوی

RE: سوال‌: برج هانوی

سوال‌: برج هانوی

RE: سوال‌: برج هانوی

RE: سوال‌: برج هانوی

Can I see some ID?

Feeling left out?

رمزت رو فراموش کردی؟

Feeling left out?