Итерационные процессы. Процесс, состояние которого на текущем шаге зависит от состояния этого же процесса на предыдущих r шагах, называется многошаговым итерационным процессом и описывается следующими рекурентными соотношениями:
y0=a0, y1=a1,...,yr-1=ar-1; (1a) (начальные условия)
yk=f(yk,yk-1,yk-2,...,yk-r,X); (1б) (текущий момент) (1)
k=r, r+1, ..., ..., k=N, (1в) (условие окончания)
где f - произвольная функция, которая может быть задана аналитически, словесно, в виде алгоритма и т. д.;
yi - состояние процесса на i-м шаге;
X - параметры процесса.
Частным случаем (1) является одношаговый итерационный процесс yn=f(yn-1), в котором текущее состояние зависит только от предыдущего. Примерами итерационных процессов являются:
• вычисление суммы: S0=0, Sn=Sn-1+un, n=1, 2,...;
• вычисление произведения: P0=1, Pn=Pn-1*mn, n=1, 2,...и многие другие.
Программирование итерационных процессов по рекуррентным формулам (1) может осуществляться двумя способами: методом итерации (повторений) и методом рекурсии. Метод итераций рассмотрен в теме №4. Для его реализации организуется цикл, на каждом шаге которого текущее состояние процесса получается путем извлечения и стирания из памяти информации о его предшествующих состояниях, вычисления нового значения по формуле (1б) и записи вновь полученных значений на место соответствующих предшествующих состояний. Так, например, рекуррентным соотношениям, описывающим вычисления F=N!, может быть поставлена в соответствие следующая программа на Прологе.
'факториал'(N,F):-
asserta ('фак'(0,1)), /* запись в БЗ */
/* начальных условий */
repeat, /* заголовок цикла */
retract ('фак'(K,P)), /* стирание из БЗ */
/* предыдущих значений */
K1 is K+1,
P1 is P1*K1,
asserta('фак'(K1,P1)), /* запись в БЗ новых значений */
K1=N, /* условие окончания цикла */
retract('фак' (N,F)), /* вывод результатов */
write (F),nl.
?-'факториал(Z,F), /* запрос */
|
Главная
Каталог файлов
