Теория алгоритмов, А тут мне помогут?:( Опции

[TOPEHTO]

Народ нужна ваша помощь! подскажите хотя бы с чего начать:Нужно доказать что НОД и НОК примитивно рекурсивные функции...кто поможет?

[Michael_Rybak]

Мин и макс Я доказывал...
НОД(x, y) = НОД(max(x, y) - min(x, y), min(x, y))
Эту формула юзать как подстановку, т.е. в неё это запихивать? или по какому праву или фор-ле?

В целом правильно.

Но в пункте 6, то, что ты пишешь "НОД(x, y) = НОД(max(x, y) - min(x, y), min(x, y))" ничего не доказывает

Мы имеем право юзать O, S, I, подстановку и прим. рекурсию.

Тебе нужно последнее. Т.е. ты записываешь:

НОД(x, 0) = блаблабла
НОД(x, y + 1) = блаблабла.

Более подробно смотри на википедии; достаточно посмотреть примеры, и уже не будет это для тебя никакой китайской клинописью (слово-то какое .

>как доказать что деление примитивно-рекурсивно

Нужно использовать формулу x / y = 1 + (x - y) / y


>чем подробнее тем лучше, и с коментами

Извини, чем могу Читай википедию, там все хорошо расписано.