Умова
задачі «Ханойська вежа»
(Завдання
виконується виключно засобами MS POWER POINT,
результат
роботи учасника зберегти у файл Vezhi.ppt)
У стародавні часи одному з ченців буддійського монастиря, що знаходився
поблизу міста Ханоя (це місто - столиця В'єтнаму) було віщування, що в ту мить,
коли монахи перекладуть вежу з 64-х кілець, настане кінець світу. За
буддійською релігією після кінця світу настане блаженство, а для служителів
Будди - найбільше блаженство.
Легенда стверджує, що процес перекладання цієї вежі триває й досі і
закінчиться не так швидко. Якщо перекладати 1 кільце за 1 секунду,
то на розв'язання цієї задачі потрібно витратити 600 мільярдів років. Отже,
кінець світу ще довго не наступить.
Це легенда, а ось правила, за якими монахи перекладали вежу. Є одна
заповнена вежа, а від двох інших - вільні стрижні. Потрібно перекласти кільця
із заповненого лівого стрижня на крайній правий. Стрижень посередині буде
допоміжним. За одну дію можна перекласти тільки одне кільце. Будь-яке кільце
можна класти або на більше за розміром кільце, або на вільний стрижень.
Вам потрібно створити презентацію, що дозволяє розв’язати задачу
всього для двох кілець. Натискання мишкою або виділяє верхнє
кільце (підсвічує кольором), або пересуває виділене кільце на обраний
стрижень, враховуючи правила перекладання. Перекладене кільце залишається
виділеним, поки не буде обрано інше кільце. Потрібно передбачити повідомлення
про успішне виконання завдання та можливість повернутися в будь-який момент до
початкового стану. Початковий та кінцевий стан зображено на малюнку.
Розв'язання[ред. • ред. код]
Головоломку можна розв'язати для будь-якої кількості дисків, більшість іграшкових версій мають близько семи-дев'яти. Багатьом новачкам гра видається нерозв'язною, хоча існує простий алгоритм розв'язання. Кількість рухів необхідна для розв'язання становить 2n -1, де n — найменша кількість дисків.[3]
- Для Ханойської вежі алгоритм Бога існує при будь-якій кількості дисків, але з додаванням дисків число ходів зростає експоненціально[15]
На Заході задачку вперше оприлюднив французький математик Едуард Лукас у 1863. Існує легенда про храм в Індії, який містив велику кімнату з трьома стовпами і 64 золотими дисками на них. Жрець брагман, виконував команду давнього пророцтва, переставляючи ці диски згідно з правилами головоломки, від того часу. Звідси друга назва головоломки — головоломка веж Брагми. Згідно з легендою, після завершального руху настане кінець світу.[1] Не ясно чи Лукас вигадав цю легенду або надихнувся нею.
Якщо легенда правдива, і якщо жрець може пересувати диски зі швидкістю один раз в секунду, найменша кількість пересувів займе в нього 264−1 секунд або близько 585 мільярдів років[2] або 18,446,744,073,709,551,615 пересувів до завершення.
Також існують інші версії легенди. Наприклад, в деяких викладеннях, храм був монастирем і жрець був монахом. Храм чи монастир може стояти в різних частинах світу — включно з Ханоєм, В'єтнам, і може приналежати будь-якій релігії. В деяких варіаціях додаються інші складові, такі як те, що вежі створили на початку світу, або що жрець чи монах може робити лише один рух в день.
