Теория и практика строительства ханойских башен

Теория и практика строительства ханойских башен

Курсовая работа по информатике

«Задача о Ханойских башнях»

1. Построение модели

2. Разработка алгоритма

2.1 Пошаговый алгоритм

3. Проверка правильности алгоритма

4. Анализ алгоритма и его сложности

5. Реализация алгоритма

Задача о Ханойских башнях. На одном из алмазных шпилей надето 64 круглых золотых диска. Диски имеют разные радиусы и расположены на шпиле в порядке убывания радиусов от основания к вершине. Требуется перенести диски с первого на второй, используя по необходимости и третий шпиль. При этом неукоснительно должны соблюдаться следующие правила:

за один раз можно перемещать только один диск;

больший диск нельзя располагать на меньшем диске;

снятый диск необходимо надеть на какой-либо шпиль перед тем, как будет снят следующий диск.

Трудолюбивые буддийские монахи день и ночь переносят диски со шпиля на шпиль. Легенда утверждает, что когда монахи закончат свою работу, наступит конец света. Можно было бы подсчитать, что для решения задачи с 64 дисками потребуется 264-1 перемещений (около 1020). Поэтому, что касается конца света, то он произойдет по истечении пяти миллиардов веков, если считать, что один диск перемещается за одну секунду. Впрочем и задачу, и легенду для неё придумал в 1883 году математик Э.Люка. Это дает нам право отложить заботы о конце света в сторону и перейти к решению следующей задачи.

Имеется три колышка a, b, c и n дисков разного размера, переномерованных от 1 до n в порядке возрастания их размеров. Сначала все диски надеты на колышек a (рисунок 1.1),

требуется перенести все диски с колышка a на колышек c (рисунок 1.2),

соблюдая при этом следующие условия:

диски можно переносить только по одному;

больший нельзя ставить на меньший (рисунок 1.3).

Написать программу, которая печатает последовательность действий (в виде «перенести диск с q на r», где q и r – это a, b или c, решающую указанную задачу для n дисков, n – заданное натуральное число).

Целью данной курсовой работы является изучение рекурсивного алгоритма решения задачи о Ханойских башнях, разработка программы, печатающей последовательность действий.

1. Построение модели

Математической моделью данной задачи является рекуррентное соотношение.

Рекуррентное соотношение – это соотношение, которое выражает значение функции с помощью других значений, вычисленных для меньших аргументов. Исходя из данного определения, следует, что для каждой рекуррентной функции нужно задавать хотя бы одно значение.

2. Разработка алгоритма

Для разработки алгоритма решения данной задачи используется рекурсивный метод.

При построении алгоритма используется подход «разделяй и властвуй». Идея заключается в следующем:

задача разбивается на несколько подзадач меньшего размера;

решаются эти подзадачи;

решения подзадач комбинируются, и получается решение исходной задачи.

Как правило, задачи решаются непосредственно, либо с помощью рекурсивного вызова.

Алгоритм называется рекурсивным, если при решении некоторой задачи он вызывает сам себя для решения подзадачи.

Для того, чтобы переложить всю пирамиду из дисков, надо сначала переложить все, что выше самого большого диска, с первого на вспомогательный колышек, потом переложить этот самый большой диск с первого на третий колышек, а потом переложить оставшуюся пирамиду со второго на третий колышек, пользуясь первым колышком как вспомогательным.

2.1 Пошаговый алгоритм (с рекурсией)

Входные данные: количество дисков, находящихся на колышке a;

Выходные данные: последовательность действий;

(шаги 1.2-1.3 выполняются рекурсивно);

3. Проверка правильности алгоритма

Правильность алгоритма проверим при n=3 и n=4.

переместить диск со стержня a на стержень c

переместить диск со стержня a на стержень b

переместить диск со стержня c на стержень b

переместить диск со стержня a на стержень c

переместить диск со стержня b на стержень a

переместить диск со стержня b на стержень c

переместить диск со стержня a на стержень c

переместить диск со стержня a на стержень b

