опять только программистам будет интересно

[avva]

Мою починку бага в языке Перл приняли и вставили в исходники. Мелочь, а приятно.

Вернусь теперь к программе, которую писал, и еще чего-нибудь наваяю...

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

Листая наугад старые заметки Дейкстры, обнаружил алгоритмическую задачку, которая помогла размять мозги немного. Для тех, кому интересно, перескажу условие под катом.

Задачка такая. Вам дают возрастающую последовательность натуральных чисел x₀, x₁, .... x_N. x₀ равно 0, а самое большое - и последнее - из этих чисел, x_N, является длиной окружности, на которой расположены N точек x₀, ..., x_N-1 - они заданы в виде длин от начальной фиксированной точки. Предположим, например, что последовательность - 0, 3, 9, 11, 12, 25; это значит, что на окружности длиной 25 есть 5 точек; начиная от фиксированной точки O и идя по окружности расстояния от O до них равны 0, 3, 9, 11 и 12. Дано также число k. Спрашивается, можно ли из N точек x₀, ... x_N-1 отобрать k таких, которые образуют правильный k-угольник?

Т.к. расстояния между точками по окружности - натуральные числа, а у правильного k-угольника они все равны и их k, то ясно, что необходимым условием является, чтобы длина окружности x_N делилась на k, и тогда частное от их деления - расстояние по окружности между двумя последовательными вершинами искомого k-угольника. Если это необходимое условие выполняется, требуется ответить на вопрос за O(N) затрат времени и места. Решение с O(N*k) тривиально, да и с O(N) не ужасно сложно, но подумать надо. Возможно, хорошая задачка для интервью.