Составители:
Рубрика:
в том, что значение функции f в точке x определяется через значения
этой функции в "предшествующих" точках.
Оператор примитивной рекурсии
Оператор примитивной рекурсии определяет (n+1)-местную
функцию f(x
,...,x ;y) через n-местную функцию g(x ,...,x
n1 1 n
) и (n+2)-
местную функцию h(x
,...,x ; y; z) следующим образом:
n1
,...,x ;0)=g(x ,...,x
f(x
),
n n1 1
,...,x ; 1)=h(x ,...,x ; 0; f(x ,...,x
f(x
; 0)),
n n n1 1 1
,...,x ; 2)=h(x ,...,x ; 1; f(x ,...,x
f(x
; 1)),
n n n1 1 1
...
f(x
,...,x ; m+1)=h(x ,...,x ; m; f(x ,...,x ; m)).
n n n1 1 1
Пример 4.5. Пусть переменные x ,...,x
n1
отсутствуют, причем рекурсивная
схема задана соотношениями
g=0,
h(y; z)=2*y+z.
Тогда
f(0)=0,
f(1)=2*0+0=0,
f(2)=2*1+0=2,
f(3)=2*2+2=6,
f(4)=2*3+6=12,
f(5)=2*4+12=20,
...
f(x+1)=2*x+f(x).
Функцию определенную данной рекурсивной схемой можно выразить
аналитически:
f(x+1)=2*x+f(x)=2*x+2*(x-1)+f(x-1)=...=
2*x+2*(x-1)+2*(x-2)+...+2*2+2*1=
2*[x+(x-1)+(x-2)+...+2+1].
Выражение в прямоугольных скобках [ ] представляет сумму чисел от 1 до x,
равную по формуле арифметической прогрессии (x+1)*x/2, поэтому получаем
f(x+1)=(x+1)*x, или f(x)=x*(x-1).
Определение4.1. Примитивно-рекурсивная функция (ПР-
функция) это одна из простейших функций:
152
Страницы
- « первая
- ‹ предыдущая
- …
- 66
- 67
- 68
- 69
- 70
- …
- следующая ›
- последняя »
