Теория алгоритмов, А тут мне помогут?:( |
Теория алгоритмов, А тут мне помогут?:( |
TOPEHTO |
Сообщение
#1
|
Пионер Группа: Пользователи Сообщений: 87 Пол: Мужской Репутация: 0 |
Народ нужна ваша помощь! подскажите хотя бы с чего начать:Нужно доказать что НОД и НОК примитивно рекурсивные функции...кто поможет?
|
Michael_Rybak |
Сообщение
#2
|
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 - |
Текстовая версия | 7.05.2024 18:31 |