|
3 / 3 / 0
Регистрация: 03.06.2019
Сообщений: 64
|
||||||
Как можно оптимизировать решение данной задачи?08.01.2020, 23:35. Показов 3863. Ответов 28
Метки нет (Все метки)
Всем привет!
Есть задачка, вот условие: Напишите функцию, которая принимает в качестве параметра целое число n и возвращает true, если число n! % (n^2) == 0. Вроде все понятно, вот только задача непростая, ведь максимум n, для которого она хоть что-либо может предложить(если делать по-простому, то есть считать каждое выражение), это примерно 20-25. Дальше все. Поэтому вот алгоритм, по которому делал я: Разбил число n ^ 2 на делители, поместил в масив nPw. Разбил числа от 1 до n на делители, поместил в values. Вычеркнул общие члены для массивов; если в nPw остались элементы, то число n! не делится на n ^ 2. Если что, вот код:
Подскажите, плиз, как можно оптимизировать алгоритм и почему, как вы думаете, вылазит ошибка?
0
|
||||||
| 08.01.2020, 23:35 | |
|
Ответы с готовыми решениями:
28
Как можно оптимизировать программу? Как можно оптимизировать код? |
|
4152 / 2731 / 433
Регистрация: 09.09.2017
Сообщений: 12,111
|
|||||||||||||||||
| 10.01.2020, 12:07 | |||||||||||||||||
Сообщение было отмечено nalbe666 как решение
Решение
Интересным образом работает даже проверка числа на простоту. Точного математического доказательства у меня пока нет, но если число n является составным, оно проходит почти все тесты, кроме 1 и 4, по крайней мере до 100`000, причем делает это мгновенно (9 мс против 76 сек моего предыдущего варианта). В связи с этим два вопроса: Почему оно работает? Почему оно не работает на четверке? Добавлено через 1 час 11 минут Попытаюсь подвести теорию и алгоритм под вычисление через простые числа. Случай первый: n - простое. Чтобы n! делилось на n2 надо чтобы (n-1)! делилось на n, то есть из множителей 1...(n-1) можно было собрать n. Но n - простое, а значит по определению не может быть представлено как произведение. Следовательно, (n-1)! на n не делится, ответ - FALSE. Случай второй: n - составное, то есть n=a*b, где 1<a,b<n. Если a!=b, то оба эти числа входят в последовательность факториала, а значит факториал делится на оба этих числа, а значит, и на n. Если же a==b, то чуть сложнее, ведь каждое число из последовательности входит в факториал только по одному разу. Но число может туда входить как сомножитель другого числа, то есть c = b*k, причем b=a ; k>1 ; 1<c<n, что эквивалентно b*k<n. Наименьшее k, которое может удовлетворять этому условию, равно 2. Подставляем n=a*b = a2. 1<a,b<n => a,2a < n => 2a<n => 2a<a2 => a>2. Таким образом, даже если оба сомножителя равны (n является квадратом), единственный случай, когда условие задачи не будет выполнено = квадрат двойки. Иначе говоря, число 4 - единственное исключение для квадратов. Результат: (n-1)! делится на n без остатка в любом случае за исключением простых n и n==4. В виде кода это выглядит так:
2
|
|||||||||||||||||
|
Диссидент
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
|
|||
| 10.01.2020, 12:40 | |||
|
0
|
|||
|
Just Do It!
|
|||||||
| 10.01.2020, 13:07 | |||||||
|
я уже написал, что выдает мой код, но ради вас повторюсь: на 1318, 2800 он выдает TRUE. Обратите внимание, что не 1, и не 0, и не true, а именно: большими буковками TRUE ![]() Кликните здесь для просмотра всего текста
0
|
|||||||
|
4152 / 2731 / 433
Регистрация: 09.09.2017
Сообщений: 12,111
|
||||
| 10.01.2020, 13:56 | ||||
|
Да даже long long переполниться может. Например, как вам 9223372036854775783? Сейчас поищу еще чиселки поменьше
1
|
||||
|
Диссидент
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
|
|
| 10.01.2020, 18:48 | |
|
COKPOWEHEU, Можно сформулировать такую "теорему"
Число n > 4 является простым тогда и только тогда, когда (n-1)! не делится на n Доказательство в вашем посте 22 Эквивалентная формулировка (возвращаясь к стартовому посту) Число n > 4 является простым тогда и только тогда, когда n! не делится на n2
0
|
|
|
4152 / 2731 / 433
Регистрация: 09.09.2017
Сообщений: 12,111
|
||
| 10.01.2020, 22:24 | ||
|
Фактически, вы сформулировали теорему, обратную моей: "число n! делится на n2 без остатка тогда и только тогда, когда оно не является простым и не равно 4".
0
|
||
|
Диссидент
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
|
||
| 10.01.2020, 22:42 | ||
![]() Теорема ровно та же, но другими словами. Впрочем, дальше уже скучно...
0
|
||
|
4152 / 2731 / 433
Регистрация: 09.09.2017
Сообщений: 12,111
|
||
| 11.01.2020, 02:31 | ||
|
0
|
||
| 11.01.2020, 02:31 | |
|
Как можно оптимизировать данный код? Можно как-то оптимизировать этот код?
Как составить формулу для данной задачи Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
|
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM
Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой.
Но использовать несколько программ не удобно. Искал другие. . .
|
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской)
Options
Preferences
General
Language
|
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент".
В данной функции нет апострофов,. . .
|
|
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы.
Карта этого меню приложена ниже.
Нужный пункт выделен красным.
Сервис
Настройки
Поведение
|
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки.
Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён".
Изменено отображение буквы Й.
Добавлена. . .
|
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки.
Добавлено:
- Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
|
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы.
Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
|