Теория алгоритмов, А тут мне помогут?:( |
Теория алгоритмов, А тут мне помогут?:( |
TOPEHTO |
Сообщение
#1
|
Пионер Группа: Пользователи Сообщений: 87 Пол: Мужской Репутация: 0 |
Народ нужна ваша помощь! подскажите хотя бы с чего начать:Нужно доказать что НОД и НОК примитивно рекурсивные функции...кто поможет?
|
Michael_Rybak |
Сообщение
#2
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
НОД: покажи, что min и max примитивно-рекурсивны, и юзай формулу НОД(x, y) = НОД(max(x, y) - min(x, y), min(x, y))
НОК: покажи, что умножение и деление примитивно-рекурсивны, и юзай формулу НОК(x, y) = x * y / НОД(x, y) |
Fanat |
Сообщение
#3
|
Fanat Группа: Пользователи Сообщений: 261 Пол: Мужской Реальное имя: Сергей Репутация: 5 |
Умножение вот так:
M(2)(X,0)=g(X)=0. M(2)(X,A+1)=h(X,A,M(X,A))=x*a+a=A(M(X,A),X) M=ро(оперотор примитивной рекурсии)[N(1),Сигма[A,I(3,3),I(3,1)]] Использовали x(a+1)=x*a+x Запись M(2)-арность функции M-2. Запись I(3,1)-арность 3,выбирает первый элемент. Где А-сложение описываетьсята так- A(2)(X,0)=g(X)=X=I(1,1) A(2)(X,A+1)=h(X,A,A(X,A))=S(A(X,A))=сигма[S,I(3,3)] x+(a+1)=(x+a)+1. Вроде так всё.Сигма-оператор суперпозиции. |
Текстовая версия | 19.05.2024 21:55 |