Практикум 3-4

	Проверьте, как работает программа вычисления факториала, добавив вывод промежуточных результатов с помощью предикатов write("N1=",N1) после вычисления N1 и write("N1=",N1," F1=",F1) после вычисления fact(N1,F1).

Программа, представленная на рис. 3.7. должна печатать на экране компьютера цифры от 1 до 10.

Рис 3.7. Программа печати чисел

Практикум 3-5

	а) Проверьте, действительно ли программа, представленная на рис. 3.7 печатает числа от 1 до 10? Исправьте программу, чтобы она работала правильно. б) Создайте программу печати чисел в обратном порядке от 10 до 1.

Программа, представленная на рис. 3.8 печатает сумму всех цифр введенного с клавиатуры числа.

Рис 3.8. Программа вычисления суммы цифр целого числа

Использование предиката ! в описании базиса рекурсии позволяет избежать здесь переполнения стека.

Практикум 3-6

	а) Проверьте, действительно ли программа, представленная на рис. 3.8 правильно считает сумму цифр. б) Создайте программу перевода десятичного числа в двоичное. (Двоичное число можно представить как строку из 0 и 1)

Хвостовая рекурсия

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

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

Пример. На рис. 3.9. представлен пример использования хвостовой рекурсии для вычисления факториала.

Вычисления осуществляются с помощью дополнительного предиката, в который передаются исходные данные и начальные значения. В дополнительном предикате третий параметр – это натуральные числа 1, 2, …, N, а в четвертом последовательно вычисляются значения 1!, 2!, … , N!

Процесс останавливается, когда третий параметр достигнет значения N.

Рис 3.9. Программа вычисления N! с использованием хвостовой рекурсии

Практикум 3-7

	С использованием хвостовой рекурсии вычислить Y=XN

Самостоятельные задания

1. На рис. 3.10 представлен пример Пролог - программы. Какого цвета использовано отсечение – красное или зеленое?

Рис 3.10. Программа с использованием отсечения

2. Даны а,n. Вычислить S=a+a²+a³+…+aⁿ

3. Даны а,n. Вычислить S=a+a(a+1)+a(a+1)(a+2)+…+a(a+1)*…*(a+n)

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 4.

Понятие списков в Прологе

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

При записи список заключают в квадратные скобки, а элементы списка разделяют запятыми, например:

[1,2,3]

[1.1,1.2,3.6]

[“вчера”,”сегодня”,”завтра”]

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

В Прологе списки должны быть обязательно объявлены в разделе domains. Для этого необходимо ввести имя нового домена и определить домен, который описывает тип элементов, объединяемых в список (в качестве такого домена можно использовать стандартные домены).

В разделе описания доменов списки описываются следующим образом:

domains

<имя спискового домена>=<имя домена элементов списка>*

Звездочка после имени домена указывает на то, что мы описываем список, состоящий из объектов соответствующего типа.

Например:

domains

list_integer = integer* /*вводится домен списка целых чисел */

list_s = symbol* /* вводится домен списка символов*/

list_list = list_s* /* элементами этого списка должны быть списки символов*/

Например: num([1,2,3]).

Пусть мы хотим описать с помощью списка породы собак (рис. 4.1).

Рис. 4.1. Пример программы со списком

В результате выполнения запроса, представленного на рис. 4.1, запроса будут напечатаны все породы собак, а после запроса:

получим:

Каждый непустой список может быть разделен на голову – первый элемент списка и хвост – остальные элементы списка. Это позволяет всякий список представить в виде бинарного дерева (рис. 4.2).

Рис. 4.2. Представление списка в виде бинарного дерева

У списка, состоящего только из одного элемента, головой является этот элемент, а хвостом – пустой список.

Хвост списка всегда есть список; голова списка есть элемент.

Если многократно отнимать первый элемент от хвоста списка, мы получим в конечном итоге пустой список ([ ]).

Пустой список не может быть разбит на голову и хвост.

Операция разделения списка на голову и хвост обозначается с помощью вертикальной черты: