Zealint

Остаток от деления на 2s-1

Zealint — Tue, 24 Apr 2012 16:57:16 +0000

При программировании на старых процессорах, на которых операции умножения и деления чисел выполнялись медленно, программисты прибегали к трюкам, позволявшим ускорить вычисления. Так, битовый трюк, позволяющий получить остаток от деления на число, равное точной степени двойки, остаётся актуальным и сейчас. Операция типа a&((1<<s)−1) всё ещё работает быстрее обычного деления (в том случае, когда компилятор не имеет возможности выполнить соответствующую оптимизацию). Но с тех времён забытым остался трюк, позволяющий похожим набором операций заменить вычисление остатка от деления на число, на единицу меньшее степени двойки. Рассмотрим, как он работает.

Обратная по модулю матрица — итоги

Zealint — Wed, 18 Apr 2012 10:09:36 +0000

Конкурс по обращению матрицы завершён. Победителем объявляется неоднократный участник моих конкурсов alexBlack.

Обратная по модулю матрица — конкурс

Zealint — Wed, 04 Apr 2012 12:48:42 +0000

После вынужденного перерыва продолжаем проводить любительские конкурсы по программированию. На этот раз конкурс связан с одним из предыдущих конкурсов, посвященных точному решению целочисленной системы уравнений. Первым шагом при использовании алгоритма, основанного на p-адических аппроксимациях, является обращение исходной матрицы по модулю простого числа P. Требуется максимально ускорить эту операцию. С этой целью и проводится конкурс. В качестве P выбрано число 2³¹-1 (максимальное простое число, которое умещается в 32 бита со знаком).

Новогодний zip-квест 2012

Zealint — Sun, 01 Jan 2012 18:35:37 +0000

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

Задача о назначениях — итоги

Zealint — Sat, 15 Oct 2011 12:40:42 +0000

Конкурс на самое быстрое решение задачи о назначениях завершён. Подведём итоги.

Задача о назначениях — Конкурс

Zealint — Sat, 01 Oct 2011 10:36:20 +0000

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

Короли на цилиндрической доске — предложение

Zealint — Mon, 05 Sep 2011 15:50:14 +0000

Недавно Vaclav Kotesovec написал мне письмо, в котором предложил продолжить его новую последовательность A137432 - число способов расставить максимальное количество (n²) не бьющих друг друга королей на цилиндрической доске 2n×2n.

Социальная гигиена. Часть I

Zealint — Tue, 05 Jul 2011 17:36:55 +0000

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

6 ферзей на тороидальной доске — итоги

Zealint — Tue, 21 Jun 2011 08:36:34 +0000

Конкурс завершён досрочно, поскольку Андрей Халявин предоставил необходимое количество чисел (и даже больше – 81 шт.), которых оказалось достаточно для проверки гипотезы. Здесь я объясню, что из этого всего получилось. Забегая вперед сообщу, что гипотеза о виде рекуррентного соотношения хоть и была правильной, но соотношение имело не минимальный порядок. Минимальный порядок будет 124, а не 142. Так же я объясню, как из 142 получить 78 для этой задачи, благодаря чему и удалось решить её так быстро. Для понимания объяснений читатель должен быть немного знаком с производящими функциями.

6 ферзей на тороидальной доске — конкурс

Zealint — Thu, 09 Jun 2011 04:55:08 +0000

Предлагаю отдохнуть от метода матрицы переноса и перейти к задаче более переборной. Как понятно из названия, предлагаю снова заняться проблемой расстановки 6 ферзей, но на этот раз не на обычной доске, а на тороидальной. Прежде чем возразить, что похожая задача уже была и что повторяться не хорошо, ознакомьтесь с моими аргументами в её пользу, которые записаны ниже в этом посте. Я никогда не выбираю задачу по принципу "просто так".