?

Log in

No account? Create an account

Previous Entry | Next Entry

Приключилось мне в интернетах искать не самые сложные задачи по программированию, чтобы задать ими обучаемых, и набрело в связи с этим на сайт под названием TopCoder, где программисты устраивают меж собою соревнования, кто быстрее разрешит разной сложности задачи. Собственно задач интересных там много, но что меня удивило — это то, с какой скоростью соревновавшиеся решали эти задачи.

Вот, например, задача, которую я могу переформулировать для простоты так. Каждое целое число n изоморфно упорядоченному множеству цифр в своей десятичной записи S(n). Найти сумму по модулю 9 всех чисел, изоморфных элементам булеана множества цифр S(n) данного числа n. Например, для числа 123 это (0+1+2+3+12+23+13+123) mod 9. Алгоритм должен работать по крайней мере для n ≤ 1080.

Задача в принципе не сложная. Мне хватило минут 15 на то, чтобы допереть до алгоритма решения. Что меня потрясло, так это то, что трое лучших олимпийцев решили эту задачу за, соответственно, 86, 90 и 96 секунд. В это время вошло чтение задачи — а там несколько абзацев текста с несколькими примерами чисел, придумывание алгоритма и написание собственно кода. Если до того, как я это увидел, у меня еще были некоторые сомнения насчет своих программистских неспособностей, теперь они развеялись окончательно.

Однажды я прочел книгу по пользованию «Фотошопом», где говорилось, что тот, кто не учится работать с этим редактором клавишами, а тыцает в команды мышкой, не имеет никаких шансов на выживание в скоротечном бизнесе редактирования изображений. Сэкономленные доли секунды в пересчете на каждое действие проводят границу между успехом и неудачей.

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

Tags:

Comments

rwalk
Dec. 26th, 2011 10:29 am (UTC)
Этот пример все-таки не столько программистский, сколько математический. Терпеть не могу олимпиадные задачи, но тут думать действительно долго не надо. У меня другой вопрос к программистам - будет ли для них существенно отличаться время написания соответствующего кода от времени написания математиком формулы (a1+...+ak)2n-1 (mod 9)=n2n-1 (mod 6) (mod 9)? И при чем тут 1080?
janatem
Dec. 26th, 2011 11:13 am (UTC)
Согласен, что это чисто математическая задача. У меня получился такой же ответ за несколько минут (только у вас опечатка — справа от знака равенства n используется как длина числа и как само число).

Даже если забыть про теорему Ферма или про функцию Эйлера, всё равно записанное в лоб выражение N*2^(n-1) (mod 9) вычисляется мгновенно для чисел, занимающих единицы байтов в разумном представлении.
rwalk
Dec. 26th, 2011 12:30 pm (UTC)
Да, конечно, - и слева и справа в показателе должно быть k-1, а не n-1. Вообще мне этот разговор о решении задач на скорость напомнил известный анекдот про фон Неймана - о двух велосипедистах и мухе.