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

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

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

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

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

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

Если уж через mod , то downto 1 нужно крутить не от меньшего числа (допустим, b), а от min (a/2,b) - думаю, пояснения не требуются ?
digitalis вне форума Ответить с цитированием
Старый 30.11.2016, 14:53   #12
Dekay
Пользователь
 
Регистрация: 21.06.2016
Сообщений: 65
По умолчанию

Требуются. Я вот ничего не понял.
Dekay вне форума Ответить с цитированием
Старый 30.11.2016, 15:12   #13
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от digitalis Посмотреть сообщение
то downto 1 нужно крутить не от меньшего числа (допустим, b), а от min (a/2,b) - думаю, пояснения не требуются ?
тоже ничего не понял...


ну и, раз тема не утихает,
Dekay, а зачем в вашем примере min() max()
насколько я понимаю, они там излишни!

сравните:
Код:
function gcd(a, b : integer) : integer;
begin
     if b = 0 then gcd := a
     else gcd := gcd(b, a mod b)
end;

var
	a, b : integer;
begin
	ReadLn(a, b);
	WriteLn(gcd(a, b))
end.
или я что-то не учитываю?
Serge_Bliznykov вне форума Ответить с цитированием
Старый 30.11.2016, 15:18   #14
Dekay
Пользователь
 
Регистрация: 21.06.2016
Сообщений: 65
По умолчанию

Да нет. Все правильно. Просто так мне удобнее.
Dekay вне форума Ответить с цитированием
Старый 30.11.2016, 17:08   #15
digitalis
Старожил
 
Аватар для digitalis
 
Регистрация: 04.02.2011
Сообщений: 4,534
По умолчанию

Элементарно, Ваксон . Даже не думал, что такое простое утверждение потребует доказательств.
Лемма. Никакой делитель целого числа N, кроме его самого, не может превышать N/2 .
Доказательство. Допустим, такое число есть M > (N/2) . Тогда частное от деления N / M < 2, но между 1 и 2 нет никаких целых чисел. Absurdum . (Напомним, что понятие "общий делитель" - это из целочисленной арифметики.)
Итого. Если b < a/2, то Н.О.Д. надо искать вниз от него, точнее, от b/2, если >, то от a/2 .
В результате агоритм получился зупер !
Код:
begin
   c:=min(a,b) div 2 ;
   For i:=c downto 1 do
      If ((a mod i) = 0) and ((b mod i) =0) then
      begin
         Result:=i;
         Exit;
      end;
end;
Кто с этим не согласен, приведите, please, такую жуткую пару чисел.

Последний раз редактировалось digitalis; 30.11.2016 в 17:26.
digitalis вне форума Ответить с цитированием
Старый 30.11.2016, 17:22   #16
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от digitalis Посмотреть сообщение
Лемма. Никакой делитель целого числа N, кроме его самого, не может превышать N/2 .
не может. я Вам даже больше скажу, никакой делитель натурального числа N, кроме его самого, не может превышать корня квадратного из N

ну и что.
Какое это имеет отношение к
Цитата:
Сообщение от digitalis Посмотреть сообщение
Если уж через mod , то downto 1 нужно крутить не от меньшего числа (допустим, b), а от min (a/2,b)
?!

Вы посмотрите внимательно на код в #13

Вы там видите цикл до какого-то значения? до a? или до a/2? или до b?
Вы вообще понимаете, что такое "наибольший общий делитель" для двух чисел?

p.s. но, по крайней мере, я понял, что Вы хотели сказать в пост #11.
так что, лично для меня уже это вопрос можно закрывать.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 30.11.2016, 19:21   #17
digitalis
Старожил
 
Аватар для digitalis
 
Регистрация: 04.02.2011
Сообщений: 4,534
По умолчанию

