Оптимизация решения..., помогите найти оптимальный вариант |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Оптимизация решения..., помогите найти оптимальный вариант |
zZz |
Сообщение
#1
|
Пионер Группа: Пользователи Сообщений: 55 Пол: Мужской Реальное имя: Алексей Репутация: 0 |
Задача такова: необходимо найти 1000 чисел не имеющих простых делителей кроме 2,3 и 5 (например 1,2,3,4,5,6,8,9,10,12,15,16,18,20,24...), за пару минут с while'ом написал программу просто перебирающую все варианты и проверяющую выполнимость условия, но проблема в том что такой вариант выполнения занимает много времени (секунд 10), хотелось бы узнать более оптимальный вариант решения... достаточно лишь описать что должен делать и в каком порядке алгоритм...
Сообщение отредактировано: zZz - |
FreeMan |
Сообщение
#2
|
- Группа: Пользователи Сообщений: 480 Пол: Мужской Репутация: 4 |
приходит на ум вывести 1000 вариантов умножения 2,3,5 друг на друга (кстати, а что там 1 делает?).
-------------------- бб
|
zZz |
Сообщение
#3
|
Пионер Группа: Пользователи Сообщений: 55 Пол: Мужской Реальное имя: Алексей Репутация: 0 |
всем спасибо, ... нашел решение, представляем все числа в виде 2^m*3^n*5^k, и при n=m=k=0 появляется 1 , затем просто приводим эт выражение под одну степень 2^m*3^n*5^k=2^(m+n*(log по осн 2 из 3)+k*(log по осн 2 из 5)), первая комбинация m n k - 0 0 0, дальше перебором находим такие m n k что новое значение m+n*(log по осн 2 из 3)+k*(log по осн 2 из 5) минимальное большее от предыдущего... все гениальное просто...да к тому же такая прога должна работать намного быстрее...
Сообщение отредактировано: zZz - |
zZz |
Сообщение
#4
|
Пионер Группа: Пользователи Сообщений: 55 Пол: Мужской Реальное имя: Алексей Репутация: 0 |
Цитата приходит на ум вывести 1000 вариантов умножения 2,3,5 друг на друга забыл об одной фишке упомянуть: все в порядке возрастания надо еще вывести, а на сортировку тож время надо, да и массив прописывать влом... |
klem4 |
Сообщение
#5
|
Perl. Just code it! Группа: Пользователи Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Цитата дальше перебором находим такие m n k что новое значение m+n*(log по осн 2 из 3)+k*(log по осн 2 из 5) минимальное большее от предыдущего А до какого числа ты собрался делать перебор ? Вот например при m = 0 n = 5 k = 10 Выражение уже не влезает в longint, а 1000 чисел еще найдено не было. Сообщение отредактировано: klem4 - -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
zZz |
Сообщение
#6
|
Пионер Группа: Пользователи Сообщений: 55 Пол: Мужской Реальное имя: Алексей Репутация: 0 |
А до какого числа ты собрался делать перебор ? Вот например при m = 0 n = 5 k = 10 Выражение уже не влезает в longint, а 1000 чисел еще найдено не было. значение при m=0 n=5 k=10 соответствует 2,1582735598713E37, а 1000ое число (в первой проге еще получил) если не ошибаюсь было 51200000 плюс/минус ноль, что значительно меньше 2,1582735598713E37, значит прокатит... ps/ все слышали про внеконкурсное участие в on-line туре всеросийской олимпиады среди школьников по программированию? Регистрация, Сайт олимпиады Сообщение отредактировано: GoodWind - |
Текстовая версия | 16.10.2024 13:52 |