الگوریتم برج هانوی بازگشتی غیر بازگشتی مرتبه زمانی

برای دریافت به ادامه مطلب مراجعه کنید

برچسب ها:

مسئله‌های الگوریتمی: برج هانوی - الگوریتمستان مسئله-الگوریتمی/برج-هانوی/
Jump to حل غیربازگشتی مسئله‌ی برج هانوی‎ - مسئله‌ی برج هانوی علاوه بر روش تابع بازگشتی، راه ... روش غیربازگشتی این مرتبه را به O(1) کاهش داد. البته این مسئله تنها دلیل بررسی روش غیربازگشتی نیست. تبدیل مرتبه‌ی مصرف فضا از O(n) به O(1) زمانی .... به صورتهای زیر تغییر بدین و با شبه کد اینجا بذارید؟
Missing: سورس ‎| ‎Must include: ‎سورس برج هانوی - ویکی‌پدیا، دانشنامهٔ آزاد برج_هانوی
برج هانویْ (در بعضی منابع «برج‌های هانویْ») از سه میله و تعدادی دیسک در اندازه‌های متفاوت .... اما آنچه که راه حل بازگشتی و غیربازگشتی را از هم متمایز می‌کند مرتبه فضای ... تبدیل مرتبه مصرف فضا از ( O( n به ( O( 1 زمانی که مرتبه اجرایی الگوریتم ... پیاده‌سازی کد این الگوریتم را نیز به شما وا می گذاریم تا با کار روی آن به خوبی بر ... الگوریتم و کد برج های هانوی در ++C – اوپن مایند برج-هانوی/
Jul 22, 2014 - مساله ی برج های هانوی (towers of Hanoi) از مساله های معروف در زمینه ی اگوریتم های بازگشتی است که در آن تعدادی دیسک را باید ازمیله ای به میله ی ...
Missing: مرتبه ‎زمانی سورس کد برج هانوی در سی شارپ Hanoi Tower به صورت گرافیکی - پی ... › برنامه نویسی › سی شارپ
سورس کد برج هانوی بصورت در سی شارت دارای دو قسمت حل به روش دستی و حل خود کار با ... برج هانوی (Tower of Hanoi) یکی از مسائل تاریخی مشهور است که در مباحث طراحی الگوریتم به آن ... کاهنان معبد در تلاش بودند تا دیسک های طلائی را از آن میله به یکی دیگر از میله‌ها تحت ... پیاده سازی مسئله برج هانوی بصورت بازگشتی در سی شارپ. دانلود رایگان سورس پروژه برج هانوی به زبان ویژوال بیسیک
Jan 22, 2012 - سورس پروژه برج های هانوی رو براتون آماده کردم در این ساعت از ام اس پی ... اما آنچه که راه حل بازگشتی و غیربازگشتی را از هم متمایز می‌کند مرتبه فضای مصرفی آن است. ... تبدیل مرتبه مصرف فضا از ( O( n به ( O( 1 زمانی که مرتبه اجرایی الگوریتم ... با عرض سلام و خسته نباشید می خواستم خواهش کنم اگه ممکنه سورس کد ... مهندسی کامپیوتر - الگوریتم برج هانوی و برنامه برج هانوی به زبان ++C کامپیوتر و برنامه نویسی
Mar 26, 201  - نباید در هیچ زمانی دیسکی بر روی دیسک با اندازه کوچکتر قرار بگیرد. ... مرتبه اجرایی این الگوریتم ( O( 2n است که چندان مرتبه مطلوبی به نظر نمی‌رسد. ... مساله برج هانوی علاوه بر روش تابع بازگشتی، راه حل‌های غیربازگشتی نیز دارد. ... پیاده‌سازی کد این الگوریتم را نیز به شما وا می‌گذارم تا با کار روی آن به خوبی ... الگوریتم حل مساله برج هانوی به روش بازگشتی در ++C - دانلود رایگان در این بخش ، سورس کد حل مساله برج هانوی در زبان c++ را قرار داده ایم. ... تابع کتابخانه ای time.h به ابتدای برنامه، قبل از اجرای قطعه کد اصلی برنامه باید ... مرتبه اجرایی الگوریتم بازگشتی برج های هانوی را به دست آورید . ... به روش غیر بازگشتی . سورس مسئله برج هانوی به زبان #C - الکترونیکا -سورس-مسئله-برج-هانوی-به-زبان-c.ht...
Mar 13, 2014 - این پروژه حل مسئله برج هانوی به زبان سی شارپ میباشد. ... هدف ما ارائه الگوریتمی است که کمترین توالی حرکت‌ها را برای انتقال ... توجه داشته باشید که بر اساس قانون اول نمی‌توان به غیر از بالاترین دیسک هر ... + ۱ با حل این رابطه بازگشتی داریم: T( n ) = 2n-1 همانطور که مشاهده می‌کنیم مرتبه ... کد تصویری را وارد کنید.
Searches related to کد سورس الگوریتم برج های هانوی بازگشتی غیر بازگشتی مرتبه زمانی پیچیدگی زمانی الگوریتم برج هانوی برج هانوی جاوا برج هانوی با 4 حلقه برج هانوی غیر بازگشتی خرید برج هانوی
برجهای هانوی ساختمان داده فروش برج هانوی مقاله در مورد برج هانوی

برای دریافت به ادامه مطلب مراجعه کنید

 

آنچه در این نوشته می‌خوانید:

   •  برج هانوی
       »  حل بازگشتی مسئله‌ی برج هانوی
       »  تحلیل پیچیدگی زمانی مسئله‌ی برج هانوی
       »  حل غیربازگشتی مسئله‌ی برج هانوی

علاقه‌مندان به مباحث مختلف طراحی الگوریتم و همینطور شرکت‌کنندگان مسابقات برنامه‌نویسی به خوبی می‌دانند که یکی از مهمترین پارامترهای طراحی موفقیت‌آمیز یک الگوریتم، شیوه‌ی صحیح فکر کردن روی حل مسئله است. حل انواع سوالات الگوریتمی به ما کمک می‌کند ذهن خودمان را برای حل مسائل پیچیده‌تر آماده کنیم.

مسئله‌ی برج هانوی (Tower of Hanoi) یکی از مسائل تاریخی مشهور است که در مباحث طراحی الگوریتم نیز به آن پرداخته می‌شود.

به شکل زیر توجه کنید:

سه میله‌ی - میله‌ی مبدأ (A) ، میله‌ی کمکی (B) و میله‌ی مقصد (C) - و تعدادی دیسک در میله‌ی مبدأ داریم. هدف انتقال تمام دیسک‌ها از این میله به میله‌ی مقصد با رعایت دو شرط زیر است:

• در هر زمان فقط یک دیسک را می‌توان جابجا نمود.
• نباید در هیچ زمانی دیسکی بر روی دیسک با اندازه‌ی کوچکتر قرار بگیرد.

به طور حتم می‌توان با روش آزمون و خطا به نتیجه‌ی مطلوب رسید. اما هدف ما ارائه‌ی الگوریتمی برای انتقال دیسک‌ها با کمترین جابجایی ممکن است.

به عنوان مثال، اگر n=2" role="presentation">n=2

باشد:

1) دیسک 1 را به میله‌ی B منتقل می‌کنیم (A→B)" role="presentation">(A→B)

:

2) دیسک 2 را به میله‌ی C منتقل می‌کنیم (A→C)" role="presentation">(A→C)

:

3) دیسک 1 را به میله‌ی C منتقل می‌کنیم (B→C)" role="presentation">(B→C)

:

توجه داشته باشید که بر اساس قانون اول، نمی‌توان به غیر از بالاترین دیسک هر میله، به دیسک دیگری از آن دسترسی پیدا کرد.

حل بازگشتی مسئله‌ی برج هانوی

برای اینکه بتوان از روش بازگشتی تقسیم و حل (یا تقسیم و غلبه - Divide and Conquer) برای حل یک مسئله استفاده نمود، مسئله باید قابلیت خرد شدن به زیرمسئله‌هایی از همان نوع مسئله‌ی اصلی و اندازه‌ی کوچکتر را داشته باشد. این ویژگی در مورد مسئله‌ی برج هانوی صدق می‌کند.

ایده‌ی اصلی از آنجا ناشی می‌شود که برای جابجا کردن بزرگترین دیسک از میله‌ی A به میله‌ی C، ابتدا باید تمامی دیسک‌های کوچکتر به میله‌ی B منتقل شوند. پس از تمام شدن این مرحله، دیسک بزرگ را از میله‌ی A به میله‌ی C منتقل کرده و مجددا به کمک میله‌ی A تمامی دیسک‌های میله‌ی B را به میله‌ی C منتقل می‌کنیم. پس به طور خلاصه می‌توان گفت:

مرحله‌ی یک: n−1" role="presentation">n−1

دیسک بالایی میله‌ی مبدأ با شرایط ذکر شده و به کمک میله‌ی C به میله‌ی B منتقل می‌شوند.

مرحله‌ی دو: بزرگترین دیسک از میله‌ی مبدأ به میله‌ی مقصد منتقل می‌شود.

مرحله‌ی سه: n−1" role="presentation">n−1

دیسک میله‌ی B با کمک گرفتن از میله‌ی A به میله‌ی مقصد منتقل می‌شوند.

می‌بینیم که توانستیم عملیات جابجا کردن n" role="presentation">n

دیسک را به دو عملیات مشابه ولی با اندازه‌ی کمتر و یک عملیات ساده تقسیم کنیم.

تابع بازگشتی زیر به زبان ++C ترتیب حرکت‌ها را چاپ می‌کند:

1	void hanoi(int nDisk, char start, char temp, char finish){
2	if(nDisk == 1)
3	cout << start << " -> " << finish << endl;
4	else{
5	hanoi(nDisk - 1, start, finish, temp);
6	cout << start << " -> " << finish << endl;
7	hanoi(nDisk - 1, temp, start, finish);
8	}
9	}

برای مثال، فراخوانی تابع به صورت ('hanoi(3, ‘A’, ‘B’, ‘C، مسئله‌ی برج هانوی را با سه دیسک که در میله‌ی A قرار دارند و با کمک میله‌ی B به میله‌ی C منتقل خواهند شد، حل می‌کند.

واضح است که تابع بازگشتی فوق کمترین تعداد حرکت را چاپ می‌کند. چرا که برای جابجا کردن بزرگترین دیسک از پایین میله‌ی A، بقیه‌ی دیسک‌ها باید در میله‌ی B باشند. فقط در این صورت این دیسک جابجا می‌شود. در فراخوانی‌های بعدی، دیسک دوم از نظر بزرگی جابجا می‌شود و الی آخر. پس در این فراخوانی‌ها جابجایی بیهوده‌ای صورت نمی‌گیرد. نیز توالی حرکت‌ها برای هر n" role="presentation">n

منحصر بفرد است. یعنی برای یک n" role="presentation">n

مشخص، دو توالی متمایز از جابجایی‌ها وجود ندارد که تعداد جابجایی آنها کمتر یا مساوی این حالت باشد.

تحلیل پیچیدگی زمانی مسئله‌ی برج هانوی

در حالت کلی می‌خواهیم بدانیم اگر تعداد دیسک‌ها n" role="presentation">n

باشد، کمترین تعداد حرکت برای جابجا نمودن دیسک‌ها چقدر است؟

فرض کنید T(n)" role="presentation">T(n)

تعداد حرکت‌های لازم جهت انتقال n" role="presentation">n دیسک به مقصد باشد. بر اساس توضیحات فوق، تعداد T(n−1)" role="presentation">T(n−1) حرکت برای انتقال n−1" role="presentation">n−1 دیسک به میله‌ی کمکی، یک حرکت برای انتقال بزرگترین دیسک به میله‌ی مقصد و مجددا T(n−1)" role="presentation">T(n−1) حرکت برای انتقال n−1" role="presentation">n−1

دیسک موجود در میله‌ی کمکی به میله‌ی مقصد نیاز است. پس:

T(n)=2T(n−1)+1" role="presentation">T(n)=2T(n−1)+1

با حل این رابطه‌ی بازگشتی به روش‌های ریاضی، به نتیجه‌ی زیر می‌رسیم:

T(n)=2n−1" role="presentation">T(n)=2n−1

مرتبه‌ی اجرایی این الگوریتم O(2n)" role="presentation">O(2n)

است که چندان مرتبه‌ی مطلوبی به نظر نمی‌رسد. اما همانگونه که بحث شد، این روش حداقل تعداد حرکت‌های ممکن را می‌دهد؛ و هرگز نمی‌توان روش دیگری با مرتبه‌ی پایین‌تر برای حل آن یافت.

حل غیربازگشتی مسئله‌ی برج هانوی

مسئله‌ی برج هانوی علاوه بر روش تابع بازگشتی، راه حل‌های غیربازگشتی نیز دارد. تا به اینجا مشخص شده است که بهترین راه حل برای جابجا کردن n" role="presentation">n

دیسک، به تعداد نمایی حرکت نیاز دارد. در نتیجه مرتبه‌ی راه حل‌های آن در بهینه‌ترین حالت - چه بازگشتی و چه غیربازگشتی - از مرتبه‌ی 2n" role="presentation">2n

خواهد بود. اما آنچه که راه حل بازگشتی و غیربازگشتی را از هم متمایز می‌کند، مرتبه‌ی فضای مصرفی آن است.

حل بازگشتی مسئله، فراخوانی‌های تو در تو و فضای پشته از مرتبه‌ی O(n)" role="presentation">O(n)

نیاز دارد. در حالی که می‌توان با استفاده از روش غیربازگشتی این مرتبه را به O(1)" role="presentation">O(1) کاهش داد. البته این مسئله تنها دلیل بررسی روش غیربازگشتی نیست. تبدیل مرتبه‌ی مصرف فضا از O(n)" role="presentation">O(n) به O(1)" role="presentation">O(1) زمانی که مرتبه‌ی اجرای الگورینم O(2n)" role="presentation">O(2n)

است، چندان قابل توجه نیست. دلیل دیگر می‌تواند این باشد که برخی زبان‌های برنامه‌نویسی از فراخوانی بازگشتی توابع پشتیبانی نمی‌کنند و مجبور به استفاده ار روشهای غیربازگشتی هستند. اما دلیل اصلی این است که با بررسی این روش‌ها، تمرین کوچکی برای تبدیل الگوریتم‌های بازگشتی به غیربازگشتی انجام می‌دهیم.

تا کنون چندین روش مختلف جهت پیاده‌سازی غیربازگشتی حل مسئله‌ی برج هانوی ارائه شده است که در اینجا دو روش معرفی می‌شود. توجه داشته باشید که همه‌ی جزئیات حل مسئله به صورت دقیق و مشروح مطرح نمی‌شود و استدلال قسمتی از نتیجه‌گیری‌ها به عنوان تمرین به خواننده واگذار می‌گردد.

روش اول- حل مسئله‌ی برج هانوی را می‌توان معادل پاسخ دادن به این سوال دانست که: در هر مرحله کدام دیسک به کدام میله منتقل می‌شود؟

سوال اول: کدام دیسک؟ فرض کنیم دیسک‌هایی به شعاع y" role="presentation">y

، x" role="presentation">x و z" role="presentation">z که رابطه‌ی x<y<z" role="presentation">x<y<z

را با هم دارند، کوچکترین دیسک هر میله باشند. به عبارت دیگر، این سه دیسک بالاترین دیسک‌های میله‌ها هستند که قابلیت جابجایی دارند. اگر میله‌ای شامل هیچ دیسکی نباشد، دیسکی با شعاع بی‌نهایت را برای آن در نظر می‌گیریم. حال به استدلال‌های منطقی زیر توجه کنید:

استدلال شماره‌ی 1) x" role="presentation">x

برابر 1 است. چرا که بر اساس قوانین حاکم بر مسئله، هیچ دیسکی نمی‌تواند روی دیسک 1 قرار بگیرد. در نتیجه این دیسک همیشه بالاترین دیسک موجود در یکی از میله‌ها است.

استدلال شماره‌ی 2) در آغاز همه‌ی دیسک‌ها روی یک میله قرار دارند که دیسک 1 بالاترین دیسک آن است. پس در اولین مرحله دیسک 1 جابجا می‌شود.

استدلال شماره‌ی 3) دیسک‌هایی که طی دو مرحله‌ی متوالی جابجا می‌شوند حتما متمایز هستند. این مسئله از بهینه بودن راه حل ناشی می‌شود. اگر قرار باشد طی دو مرحله‌ی متوالی یک دیسک خاص را جابجا کنیم، می‌توانیم دو مرحله را با هم ادغام کرده و کل جابجایی را یکجا انجام دهیم.

استدلال شماره‌ی 4) با توجه به قوانین حاکم بر مسئله، دیسک z" role="presentation">z

نمی‌تواند حرکت کند. چرا که دیسک‌های x" role="presentation">x و y" role="presentation">y

هر دو از آن کوچکتر هستند.

استدلال شماره‌ی 2 می‌گوید که اولین حرکت همیشه با دیسک 1 است. استدلال شماره‌ی 3 می‌گوید حرکت بعدی با دیسکی غیر از دیسک 1 است. استدلال شماره‌ی 4 می‌گوید این دیسک نمی‌تواند بزرگترین دیسک موجود در بالای میله‌ها باشد. پس در مرحله‌ی بعدی دیسک y" role="presentation">y

جابجا خواهد شد. و بالاخره حرکت بعدی باز هم با دیسک 1 است (چرا؟).

پس با بررسی منطقی خود به این نتیجه رسیدیم که دیسک 1 و دیسکی که بزرگترین دیسک در آن مرحله نیست، به صورت متناوب جابجا می‌شوند. مراحل با شماره‌ی فرد برای دیسک 1 و مراحل با شماره‌ی زوج برای دیسک y.

سوال دوم: کدام میله؟ حال که می‌دانیم در هر مرحله کدام دیسک جابجا می‌شود، به سراغ میله‌ی مقصد می‌رویم. در مراحل زوج که دیسک y" role="presentation">y

منتقل خواهد شد، تشخیص میله‌ی مقصد بسیار آسان است. چرا که روی یکی از میله‌ها دیسک 1 قرار دارد که دیسک y" role="presentation">y نمی‌تواند روی آن قرار بگیرد. در نتیجه به تنها میله‌ی باقیمانده (میله‌ی دیسک z" role="presentation">z

) منتقل می‌شود. در مورد مراحلی هم که دیسک 1 قرار است جابجا شود، می‌توان اینطور استدلال کرد:

فرض کنیم دیسک 1 روی میله‌ی A قرار داشته باشد و آن را به میله‌ی C منتقل کنیم. در مرحله‌ی بعدی دیسک y جابجا می‌شود. و در مرحله‌ی بعد باز هم دیسک 1 باید جابجا شود. حال اگر این دیسک را به میله‌ی A بازگردانیم، به نوعی کار اضافی و بازگشت به عقب انجام داده‌ایم. برای آشکار شدن این موضوع کافی است مسئله‌ی برج هانوی را با دو دیسک حل کنید و در حرکت دوم دیسک 1، آن را به میله‌ای بازگردانید که از آن آمده بود. پس می‌توان گفت: در حرکت‌های متوالی، دیسک شماره‌ی 1 به میله‌ای حرکت می‌کند که از آن به میله‌ی فعلی خود نیامده است. این مسئله نه تنها در مورد دیسک 1 که در مورد همه‌ی دیسک‌ها صادق است. یعنی همه‌ی دیسک‌ها در حرکت‌های خود به سمت میله‌ای می‌روند که در حرکت قبلی خود از آن نیامده‌اند. اما لحاظ کردن این شرط برای این دیسک‌ها لازم نیست. چرا که در هر مرحله، تنها یک انتخاب برای حرکت خود دارند.

تنها مسئله‌ی باقیمانده، میله‌ی مقصد دیسک 1 در اولین حرکت خود است. زمانی که این دیسک اولین حرکت خود را انجام می‌دهد، نمی‌توان از استدلال فوق برای تشخیص میله‌ی مقصد استفاده کرد (چرا؟). استدلال این قسمت را هم که چندان دشوار نیست به شما وا می‌گذارم و تنها به بیان نتیجه می‌پردازم: اگر تعداد دیسک‌ها زوج باشد، دیسک 1 را در اولین حرکت به میله‌ی کمکی (یعنی میله‌ی B) و در غیر اینصورت به میله‌ی مقصد (یعنی میله‌ی C) منتقل می‌کنیم.

به این ترتیب حل مسئله‌ی برج هانوی به صورت غیربازگشتی پیاده‌سازی می‌شود. حال می‌دانیم که در هر مرحله کدام دیسک به کدام میله منتقل می‌شود.

روش دوم: یکی دیگر از روش‌های پیاده‌سازی غیربازگشتی حل مسئله‌ی برج هانوی که در یک منبع اینترنتی مشاهده کردم، از الگوریتم زیر تبعیت می‌کند:

1	void hanoi(int nDisk, char start, char temp, char finish){
2	int max = nDisk;
3	char dest = finish;
4	int disk = max;
5	while(true){
6	while(disk > 0){
7	if(moving disk succeeds)
8	{
9	if(disk == max){
10	max--;
11	if(max == 0)
12	return;
13	}
14	dest = the final place of max;
15	}
16	else
17	dest = the alternative place between dest and the current place of disk;
18	disk--;
19	}
20	p and q = the places different of dest;
21	disk = the smaller of the disks on top of p and q;
22	dest = the place between p and q with greater disk on top;
23	}
24	}

تشریح عملکرد این الگوریتم یک تمرین خوب است. توضیح اینکه این الگوریتم بر خلاف الگوریتم قبلی که سعی در یافتن قوانین حرکت دیسک‌ها داشت، دقیقا همان روش بازگشتی را شبیه‌سازی می‌کند.

در پایان توجه داشته باشید که دو روش ذکر شده، تنها روشهای پیاده‌سازی غیربازگشتی حل مسئله نیستند.