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