فرمت فایل: ورد - Word  

مرجع فایل - قابل ویرایش ) 

تعداد صفحه : 5
مسئله كلاسيك برج هانوي به صورت زير است : سه برج (ميله) و n ديسك باقطر هاي متفاوت روي اولين برج داريم . ديسك ها به ترتيب نزولي روي اولين برج از پايين به بالا چيده شده اند .كل ديسك ها را از برج اول به برج سوم منتقل كنيد.به گونه اي كه دقيقا همان تركيب ديسك ها در برج اول در برج سوم پديد آيد . البته در اين عمليات دو محدوديت اصلي وجود دارد . الف :در هر بار انتقال فقط يك ديسك مي نواند جا به جا شود . ب : در هيچ مر حله اي م=نمي توان يك ديسك كوچكتر را روي ديسك بزرگ تر قرار داد.در اين عمليات مي توان از يك ميله كمكي نيز وضعيت او ليه و نهايي بايد به صورت زير باشد : n=2 مثلا برا ي وضعيت اوليه وضعيت نهايي اگر n=1 باشد مسئله خيلي ساده بود و تن ها با يك جا به جايي (بون كمك ميله B )حل ميشد . يع ني فقط كافي بود كه ديسك از ميله A به ميله C اتقال داده بشه . اگر N=2 باشد به 3 جا به جايي مطابق شكل زير نياز داريم : B TO C A TO C A TO B وضعيت اول و اگر N=3 باشد به 7 جا به جايي مطابق روش زير نياز است : C TO B A TO B A TO C وضع اوليه A TO C B TO C B TO A A TO C همان طور كه مشاهده مي شود با افزايش N پيچيدگي مسئله بيشتر شده و مقدار جابه جايي ها نيز افزايش ميابد . در حالت كلي اثبات مي شود براي حل مسئله برج هانوي با N ديسك 2^N-1 جا به جايي نياز است .يعني پيچيدگي