IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> Оптимизация решения..., помогите найти оптимальный вариант
сообщение
Сообщение #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 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов(1 - 5)
сообщение
Сообщение #2


-
****

Группа: Пользователи
Сообщений: 480
Пол: Мужской

Репутация: -  4  +


приходит на ум вывести 1000 вариантов умножения 2,3,5 друг на друга (кстати, а что там 1 делает?).


--------------------
бб
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Пионер
**

Группа: Пользователи
Сообщений: 55
Пол: Мужской
Реальное имя: Алексей

Репутация: -  0  +


всем спасибо, ... нашел решение, представляем все числа в виде 2^m*3^n*5^k, и при n=m=k=0 появляется 1 smile.gif , затем просто приводим эт выражение под одну степень 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) минимальное большее от предыдущего... все гениальное просто...да к тому же такая прога должна работать намного быстрее... wink.gif

Сообщение отредактировано: zZz -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Пионер
**

Группа: Пользователи
Сообщений: 55
Пол: Мужской
Реальное имя: Алексей

Репутация: -  0  +


Цитата
приходит на ум вывести 1000 вариантов умножения 2,3,5 друг на друга

забыл об одной фишке упомянуть: все в порядке возрастания надо еще вывести, а на сортировку тож время надо, да и массив прописывать влом...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #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";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #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 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 4:56
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name