Схема примитивной рекурсии
Перейти к навигации
Перейти к поиску
→ Рекурсия
Схема примитивной рекурсии — это алгоритм определения вида функции 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).
1. Определяем выражения функции f(x, y).
f(x,0) = φ(x)
f(x,1) = ψ(x,0,f(x,0))
f(x,2) = ψ(x,1,f(x,1))
…,
f(x,n−1) = ψ(x,n−2,f(x,n−2))
f(x,n) = ψ(x,n−1,f(x,n−1))
2. По аналогии определяем формулу f(x, y).
3. Методом математической индукции доказываем формулу f(x, y), проведя индукцию по y.
Выходные данные: f(x, y).
Примеры работы алгоритма[править]
Пример 1[править]
Входные данные: n = 3; φ(x) = x; ψ(x, y, z) = xz.
Выходные данные: f(x, y) = xy+1.
Пример 2[править]
Входные данные: n = 3; φ(x) = 0; ψ(x, y, z) = x + y.
Выходные данные: f(x, y) = x + y - 1.
Другие алгоритмы[править]
- метод математической индукции;
- алгоритмы в арифметике;
- алгоритмы перевода чисел;
- комбинаторные алгоритмы;
- сортировка;
- алгоритм определения мест;
- логистические алгоритмы;
- алгоритмы решения транспортных задач;
- численные методы;
- схема примитивной рекурсии;
- виды рекурсии;
- машина Поста;
- машина Тьюринга (вероятностная);
- синтез автомата Мили;
- синтез автомата Мура.