Как-то давным-давно я наткнулся на одну мозголомную задачу по программированию. Как многие задачи подобного рода она служит только для разминки мозга, её решение не представляет никакой практической ценности и может служить разве что как извращённый способ обфускации. Сегодня я хочу поделиться с вами её условием, моим решением, а также дать вам пару подсказок, если вы захотите подумать над задачей самостоятельно. Решение с подсказками я, конечно, спрятал под спойлер.
Задача
Перебрать все целые числа на заданном отрезке с заданным шагом, не используя операторы ветвления (if, if-else, switch-case…), операторы цикла (for, while, do-while…) и операторы безусловного перехода (goto, break…). Также нельзя генерировать и выполнять код во время выполнения программы, то есть в JavaScript, например, вам нельзя использовать функцию eval.
Язык программирования можете взять любой. Я выбрал JavaScript.
Примеры такого перебора. В данном случае это просто вывод всех перебираемых чисел на консоль. (Реализация функции iterate, естественно, пропущена):
// от 0 до 5 с шагом 1 iterate(0, 5, 1, console.log); // 0, 1, 2, 3, 4, 5 // от 0 до 10 с шагом три iterate(0, 10, 3, console.log); // 0, 3, 6, 9 // от 5 до -5 с шагом -2 iterate(5, -5, -2, console.log); // 5, 3, 1, -1, -3, -5 // от 3 до 3 с шагом 2 iterate(3, 3, 2, console.log); // 3 // от 3 до 0 с шагом 2 iterate(3, 0, 2, console.log); // не выведет ничего
Подсказки
Смотреть по порядку!
Раз:
Вместо циклов используйте рекурсию. Не забывайте, что для прекращения рекурсивных вызовов нельзя использовать if.
Два:
Для ветвления кода можно использовать оптимизацию выполнения логических выражений. При такой оптимизации интерпретатор не выполняет оставшиеся подвыражения логического выражения, если в ходе вычисления стало возможно определить значение всего логического выражения заранее.
Пример такой оптимизации:
var sayNya = function () { console.log('Nya!'); }; /* * 'Nya!' на консоль не выведется, * поскольку выражение * false && любоеБулевскоеЗначение * всегда будет равно false * и не зачем приступать к вычислению значения * второго операнда */ false && sayNya(); /* * Здесь 'Nya!' на консоль тоже не выведется (, * поскольку выражение * true || любоеБулевскоеЗначение * всегда будет равно true * и не зачем приступать к вычислению значения * второго операнда */ true || sayNya();
Три:
Ветка кода после условного оператора должна быть заключена в фигурные скобки, если в ней несколько выражений, в противном случае при срабатывании условного оператора выполнится только первое выражение. Для объединения нескольких действий в один операнд логического выражения можно использовать самовызывающиеся анонимные функции.
Например:
var invoke = true; invoke && (function () { console.log('neko'); console.log('nya'); console.log('^_^'); })();
Если переменной invoke при инициализации присвоить false, то на консоль ничего не выведется.
Решение:
var iterate = function (start, end, step, callback) { var current = start, next = function () { var hasNext = start <= end && step > 0 && current <= end || start >= end && step < 0 && current >= end; hasNext && (function () { callback(current); current += step; next(); })(); }; next(); };
Рассмотрим сначала, как вычисляется значение переменной hasNext, значение которой показывает, нужна ли следующая итерация или нет. Нас интересуют два случая:
- Когда число, с которого начинается перебор, меньше чем число, которым он заканчивается, и шаг перебора больше нуля.
- Когда число, с которого начинается перебор, больше чем число, которым он заканчивается, и шаг перебора меньше нуля.
В остальных случаях перебор даже не должен начаться.
Осталось только для случаев 1 и 2 проверить не вышел ли текущий элемент за границы перебора.
Теперь, когда известно, нужна ли следующая итерация или нет, сымитируем поведение условного оператора (см подсказку 2): код после операнда hasNext не выполнится, если значение hasNext будет равно false, так как в этом случае значении всего выражения заведомо известно, и так же равно false
Второй операнд логического выражения это самовызвающаяся функция, необходимая для того, чтобы объединить несколько действий в один операнд логического выражения (см подсказку 3).
Жду ваших решений
Если вы придумали своё решение и хотите им поделится, то милости прошу. Только не спойлерите – другим, возможно, тоже захочется подумать. Воспользуйтесь для размещения кода какими-нибудь сервисами, например, gist или pastie, и приведите в комментарии только ссылку.
Успехов вам. Разминайте мозги!