переместить диск со стержня a на стержень c

переместить диск со стержня b на стержень c

переместить диск со стержня a на стержень b

переместить диск со стержня c на стержень a

переместить диск со стержня c на стержень b

переместить диск со стержня a на стержень b

переместить диск со стержня a на стержень c

переместить диск со стержня b на стержень c

переместить диск со стержня b на стержень a

переместить диск со стержня c на стержень a

переместить диск со стержня b на стержень c

переместить диск со стержня a на стержень b

переместить диск со стержня a на стержень c

переместить диск со стержня b на стержень c

4. Анализ алгоритма и его сложности

Алгоритм решения задачи о Ханойских башнях является конечным, так как все используемые циклы выполняются конечное число раз.

Сложность – количественная характеристика алгоритма, которая говорит о том, сколько времени он работает (временная сложность), либо о том, какой объем памяти он занимает (емкостная сложность). На практике сложность рассматривают как временную сложность.

Из определения сложности следует, что она зависит от размерности входных данных или, как говорят, от длины входа. В задаче о Ханойских башнях входными данными является число дисков.

Рассчитаем порядок временной сложности в соответствии с пошаговым алгоритмом.

Временная сложность процедуры Perenesti будет зависеть от количества переносов, которое равно 2n-1, значит О(2n-1).

5. Реализация алгоритма

uses crt;(подключение модуля очистки экрана)

n: integer;(целый тип данных)

a,b,c: char;(описание символьных типов данных)

procedure Perenesti(n: integer;a,b,c: char);

ifn>0 then(если n>0 значит)

writeln (‘Peremestit" disk so sterzhnya ‘,a,’ na sterzhen" ‘,b);(ввели)

