метод Евклида - Форум
Воскресенье, 04.12.2016, 17:13
Задачи по информатике
Главная | Регистрация | Вход Приветствую Вас Гость | RSS
[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
Страница 1 из 11
Модератор форума: ignorer, KOT_B_MEIIIKE, PASCAL26, atvrider 
Форум » Решение задач по информатике » Задачи по программированию + блок-схемы » метод Евклида
метод Евклида
focusДата: Воскресенье, 11.07.2010, 10:49 | Сообщение # 1
Рядовой
Группа: Новичок
Сообщений: 2
[ 0 ]
Статус: Offline
Дано целое число А и В.
Найти наибольший общий делитель используя алгоритм Евклида: НОД (А, В) = НОД (В, А mod B), если В <> 0, НОД (А, 0), где mod обозначает операцию взятия остатка от деления. А = 5434 В=95 НОД(А; В) = 19
 
BinaryWolfДата: Воскресенье, 11.07.2010, 12:35 | Сообщение # 2
Генерал-лейтенант
Группа: Новичок
Сообщений: 51
[ 0 ]
Статус: Offline
Изложить суть метода Евклида или дать конкретный код?

Луна, единственная спутница моя, отведи меня домой, залечи раны мои и помоги забыть всё.
 
focusДата: Воскресенье, 11.07.2010, 14:38 | Сообщение # 3
Рядовой
Группа: Новичок
Сообщений: 2
[ 0 ]
Статус: Offline
дать программу, блок схему я составил, но с турбопаскалем я не дружу(
 
BinaryWolfДата: Понедельник, 12.07.2010, 03:16 | Сообщение # 4
Генерал-лейтенант
Группа: Новичок
Сообщений: 51
[ 0 ]
Статус: Offline
Я на С могу, паскаль не знаю. Если найдёшь человека, который перепишет тебе с С на Паскаль, то тогда...
Самый простой вариант для положительных чисел:
/////////////////////////////////////////////
int NOD(int a, int b)
{
if(a==b)
return a;
while(a!=b)
{ if(a>b)
a=a-b;
else
b=b-a;
}
return a;
}
//////////////////////////
Вот так вот biggrin


Луна, единственная спутница моя, отведи меня домой, залечи раны мои и помоги забыть всё.
 
WinGeekДата: Воскресенье, 18.07.2010, 22:03 | Сообщение # 5
Лейтенант
Группа: Заблокированные
Сообщений: 13
[ 1 ]
Статус: Offline
если на паскале и по методу евклида (прошлое решение не совсем по нему), то:
Code

function nod(a,b:integer):integer;
begin
   if (a<>b) and(b<>0) then nod:=nod (b, a mod b)
     else nod:=a;
end;
 
BinaryWolfДата: Понедельник, 19.07.2010, 17:48 | Сообщение # 6
Генерал-лейтенант
Группа: Новичок
Сообщений: 51
[ 0 ]
Статус: Offline
Мой метод как раз по Евклиду в оригинале, мне его аспирант-математик описывал, просто с Модом - более оптимизировано.

Твой решение ведёт к бесконечному циклу:
Пример: а=20, b=30, тогда вызывается нод(30,20), которая в свою очередь вызывает нод(30,20)
Ибо (20 МОД 30)=20

Переделай, чтобы было ближе к моему smok


Луна, единственная спутница моя, отведи меня домой, залечи раны мои и помоги забыть всё.
 
WinGeekДата: Вторник, 20.07.2010, 03:44 | Сообщение # 7
Лейтенант
Группа: Заблокированные
Сообщений: 13
[ 1 ]
Статус: Offline
там аргументы местами меняются - на втором цикле рекурсии получается нод (30, 20), а 30 MOD 20 = 10 :). Так что всё ок )
 
BinaryWolfДата: Вторник, 20.07.2010, 09:14 | Сообщение # 8
Генерал-лейтенант
Группа: Новичок
Сообщений: 51
[ 0 ]
Статус: Offline
Прошу прощения, не заметил.
Ну всё, решено!
Можно курить smok


Луна, единственная спутница моя, отведи меня домой, залечи раны мои и помоги забыть всё.
 
ignorerДата: Суббота, 24.07.2010, 22:00 | Сообщение # 9
Генералиссимус
Группа: Модераторы
Сообщений: 602
[ 18 ]
Статус: Offline
вот блин, я опять всё пропустил. тут как раз паскаль, а я на море smile ну ладно, давайте покурим... smok
 
BinaryWolfДата: Вторник, 27.07.2010, 14:04 | Сообщение # 10
Генерал-лейтенант
Группа: Новичок
Сообщений: 51
[ 0 ]
Статус: Offline
А ты попробуй оптимизировать метод Евклида biggrin

Луна, единственная спутница моя, отведи меня домой, залечи раны мои и помоги забыть всё.
 
ignorerДата: Воскресенье, 08.08.2010, 13:19 | Сообщение # 11
Генералиссимус
Группа: Модераторы
Сообщений: 602
[ 18 ]
Статус: Offline
извините, я опять уехал. ну, оптимизировать-то я могу попытаться, но мне кажется, что:
1) у меня не получится, потому что Евклид был великий математик smile
2) я думал, что алгоритм Евклида вообще другой, либо я его забыл
 
Форум » Решение задач по информатике » Задачи по программированию + блок-схемы » метод Евклида
Страница 1 из 11
Поиск:

Copyright MyCorp © 2016