Помощь - Поиск - Пользователи - Календарь
Полная версия: Теория алгоритмов
Форум «Всё о Паскале» > Разработка ПО, алгоритмы, общие вопросы > Алгоритмы
TOPEHTO
Народ нужна ваша помощь! подскажите хотя бы с чего начать:Нужно доказать что НОД и НОК примитивно рекурсивные функции...кто поможет?
MAXXX
Нод(а,б)={
Если а=0 и б=0 то Нод-любое число
Если а=0 или б=0 то Нод равен (а+б)
Если а>б то Нод(а мод б,б)
иначе равен Нод(а,б мод а)
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(... тут юзаешь формулу; вот здесь - куча подстановок как раз ...)

Еще, кроме мин и макс, тут минус понадобится, но он вроде как уж совсем примитивно-рекурсивный, чтоб это доказывать smile.gif
TOPEHTO
ОК спс...Вечерком попробую-отчет обязательно напишу=) точнее скорее всего еще кучу вопросов)
TOPEHTO
Так, пришел Я значит к алгоритмуsmile.gif
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)) и тем самым Я все доказываю, Я прально мысллить начал? smile.gif
p/s/ Если что не так пиши плиз максимально подробно и доступно, т.к. это для меня китайская клинописьsmile.gif

Добавлено через 2 мин.
Кста, как доказать что деление примитивно-рекурсивноsmile.gif
Помогите плиз, чем подробнее тем лучшеsmile.gif и с коментамиsmile.gif
Michael_Rybak
Цитата(TOPEHTO @ 21.05.2007 9:51) *

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

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

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

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

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

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

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

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

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


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

Извини, чем могу smile.gif Читай википедию, там все хорошо расписано.
TOPEHTO
С каждым разом все яснее и яснееsmile.gif
Цитата
НОД(x, 0) = x
НОД(x, y + 1) = f(... тут юзаешь формулу; вот здесь - куча подстановок как раз ...)

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

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

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

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

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

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

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

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

>СпасиБеще

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

Добавлено через 10 мин.
и еще НОК(х,0)=х
НОК(х,у+1)=f([?e?f([?e))
такс?smile.gif
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 - тоже.

Удачи smile.gif

Добавлено через 3 мин.
Хм. Я тут подумал... Еще надо домутить как-то, чтоб если x < y, деление 0 возвращало smile.gif Подумаешь, как smile.gif Что-то типа if-then-else надо сделать.
TOPEHTO
Насчета НОКа Я правильно написал-то?smile.gif
и еще НОК(х,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, с точки зрения грамотностиsmile.gif
СпасиБо за помощьsmile.gif

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

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

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

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

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

Не так.

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

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

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

Просто деление (не целочисленное) доказать нельзя. А целочисленное - я показал как, только надо еще условие x<y добавить там (см. выше).
TOPEHTO
не сдал сегодня...
В начале не смог разобраться с примером, но кое-как убедил ее...Помог и объяснять она не захотела, мол долго и вообще задача мояsmile.gif
Вопрос вот в чем, надо как-то эту функцию зациклить(зарекурсивить))) просто к какомы выводу Я пришел...
нод(х,у)=либо НОД(х,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)=х...
Если можешь помоги плиз, т.к. препод сказал, что до рекурсии далеко моим методом...или еше лучше это поменять алгоритм...Я без сил уже((( надеюсь только на тебя...
Смотри ЛС плизsmile.gif
Надесь на твою помощь СПС ОГРОМНОЕsmile.gif
Michael_Rybak
Цитата
Помог и объяснять она не захотела, мол долго и вообще задача моя


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

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

Ну ок, давай в асе пообсуждаем.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.