صفحه اصلی

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

آشنایی با توابع دوست کلاس در زبان برنامه‌نویسی ++C و کاربرد آنها در سربارگذاری عملگرها
بررسی سوال مسابقات برنامه‌نویسی Turn for MEGA، و راه حل آن
بررسی مساله برج هانوی و روش‌های حل بازگشتی و غیربازگشتی آن
پنج نکته آموزنده در مورد برنامه‌نویسی به زبان برنامه‌نویسی ++C
بررسی مساله مربی ناامید، از سوالات مسابقات برنامه‌نویسی ACM
بحث در مورد ضرب زنجیره‌ای ماتریس‌ها و روش پیاده‌سازی الگوریتم پرانتزبندی بهینه آن با روش تقسیم و حل و روش برنامه‌نویسی پویا
بررسی معمای هشت وزیر یا n وزیر و راهبرد عقبگرد برای حل مساله
بررسی روش‌های بسط لاپلاس، گاوس، فرمول تحویل و ساروس، برای محاسبه دترمینان ماتریس مربعی، و پیچیدگی زمانی آنها
آشنایی با مفهوم و عملکرد اشاره‌گرها در زبان برنامه‌نویسی ++C و ارائه مثالهایی از کاربرد آن
آشنایی با حلقه‌های تکرار در زبان برنامه‌نویسی ++C و دستورات کنترلی مورد استفاده در آن
آشنایی با روش مرتب‌سازی درجی، همراه با قطعه کد به زبان برنامه‌نویسی ++C
آشنایی با مفهوم سربارگذاری عملگرها در زبان ++C
آشنایی با صف اولویتی (Priority Queue)، کاربردها و نحوه پیاده‌سازی آن
آشنایی با روش برنامه‌نویسی پویا (یا برنامه‌ریزی پویا - Dynamic Programming) به عنوان یکی از روش‌های پر کاربرد طراحی الگوریتم و یافتن راه حل بهینه مسائل، و روش محاسبه دنباله فیبوناچی

  »   برج هانوی
              پنجشنبه، 1 مهر ماه 1389

مطلبی که می‌خوانید، ویراست دوم مطلبی است که نسخه اولیه آن با عنوان "حل مساله برج هانوی به روش غیربازگشتی" از طریق وب‌سایت برنامه‌نویسی و طراحی الگوریتم (عنوان و طرح پیشین وب‌سایت الگوریتمستان) منتشر شده بود.

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

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

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

 

برج هانوی

 

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

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

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

به عنوان مثال، اگر n = 2 باشد:

 

برج هانوی

 

1) دیسک 1 را به میله B منتقل می‌کنیم (A --> B):

 

برج هانوی

 

2) دیسک 2 را به میله C منتقل می‌کنیم (A --> C):

 

برج هانوی

 

3) دیسک 1 را به میله C منتقل می‌کنیم (B --> C):

 

برج هانوی

 

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

 

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

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

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

مرحله یک: n - 1 دیسک بالایی میله مبدا با شرایط ذکر شده و به کمک میله C به میله B منتقل می‌شوند.

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

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

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

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

 

void hanoi( int nDisk, char start, char temp, char finish )

{

  if( nDisk == 1 )

  {

    cout << start << " --> " << finish << endl;

  }

  else

  {

    hanoi( nDisk - 1, start, finish, temp );

    cout << start << " --> " << finish << endl;

    hanoi( nDisk - 1, temp, start, finish );

  }

}

 

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

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

 

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

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

