Sunday November 13, 2005 01:45:41 ب.ظ

برج هانوی

 مسئله برج هانوی به افسانه ای از هندوستان بازمی گردد. در یکی از معابد هندوستان سه ستون وجود داشته که در یکی 64 عدد حلقه به ترتیب قطرشان و جود داشته است. موبدان بر این باور بوده اند که هر گاه توانستند تمام این 64 حلقه را به به ستون سوم ببرند ، عمر جهان پیدا شده و دنیا به پایان خواهد رسید. بتا بر این موبدان دست به کار شدند و شروع به انتقال دادن حلقه ها کردند. البته در این انتقال :

1- در هر جابجایی تنها یک حلقه را جابجا کنند

2- حلقه بزرگتر روی کوچکتر قرار نگیرد.

این سوژه جالب موضوع بحث ریاضی دانان شد و بعد اهالی علم کامپیوتر به این فکر افتادند که این بازی را پیاده سازی کنند. برای حل این مسئله چند الگوریتم پیشنهاد می گردد:

الف) روش تقسیم و حل:

پایه اصلی این روش بر اساس روش باز گشتی است. الگوریتم این مسئله به صورت زیر است:

Hanoi tower
• There are three poles labeled A, B, and C.
• There are N heavy disks of different sizes with holes in the middle.
• Disks are heavy, only one can be moved at a time
• When two or more disks are placed on a given pole, a disk must be on top of a larger one.
• Disks are originally placed on pole A.
• Problem to solve
– Move N disks from pole A to pole B using C is a spare pole.

 برنامه این نوع الگوریتم به صورت زیر است:

public static void Towers(int Count, char Source, char Dest, char Spare)
{
              if (Count == 1)
                         System.out.println( “move top disk from ” + Source + “ to ” + Dest);
              else {
                         Towers(Count-1, Source, Spare, Dest);
                         System.out.println( “move disk ” + Count + “From”+Source + “ to ” + Dest);
                         Towers(Count-1,Spare, Dest, Source);
               }
}

تعداد جابجایی ها به ازای n حلقه برابر 2ⁿ -1 جابجایی است . پس موبدان اگر در هر ثانیه یک حلقه را جابجا کنند  باید 2⁶⁴ ثانیه یعنی تقریبا 584 بیلیون سال!!!

اگر هم شما از زندگی سیر شده اید و می خواهید موبدان را در این کار یاری کنید به آدرس زیر سری بزنید:

http://www.lapoo.nl/hanoi

دانلود:

بازی برج هانوی                         مراحل جابجایی ها