 Оптимизация решения..., помогите найти оптимальный вариант |
Прочтите прежде чем задавать вопрос!
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
| zZz |
 18.04.2006 16:13
Сообщение
#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 - 18.04.2006 16:16 |
   |
 
|
  |
Ответов(1 - 5)
| FreeMan |
18.04.2006 17:01
Сообщение
#2
|
|
- Группа: Пользователи Сообщений: 480 Пол: Мужской Репутация: 4 |
приходит на ум вывести 1000 вариантов умножения 2,3,5 друг на друга (кстати, а что там 1 делает?).
-------------------- бб
|
|
|
|
| zZz |
 18.04.2006 18:04
Сообщение
#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 - 18.04.2006 18:32 |
|
|
|
| zZz |
18.04.2006 18:30
Сообщение
#4
|
|
Пионер Группа: Пользователи Сообщений: 55 Пол: Мужской Реальное имя: Алексей Репутация: 0 |
Цитата приходит на ум вывести 1000 вариантов умножения 2,3,5 друг на друга забыл об одной фишке упомянуть: все в порядке возрастания надо еще вывести, а на сортировку тож время надо, да и массив прописывать влом... |
|
|
|
| klem4 |
19.04.2006 7:46
Сообщение
#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 - 19.04.2006 7:46 -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
|
|
|
| zZz |
19.04.2006 11:52
Сообщение
#6
|
|
Пионер Группа: Пользователи Сообщений: 55 Пол: Мужской Реальное имя: Алексей Репутация: 0 |
Цитата(klem4 @ 19.04.2006 9:46)  А до какого числа ты собрался делать перебор ? Вот например при m = 0 n = 5 k = 10 Выражение уже не влезает в longint, а 1000 чисел еще найдено не было. значение при m=0 n=5 k=10 соответствует 2,1582735598713E37, а 1000ое число (в первой проге еще получил) если не ошибаюсь было 51200000 плюс/минус ноль, что значительно меньше 2,1582735598713E37, значит прокатит... ps/ все слышали про внеконкурсное участие в on-line туре всеросийской олимпиады среди школьников по программированию? Регистрация, Сайт олимпиады Сообщение отредактировано: GoodWind - 19.04.2006 11:58 |
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
Текстовая версия | 20.06.2025 9:31 |