Cтраница 3
Рисование меток на шнейке с помощью рскурсившж про-граммы не нредспнынсг схоОой сложности, но не существует ли Go-i ее простого способ л исчисления длимы Лой четки для любого данного иначсиин П НУ рис, 59 показан еще один просто вычислительный процесс, дающий ответ на этот вопрос, / - ый номер, заводимый н программой решения задачи о ханойских башнях, it программой рнсовиния линейки. Это утверждение МОЖРЮ локазять методом лндукцми по соответствию с [ формулировкой метод д раздел ни н властвуй д вя процесса вывода таблицы / г - разрядных ч и осл: достаточно напечатать та и л ti ну ( л - 1) - раз [ ядныч кшсел каждому HJ которых шествует 0-и р рчл. [31]
Выбор между рекурсией и итерацией обычно определяется требованиями к объему рабочей памяти. При решении задачи Ханойской башни информация о позиции дисков на каждом этапе хранилась в локальных переменных, и если для этих переменных места в памяти не хватает, проблема становится неразрешимой. Можно найти и нерекурсивное решение, но в данном случае рекурсия выглядит просто и естественно. [32]
В задаче о Ханойской башне управление вызывающего преобразователя должно было продолжать работу с элемента вычислительной среды, полученного от вызванного процесса. Во втором случае в задаче о восьми ферзях управление, получив информацию от вызванного преобразователя, продолжает свою работу из того же элемента, в котором произошел вызов. [33]
Теперь, когда мы уже изучили уровень команд трех машин, нам нужно все обобщить. Давайте подробно рассмотрим тот же пример программы ( Ханойская башня) для всех трех машин. В листинге 5.6 приведена версия этой программы на языке Java. В следующих разделах для решения этой задачи мы предложим программы на ассемблере. [34]
В этом параграфе мы представляем очень хороший тест, проверяющий на простоту числа Мерсенна. Первым его обнаружил Люка ( известный нам как создатель Ханойских башен) в 1878 году. Затем тест был усовершенствован Лемером ( D. H. Lehmer) в 1932 году, и теперь он называется тестом Люка - Лемера. [35]
Оставляя временно вопрос о копне света, поищем алгоритм для перенесения ( всех) дисков с одного шпиля на другой. Что это не так просто, вы сможете убедиться, изготовив модель ханойских башен и поупражнявшись с нею. [36]
За сколько ходов можно перенести с одного колышка на другой кольца в игре Ханойская башня. В этой главе мы рассмотрим один класс хитроумных логических головоломок, применение к которым математической индукции в общем случае менее известно и таит в себе немало забавных ловушек. [37]
Как это делается, покажем на примере решения одной из задач. В качестве характерной в книгах по искусственному интеллекту часто рассматривается так называемая задача о Ханойской башне. [38]
Рассмотрим алгоритм маркировки всех вершин графа, достижимых из начальной вершины. Алгоритм маркировки применяется в программах сборки мусора систем обработки списков и наряду с задачей о Ханойской башне является одним из излюбленных алгоритмов для демонстрации перевода рекурсии в итерацию. [39]
В некоторых учебниках рекурсия вводится в какой-либо из последних глав; но мы считаем, что эту тему лучше всего охватывать постепенно, на всем протяжении текста. В объемистый набор из 39 упражнений в конце 5 - й главы включены некоторые классические рекурсивные задачи, например, Ханойская башня. [40]
Но эта универсальность относилась лишь к ограниченной области математических головоломок с относительно небольшим множеством состояний и хорошо очерченных формальных правил. Как и большинство ее современниц, система GPS функционировала в таком формализованном микромире, где возникающие проблемы ( например, задача Ханойская башня, задача о миссионерах и людоедах), с точки зрения людей, проблемами и не являются. [41]
Была проделана большая работа по разработке этой модели, Hq для решения практических задач эта идея не нашла широкого применения. В первых учебниках по искусственному интеллекту [ Хант, 1986; Эндрю, 1985 ] описаны эти программы - они играют в игру 15, собирают Ханойскую башню, играют в шашки и шахматы. [42]
Рекурсивное решение проблемы состоит из двух этапов. Первый этап решения заключается в сведении данной проблемы к новой, похожей на исходную, но несколько проще. При решении задачи Ханойской башни этот этап состоял в замене переноса 64 дисков переносом 63 дисков. Подобная замена может производиться повторно до тех пор, пока решение проблемы не станет тривиальным. Задача Ханойской башни будет решена, когда для переноса не останется ни одного диска. [43]
Есть и другие категории проблем, которые можно определить и тем самым решить рекурсивно. К ним относится то, что можно классифицировать как загадки или игры. Классический пример - задача Ханойская башня, в которой набор дисков различной величины перемещается с одной башни на другую. Имеется три башни и произвольное число дисков, помещенных в башни. В начале игры все диски расположены на одной башне по размеру, причем наибольший - внизу башни. Правила задают, что за один раз можно перемещать только один диск и больший диск никогда не помещать на меньший. [44]
Рисование меток в порядке, показанном на рис. 5.8, может оказаться более предпочтительным по сравнению с выполнением вычислений в измененном порядке, содержащихся в программе 5.9 и приведенных на рис. 5.11, поскольку можно нарисовать линейку произвольной длины. Достаточно представить себе графическое устройство, которое просто перемещается вдоль непрерывной ленты к следующей метке. Аналогично, при решении задачи о ханойских башнях мы ограничиваемся перемещением дисков в требуемом порядке перемещения. Вообще говоря, многие рекурсивные программы основываются на решениях подзадач, которые должны быть выполнены в конкретном порядке. Для других вычислений ( например, см. программу 5.6) порядок решения подзадач роли не играет. Для таких вычислений единственным ограничением служит необходимость решения подзадач перед тем, как можно будет решить главную задачу. Понимание того, когда можно изменять порядок вычисления, не только служит ключом к успешной разработке алгоритма, но и оказывает непосредственное практическое влияние во многих случаях. Например, этот вопрос исключительно важен при исследовании возможности реализации алгоритмов в параллельных процессорах. [45]