writeln (‘Vvedite natural"noe chislo n’);

read (n);(ввод числовых данных)

a:=’a’; b:=’b’; c:=’c’;присвоение по членных переменных (то ,что до этого ввели)

© 2002 г. Александр Легалов

(опубликовано в журнале «Программист» № 11/2002)

Сопоставляется рекурсивное и различные итеративные решения задачи о Ханойской башне. Делается попытка упростить итеративный алгоритм за счет использования зависимостей между числом дисков, номером шага итерации и осями, используемыми для перекладывания.

Введение

Постоянный интерес к старым задачам обусловлен множеством причин. Это и красивые легенды, обрамляющие условие, и изящные решения, и интересные расширения, вытекающие из исходных ограничений. Несомненно, что задача о Ханойских башнях сопровождается одной из самых интригующих легенд о конце света. Дополнительный колорит ей придает блеск золотых дисков и алмазных стержней [1].

Не меньший интерес вызывают попытки использовать различные подходы и парадигмы, одна из которых, связанная с автоматным программированием [2], побудила меня продолжить известную всем историю. Поиск других вариантов обуславливался следующими мотивами:

Согласно легенде монахи должны сменяться из поколения в поколение, поэтому перекладывание дисков может совершенно не зависеть от того, в каком из своих внутренних состояний находится тот или иной монах при сдаче смены. То есть, достаточно одного состояния и рабочей памяти, фиксирующей текущее положение дисков. Подобные автоматы широко используются при построении трансляторов. Возможность получения такого решения подтверждается присутствием одного условного оператора в рекурсивной программе, определяющего завершение процедуры. Встает резонной вопрос, а стоит ли вообще утруждать себя автоматным решением, если алгоритм управления так прост?

Итеративные алгоритмы опираются на простое условие при выборе стержня, используемого для переноса любого диска. Оно зависит от четности дисков башни и номера текущего диска [2]. Простота действий ведет к вполне резонному вопросу: почему сложность и размер всех итерационных алгоритмов оказывается намного больше по сравнению с рекурсивным решением [3]?

Что показывает рекурсия

Приводимый практически во всех источниках рекурсивный алгоритм описывает лишь одно полезное действие: перекладывание диска с одной оси на другую. При этом отсутствует какая-либо манипуляция с дополнительной памятью кроме передачи параметров, однозначно переставляемых при каждом вызове. Это наводит на мысль, что основной задачей рекурсии является динамическое определение того, на какой стержень переложить самый верхний диск при выполнении первого шага. Остальные переносы дисков однозначно зависят от этого выбора. Рекурсивное порождение и автоматический обход позволяют не задумываться об общем количестве шагов, равном 2 N -1, где N – количество дисков. Это позволяет без каких-либо проблем и дополнительных ухищрений запускать программу с исходным числом дисков, значительно, превышающим число, определяющее достижение результата за разумный интервал времени (на компьютере с 512 Мб памяти мне удалось запустить программу, осуществляющую перебор 32454 дисков). Следует отметить и то, что размер дисков является несущественным для решения задачи. Программа будет точно также работать при переносе с место на место столбиков из одинаковых монет.

О виде рекурсии

Одним из интересных моментов, рассмотренных в работе [2], для меня явилось сведение рекурсии к итерации без использования дополнительной памяти (во втором примере). Известно, что таким свойством обладают лишь «концевые» рекурсии. Поэтому вполне естественным является вопрос: как подобное могло случиться? Ответ можно найти, если дополнительно изучить специфику рекурсивного решения.

Простой анализ показывает, что рекурсивные вызовы отличаются друг от друга значениями параметров, определяющими количество обрабатываемых дисков, и стержней, используемых для переноса на каждом шаге. А что произойдет, если удастся избавиться от этих параметров? Тогда рекурсивное решение запишется следующим образом:

Таким образом, имеются две «концевые», а не «внутренние» рекурсии, которые легко сводятся к итерациям:

Подобные трюки широко используются при разработке трансляторов и подробно описаны, например, в моих лекциях [4].

Параметрическое решение

Для того чтобы реализовать рассмотренное выше итеративное решение, достаточно получить формулы, определяющие исходный и приемный стержни в зависимости от номера шага. Не сомневаюсь, что подобные формулы уже существуют в готовом виде. Самое близкое, что я сумел найти, представлено в источнике [5]. Однако предлагаемый в нем алгоритм ориентируется на анализ относительных размеров диска и не определяет прямую зависимость от итераций. Поэтому пришлось провести собственное небольшое расследование.

Достаточно легко получить связь между номером итерации i и перекладываемым диском k. Оно зависит от числа делений i на 2 без остатка. Поэтому без особых проблем можно выявить, что номер перекладываемого диска равен количеству нулей в двоичном представлении номера итерации i, предшествующих самой младшей единице, плюс один. Алгоритмически подобный подсчет можно осуществить операцией сдвига вправо до тех пор, пока результат сдвига станет нечетным.

Шаг t, определяющий перемещение диска с исходного стержня на приемный, легко можно получить по известному номеру перекладываемого диска:

диски перекладываются со стержня на стержень с разными шагами, но по модулю 3, что определяется использованием трех стержней;

если четность (нечетность) общего числа дисков в башне совпадает с четностью (нечетностью) перекладываемого диска, то используется шаг, равный минус 1 или его положительный эквивалент, равный 2. В противном случае шаг равен плюс 1.

Зная номер диска k и количество проделанных итераций i, без труда можно выяснить, в который раз перекладывается искомый диск. Умножив это и предшествующее ему числа на шаг t (не забывая «ужать» результат по модулю 3), получим номера принимающего и исходного стержней.

Ниже приведена программа соответствующая представленным рассуждениям.

Несмотря на то, что данная программа превосходит по размеру рекурсивную версию, вряд ли стоит утверждать, что она концептуально сложнее.

Повышение эффективности

Полученное решение подтверждает возможность сведения задачи к «концевым» рекурсиям, что обеспечивает ее итеративную реализацию без использования дополнительной памяти. Однако, программа написана неэффективно. Локальные попытки исправить положение вынесением одноразовых вычислений за циклы, преобразованием формул, исключающим дублирование, дают небольшой эффект. Необходимы кардинальные перестройки, изменяющие структуру алгоритма.

Анализ показывает, что существенное торможение происходит при работе цикла, определяющего номер диска по номеру итерации. Сократить время выполнения данного фрагмента можно только за счет дополнительной рабочей памяти, позволяющей заменить итерации другими метафорами, например использованием относительных размеров дисков. Самый простой (но, возможно, не самый эффективный) способ заключается в непосредственном моделировании стержней и перемещаемых дисков матрицей размерностью 3*N, что позволяет легко получить информацию об их текущем положении и относительном размере. От представления дисков на стержнях в виде отдельных непрерывных диапазонов я отказался, из-за необходимости вводить дополнительные проверки.

Другим направлением на пути ускорения переборов является избавление от проверки очевидных условий. В большинстве предлагаемых итеративных алгоритмов вычисление исходного и принимающего стержней осуществляется на каждом шаге. Вместе с тем можно легко заметить, что строительство новой башни состоит из четырех постоянно повторяющихся шагов, ассоциируемых с промежуточным созданием двухэтажной башни:

Разборка двухэтажной башни: первый диск снимается с вершины и переносится на требуемый стержень.

Построение основания двухэтажной башни: второй диск переносится на соответствующий стержень.

Завершение строительства двухэтажной башни: первый диск переносится на второй диск.

Укладка нового фундамента: более крупный диск перекладывается на освободившееся место, или переносится диск, ранее находившийся под первым диском (именно это действие и является основным источником дополнительного анализа).

Постоянное чередование осей ведет к тому, что через 2 N-2 -1 полных четырех шаговых итераций (их, естественно, в 4 раза меньше числа шагов) останется выполнить только три последних шага (укладка нового фундамента невозможна в связи с отсутствием диска с номером N+1).

Можно непосредственно реализовать этот прием. Но следует заметить, что три последние итерации проще перенести в самое начало. В этом случае, до начала основного цикла, можно осуществить выход из программы при числе дисков меньше трех, ускорив, тем самым вычисления. Итерации начинаются с закладки нового фундамента и заканчиваются строительством очередной двухэтажной башни. После небольших косметических манипуляций, связанных с подчисткой ряда промежуточных вычислений и заменой прямых операций на их более быстрые аналоги, программа будет выглядеть следующим образом.

Использование «натурного» моделирования Ханойских башен позволило достаточно просто обойти проблему размерности. Первая из представленных программ могла справиться с башней, высота которых была ограничена длинной используемого машинного слова, что заметно проигрывает размерности, «оказывающейся по зубам» рекурсивной программе. Однако введение условия окончания по появлению последнего диска на искомой оси позволяет довести общее число дисков до абсурда (в моем случае оно превысило 67 миллионов).

Заключение

Предложенное в статье параметрическое решение задачи о Ханойских башнях показывает, что в целом итеративный алгоритм не сложнее своего рекурсивного аналога. Вместе с тем, любая оптимизация ведет к усложнению анализа условий, обеспечивающих более быстрый выбор нужных стержней для выполнения переносов дисков. Следовательно, сложнее становится и управление программой за счет появления ветвей. Это позволяет интерпретировать алгоритм с позиции теории автоматов, что вряд ли является целесообразным для задачи, базирующейся на описании решения в виде формул.

В статье я ни в коей мере не хотел подвергать сомнению возможности автоматного программирования. Однако, каждый из подходов, на мой взгляд, может (и должен) использоваться в соответствующих областях. Теория автоматов нашла эффективное применение при решении задач обработки постоянно меняющихся параметров, взаимосвязанных отношениями со слабо выраженными функциональными зависимостями. В этих случаях на каждом шаге необходимо осуществлять неочевидный выбор следующего направления среди множества разветвляющихся путей. Иногда, приходится возвращаться и начинать все сначала.

В случае ханойских башен достаточно просто вычислить любой из отрезков пути, никак не привязываясь при этом к текущему положению. Поэтому, лабиринт на поверку оказывается ломаной линией длиной 2 N -1.

Литература

Арсак Ж. Программирование игр и головоломок: Пер. с франц. – М.: Наука. гл. ред. физ.-мат. лит., 1990. – 224 с.

Шалыто А.А., Туккель Н.И., Шамгунов Н.Н. Ханойские башни и автоматы. Программист, 2002, №8, с. 82-90. (Статья также размещена на этом сайте)

Теория ханойской башни

Всякая теория — потому и теория, что состоит из теорем, не исключение и теория ханойской башни. Но сначала – приведу описание этой головоломки, ведь не все с ней знакомы.(а кто знаком, может спокойно это описание пропустить.)
Пусть у нас есть n дисков различных диаметров (и нет ни одного повторяющегося диаметра) и три позиции. Пусть в исходном состоянии все диски, в порядке уменьшения диаметра (снизу вверх) находятся в позиции 1 (исходной)
Требуется: получить ситуацию, в которой все диски (в порядке уменьшения диаметра, снизу вверх) находятся в позиции 3 (конечной)
Допустимые операции: любой диск, если он в верхней позиции, можно переносить в любую другую позицию, если она свободна или только на диск бОльшего диаметра.(чем перемещаемый диск)

В дополнение к этому сразу скажу, что вам легче будет понимать эту статью, если вы обзаведётесь соответствующим инвентарём. Например, возьмите для этого несколько монет разного достоинства: 5, 2, 1, 0.5 и 0.1 руб. И, в процессе чтения статьи, воспроизводите те ситуации, о которых идёт речь в статье.

В оригинальной головоломке – 8 дисков. Но мы, вовсе не страдая (крутым) честолюбием, сначала попробуем решить для этой задачи самый простой её вариант, банальный, с 1 диском.
В итоге — получится 1-ая теорема теории Ханойской башни:
если количество дисков=1, то диск сразу переставляем в целевую позицию.(что и позволит решить задачу в 1 шаг, то есть наиболее оптимально.)
И принимается эта теорема без доказательств.
(А точнее — без логических доказательств. Ибо доказательство мы получили на практике, путём эксперимента.
И это, как ни странно (для серьёзных геометров, например) допустимо.
Ибо серьёзные геометры, в отличие от серьёзных же физиков, не понимают, что свои аксиомы как-так они приняли без доказательств? И это, стало быть, выдумки? Нет, это результаты опыта, теперь уже геометрического. А что, разве таких (опытов) не бывает? Почему же?)

(а значит, это – аксиома, или теорема 0-го уровня. (как я их называю. А что тут голову морочить-то? Ведь и теорема и аксиома – это утверждения, причём зарегистрированные, как истинные. А кроме того, и теоремы есть разных уровней: 1-го, 2-го и т. д.)

Отсюда вывод (а точнее, гипотеза): любая теория имеет аксиомы. Но доказать эту гипотезу весьма просто: для доказательства всякой теоремы используются опорные утверждения (уже доказанные)(как минимум, стало быть, одно), поэтому в итоге придём к ситуации, когда принимать опорное утверждение придётся без доказательства. Что и разорвёт этот порочный круг.) Но это не значит, что в истинности её не надо убеждаться. Но как убедиться? А на опыте.
Да и что, собственно, нужно доказывать? Если нет короче (то есть оптимальнее) алгоритма, чем в 1 шаг? Ну, разве что то, что нет иных таких алгоритмов. Но опять же, откуда возьмутся иные (данному) алгоритму (и причём оптимальные) алгоритмы, если исходный алгоритм – состоит из одного шага? Ведь иные алгоритмы возникают для алгоритмов из 2-х и более шагов. (Доказательство: например, как достичь (кратчайшим путём) пункта Б из пункта А? Иной скажет: тут есть 2 варианта: двигаясь через пункт В или через пункт Г. Но как быть, если нет на нашей «географической» карте пункта В и пункта Г? Только так: сразу перейти из А в Б. Что и требовалось доказать.)

2-ая теорема ХБ. Она получается при переходе к более сложной задаче, для 2-х дисков. Предположим, что диск 2 (нумерацию дисков ведём по убыванию их диаметра) уже отсутствует на позиции 1, тогда бы задача свелась к уже решенной в теореме 1: надо диск 1 переложить сразу в позицию 3. Как бы мы смогли подготовить этот шаг? Понятно, что переложив диск 2 в позицию 2. Вот мы и доказали теорему 2: если в пирамиде 2 диска, то 1-ый шаг – это перекладка диска 2 в позицию 2. (а не в позицию 3, как это было в предыдущей задаче)

Отсюда возникает следующая гипотеза (в будущем – теорема3): если в пирамиде нечётное количество дисков, то 1-ый ход оптимального алгоритма – это перемещение (верхнего) диска сразу в позицию 3. А если в пирамиде – чётное количество дисков, то 1-ый ход – это перемещение верхнего диска в позицию 2 (промежуточную)
Докажем эту гипотезу. Но сначала докажем лемму (то есть вспомогательную теорему):
добавление одного диска в пирамиду приводит к смещению 1-го шага из позиции 3 в позицию 2 или наоборот.
Пускай доказано, что в решении задачи для пирамиды с n дисками 1-ый оптимальный ход – это перемещение верхнего диска в позицию х. Перейдём к решению задачи с n+1 дисками. Предположим, что верхний диск уже перемещен. Тогда решение задачи сводится к решению задачи для n дисков. 1-ый оптимальный ход которой, согласно допущению — перемещение верхнего диска в позицию х. Тогда как мы можем обеспечить выполнение этого шага? Только переместив диск n+1 – в позицию иную, чем х (то есть в позицию 2 при х=3 и наоборот) Что и требовалось доказать.

После этого доказательство основной теоремы (=теоремы3) – сводится к весьма простым рассуждениям.
Поскольку доказано, что для решения задачи при n=1 1-ый оптимальный шаг – это перемещение диска в позицию 3, то для решения задачи с n+1 дисками (в соответствии с доказанной выше леммой) 1-ый оптимальный шаг – это перемещение диска в позицию 2. Отсюда понятно, что при переходе от нечетного к чётному количеству дисков 1-ый оптимальный шаг – всегда будет меняться с перемещения диска в позицию 3 – на перемещение диска в позицию 2, и наоборот (то есть при переходе с чётного количества дисков – на нечётное) В итоге всем задачам с нечётным количеством дисков – соответствует 1-ый оптимальный шаг в позицию 3, а всем задачам с чётным количеством дисков — соответствует 1-ый оптимальный шаг в позицию 2. Что и требовалось доказать.
Заметьте, теорема1 и теорема2 – являются частными случаями теоремы3. И это – результат применения принципов решения т-задач. Теорема3 теперь основная теорема теории.

Ну что ж, вроде бы всё? Нет, нужна еще одна теорема, теорема4.
И она нужна для того, чтобы не только в начальной ситуации определять оптимальный ход, но и в любой, возникающей в процессе решения задачи.
Так, пусть n=3 и 1-ый ход уже совершён, то есть возникла ситуация С1: a=1,2; b=; c=3. (здесь позиции обозначены буквами, диски, как и прежде — числами) В этой ситуации теорема3 нам подсказывает ход к С2: a=1; b=2; c=3.
В ситуации же С2 рекомендуемый ход таков: 1:ac, но он недопустим согласно правилам. Но его можно сделать допустимым засчёт хода: 3:cb. Именно этот ход мы и назовём обеспечивающим ходом в ситуации С2, ход же 1:ac – обеспечиваемым ходом в этой ситуации. В возникшей в результате ситуации С4 опять рекомендуемый ход 2:bc опять становится обеспечиваемым и для него требуется обеспечивающий ход 3:ba, после чего мы без проволочек идём к цели.

Отсюда вывод: существуют такие промежуточной ситуации решения задачи ХБ, что рекомендуемый теоремой3 ход является недопустимым согласно правилам. В этом случае сначала выполняется ход, опеспечивающий рекомендумый ход, а потом рекомендуемый.
Поскольку основанием для запрета хода является либо занятость целевой позиции меньшим диском либо покрытость исходной позиции меньшим диском, что несовместимо, а рекомендуемый теоремой3 ход – всегда 1, то и обеспечивающий ход в любой позиции будет всего 1 (или его вообще не будет) Что и говорит об оптимальности получаемого в итоге алгоритма.

(Для пущей убедительности приведём спецификацию всех ходов в любой промежуточной ситуации:
-1 ход является обратным (поэтому неактуальным для нашей задачи, далее по этому поддереву не углубляемся);
-1 ход – нерекомендуемый (=неоптимальный, далее по этому поддереву не углубляемся)
-1 ход – рекомендуемый
Если рекомендуемый ход недопустим, то для него существует:
-1 обеспечивающий ход
-1 блокирующий ход, далее по этому поддереву не углубляемся)
(А1-)

Ну вот, теперь уфф!
Ибо в итоге нами был получен чёткий критерий, который помогает выбрать оптимальный ход в любой ситуации решения данной головоломки.(а стало быть, безошибочно находить оптимальный алгоритм для решения задач ХБ любой сложности, то есть в любым количеством дисков) Но, может, вы думаете, что получение его заняло у автора всего 1 вечер (который ушёл на написание статьи?) Нет, это стоило автору почти 2 месяца его жизни.

Да, чуть не забыл. Зачем я написал это статью? А чтобы показать, что оптимальное решение задачи создания теории (назовём такую задачу т-задачей) – лежит в русле применения теории решения такой задачи, а вовсе не метода проб и ошибок, как повелось. Метод проб и ошибок – да, допустим (и даже более того – является единственным средством решения) только для совершенно новых задач.
Что же касается реплик о том, что я здесь, вроде бы, создал некую пустяковую, в общем-то теорию – теорию некоторой игры, а поэтому какое значение это имеет для развития науки? Да ровно никакого!
То на них отвечу так: теория игры – это правила создания выигрышного алгоритма для данной игры, в данной ситуации. Но чем наше знание, например, физики – это не правила создания алгоритма вычисления при решении физических задач?

P.S. Уважаемые читатели, пожалуйста, в своих отзывах не исходите из того, что отзыв – это всего лишь похвала. Я принимаю всё: и похвалы, и критику и вопросы. И с удовольствием отвечу на все ваши реплики. Но желательно, не очень уж язвительные.

**
-А1: Всё вроде бы убедительно, но заметьте: в данном случае мы применяли теорему3 для любой подзадачи исходной задачи. Но каковы основания для этого?
Взглянем на (n)-задачу ХБ (для определённости пусть n нечётно) с другого ракурса:
1)чтобы решить (1,n)-задачу (где n>1), нужно сначала решить (2,n)-задачу (в промежуточную позицию)(и это равносильно (1,n-1)-задаче, т.к. диск1 не задействуется), затем переместить диск1 в целевую позицию, после чего опять решить (2,n)-задачу, но уже в целевую позицию.
И это, заметьте, у же не гипотеза!
Отсюда можно построить рекуррентную последовательность утверждений:
2)чтобы решить (2,n)-задачу, нужно сначала решить (3,n)-задачу (в промежуточную позицию)(и это равносильно (1,n-2)-задаче, т.к. диск2 не задействуется), затем переместить диск2 в целевую позицию, после чего опять решить (3,n)-задачу, но уже в целевую позицию.
B так далее, пока не дойдём до :
n-1)чтобы решить (n-1,n)-задачу, нужно сначала решить (n,n)-задачу (в промежуточную позицию)(и это равносильно (1,1)-задаче, т.к. диск(n-1) не задействуется), затем переместить диск(n-1) в целевую позицию, после чего опять решить (n,n)-задачу, но уже в целевую позицию.
n)чтобы решить (n,n)-задачу, нужно переместить диск(n) в целевую позицию. И всё.

