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

[TOPEHTO]

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

[Michael_Rybak]

>вместо блаблабла?

Что писать вместо блаблабла - ты уж все-таки сам, ну серьезно, у тебя есть все, что нужно. Ок, подсказываю: тебе, получается, нужно здесь выразить не НОД(х, у), а НОД(х, у+1). А у тебя есть формула для НОД(х, у). Рекуррентная формула (обращающася сама к себе), т.е. как раз такая, как тебе нужно. Что надо с ней сделать, чтоб она совсем подошла? ;)

Ну и приведи к тому виду, который требуют правила записи (опять же, см. википедию).

>говорят что х\у не прим-рекурсия

Конечно, речь шла о целочисленном делении. Дело в том, что x * y всегда делится нацело на НОД(x, y), поэтому деление вынуждено будет быть целочисленным

>т.е. доказав НОД, НОК впринципе доказывается уже автоматическм, да?

Угу, если умножение и деление есть, то да.

>СпасиБеще

Всегда рад