Цитата:
Сообщение от Serge_Bliznykov Посмотреть сообщение
не может. я Вам даже больше скажу, никакой делитель натурального числа N, кроме его самого, не может превышать корня квадратного из N ну и что.
Какое это имеет отношение к ?!
Sqrt(16) = 4 . А посему 8 - никакой не делитель числа 16, а так, погулять вышел. А то, что Н.О.Д. обязан быть, как минимум, просто делителем любого из чисел пары - для меня несомненно. Вот такое это имеет отношение к .

Цитата:
Вы посмотрите внимательно на код в #13
Вы там видите цикл до какого-то значения? до a? или до a/2? или до b?
Посмотрел. Там рекурсия. Я ее и не обсуждаю. Мой пост касался newerow1989, его алгоритм я предлагал улучшить. И в моем предложении цикл не до, а от .
Цитата:
Вы вообще понимаете, что такое "наибольший общий делитель" для двух чисел?
Да вроде как понимаю, хотя бы на уровне:
http://shkolo.ru/naibolshiy-obshhiy-delitel/
Только судя по началу Вашего поста №16, Н.О.Д.ы у нас разные

Цитата:
так что, лично для меня уже это вопрос можно закрывать.
Категорически присоединяюсь

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

Цитата:
Сообщение от digitalis Посмотреть сообщение
Теперь мне понятно, что у кого-то была двойка по теории чисел в универе, и я даже знаю - у кого Sqrt(16) = 4 . А посему 8 - никакой не делитель числа 16, а так, погулять вышел. А то, что Н.О.Д. обязан быть, как минимум, просто делителем любого из чисел пары - для меня несомненно. Вот такое это имеет отношение к .
Серж не совсем это подразумевал.
Дело в том, что можно перебирать все до корня. Дело в том, что каждому делителю до корня соответсвует делитель больший корня. Поэтому можно ускорить процесс.
Но все равно сложность будет sqrt(n). Правильное решение не должно иметь сложность больше ln(n)
Dekay вне форума Ответить с цитированием
Старый 30.11.2016, 21:09   #19
digitalis
Старожил
 
Аватар для digitalis
 
Регистрация: 04.02.2011
Сообщений: 4,534
По умолчанию

Цитата:
Сообщение от Dekay Посмотреть сообщение
Дело в том, что можно перебирать все до корня. Дело в том, что каждому делителю до корня соответсвует делитель больший корня.
Бесспорно. Именно так и поступают, проверяя число на "простоту", т.е. на наличие делителей. Здесь же малость другое ( я имею в виду все тот же алгоритм с поста #2). Вопрос не "до" чего считать, а "от" чего. "До" всегда будет, в крайнем случае 1. Так вот - откуда цикл крутить вниз ? От N до Sqrt(N) ? Несерьезно. От Sqrt(N) ? Тогда для 8, 16 Н.О.Д будет 4, потому что начали рассмотрение 4 downto 1 . Так что для обсуждаемого алгоритма я пока альтернативы своей поправке не вижу, правда, предварительно надо проверить, не является ли уже младшее из чисел Н.О.Д.
Рекурсивный вариант работает на удивление быстро, хотя я не до конца въехал - как. Буду вникать.
digitalis вне форума Ответить с цитированием
Старый 30.11.2016, 21:33   #20
Dekay
Пользователь
 
Регистрация: 21.06.2016
Сообщений: 65
По умолчанию

Цитата:
Сообщение от digitalis Посмотреть сообщение
Так вот - откуда цикл крутить вниз ?
Откуда хочешь.
Давай скажем, что у нас числа А и Б. Причем А меньше.
Идем до корня до А. И смотрим if a mod i = 0 then у нас имеется два делителя. i и a div i. Проверь каждый на кратность Б и выбери возьми наибольший из предыдущего ответа и подходящего нынешнего. Проблема решена.

Наверное все-таки формулки понятнее. Но не могу с телефона их подгружать.

Цитата:
Сообщение от digitalis Посмотреть сообщение
Рекурсивный вариант работает на удивление быстро, хотя я не до конца въехал - как. Буду вникать.
Нечего вникать. Если вариант с вычетанием тебе понятен, то с модом должен быть просто очевиден
Dekay вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 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