Схема примитивной рекурсии

Схема примитивной рекурсии - это алгоритм определения вида функции f(x,y) на основе известных функций φ(x) и ψ(x,y,z), причём f(x,0)=φ(x), а f(x,n)=ψ(x,n-1,f(x,n-1)).

Алгоритм

Входные данные: n; φ(x); ψ(x,y,z).

Выходные данные: f(x,y).

Примеры работы алгоритма

Пример 1

Входные данные: n=3; φ(x)=x; ψ(x,y,z)=xz.

Выходные данные: f(x,y)=x^y+1.

Пример 2

Входные данные: n=3; φ(x)=0; ψ(x,y,z)=x+y.

Выходные данные: f(x,y)=x+y-1.

Другие алгоритмы:

• алгоритм метода математической индукции;
• алгоритмы в арифметике;
• алгоритмы перевода чисел;
• комбинаторные алгоритмы;
• алгоритм сортировки;
• алгоритм определения мест;
• логистические алгоритмы;
• алгоритмы решения транспортных задач;
• алгоритмы численных методов;
• алгоритмы построенные с помощью машины Поста;
• алгоритмы построенные с помощью машины Тьюринга;
• алгоритм синтеза автомата Мили;
• алгоритм синтеза автомата Мура.

Ссылки

• Участник:Logic-samara