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