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

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

Задача

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

Подсказки

Смотреть по порядку!

Решение

Рассмотрим сначала, как вычисляется значение переменной hasNext, значение которой показывает, нужна ли следующая итерация или нет. Нас интересуют два случая:

  • Когда число, с которого начинается перебор, меньше чем число, которым он заканчивается, и шаг перебора больше нуля.
  • Когда число, с которого начинается перебор, больше чем число, которым он заканчивается, и шаг перебора меньше нуля.

В остальных случаях перебор даже не должен начаться.

Осталось только для случаев 1 и 2 проверить не вышел ли текущий элемент за границы перебора.

Теперь, когда известно, нужна ли следующая итерация или нет, сымитируем поведение условного оператора (см подсказку 2): код после операнда hasNext не выполнится, если значение hasNext будет равно false, так как в этом случае значении всего выражения заведомо известно, и так же равно false

Второй операнд логического выражения это самовызвающаяся функция, необходимая для того, чтобы объединить несколько действий в один операнд логического выражения (см подсказку 3).

Жду ваших решений

Если вы придумали своё решение и хотите им поделится, то милости прошу. Только не спойлерите – другим, возможно, тоже захочется подумать. Воспользуйтесь для размещения кода какими-нибудь сервисами, например, gist или pastie, и приведите в комментарии только ссылку.

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

  • Михась Коберник

    Реализовал, но хуже — https://gist.github.com/m-kobernyk/26340dd47d69f6ab8405
    Странное дело — если не делаю console.log(‘in @upIterate’);, то мой комилятор не может (node 0.10.26) ругается на невозможность найти функцию upIterate()/downIterate(). What’s wrong?

    • Спасибо за решение! А чтобы избавиться от ошибки просто расставьте точки с запятой.
      (см. мой форк)
      https://gist.github.com/Gooz92/d944dbf54b39acbaa260

      • Михась Коберник

        Все так. Спасибо 🙂

      • Михась Коберник

        BTW, где искать подобные задачи? В идеале, рассчитанные на js или на худой конец php

        • Даже и не знаю… Если у меня будет настроение, то я попытаюсь повспоминать и попридумывать ещё подобных задач.

  • mops1k

    Попробовал на PHP сделать:
    https://gist.github.com/5efc200c6824abc1509c.git

  • Антон Надежкин

    Всем привет. Начал изучать js. Вроде работает https://gist.github.com/mgelios/9fe60a93083872edf0f5 .

  • ШИК!

  • Eduard

    Получлось так:

    function iterate(start, end, step, callback)
    {
    var next = start + step;
    console.log(next);
    return ( next < end-step ) && iterate(next, end, step);
    }

    iterate(0, 10, 3);

    • Dmitryck MPreobrazhenskiy

      самое элегантное решение, если <= можно юзать..

    • Sergey Pestov

      Первое значения не всегда требуется выводить.

  • Dmitryck MPreobrazhenskiy

    использовать и тп это ведь те же условия if, просто без оператора этого..
    но сам факт-то условных сравнений присуствует..

    исходя из задания я пилил так:

    function iterate(a, b, c){
    code = {
    0:function(a, b, c, k){
    console.log(a + c*k)
    k++
    code[~~((a + c*k)/b)](a, b, c, k)
    },
    1:function(){ return }
    }
    code[0](a, b + 1, c, 0)
    }

    iterate(-3, 10, 4)

  • Sergey Pestov

    Вот решение без условных операторов:
    https://gist.github.com/pestovsa/8db096715302ebc21038c20b20cd1bf7