Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

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

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

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

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

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

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

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

Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 22 comments