Теория алгоритмов, А тут мне помогут?:( |
Теория алгоритмов, А тут мне помогут?:( |
TOPEHTO |
Сообщение
#1
|
Пионер Группа: Пользователи Сообщений: 87 Пол: Мужской Репутация: 0 |
Народ нужна ваша помощь! подскажите хотя бы с чего начать:Нужно доказать что НОД и НОК примитивно рекурсивные функции...кто поможет?
|
MAXXX |
Сообщение
#2
|
В поисках Занаду Группа: Пользователи Сообщений: 17 Пол: Мужской Реальное имя: Андрей Максай Репутация: 0 |
Нод(а,б)={
Если а=0 и б=0 то Нод-любое число Если а=0 или б=0 то Нод равен (а+б) Если а>б то Нод(а мод б,б) иначе равен Нод(а,б мод а) Сообщение отредактировано: MAXXX - |
TOPEHTO |
Сообщение
#3
|
Пионер Группа: Пользователи Сообщений: 87 Пол: Мужской Репутация: 0 |
Примитивно рекурсивные!!! разницу чуствуешь? надо привести примитивно рекурсивное описание...Эт Я и сам знаю=)
|
Michael_Rybak |
Сообщение
#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) |
Fanat |
Сообщение
#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. Вроде так всё.Сигма-оператор суперпозиции. |
TOPEHTO |
Сообщение
#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)) Эту формула юзать как подстановку, т.е. в неё это запихивать? или по какому праву или фор-ле? |
Michael_Rybak |
Сообщение
#7
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Нет, не как подстановку, а как примитивную рекурсию.
НОД(x, 0) = x НОД(x, y + 1) = f(... тут юзаешь формулу; вот здесь - куча подстановок как раз ...) Еще, кроме мин и макс, тут минус понадобится, но он вроде как уж совсем примитивно-рекурсивный, чтоб это доказывать |
TOPEHTO |
Сообщение
#8
|
Пионер Группа: Пользователи Сообщений: 87 Пол: Мужской Репутация: 0 |
ОК спс...Вечерком попробую-отчет обязательно напишу=) точнее скорее всего еще кучу вопросов)
|
TOPEHTO |
Сообщение
#9
|
Пионер Группа: Пользователи Сообщений: 87 Пол: Мужской Репутация: 0 |
Так, пришел Я значит к алгоритму
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 |
Сообщение
#10
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Мин и макс Я доказывал... НОД(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 |
Сообщение
#11
|
Пионер Группа: Пользователи Сообщений: 87 Пол: Мужской Репутация: 0 |
С каждым разом все яснее и яснее
Цитата НОД(x, 0) = x НОД(x, y + 1) = f(... тут юзаешь формулу; вот здесь - куча подстановок как раз ...) Вот это писать вместо блаблабла? Тады вот тут НОД(x, y + 1) = Что такого отписать, просто в душе не понимаю примеры глянул кое-что попонятней И насчет деления, говорят что х\у не прим-рекурсия...3\5 не принадлежит натуральным числам, вот [3\5] , т.е. взятие целой части-прим\рекурсия...но это в принципе доказано, просто удостовериваюсь И еще масенький вопрос: НОК:НОК(x, y) = x * y / НОД(x, y) т.е. доказав НОД, НОК впринципе доказывается уже автоматическм, да? Добавлено через 1 мин. СпасиБеще ОГРОМНОЕ за ПОМОЩЬ!!!!!!!!!!!!!!!!!!!!! |
Michael_Rybak |
Сообщение
#12
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
>вместо блаблабла?
Что писать вместо блаблабла - ты уж все-таки сам, ну серьезно, у тебя есть все, что нужно. Ок, подсказываю: тебе, получается, нужно здесь выразить не НОД(х, у), а НОД(х, у+1). А у тебя есть формула для НОД(х, у). Рекуррентная формула (обращающася сама к себе), т.е. как раз такая, как тебе нужно. Что надо с ней сделать, чтоб она совсем подошла? ;) Ну и приведи к тому виду, который требуют правила записи (опять же, см. википедию). >говорят что х\у не прим-рекурсия Конечно, речь шла о целочисленном делении. Дело в том, что x * y всегда делится нацело на НОД(x, y), поэтому деление вынуждено будет быть целочисленным >т.е. доказав НОД, НОК впринципе доказывается уже автоматическм, да? Угу, если умножение и деление есть, то да. >СпасиБеще Всегда рад |
TOPEHTO |
Сообщение
#13
|
Пионер Группа: Пользователи Сообщений: 87 Пол: Мужской Репутация: 0 |
Насчет блаблабла
НОД(x, 0) = х НОД(x, у+1) =F(x,y,НОД(х,у)) а нод(х.у), мы как доказывали вроде ужо обсудили Если чтото не так, ты уже скажи как, а то скоро сдавать уже но вроде приложил максимум ума |
TOPEHTO |
Сообщение
#14
|
Пионер Группа: Пользователи Сообщений: 87 Пол: Мужской Репутация: 0 |
подскажи в кратце, как целочисленное деление доказать, ато в тетради много решений незаконченных...
одно решение через конечное произведение... спс заранее Добавлено через 10 мин. и еще НОК(х,0)=х НОК(х,у+1)=f([?e?f([?e)) такс? |
Michael_Rybak |
Сообщение
#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 - тоже. Удачи Добавлено через 3 мин. Хм. Я тут подумал... Еще надо домутить как-то, чтоб если x < y, деление 0 возвращало Подумаешь, как Что-то типа if-then-else надо сделать. Сообщение отредактировано: Michael_Rybak - |
TOPEHTO |
Сообщение
#16
|
Пионер Группа: Пользователи Сообщений: 87 Пол: Мужской Репутация: 0 |
Насчета НОКа Я правильно написал-то?
и еще НОК(х,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 |
Сообщение
#17
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Для НОКа тебе вообще не нужна примитивная рекурсия: просто вызываешь умножение, деление и НОД. Обычные подстановки.
Насчет I3 - честное слово, на википедии все разобрано. Ну найди еще пример где нибудь. Или в группе товарищей спроси. Ну лень мне выписывать все подстановки Суть в том, что у нас есть строго ограниченный набор того, что можно писать. Везде у нас одни только функции. Функции что-то возвращают. Все функции записываются в виде f(a1, a2, .. , ak). И есть правила: подстановка, и прим. рекурсия. Их тоже можно юзать. Вот тебе вся система. В ней и работай. На крайняк так и неси преподу уже как есть, он только рад будет что-то объяснить пытливому уму >и еще такой вопрос, если рассмотреть на конкретном примере: >НОД(27,9)=(27-9,9) Не так. НОД(27, 9) = I3(27, 9, НОД(-(max(27, 9), min(27, 9)))) Вот я и написал таки всё за тебя. Тебе осталось обобщить >как просто деление доказать Просто деление (не целочисленное) доказать нельзя. А целочисленное - я показал как, только надо еще условие x<y добавить там (см. выше). |
TOPEHTO |
Сообщение
#18
|
Пионер Группа: Пользователи Сообщений: 87 Пол: Мужской Репутация: 0 |
не сдал сегодня...
В начале не смог разобраться с примером, но кое-как убедил ее...Помог и объяснять она не захотела, мол долго и вообще задача моя Вопрос вот в чем, надо как-то эту функцию зациклить(зарекурсивить))) просто к какомы выводу Я пришел... нод(х,у)=либо НОД(х,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 |
Сообщение
#19
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Цитата Помог и объяснять она не захотела, мол долго и вообще задача моя Если я правильно себе представляю ситуацию, то ее работа состоит в том, чтоб тебе это всё было понятно. Другое дело, кто из вас с ней при этом втыкал. Ну ок, давай в асе пообсуждаем. |
Текстовая версия | 23.04.2024 20:01 |