задачки (программистское)

[avva]

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

Советую пытаться их все решать в уме - а если никак не выходит, тогда пробовать с бумагой или компьютером.

Особенно понравились следующие (но вообще почти все хороши): Parody Bit, Unshuffle, Amphibious Discursion, Distinctly Odd, и Poppyseed Place. Последняя, Poppyseed Place, в которой надо выбрать, какой набор операций из четырех лишний (+/-, min/max, gcd/lcm, &/|), понравилась тем, что я к ней три разных ответа придумал, и не знаю, какой верный.

Если что-то непонятно в условиях или кто-то хочет обсудить решения, давайте в комментариях.

Comments

[kaathewise.livejournal.com]

Duncing Lunks подвешивает как-то. А в Poppyseed как раз все понятно, имхо. Там же три пары операций делают по большому счету одно и то же, т.е. две из них - частные случаи третьей.

[avva.livejournal.com]

Duncing Lunks - я как раз просто знал этот трюк, не знаю, насколько мне тяжело было бы его придумать. А в Poppyseed не понимаю, что вы имеете в виду под "по большому счету" - ясно, что скажем, на два числа 12 и 20 все четыре набора операций дадут разные ответы.

[neatfires.livejournal.com]

Впрочем, не уверен, что у меня то решение, которое знает авва. Попытаюсь намекнуть так, чтобы не спалить совсем: вершины разбиты на 2/3 и еще 1/3.

[(Anonymous)]

Недавно попался интересный наборчик (не для программистов): Jewish Problems (http://arxiv.org/abs/1110.1556)

[(Anonymous)]

Ну эти-то в уме не шибко порешаешь. Хотя, конечно, всякие гении бывают...

[darth-mozg.livejournal.com]

Я никак не пойму как происходит умножение в The Dismal (Computer) Science. По какому принципу берется наименьшее?

[avva.livejournal.com]

169
248
---

первая строка: 169x8 = 168 (в каждом разряде вместо умножения берем меньшую из двух цифр как результат; переноса никакого нет)

169x4 = 144
169x2 = 122

теперь складываем столбики, в каждом разряде берем наибольшую цифру.

[spamsink.livejournal.com]

В Poppyseed Place min/max отличается от остальных гораздо сильнее, чем они все остальные друг от друга: результат min и max всегда равен одному из аргументов; все остальные различия перед этим меркнут. :)

[avva.livejournal.com]

Это мой "альтернативный" ответ, но не тот, подозреваю, что имел в виду автор задачи :)

[ilya-dogolazky.livejournal.com]

это кстати неправда, результат равен одному из аргументов только если порядок полный, а в условии задачи ничего не сказано насчёт множества на котором операция определена

[neatfires.livejournal.com]

Lorem Ipsum

[avva.livejournal.com]

если честно, я не очень понял, но возможно форматирование помешало :)

если хотите знать, какое решение я знаю, подсмотрите спойлер в комменте димруба.

[dimrub.livejournal.com]

Застрял прямо на первом. Разве результат не зависит от того, используется ли на данной архитектуре 1's complement или 2's complement?

[darth-mozg.livejournal.com]

Если я правильно решил это задание, то нет, не зависит.

[avva.livejournal.com]

Я бы предполагал 2's complement везде, где другое не указано явно.

[184467440737095.livejournal.com]

в Poppyseed Place +- не задает решетку.

[(Anonymous)]

Только мне кажется, что в Amphibious Discursion нечетное число круглых скобок?

[avva.livejournal.com]

Да, одна закрывающая лишняя.

Про лягушек

[grep.myopenid.com (from livejournal.com)]

Довольно легко понять, что речь идет о количестве представлений числа в виде суммы четырех треугольных. А численный эксперимент как бы подсказывает, что жабами являются простые (точнее, frog(4,n,1,0) равно сумме делителей 2n-1) - но непонятно, как увязать одно представление с другим

Re: Про лягушек

[grep.myopenid.com (from livejournal.com)]

Ага, и OEIS подтверждает: http://oeis.org/A008438

Re: Про лягушек

[avva.livejournal.com]

Я дошел до смысла функции, но смысл бытия лягушек не постиг (эксперимент не запускал, лень было), так что спасибо за объяснение и ссылку. Наверное, это не вполне тривиальный результат (связывающий их).

[(Anonymous)]

В Two's compliment ответ ?

[avva.livejournal.com]

по-моему да.

[(Anonymous)]

А как вы определили знак числа?

[p_govorun.livejournal.com]

Решение для Duncing Lunks: половину списка линковать в одну сторону, а другую -- в другую. Такой список проходится в обе стороны with equal efficiency. Условие соблюдено, остальное меня не касается. У нас программирование, или что? :-)

[grep.myopenid.com (from livejournal.com)]

Это классическая задача, эксплуатирующая тот факт, что [spoiler] и [/spoiler]