Итак,теперь понятно, как устроен итоговый алгоритм при нечётном n (далее целевая позиция – c, промежуточная — b):

Дай человеку решение, и ты обеспечишь его ответами на один день. Дай человеку алгоритм — обеспечишь его ответами на всю жизнь.
А вообще подобные задачкаи, наряду с пятнашками, встречаются мне порою в квестах (один из немногих жанров компьютерных игр, в который я еще поигрываю), и осознание наличия достаточно простого способа решения не мешает мне ругаться на разработчика 🙂

Спасибо, Гжегож, за отзыв! И тем более, что не всякий отваживается обсуждать такие темы.
"Дай человеку алгоритм — обеспечишь его ответами на всю жизнь."
Гжегож, в данной статье я дал больше, чем алгоритм. А именно — теорию создания алгоритмов.(для данной конкретной задачи, конечно. Но увы, все до сих пор крутились вокруг да около этого.)
Что же касается квестов, то это, вроде бы, не головоломки вовсе. И я бы с Вами согласился, если бы с Ханойской башней наряду упомянули Вы хотя бы тетрис, например.

Во многих квестах есть мини-игры — часто классические головоломки (хотя в последние годы опытные разработчики их уже избегают, но раньше они были в каждой второй игре). И из-за переиспользования и того, что обычно в мире квеста эти задачки смотрятся не органично, они вызывают негодование у игрока, такого как я 🙂

