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

[TOPEHTO]

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

[Michael_Rybak]

>Насчет блаблабла
>НОД(x, 0) = х
>НОД(x, у+1) =F(x,y,НОД(х,у))

Я вообще могу ошибаться, т.к. не учил ничего такого, и юзал только википедию (вру, учил вроде, но не помню ничего), но я бы написал так:

НОД(x, 0) = х
НОД(x, у+1) =F(x,y,HОД(max(x, y+1) - min(x, y+1), min(x, y+1)))

Только то, что выделено курсивом, надо еще расписать по правилам (через подстановки, I, S, и полученые ранее функции min, max, +, -). И еще саму F написать, чтоб она возвращала I3, как в примерах из википедии.

>как целочисленное деление доказать

Я ведь подсказывал уже: нужно использовать формулу x / y = 1 + (x - y) / y.

DIV(x, 0) = 1 // не страшно, разрешаем делить на 0
DIV(x, y + 1) = F(x, y, 1 + DIV(x - (y + 1)) / (y + 1)).

Опять же, то, что внутри F надо расписать, как на википедии, и саму F - тоже.

Удачи

Добавлено через 3 мин.
Хм. Я тут подумал... Еще надо домутить как-то, чтоб если x < y, деление 0 возвращало Подумаешь, как Что-то типа if-then-else надо сделать.

Сообщение отредактировано: Michael_Rybak - 23.05.2007 23:03