مسئله برج هانوی
English -فارسي

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 حلقه برابر 2n -1 جابجایی است . پس موبدان اگر در هر ثانیه یک حلقه را جابجا کنند  باید 264 ثانیه یعنی تقریبا 584 بیلیون سال!!!

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

http://www.lapoo.nl/hanoi

دانلود:

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

 

 

Internet Access
Copyright © 2005 ifjam inc.All right reserved
Email to: ifjam@hotmail.com