Интересная задачка по программированию

Интересная задачка по программированию

Как-то давным-давно я наткнулся на одну мозголомную задачу по программированию. Как многие задачи подобного рода она служит только для разминки мозга, её решение не представляет никакой практической ценности и может служить разве что как извращённый способ обфускации. Сегодня я хочу поделиться с вами её условием, моим решением, а также дать вам пару подсказок, если вы захотите подумать над задачей самостоятельно. Решение с подсказками я, конечно, спрятал под спойлер.

Задача

Перебрать все целые числа на заданном отрезке с заданным шагом, не используя операторы ветвления (ifif-elseswitch-case…), операторы цикла (forwhiledo-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, и приведите в комментарии только ссылку.

Успехов вам. Разминайте мозги!

 

Добавить комментарий

Ваш адрес email не будет опубликован.