Ханойська вежа

Модель Ханойські вежі з вісьмома дисками

Ханойська вежа є однією з популярних головоломок XIX століття. Дано три стрижня, на один з яких нанизані вісім кілець, причому кільця відрізняються розміром і лежать меншу на більшому. Завдання полягає в тому, щоб перенести піраміду з восьми кілець за найменше число ходів. За один раз дозволяється переносити тільки одне кільце, причому не можна класти більше кільце на менше.


1. Історія створення головоломки

Цю відому гру придумав французький математик Едуард Люка, в 1883 [1] її продавали як забавну іграшку. Спочатку вона називалася "Професор Клаус (Claus) з Коледжу Лі-Су-стьяне (Li-Sou-Stian)" [1] але незабаром виявилося, що таємничий професор з неіснуючого коледжу - не більше ніж анаграма прізвища винахідника гри - професора Люка (Lucas ) з коледжу Сен-Луї (Saint Louis).

Хід вирішення головоломки з чотирма дисками.

2. Рішення

Блок схема рекурсивного алгоритму рішення.

Почнемо з самого маленького кільця і ​​перекладемо його на будь-яку позначку. Надалі це кільце потрібно переміщати в тому ж напрямку, що і при першому перекладанні. Потім зробимо єдино можливе переміщення решти кілець, після чого знову перекладемо саме маленьке кільце і т. д. (Цікаво зауважити, що, Перенумерувати "кільця" по порядку, ми доб'ємося несподіваного ефекту: парні кільця будуть переміщатися з однієї вершини трикутника до іншої в одному напрямку, а непарні - в протилежному напрямку.)


3. Застосування коду Грея для вирішення

Код Грея, рефлексний двійковий код у двійковій системі числення, в якому два сусідніх значення розрізняються тільки в одному двійковому розряді.

Спочатку, код Грея призначався для захисту від помилкового спрацьовування електромеханічних перемикачів. Сьогодні коди Грея широко використовуються для спрощення виявлення та виправлення помилок у системах зв'язку, а також у формуванні сигналів зворотного зв'язку в системах управління. Код отримав ім'я дослідника лабораторій Bell Labs Френка Грея. Він використовував цей код у своїй імпульсної системі зв'язку, для чого був написаний патент за номером 2632058.

Коди Грея застосовуються у вирішенні задачі про Ханойські вежах. Нехай N - кількість дисків. Почнемо з коду Грея довжини N, що складається з одних нулів (тобто G (0)), і будемо рухатися за кодами Грея (від G (i) переходити до G (i +1)). Поставимо у відповідність кожному I-ому биту поточного коду Грея I-ий диск (причому наймолодшому биту відповідає найменший за розміром диск, а найстаршому битку - найбільший). Оскільки на кожному кроці змінюється рівно один біт, то ми можемо розуміти зміну біта I як переміщення I-го диска. Зауважимо, що для всіх дисків, окрім найменшого, на кожному кроці є рівно один варіант ходу (за винятком стартової та фінальної позицій). Для найменшого диска завжди є два варіанти ходу, однак є стратегія вибору ходу, завжди приводить до відповіді: якщо N непарній, то послідовність переміщень найменшого диска має вигляд f-> t-> r-> f-> t-> r-> ... (де f-стартовий стрижень, t-фінальний стрижень, r-залишився стрижень), а якщо N парне, то f-> r-> t-> f-> r-> t -> ...

Реалізації алгоритму

Приклад алгоритму рішення на мові C + + :

 / / Ханойські вежі  # Include   using  namespace  std  ;  void  hanoi_towers  (  int  quantity,  int  from,  int  to,  int  buf_peg  )  / / Quantity-число кілець, from-початкове положення кілець (1-3), to-кінцеве положення кілець (1-3)  {  / / Buf_peg - проміжний кілочок (1-3)  if  (  quantity  !  =  0  )  {  hanoi_towers  (  quantity  -  1  , From, buf_peg, to  )  ;  cout  <<  from  <<  "->"  <<  to  <<  endl  ;  hanoi_towers  (  quantity  -  1  , Buf_peg, to, from  )  ;  }  }  int  main  (  )  {  setlocale  (  LC_ALL,  "Rus"  )  ;  int  start_peg, destination_peg, buffer_peg, plate_quantity  ;  cout  <<  "Номер першого стовпчика:"  <<  endl  ;  cin  >>  start_peg  ;  cout  <<  "Номер кінцевого стовпчика:"  <<  endl  ;  cin  >>  destination_peg  ;  cout  <<  "Номер проміжного стовпчика:"  <<  endl  ;  cin  >>  buffer_peg  ;  cout  <<  "Кількість дисків:"  <<  endl  ;  cin  >>  plate_quantity  ;  hanoi_towers  (  plate_quantity, start_peg, destination_peg, buffer_peg  )  ;  return  0  ;  } 

Приклад алгоритму рішення на мові Pascal :

 program  hanoi  -  bns  (  input  ,  output  )  ;  var  n  :  integer  ;  procedure  tower  (  k  :  integer  ;  a  ,  b  ,  c  :  char  )  ;  begin  if  k>  1  then  tower  (  k  -  1  ,  a  ,  c  ,  b  )  ;  writeln  (  'From'  ,  a  ,  'To'  ,  b  )  ;  if  k>  1  then  tower  (  k  -  1  ,  c  ,  b  ,  a  )  end  ;  begin  read  (  n  )  ;  tower  (  n  ,  'A'  ,  'C'  ,  'B'  )  end  . 

Приклад алгоритму рішення на мові Python :

 def  Hanoi  (  n  ,  A  ,  C  ,  B  )  :  if  n  ! =  0  : Hanoi  (  n -  1  ,  A  ,  B  ,  C  )  print  'Move the plate from'  ,  A  ,  'To'  ,  C Hanoi  (  n -  1  ,  B  ,  C  ,  A  ) 

Приклад ітеративного алгоритму рішення на мові C

 # Include   # Include   void  carryingOver  (  int  ,  int  ,  int  )  ;  main  (  )  {  int  number  ,  countDisk  ,  counter  =  1  ,  count  ;  printf  (  "Введіть кількість дисків:"  )  ;  / * Ханойська вежа * /  scanf  (  "% D"  ,  &  number  )  ;  while  (  counter  <=  pow  (  2  ,  number  )  -  1  )  {  / * Запускаємо цикл повторень * /  if  (  counter  %  2  ! =  0  )  {  / * На непарному ходу ми будемо чіпати тільки найменший диск * /  printf  (  "% 3d% d"  ,  counter  ,  1  )  ;  carryingOver  (  number  ,  counter  ,  1  )  ;  / * За допомогою цієї функції визначаємо для даного диска переміщення * /  }  else  {  / * Визначаємо диск якою перемістити на парному ходу * /  count  =  counter  ;  countDisk  =  0  ;  while  (  count  %  2  ==  0  )  {  / * Диск якою перемістити * /  countDisk  + +;  / * Буде числом поділу номери ходу на 2 без залишку * /  count  =  count  /  2  ;  }  printf  (  "% 3d% d"  ,  counter  ,  countDisk  +  1  )  ;  carryingOver  (  number  ,  counter  ,  countDisk  +  1  )  ;  }  counter  + +;  }  return  0  ;  }  / * Функція визначення переміщення дисків * /  void  carryingOver  (  int  n  ,  int  i  ,  int  k  )  {  int  t  ,  axisX  ,  axisY  ,  axisZ  ;  if  (  n  %  2  ==  0  )  {  / * Визначаємо порядок осей залежно від парності * /  axisX  =  1  ;  / * І не парності кількості дисків * /  axisY  =  2  ;  axisZ  =  3  ;  }  else  {  axisX  =  1  ;  axisY  =  3  ;  axisZ  =  2  ;  }  / * Номер ходу можна уявити єдиним чином * /  / * Як добуток якогось непарного числа на ступінь двійки * /  / * K буде номером диска який ми переміщаємо * /  t  =  (  (  i  /  pow  (  2  ,  k  -  1  )  )  -  1  )  /  2  ;  if  (  k  %  2  ! =  0  )  {  / * Визначаємо переміщення дисків для непарного ходу * /  switch  (  t  %  3  )  {  / * Вибираємо переміщення залежно від даної умови * /  case  0  :  printf  (  "% D ->% d  \ N  "  ,  axisX  ,  axisY  )  ;  break  ;  case  1  :  printf  (  "% D ->% d  \ N  "  ,  axisY  ,  axisZ  )  ;  break  ;  case  2  :  printf  (  "% D ->% d  \ N  "  ,  axisZ  ,  axisX  )  ;  break  ;  }  }  else  {  / * Визначаємо переміщення дисків для парного ходу * /  switch  (  t  %  3  )  {  case  0  :  printf  (  "% D ->% d  \ N  "  ,  axisX  ,  axisZ  )  ;  break  ;  case  1  :  printf  (  "% D ->% d  \ N  "  ,  axisZ  ,  axisY  )  ;  break  ;  case  2  :  printf  (  "% D ->% d  \ N  "  ,  axisY  ,  axisX  )  ;  break  ;  }  }  } 

Існують програми візуалізації вирішення цієї головоломки.


4. Легенди

Легенда свідчить, що у Великому храмі міста Бенарас, під собором, що відзначає середину світу, знаходиться бронзовий диск, на якому укріплені 3 алмазних стрижня, висотою в один лікоть і завтовшки з бджолу. Давним-давно, на самому початку часів, ченці цього монастиря завинили перед богом Брахмою. Розгніваний, Брахма спорудив три високих стрижня і на один з них поклав 64 диска зроблених з чистого золота. Причому так, що кожен менший диск лежить на більшому.

Як тільки всі 64 диска будуть перекладені зі стрижня, на який Брахма склав їх при створенні світу, на інший стрижень, башта разом з храмом звернуться в пил і під громові гуркіт загине світ.

Кількість перекладань залежно від кількості кілець обчислюється за формулою 2 ^ n-1 .

Число переміщень дисків, які повинні здійснити ченці, одно 18 446 744 073 709 551 615. Якби ченці, працюючи день і ніч, робили кожну секунду одне переміщення диска, їх робота тривала б 584000000000 років.

В інформатиці задачі, засновані на легенді про Ханойські вежі, часто розглядають як приклад використання рекурсивних алгоритмів і перетворення їх до НЕ рекурсивним.


5. У культурі

В оповіданні Еріка Френка Рассела "Ваш хід" ("Quiz Game", в іншому перекладі "Гра на виживання") [2] щоб відтягнути час страти головний герой вибирає гру в Ханойську вежу з 64 дисками в якості останньої гри. Оголошені правила модифіковані для двох гравців - гравці повинні перекладати диски по одному за хід, переможцем вважається той, хто зробить останній хід. Герой називає таку гру "арки-маларкі" і клянеться, що "священнослужителі бенареська храму" на Землі грають у цю гру.


Примітки

  1. 1 2 Мартін Гарднер, Математичні головоломки і розваги
  2. Рассел, Ерік Френк (квітень 1994). "Ваш хід". Якщо : 34-42.