"Дай человеку решение, и ты обеспечишь его ответами на один день. Дай человеку алгоритм — обеспечишь его ответами на всю жизнь."
Перефразирую это так:
Дай человеку решение, и ты обеспечишь его ответами на одну конкретно-точечную задачу. Дай человеку алгоритм (решения задач такого же типа, то есть с одной матмоделью) — обеспечишь его ответами на всю жизнь.(но только для задач с данной матмоделью)

А что делать, если матмодель задачи другая?
Составить её.

Именно о принципах получения матмоделей (=алгоритмов) решения задач и говорит эта статья

Портал Проза.ру предоставляет авторам возможность свободной публикации своих литературных произведений в сети Интернет на основании пользовательского договора. Все авторские права на произведения принадлежат авторам и охраняются законом. Перепечатка произведений возможна только с согласия его автора, к которому вы можете обратиться на его авторской странице. Ответственность за тексты произведений авторы несут самостоятельно на основании правил публикации и законодательства Российской Федерации. Вы также можете посмотреть более подробную информацию о портале и связаться с администрацией.

Ежедневная аудитория портала Проза.ру – порядка 100 тысяч посетителей, которые в общей сумме просматривают более полумиллиона страниц по данным счетчика посещаемости, который расположен справа от этого текста. В каждой графе указано по две цифры: количество просмотров и количество посетителей.

© Все права принадлежат авторам, 2000-2020. Портал работает под эгидой Российского союза писателей. 18+

Название: Задача о Ханойских башнях
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Добавлен 19:19:47 05 февраля 2010 Похожие работы
Просмотров: 527 Комментариев: 14 Оценило: 3 человек Средний балл: 5 Оценка: неизвестно Скачать
Ссылка на основную публикацию
Телефонный шлюз что это
VoIP-шлюз — это межсетевой шлюз, предназначенный для перевода трафика между сетями различных типов. VoIP-шлюзы можно разделить на многоканальные и одноканальные:...
Сравнить технические характеристики rx330 и rx350
Линейка популярных люксовых SUV Lexus RX пополнилась новой модификацией – RX 350. Теперь покупателем RX быть еще приятнее – ведь...
Сравнить процессоры кирин и снапдрагон
Snapdragon 636 vs. Kirin 960: кто лучше? Результаты тестов и сравнительных таблиц, описанных в этой статье, помогут определить, какой из...
Телефонная клавиатура на компьютере
Виртуальная клавиатура выручит Вас, когда выйдет из строя основное физическое устройство ввода, полностью или частично ( поломается несколько клавиш )....
Adblock detector