 Теория алгоритмов, А тут мне помогут?:( |
Правила форума :: Скачать Pascal :: FAQ // Ада–2020 :: Скачать GNAT :: OEM–2015 :: Ada -> C/C++
| TOPEHTO |
Сообщение
#1
|
|
Пионер  Группа: Пользователи Сообщений: 87 Пол: Мужской Репутация:  0   |
Народ нужна ваша помощь! подскажите хотя бы с чего начать:Нужно доказать что НОД и НОК примитивно рекурсивные функции...кто поможет?
|
   |
 
|
  |
Ответов
| Michael_Rybak |
Сообщение
#2
|
|
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 Теория алгоритмов 20.05.2007 13:23
MAXXX Нод(а,б)={
Если а=0 и б=0 то Нод-любое число
Если … 20.05.2007 13:44 TOPEHTO Примитивно рекурсивные!!! разницу чуст… 20.05.2007 14:52 Michael_Rybak НОД: покажи, что min и max примитивно-рекурсивны, … 21.05.2007 6:16
Fanat Умножение вот так:
M(2)(X,0)=g(X)=0.
M(2)(X,A+1)=… 21.05.2007 11:51 TOPEHTO
Мин и макс Я доказывал...
НОД(x, y) = НОД(max(x, … 21.05.2007 13:51 Michael_Rybak Нет, не как подстановку, а как примитивную рекурси… 21.05.2007 16:26 TOPEHTO ОК спс...Вечерком попробую-отчет обязательно напиш… 21.05.2007 22:40 TOPEHTO Так, пришел Я значит к алгоритму:)
1) доказываю пр… 22.05.2007 0:01 Michael_Rybak
Мин и макс Я доказывал...
НОД(x, y) = НОД(max(x, … 22.05.2007 3:52 TOPEHTO С каждым разом все яснее и яснее:)
Вот это писать… 22.05.2007 10:47 Michael_Rybak >вместо блаблабла?
Что писать вместо блаблабла… 22.05.2007 15:45 TOPEHTO Насчет блаблабла:)
НОД(x, 0) = х
НОД(x, у+1) =F(x,… 23.05.2007 23:17 TOPEHTO подскажи в кратце, как целочисленное деление доказ… 24.05.2007 0:51 Michael_Rybak >Насчет блаблабла
>НОД(x, 0) = х
>НОД(x, … 24.05.2007 3:01 TOPEHTO Насчета НОКа Я правильно написал-то?:)
и еще НОК(х… 24.05.2007 23:49 TOPEHTO не сдал сегодня...
В начале не смог разобраться с … 26.05.2007 20:25 Michael_Rybak
Если я правильно себе представляю ситуацию, то е… 26.05.2007 23:59 |
2 чел. читают эту тему (гостей: 2, скрытых пользователей: 0)
Пользователей: 0
|
Текстовая версия | 13.09.2025 10:47 |
Связь с администрацией: bu_gen в домене octagram.name