Clauses. Nondeterm min(integer,integer,integer,integer)

Nondeterm repeat

Nondeterm vxod

Predicates

Min(A1,B1,Y1,X).

Goal

Min(A1,B1,Y1,X).

Clauses

Nondeterm min(integer,integer,integer,integer)

Predicates

Factor(N1,Z1,X).

Goal

Factor(N1,Z1,X).

Clauses

Nondeterm factor(integer,integer,integer)

Predicates

ЛАБОРАТОРНАЯ РАБОТА №3.

РЕКУРСИЯ И ПОВТОРЕНИЯ.

ЦЕЛЬ. Изучить механизм рекурсии и механизм повторения в языке Пролог.

ТЕОРИЯ. Рекурсия – это вызов одного предиката через самого себя. Обычно в качестве примера дают вычисление факториала. Рассмотрим, как это делается в Прологе.

include "my.inc"

factor(1,Z,X):- X=Z.

factor (N,Z,X):-

Z1=Z*N,

N1=N-1,

factor(5,1,X), write("Factor=",X), readchar(_).

Здесь вычисляется факториал 5. Он равен 120 (5!=120). Вычисление факториала n! Реализуется по формуле FACTOR(n)=n*FACTOR(n-1). Такая формула называется рекурсивной, поскольку она вычисляется через саму себя, но с меньшим значением аргумента. В программе в формуле FACTOR(…) три аргумента: само число, накопленное значение факториала и переменная для результирующего значения.

Имеется два правила. Легче всего понять второе:

factor (N,Z,X):-

Z1=Z*N,

N1=N-1,

Здесь считается, что Z – текущее накопленное произведение (вычисленная часть факториала). Далее формируется новое произведение: Z1=Z*N,

Само число N уменьшается на единицу: N1=N-1,

После этого вызывается factor(N1,Z1,X) для уменьшенного уже на единицу числа N и нового промежуточного значения факториала. Рано или поздно после вычитания единиц из числа это число само станет равным 1 и тогда нам потребуется первое правило: factor(1,Z,X):- X=Z.

Здесь Z уже и будет реальным накопленным произведением, равным значению факториала.

Другой пример – рекурсивное вычисление минимума из двух чисел:

min(0,B,Y,X):- X=Y.

min(A,0,Y,X):- X=Y.

min(A,B,Y,X):-

A1=A-1,

B1=B-1,

Y1=Y+1,

min(5,3,0,X), write("Minimum=",X), readchar(_).

Здесь для отыскания минимума из чисел 5 и 3 вызываем предикат: min(5,3,0,X), значение минимума записываем в X. Будем считать, что минимум отыскивается для положительных чисел. Основное рекурсивное правило такое:

min(A,B,Y,X):-

A1=A-1,

B1=B-1,

Y1=Y+1,

Это правило следует понимать так, что минимальное из двух чисел не изменится, если из каждого из этих чисел вычесть по 1. Само минимальное значение при этом нужно нарастить на 1. Теперь должен быть ясен смысл первых двух правил:

min(0,B,Y,X):- X=Y.

min(A,0,Y,X):- X=Y.

ЗАДАНИЕ НА РЕКУРСИЮ.

1. Написать программу для рекурсивного определения функции X². (X – целое положительное)
2. Написать программу для рекурсивного определения суммы 1+2+3+4+…+n. n задается.
3. Написать программу для рекурсивного определения min(A, B,C).

Теперь обратимся к повторениям. Рассмотрим следующий пример.

vxod:-

Дата добавления: 2015-06-27