четверг, 5 сентября 2013 г.

Нахождение всех перестановок на PHP в функциональном стиле

Во время недавнего гугления по какому-то поводу попалась мне на глаза заметка, в которой автор приводил реализацию алгоритма получения всех перестановок (permutations) на PHP. Видимо, по той причине, что обработка входного массива выполнялась "по месту", что существенно экономило память,  реализация алгоритма получилась весьма витиеватой. То есть, чтобы разобраться, как он работает, пришлось натурально браться за ручку и бумагу ))

И вот задумался я, а можно ли как-то все это реализовать в более понятном ключе ?....

вторник, 3 сентября 2013 г.

Решение задачи о поиске двоичного периода числа на Haskell

Не так давно на хабре проскочила заметка, в которой автор описывал задачи, требующие решения для получения доступа на некую зарубежную биржу фриланса. Одна из задач звучала так: имеется некоторое целое число N в диапазоне от 1 до 1,000,000,000. Необходимо найти двоичный период этого числа. Что такое двоичный период ? Это количество символов двоичной последовательности наименьшей длины, которая будучи повторена минимум 2 раза приведет при её зацикливании к получению этого самого числа N на длине двоичного представления N.

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

Двоичный период числа 127 равен 1, так как двоичное представление числа 127 - суть "1111111" (7 единиц), и двоичная последовательность наименьшей длины, которая при зацикливании воссоздаст двоичное представление числа 127 - это 1. А длина двоичного представления единицы тоже равна одному.

Рассмотрим число 955. Двоичное представление его есть "1110111011". Видно, что паттерн "1110" при повторе его 3 раза (третий раз - только первые 2 знака) даст нам полное повторение двоичного представления числа 955. Длина этого паттерна равна 4, а значит и двоичный период тоже равен 4.

Итак, суть понятна. Попробуем решить эту задачу на Haskell.