Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 30.11.2016, 22:15   #21
digitalis
Старожил
 
Аватар для digitalis
 
Регистрация: 04.02.2011
Сообщений: 4,537
По умолчанию

Мы о разном говорим все-таки. Я про это (#2):
For i:=c downto 1 do
If (a mod i=0) and (b mod i=0) then
begin
Result:=i;
Exit;
end;
Что есть в данном случае с ?
С модом я мало работал. Щас буду экспериментировать, к примеру 7000 div 7002.

Последний раз редактировалось digitalis; 30.11.2016 в 22:17.
digitalis вне форума Ответить с цитированием
Старый 30.11.2016, 22:52   #22
Dekay
Пользователь
 
Регистрация: 21.06.2016
Сообщений: 65
По умолчанию

Цитата:
Сообщение от digitalis Посмотреть сообщение
Что есть в данном случае с ?
В моем понимании это совсем не важно.
Сложность в любом случаее будет O(N). И не важно N/2, N/3 или даже N/144.

Я предлагаю или использовать решение за корень или за логарифм. Последнее понятно дело лучше.
Код:
res := 1;
for i := 1 to round(sqrt(a)) do begin
    if (a mod i = 0) then begin
          if (b mod i = 0) then res := max(res, i);
          if (b mod (a div i) = 0) then res := max(res, a div i);
    end
end
Dekay вне форума Ответить с цитированием
Старый 01.12.2016, 11:18   #23
digitalis
Старожил
 
Аватар для digitalis
 
Регистрация: 04.02.2011
Сообщений: 4,537
По умолчанию

Красивое решение. Вторым if проверяется делитель, "симметричный" i относительно Sqrt .
Но справедливости ради: на некоторых парах данных решение #2 (с моей добавкой ) будет быстрее: при просмотре сверху первое же найденное решение и будет результатом, цикл прекращаем. Например, 1000000 и 2000000 . Хотя в общем случае, конечно, проигрывает.

Последний раз редактировалось digitalis; 01.12.2016 в 11:22.
digitalis вне форума Ответить с цитированием
Старый 04.12.2016, 14:25   #24
newerow1989
Я самый любопытный
Участник клуба
 
Аватар для newerow1989
 
Регистрация: 24.07.2012
Сообщений: 1,949
По умолчанию

А если 2 одинаковых числа: 100 и 100?
С запрограммированным приветом, Неверов Евгений!
Сайт: http://newerow1989.ru
[Паскаль] [Delphi]
newerow1989 вне форума Ответить с цитированием
Старый 04.12.2016, 16:30   #25
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от newerow1989 Посмотреть сообщение
А если 2 одинаковых числа: 100 и 100?
в этом случаи НОД будет равен 100
Serge_Bliznykov вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
C#: Найти делители данного натурального числа N, которые являются квадратами какого то числа Х Namatrasnik Помощь студентам 1 20.10.2016 16:14
найти все простые делители числа н keyshia_nicole Visual C++ 0 31.01.2014 18:39
Найти все общие делители двух чисел (осталось оптимизировать) KObotan Общие вопросы C/C++ 4 13.09.2012 01:27
Pascal. Найти все делители числа N torah Помощь студентам 0 24.11.2010 10:37
Найти все делители числа N torah Помощь студентам 33 06.11.2010 00:15