IPB
ЛогинПароль:

 
 Ответить  Открыть новую тему 
> Теория алгоритмов, А тут мне помогут?:(
сообщение
Сообщение #1


Пионер
**

Группа: Пользователи
Сообщений: 87
Пол: Мужской

Репутация: -  0  +


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


В поисках Занаду
*

Группа: Пользователи
Сообщений: 17
Пол: Мужской
Реальное имя: Андрей Максай

Репутация: -  0  +


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

Сообщение отредактировано: MAXXX -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Пионер
**

Группа: Пользователи
Сообщений: 87
Пол: Мужской

Репутация: -  0  +


Примитивно рекурсивные!!! разницу чуствуешь? надо привести примитивно рекурсивное описание...Эт Я и сам знаю=)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

НОК: покажи, что умножение и деление примитивно-рекурсивны, и юзай формулу НОК(x, y) = x * y / НОД(x, y)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Fanat
***

Группа: Пользователи
Сообщений: 261
Пол: Мужской
Реальное имя: Сергей

Репутация: -  5  +


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

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

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Пионер
**

Группа: Пользователи
Сообщений: 87
Пол: Мужской

Репутация: -  0  +


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

Мин и макс Я доказывал...
НОД(x, y) = НОД(max(x, y) - min(x, y), min(x, y))
Эту формула юзать как подстановку, т.е. в неё это запихивать? или по какому праву или фор-ле?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

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

Еще, кроме мин и макс, тут минус понадобится, но он вроде как уж совсем примитивно-рекурсивный, чтоб это доказывать smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Пионер
**

Группа: Пользователи
Сообщений: 87
Пол: Мужской

Репутация: -  0  +


ОК спс...Вечерком попробую-отчет обязательно напишу=) точнее скорее всего еще кучу вопросов)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Пионер
**

Группа: Пользователи
Сообщений: 87
Пол: Мужской

Репутация: -  0  +


Так, пришел Я значит к алгоритму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
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата(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 Читай википедию, там все хорошо расписано.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Пионер
**

Группа: Пользователи
Сообщений: 87
Пол: Мужской

Репутация: -  0  +


С каждым разом все яснее и яснее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
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

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

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

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

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

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

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

>СпасиБеще

Всегда рад smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Пионер
**

Группа: Пользователи
Сообщений: 87
Пол: Мужской

Репутация: -  0  +


Насчет блаблаблаsmile.gif
НОД(x, 0) = х
НОД(x, у+1) =F(x,y,НОД(х,у))
а нод(х.у), мы как доказывали вроде ужо обсудилиsmile.gif
Если чтото не так, ты уже скажи как, а то скоро сдавать ужеsmile.gif но вроде приложил максимум умаsmile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Пионер
**

Группа: Пользователи
Сообщений: 87
Пол: Мужской

Репутация: -  0  +


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

Добавлено через 10 мин.
и еще НОК(х,0)=х
НОК(х,у+1)=f([?e?f([?e))
такс?smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


>Насчет блаблабла
>НОД(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 надо сделать.

Сообщение отредактировано: Michael_Rybak -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Пионер
**

Группа: Пользователи
Сообщений: 87
Пол: Мужской

Репутация: -  0  +


Насчета НОКа Я правильно написал-то?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((
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

Насчет 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 добавить там (см. выше).
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Пионер
**

Группа: Пользователи
Сообщений: 87
Пол: Мужской

Репутация: -  0  +


не сдал сегодня...
В начале не смог разобраться с примером, но кое-как убедил ее...Помог и объяснять она не захотела, мол долго и вообще задача моя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
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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


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

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

Ну ок, давай в асе пообсуждаем.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 22.09.2020 13:09
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name