Схема примитивной рекурсии — различия между версиями
Материал из ALL
Ws (обсуждение | вклад) (Восстановление статей Logic-samara) |
м (описание правки удалено) |
||
(не показано 12 промежуточных версий 2 участников) | |||
Строка 1: | Строка 1: | ||
'''Схема примитивной рекурсии''' - это алгоритм определения вида функции '''f(x,y)''' на основе известных функций '''φ(x)''' и '''ψ(x,y,z)''', причём '''f(x,0)=φ(x)''', а '''f(x,n)=ψ(x,n-1,f(x,n-1))'''. | '''Схема примитивной рекурсии''' - это алгоритм определения вида функции '''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)'''. | Входные данные: '''n; φ(x); ψ(x,y,z)'''. | ||
Строка 7: | Строка 6: | ||
Выходные данные: '''f(x,y)'''. | Выходные данные: '''f(x,y)'''. | ||
− | + | == Примеры работы алгоритма == | |
− | == Пример 1 == | + | === Пример 1 === |
Входные данные: '''n=3; φ(x)=x; ψ(x,y,z)=xz'''. | Входные данные: '''n=3; φ(x)=x; ψ(x,y,z)=xz'''. | ||
Строка 14: | Строка 13: | ||
Выходные данные: '''f(x,y)=x<sup>y+1</sup>'''. | Выходные данные: '''f(x,y)=x<sup>y+1</sup>'''. | ||
− | + | === Пример 2 === | |
− | == Пример 2 == | + | |
Входные данные: '''n=3; φ(x)=0; ψ(x,y,z)=x+y'''. | Входные данные: '''n=3; φ(x)=0; ψ(x,y,z)=x+y'''. | ||
Строка 21: | Строка 19: | ||
Выходные данные: '''f(x,y)=x+y-1'''. | Выходные данные: '''f(x,y)=x+y-1'''. | ||
− | + | == Другие алгоритмы: == | |
+ | {{Список Алг}} | ||
== Ссылки == | == Ссылки == | ||
* [[Участник:Logic-samara]] | * [[Участник:Logic-samara]] | ||
− | [[Категория:Дискретная математика | + | [[Категория:Дискретная математика]][[Категория:Алгоритмы]] |
Текущая версия на 06:08, 17 октября 2020
Схема примитивной рекурсии - это алгоритм определения вида функции 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.
Другие алгоритмы:
- алгоритм метода математической индукции;
- алгоритмы в арифметике;
- алгоритмы перевода чисел;
- комбинаторные алгоритмы;
- алгоритм сортировки;
- алгоритм определения мест;
- логистические алгоритмы;
- алгоритмы решения транспортных задач;
- алгоритмы численных методов;
- алгоритмы построенные с помощью машины Поста;
- алгоритмы построенные с помощью машины Тьюринга;
- алгоритм синтеза автомата Мили;
- алгоритм синтеза автомата Мура.