|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
10.11.2016, 17:10 | #11 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Да, выбрал те, произведение которых равно n. А нужно еще те, произведение которых делится нацело на на n. Для 12 считает 1*12, 2*6 и 3*4. А еще есть 8*9*10 дважды делится на 12
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
10.11.2016, 17:12 | #12 |
Старожил
Регистрация: 20.04.2008
Сообщений: 5,526
|
только математика
1. любое число(<N) можно представить как ПРОИЗВЕДЕНИЕ ВСЕХ простых множителей q1...qm каждый из которых <=N (возможно с нулевой степенью) n = q1^a1 * q2^a2 * ... * qm^am 2. факториал этого же числа суть произведение ТЕХ же множителей с ДРУГИМИ коэффициентами. n! = q1^x1 * q2^x2 * ... * qm^xm (x1, ... xm) вот это придется посчитать 3. степень числа ТЕ же множители и еще раз ДРУГИЕ коэффициенты n^k = q1^(a1*k) * q2^(a2*k) * ... qm^(am*k) 4. КОГДА ОДНО число делится на другое нацело? когда в их разложении на простые множители (см. п.1) степень при КАЖДОМ множителе для первого числа >= соответствующей степени второго числа (qi^xi) делится нацело на (qi^yi) <==> xi >=yi 5. найти максимальное k такое что a) n! делится нацело n^k <=> xi>=(ai*k) для всех i б) n! НЕ делится нацело на n^(k+1) <=> НАЙДЕТСЯ такое i, где будет нарушено условие xi >=(ai*(k+1)), т.е. xi<(ai*(k+1))
программа — запись алгоритма на языке понятном транслятору
Последний раз редактировалось evg_m; 10.11.2016 в 17:19. |
10.11.2016, 17:19 | #13 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Лихо. А можно так. Заводим массив A[1..n] в котором 1,2,..,n.
n разложим на простые множители и в массив B[1..m] Для 12 В = [2,2,3]. И сколько раз удастся сократить полностью элементы B по элементам массива А то и результат. При каждом сокращении в A остается остаток от деления вплоть до 1
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
10.11.2016, 17:21 | #14 |
Новичок
Джуниор
Регистрация: 10.11.2016
Сообщений: 9
|
Я так и делал, у меня не получилось реализовать.(
|
10.11.2016, 17:26 | #15 |
Новичок
Джуниор
Регистрация: 10.11.2016
Сообщений: 9
|
Спасибо за наводку, пробую что-то делать
|
10.11.2016, 17:45 | #16 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Так вроде оно, только делфи и можно наверняка оптимальней
Код:
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
10.11.2016, 17:49 | #17 |
Новичок
Джуниор
Регистрация: 10.11.2016
Сообщений: 9
|
Спасибо за помощь. Проверю через время!
|
10.11.2016, 19:44 | #18 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Только оно не оптимально, для больших n по времени вылетит
Ближе к тому, что evg_m предлагал, без большого массива и считает оптимально для близких к 10^9. Динамический массив можно просто заменить на односвязный список. Для 1<n<=10^9. Для простых чисел близких к 10^9 (например 982451653) небольшой тормоз при разложении на множители Код:
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Последний раз редактировалось Аватар; 10.11.2016 в 19:56. |
10.11.2016, 21:43 | #19 |
Забанен
Форумчанин Подтвердите свой е-майл
Регистрация: 01.11.2006
Сообщений: 420
|
Код:
Код:
Если ничто другое не помогает, прочтите, наконец, инструкцию! Аксиома Кана
|
10.11.2016, 22:28 | #20 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Отож, вместо 18 сек за 9 отрабатывает для n=982451653
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Помогите пожалуйста в решении задачи на Delhpi | Anton La Iv | Помощь студентам | 1 | 08.07.2009 22:13 |
помогите в решении задачи. | gaddam | Паскаль, Turbo Pascal, PascalABC.NET | 2 | 24.11.2008 19:06 |
Помогите в решении задачи! | Toxass | Общие вопросы Delphi | 16 | 19.11.2008 22:06 |