فرض کنید ( T( n تعداد حرکت‌های لازم جهت انتقال n دیسک به مقصد باشد. بر اساس توضیحات فوق، تعداد ( T( n - 1 حرکت برای انتقال n - 1 دیسک به میله کمکی، یک حرکت برای انتقال بزرگترین دیسک به میله مقصد، و مجددا ( T( n - 1 حرکت برای انتقال n - 1 دیسک موجود در میله کمکی به میله مقصد نیاز است. پس:

 

T( n ) = 2 T( n - 1 ) + 1

 

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

 

T( n ) = 2n - 1

 

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

 

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

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

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

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

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

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

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

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

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

استدلال شماره 4) با توجه به قوانین حاکم بر مساله، دیسک z نمی‌تواند حرکت کند. چرا که دیسک‌های x و y هر دو از آن کوچکتر هستند.

استدلال شماره 2 می‌گوید که اولین حرکت همیشه با دیسک 1 است. استدلال شماره 3 می‌گوید حرکت بعدی با دیسکی غیر از دیسک 1 است. استدلال شماره 4 می‌گوید این دیسک نمی‌تواند بزرگترین دیسک موجود در بالای میله‌ها باشد. پس در مرحله بعدی دیسک y جابجا خواهد شد. و بالاخره حرکت بعدی باز هم با دیسک 1 است (چرا؟).

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

سوال دوم: کدام میله؟ حال که می‌دانیم در هر مرحله کدام دیسک جابجا می‌شود، به سراغ میله مقصد می‌رویم. در مراحل زوج که دیسک y منتقل خواهد شد، تشخیص میله مقصد بسیار آسان است. چرا که روی یکی از میله‌ها دیسک 1 قرار دارد، که دیسک y نمی‌تواند روی آن قرار بگیرد. در نتیجه به تنها میله باقی‌مانده (میله دیسک z) منتقل می‌شود. در مورد مراحلی هم که دیسک 1 قرار است جابجا شود، می‌توان اینطور استدلال کرد:

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

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

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

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

 

void hanoi( int nDisk, char start, char temp, char finish )

{

  int max = nDisk;

  char dest = finish;

  int disk = max;

  while( true )

  {

    while( disk > 0 )

    {

      if( moving disk succeeds )

      {

        if( disk == max )

        {

          max--;

          if( max == 0 )

          {

            return;

          }

        }

        dest = the final place of max;

      }

      else

      {

        dest = the alternative place between dest and the current place of disk;

      }

      disk--;

    }

    p and q = the places different of dest;

    disk = the smaller of the disks on top of p and q;

    dest = the place between p and q with greater disk on top;

  }

}

 

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

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

‌چاپ مطلب
نسخه قابل چاپ مشاهده نسخه قابل چاپ و ارسال به چاپگر
امتیاز مطلب
1 2 3 4 5
ارسال پیام
» aa

چهارشنبه، 28 مهر ماه 1389، ساعت 11:52
منبع: ويكي پديا

» مسعود اقدسی‌فام

چهارشنبه، 28 مهر ماه 1389، ساعت 14:08
دوست خوبم،
تمامی مطالب این وب‌سایت نوشته‌های خود من هستن.
این مطلب رو همونطور که در ابتدای نوشته هم مشاهده می کنید، مدتها قبل از طریق وب‌سایت برنامه‌نویسی و طراحی الگوریتم منتشر کرده بودم و با کمی ویرایش مجددا اینجا قرار دادم.
دوست عزیزی لطف کرده و این مطلب رو داخل ویکی‌پدیا درج کرده. اگر هم دقت کنید آخر مطلب اشاره کرده که یکی از منابع نوشته‌هاش وب‌سایت برنامه‌نویسی و طراحی الگوریتم بوده.
باز هم ممنون از توجهت.

» امید

جمعه، 12 آذر ماه 1389، ساعت 17:26
استفاده کردیم
مرسی

» shokouh

دوشنبه، 22 فروردین ماه 1390، ساعت 21:34
ممنون که اطلاع رسانی میکنید.موفق باشید

» شادی

شنبه، 23 مهر ماه 1390، ساعت 13:57
خوب بود ممنون

» کیارش

سه‌شنبه، 26 مهر ماه 1390، ساعت 16:08
سلام دوست عزیز من دانشجوی دانشگاه زنجانم استاد ما یه تمرین خواسته که الگوریتم بازگشتی مسئله برج هانوی راکه اجازه ی انتقال مستقیم دیسک از میله مبدا به میله مقصد وجود نداشته باشد را بنویسید. از کجا میشه یه کمکی بگیرم؟ تا فردا ظهر وقت دارم وگرنه به اضای هر 1 جلسه دیر کرد 40 درصد نمره مربوطه رو  از دست میدم

» masoud

جمعه، 4 آذر ماه 1390، ساعت 11:49
با سلام.
من الگوریتم برج هانویی رو میخوام که با 3 دیسک باشد و هر 3 میله ارزش مساویی دارند.به عنوان مثال توی هر میله 3 تا دیسک یک نو است میخواهیم این 3 میله به هم تغییر کنند

» شقایق

سه‌شنبه، 15 آذر ماه 1390، ساعت 19:36
خیلی عالی بود.مدت ها بود از اینکه توی سایتی میچرخم لذت نبرده بودم.موفق باشید

» ناشناس

سه‌شنبه، 29 آذر ماه 1390، ساعت 23:49
سلام واقعا ممنون
خیلی بدردم خورد

» Arm!n

جمعه، 26 خرداد ماه 1391، ساعت 10:28
سلام
ممنون عالی بود...

» عسل

سه‌شنبه، 30 خرداد ماه 1391، ساعت 11:18
سلام،مرسی خیلی خوب بود

» ms ghozat

دوشنبه، 6 آذر ماه 1391، ساعت 18:47
برنامه به زبان پاسکال برای جابجایی 13 مهره برج هانوی18

» ms ghozat

دوشنبه، 6 آذر ماه 1391، ساعت 18:47
برنامه به زبان پاسکال برای جابجایی 13 مهره برج هانوی18

» یه غریبه‌ی دوست داشتنی

پنجشنبه، 5 بهمن ماه 1391، ساعت 12:00
واقعا عالیه
استاد ما باید بیاد از شما یاد بگیره
چقدر سهل و روشن توضیح دادید
دستتون رو باید بوسید

» مریم

پنجشنبه، 26 بهمن ماه 1391، ساعت 19:48
مرثی

» امیر

شنبه، 19 اسفند ماه 1391، ساعت 21:57

خیلی خوب بود

» راضیه

چهارشنبه، 1 خرداد ماه 1392، ساعت 11:51
سلام. ممنون از راهنماییهای خوبتون. میخواستم بپرسم شما میتونید الگوریتم بازگشتی هانوی رو به صورتهای زیر تغییر بدین و با شبه کد اینجا بذارید؟؟؟؟ من خیلی بهش احتیاج دارم. شنبه هم امتحان پایان ترم دارم. اگه این لطف رو کنید ممنون میشم
1- الگوریتم برج هانوی رو طوری تغییر بدید که از هر دیسک 2عدد موجود باشد (راهنمایی: یعنی در برج c 2تادیسک n روی هم، بعد 2تا دیسک n-1 و همینطور تا دوتا دیسک 1 روی هم باشند.

2- الگوریتم برج هانوی را طوری تغییر بدید که از هر دیسک به تعداد شماره آن موجود باشد. ( یعنی njh از دیسک شماره n روی هم باشن بعدش n-1jh از دیسک شماره n-1 روی هم باشن تا الی آخر که 2تا از دیسک 2 و یکی از دیسک 1 باشد)

3- روی برج A از 1 تا n دیسک زوج داریم و روی برج B همین تعداد دیسک فرد داریم. الگوریتم برج هانوی را طوری تغییر بدید که در برج C جفت جفت دیسکها روی هم قرار بگیرند. ( مثلا دوتا nها روی هم، بعد دوتا n-1ها و الی آخر)

پیشاپیش از لطفتون ممنون

» محمدرضا

چهارشنبه، 25 دی ماه 1392، ساعت 14:30
من 15 سالمه معلمه فیزیکمون خواسته در مورد الگوریتمش تحقیق کنیم و درباش بفهمیم ولی مطالبش اانقدررررر سنگیننههه ک من هیچی درک نمیکنم اصن نمیدونم n-1  یعنی چی(t) یعنی چی ولی ممنون از ااینکه گذاشتید ولی کاش مطالبش سبک تر بود که ما هم یه چیزی بفهمیم



دوست عزیزم، لطفا قبل از ارسال پیام به موارد زیر توجه داشته باشید:

1- تا حد ممکن از حروف فارسی برای نگارش پیام خود استفاده کنید. امکان ارسال پیام لاتین و کدهای برنامه‌نویسی با چیدمان چپ به راست نیز وجود دارد.
2- به درخواست پروژه‌های آماده و موارد مشابه پاسخ داده نخواهد شد.
3- از قرار دادن هرگونه نشانی یا شماره تماس در متن پیام خودداری کنید.
4- از ارسال پیام‌های تبلیغاتی خودداری کنید.
5- از ارسال سوال و پیام غیرمرتبط با مطلب ارائه شده خودداری کنید.
6- لطفا نظر خود را در مورد مطلب ارائه شده، با ثبت امتیاز مشخص نمایید.

پیشاپیش از همکاری شما سپاسگذارم.


نام:  
پست الکترونیک
وب‌سایت:
متن پیام: