К главе 11

Задача 11.1

Найдите значение следующих s-выражений:

Задача 11.2

Найдите значение следующих s-выражений:

Задача 11.3

Найдите значение следующих s-выражений

Предположим, что функция POWER (СТЕПЕНЬ) определена следующим образом:

Что случится, если этой функции в качестве показателя степени дается отрицательное число? Обобщите функцию POWER так, чтобы она правильно работала и с отрицательными степенями.

Задача 11.4

Модифицируйте функцию POWER так, чтобы получить рекурсивный вариант функции FACTORIAL (ФАКТОРИАЛ), для вычисления числа

Задача 11.5

Числа Фибоначчи определяются следующим образом:

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

Задача 11.6

Предположим, функция BIGGEST (НАИБОЛЬШИЙ) определена следующим образом:

Модифицируйте функцию BIGGEST так, чтобы определить функцию SUMUP (СЛОЖИТЬ), которая складывает друг с другом все числа в s-выражении, все атомы которого являются числами.

Задача 11.7

Задача о Ханойской башне состоит в следующем: имея стопку различных дисков на стержне А, перенести их на В, но перемещать диски можно только по одному (верхний в каждой стопке) и никогда нельзя класть больший диск поверх меньшего. См. рис. 17.11.7.

Рис. 17.11.7

Часть 1. Напишите процедуру на языке Лисп, которая дает решение для любого числа дисков. Сначала, разумеется, вам потребуется подходящее представление для этой задачи. Пусть А, В и С будут глобальными переменными, соответствующими трем стопкам, значениям которых будут списки дисков, в настоящий момент находящиеся в стопках и упорядоченные сверху вниз. Вначале значением переменной А будет что-то вроде (12 3 4), тогда как В и С имеют значение NIL. Ваша процедура будет осуществлять манипуляции в такой базе данных точно так же, как если бы вы двигали диски рукой. Процедура должна вызывать MOVE (ПЕРЕМЕСТИТЬ). У нее должно быть четыре входных переменных N, FROM (С), ТО (НА) и SPARE (ЛИШНЕЕ). Ее побочный эффект будет состоять в том, чтобы переместить N дисков из стопки FROM в стопку ТО, используя стопку SPARE. Значение функции MOVE роли не играет. Например, (MOVE 'А 'В 'С) должно привести к решению вышеуказанной задачи. Вот существенная подсказка: подумайте о том, как бы вы могли переместить все диски, кроме самого нижнего, так чтобы последний можно было бы перенести, не нарушая условия задачи.

Часть 2. Пусть "ходом" считается перемещение диска с одного стержня на другой. Как много ходов потребуется в вашем решении для случая N дисков?