Войти в систему

Home
    - Создать дневник
    - Написать в дневник
       - Подробный режим

LJ.Rossia.org
    - Новости сайта
    - Общие настройки
    - Sitemap
    - Оплата
    - ljr-fif

Редактировать...
    - Настройки
    - Список друзей
    - Дневник
    - Картинки
    - Пароль
    - Вид дневника

Сообщества

Настроить S2

Помощь
    - Забыли пароль?
    - FAQ
    - Тех. поддержка



Пишет kouzdra ([info]kouzdra)
@ 2005-08-26 18:16:00


Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Компутерное
Интересно, а почему на всяческих программистских конкурсах/олимпиадах etc
так редко используется формат ICFP-шных контестов - когда дается "открытая"
задача, а победителем объявляется тот, кто сумеет решить ее как можно лучше?

Мы недавно попробовали - придумываются задачи легко, и сохраняется стимул
для "хорошего программирования" (что есть главная проблема всех подобных затей).

Конкретная задача (уже была использована):

"Написать программу, которая найдет за 5 минут наибольшую пару простых
чисел-близнецов (т.е.отличающихся на 2). Найденные пары регистрируются библиотченой
функцией register_result (a, b), которую можно вызывать несклько раз. результатом
считается максимальная зарегистрированная пара"

На самом деле, простая-то она простая, но если учесть, что Вам надо не просто решить
задачу, а решить ее лучше других - она довольно нетривиальна. Особенно если не знать
точных характеристик компа, на котором оно будет считаться.

Вариант решения на Haskell, не оптимальный, но неплохой:

is_siblings n = null [m | m <- takeWhile (\x -> x*x <= n) (2:[3,5..]), 
                                   n `rem` m == 0 || (n+2) `rem` m == 0] 
find_siblings_at n = [(k, k+2) | k <- [n, n-2 .. 3], is_siblings k]
main = print [(register_pair. head . find_siblings_at . round) (10.0 ** e - 1) | e <- [2.0, 3.0..]]


Upd: Немножко подумав, понял что есть способ заметно улучшить результат, исправив всего 2 символа.
Догадайтесь, как.


(Добавить комментарий)


[info]ifp5
2005-08-29 15:29 (ссылка)
Гм. Единственное что приходит в голову с заменой двух символов, это:

find_siblings_at n = [(k, k+2) | k <- [n, n+2 .. ], is_siblings k]

но заметным улучшением это назвать нельзя.

Как же именно?

(Ответить) (Ветвь дискуссии)


[info]kouzdra
2005-08-29 15:40 (ссылка)
Заменить
10.0 ** e
на
2.0 ** e
:)

С меньшим шагом она успевает точнее приблизиться к границе своих способностей, прежде, чем выдет время. Вопрос, какая именно база является оптимальной, кстати, открыт - вряд ли именно 2.0, а в подобных соревнованиях это может стать решающим фактором.

А вообще - там есть большой простор для улучшений. Например - использовать стохастический тест и как-то автоматически оценивать ожидаемое время работы и исходя из него - выбирать, где именно пробовать подобрать резульатат.

(Ответить) (Уровень выше)