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

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Наибольший общий делитель, Алгоритм Евклида
сообщение
Сообщение #1


Пионер
**

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

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


Всем привет! smile.gif
Дана задача: Описать нерекурсивную функцию NOD2(A,В) целого типа, находящую наибольший общий делитель (НОД) двух натуральных чисел A и B, используя алгоритм Евклида. С помощью этой функции найти наибольшие общие делители пар A и B, A и C, A и D, если даны числа A, B, C, D.
Никогда не пользовался этим алгоритмом, подскажите в чем суть алгоритма Евклида?

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


Знаток
****

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

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


первый вариaнт

function nod(a,b : longint):longint;
begin
while (a > 0) and (b > 0) do
if a > b then a := a - b
else b := b-a;
nod := a + b;
end;


второй вариант

function nod(a,b : longint):longint;
begin
while (a > 0) and (b > 0) do
if a > b then a := a - b * (a div b )
else b := b-a * (b div a);
nod := a + b;
end;


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


Пионер
**

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

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


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


Бывалый
***

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

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


В этих вариантах могут быть кое-какие проблемы если передать отрицательные
числа.
function nod(a,b : longint):longint;
begin
while (a > 0) and (b > 0) do
if a > b then a := a - b else b := b-a;
nod := a + b;
end;
....
BEGIN
....
i:=NOD(-15,-30);
....
END;

i будет равен -45. Что бы этого не случилось нужно делать так:
function nod(a,b : longint):longint;
begin
If a<0 then a:=abs(a);
If b<0 then b:=abs(B);
while (a > 0) and (b > 0) do
if a > b then a := a - b else b := b-a;
nod := a + b;
end;
....
BEGIN
....
i:=NOD(-15,-30);
....
END;

Тогда i будет равен 15.

Сообщение отредактировано: volvo -


--------------------
Доброго времени суток.
:nnn:
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






Цитата(Дож @ 28.08.05 10:50)
В этих вариантах могут быть кое-какие проблемы если передать отрицательные числа.

blink.gif Дож, а с какой это радости надо передавать в функцию отрицательные числа? В следующий раз внимательно читай задание:
Цитата(kent @ 22.08.05 6:44)
Описать нерекурсивную функцию NOD2(A,В) целого типа, находящую наибольший общий делитель (НОД) двух натуральных чисел A и B, используя алгоритм Евклида.
Где ты видел отрицательные натуральные числа? Они все положительны ПО ОПРЕДЕЛЕНИЮ !!!
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Злостный любитель
*****

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

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


Объясните пожалуйста, зачем делать a := a - b * (a div b ), если есть операция mod?
И вычитать тоже очень неоптимально - возьмите 1000000000 и 1 и найдите их НОД первым алгоритмом.


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


Гость






TarasBer, ты б еще лет через 10 зашел и попросил объяснить dry.gif
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


?
***

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

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


lol.gif а че волне вероятно, 4 года терпел, че там еще 4 можна будет good.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

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

 





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