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

[TOPEHTO]

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

[MAXXX]

Нод(а,б)={
Если а=0 и б=0 то Нод-любое число
Если а=0 или б=0 то Нод равен (а+б)
Если а>б то Нод(а мод б,б)
иначе равен Нод(а,б мод а)

Сообщение отредактировано: MAXXX - 20.05.2007 9:44

[TOPEHTO]

Примитивно рекурсивные!!! разницу чуствуешь? надо привести примитивно рекурсивное описание...Эт Я и сам знаю=)

[Michael_Rybak]

НОД: покажи, что min и max примитивно-рекурсивны, и юзай формулу НОД(x, y) = НОД(max(x, y) - min(x, y), min(x, y))

НОК: покажи, что умножение и деление примитивно-рекурсивны, и юзай формулу НОК(x, y) = x * y / НОД(x, y)

[Fanat]

Умножение вот так:
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.

Вроде так всё.Сигма-оператор суперпозиции.

[TOPEHTO]

НОД: покажи, что min и max примитивно-рекурсивны, и юзай формулу НОД(x, y) = НОД(max(x, y) - min(x, y), min(x, y))

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

[Michael_Rybak]

Нет, не как подстановку, а как примитивную рекурсию.

НОД(x, 0) = x
НОД(x, y + 1) = f(... тут юзаешь формулу; вот здесь - куча подстановок как раз ...)

Еще, кроме мин и макс, тут минус понадобится, но он вроде как уж совсем примитивно-рекурсивный, чтоб это доказывать

[TOPEHTO]

ОК спс...Вечерком попробую-отчет обязательно напишу=) точнее скорее всего еще кучу вопросов)

[TOPEHTO]

Так, пришел Я значит к алгоритму
1) доказываю про мин, что он п-р
2) аналогично с максимум)
3)Доказываю разность
4)В разность сую макс и мин, и получаю max(x, y) - min(x, y)
5) сую в итогувую фор-лу все вместе и получаю НОД(max(x, y) - min(x, y), min(x, y))
6) пишу НОД(x, y) = НОД(max(x, y) - min(x, y), min(x, y)) и тем самым Я все доказываю, Я прально мысллить начал?
p/s/ Если что не так пиши плиз максимально подробно и доступно, т.к. это для меня китайская клинопись

Добавлено через 2 мин.
Кста, как доказать что деление примитивно-рекурсивно
Помогите плиз, чем подробнее тем лучше и с коментами

[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


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

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

[TOPEHTO]

С каждым разом все яснее и яснее

НОД(x, 0) = x
НОД(x, y + 1) = f(... тут юзаешь формулу; вот здесь - куча подстановок как раз ...)

Вот это писать вместо блаблабла?
Тады вот тут НОД(x, y + 1) =
Что такого отписать, просто в душе не понимаю примеры глянул кое-что попонятней
И насчет деления, говорят что х\у не прим-рекурсия...3\5 не принадлежит натуральным числам, вот [3\5] , т.е. взятие целой части-прим\рекурсия...но это в принципе доказано, просто удостовериваюсь
И еще масенький вопрос:
НОК:НОК(x, y) = x * y / НОД(x, y)
т.е. доказав НОД, НОК впринципе доказывается уже автоматическм, да?

Добавлено через 1 мин.
СпасиБеще ОГРОМНОЕ за ПОМОЩЬ!!!!!!!!!!!!!!!!!!!!!

[Michael_Rybak]

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

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

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

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

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

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

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

>СпасиБеще

Всегда рад

[TOPEHTO]

Насчет блаблабла
НОД(x, 0) = х
НОД(x, у+1) =F(x,y,НОД(х,у))
а нод(х.у), мы как доказывали вроде ужо обсудили
Если чтото не так, ты уже скажи как, а то скоро сдавать уже но вроде приложил максимум ума

[TOPEHTO]

подскажи в кратце, как целочисленное деление доказать, ато в тетради много решений незаконченных...
одно решение через конечное произведение...
спс заранее

Добавлено через 10 мин.
и еще НОК(х,0)=х
НОК(х,у+1)=f([?e?f([?e))
такс?

[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

[TOPEHTO]

Насчета НОКа Я правильно написал-то?
и еще НОК(х,0)=х
НОК(х,у+1)=f(x,y,f(x,y))
???
потом, честно как с I3 действовать так и не понял...
примерно получил:
f(x,y,z)=(i1(x,y,z),s(i3(x,y,z))
помойму так...где-то...
и еще такой вопрос, если рассмотреть на конкретном примере:
НОД(27,9)=(27-9,9)
что еще надо дописать чтобы смело написать что этот НОД равен 9, с точки зрения грамотности
СпасиБо за помощь

Добавлено через 2 мин.
Кста, как просто деление например доказать:x / y = 1 + (x - y) / y.
???
чето Я совсем запутался((

[Michael_Rybak]

Для НОКа тебе вообще не нужна примитивная рекурсия: просто вызываешь умножение, деление и НОД. Обычные подстановки.

Насчет I3 - честное слово, на википедии все разобрано. Ну найди еще пример где нибудь. Или в группе товарищей спроси. Ну лень мне выписывать все подстановки

Суть в том, что у нас есть строго ограниченный набор того, что можно писать. Везде у нас одни только функции. Функции что-то возвращают. Все функции записываются в виде f(a1, a2, .. , ak).

И есть правила: подстановка, и прим. рекурсия. Их тоже можно юзать. Вот тебе вся система. В ней и работай. На крайняк так и неси преподу уже как есть, он только рад будет что-то объяснить пытливому уму

>и еще такой вопрос, если рассмотреть на конкретном примере:
>НОД(27,9)=(27-9,9)

Не так.

НОД(27, 9) = I3(27, 9, НОД(-(max(27, 9), min(27, 9))))

Вот я и написал таки всё за тебя. Тебе осталось обобщить

>как просто деление доказать

Просто деление (не целочисленное) доказать нельзя. А целочисленное - я показал как, только надо еще условие x<y добавить там (см. выше).

[TOPEHTO]

не сдал сегодня...
В начале не смог разобраться с примером, но кое-как убедил ее...Помог и объяснять она не захотела, мол долго и вообще задача моя
Вопрос вот в чем, надо как-то эту функцию зациклить(зарекурсивить))) просто к какомы выводу Я пришел...
нод(х,у)=либо НОД(х,0)=х если у=0, либо нод(х,у)=НОД(max(x, y) - min(x, y), min(x, y)) если у<>0
просто более крутого способа Я не нашел...
ПРО было примерно таким:
f1:max
f2:min
f3:x-y
f4: P(f3,f1,f2)

А вот дальше неизвестно как сделать рекурсию чтобы мы вычитали из максимума минимум до тех пор пока у=о, и смело писали что НОД(х,0)=х...
Если можешь помоги плиз, т.к. препод сказал, что до рекурсии далеко моим методом...или еше лучше это поменять алгоритм...Я без сил уже((( надеюсь только на тебя...
Смотри ЛС плиз
Надесь на твою помощь СПС ОГРОМНОЕ

[Michael_Rybak]

Помог и объяснять она не захотела, мол долго и вообще задача моя

Если я правильно себе представляю ситуацию, то ее работа состоит в том, чтоб тебе это всё было понятно.

Другое дело, кто из вас с ней при этом втыкал.

Ну ок, давай в асе пообсуждаем.