jump to navigation

Кулите од Ханои May 28, 2008

Posted by admin in Математика.
Tags: , , ,
trackback

Првиот пост на овој блог ќе биде посветен за еден многу познат проблем од доменот на дискретната математика. Се работи за проблемот познат како Tower of Hanoi. Значи, на еден стап имаме N различни по големина дискови и треба да ги префрлиме на друг стап со минимален број на операции, а имаме уште еден помошен стап. Или, како што се гледа на сликата:

undefined

Со k(n) го бележиме минималниот број операции за да се префрлат n дискови. Јасно е дека k(1)=1 и k(2)=2:

  1. горниот диск го префрламе на помошниот стап
  2. долниот диск го префрламе на вториот стап
  3. горниот диск го префрламе од помошниот на вториот стап

За случајот k(3), постапката е слична:

  1. ги префрламе сите дискови освен последниот на помошниот стап = k(2) чекори
  2. го префлраме најголемиот диск на вториот стап = 1 чекор
  3. ги префрламе дисковите од помошниот стап на вториот стап = k(2) чекори

Односно, k(3)=2k(2)+1=7, аналогно k(4)=2k(3)+1=15, k(5)=2k(4)+1=31, а тоа воопштено е k(n)=2k(n-1)+1. Се забележува дека k(n)=2^n-1. По пат на индукција (ќе го презентирам само последниот чекор):

k(n)=2k(n-1)+1=2(2^ {n-1}-1)+1=2^n-1

Се надевам дека првиот запис ви се допадна. Слободно напишете коментар доколку сакате да придонесете содржина на блогот или доколку сакате да споделите мислење во врска со проблемот.

Comments»

No comments yet — be the first.