![]() |
|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
![]() |
|
|
Опции темы | Поиск в этой теме |
![]() |
#11 |
Старожил
Регистрация: 04.02.2011
Сообщений: 4,586
|
![]()
Если уж через mod , то downto 1 нужно крутить не от меньшего числа (допустим, b), а от min (a/2,b) - думаю, пояснения не требуются ?
|
![]() |
![]() |
![]() |
#12 |
Пользователь
Регистрация: 21.06.2016
Сообщений: 65
|
![]()
Требуются. Я вот ничего не понял.
|
![]() |
![]() |
![]() |
#13 | |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
![]() Цитата:
ну и, раз тема не утихает, Dekay, а зачем в вашем примере min() max() насколько я понимаю, они там излишни! сравните: Код:
|
|
![]() |
![]() |
![]() |
#14 |
Пользователь
Регистрация: 21.06.2016
Сообщений: 65
|
![]()
Да нет. Все правильно. Просто так мне удобнее.
|
![]() |
![]() |
![]() |
#15 |
Старожил
Регистрация: 04.02.2011
Сообщений: 4,586
|
![]()
Элементарно, Ваксон .
![]() Лемма. Никакой делитель целого числа N, кроме его самого, не может превышать N/2 . Доказательство. Допустим, такое число есть M > (N/2) . Тогда частное от деления N / M < 2, но между 1 и 2 нет никаких целых чисел. Absurdum . (Напомним, что понятие "общий делитель" - это из целочисленной арифметики.) Итого. Если b < a/2, то Н.О.Д. надо искать вниз от него, точнее, от b/2, если >, то от a/2 . В результате агоритм получился зупер ! Код:
![]() Последний раз редактировалось digitalis; 30.11.2016 в 17:26. |
![]() |
![]() |
![]() |
#16 | ||
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
![]() Цитата:
ну и что. Какое это имеет отношение к Цитата:
Вы посмотрите внимательно на код в #13 Вы там видите цикл до какого-то значения? до a? или до a/2? или до b? Вы вообще понимаете, что такое "наибольший общий делитель" для двух чисел? ![]() p.s. но, по крайней мере, я понял, что Вы хотели сказать в пост #11. ![]() так что, лично для меня уже это вопрос можно закрывать. |
||
![]() |
![]() |
![]() |
#17 | ||||
Старожил
Регистрация: 04.02.2011
Сообщений: 4,586
|
![]() Цитата:
Цитата:
Цитата:
http://shkolo.ru/naibolshiy-obshhiy-delitel/ Только судя по началу Вашего поста №16, Н.О.Д.ы у нас разные ![]() Цитата:
![]() Последний раз редактировалось digitalis; 30.11.2016 в 21:12. |
||||
![]() |
![]() |
![]() |
#18 | |
Пользователь
Регистрация: 21.06.2016
Сообщений: 65
|
![]() Цитата:
Дело в том, что можно перебирать все до корня. Дело в том, что каждому делителю до корня соответсвует делитель больший корня. Поэтому можно ускорить процесс. Но все равно сложность будет sqrt(n). Правильное решение не должно иметь сложность больше ln(n) |
|
![]() |
![]() |
![]() |
#19 | |
Старожил
Регистрация: 04.02.2011
Сообщений: 4,586
|
![]() Цитата:
Рекурсивный вариант работает на удивление быстро, хотя я не до конца въехал - как. Буду вникать. |
|
![]() |
![]() |
![]() |
#20 |
Пользователь
Регистрация: 21.06.2016
Сообщений: 65
|
![]()
Откуда хочешь.
Давай скажем, что у нас числа А и Б. Причем А меньше. Идем до корня до А. И смотрим if a mod i = 0 then у нас имеется два делителя. i и a div i. Проверь каждый на кратность Б и выбери возьми наибольший из предыдущего ответа и подходящего нынешнего. Проблема решена. Наверное все-таки формулки понятнее. Но не могу с телефона их подгружать. Нечего вникать. Если вариант с вычетанием тебе понятен, то с модом должен быть просто очевиден |
![]() |
![]() |
![]() |
|
![]() |
||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
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 |