110100100020000

Недавно, на собеседовании мне задали задачу.

Дана последовательность единиц и нулей вида: 11010010001000010000…. Тоесть это последовательность степеней десятки. Необходимо написать метод(функцию), который на вход принимает позицию числа в последовательности(счёт начинается с нуля), а на выходе возвращает единицу или ноль, в зависимости от того, какое число стоит на данной позиции.

На самом собеседовании, я естественно затупил, и ничего работающего не написал. Единственное, что я предложил, это использование двух вложенных циклов, один будет бежать по 1-м, а другой по нулям. И длинна выполнения каждого нулевого цикла, естественно будет зависть от того, какая по счёту итерация цикла внешнего. Отстойное и медленное решение! Но потом,  уже дома, я придумал другое решение, и как по мне, так оно вполне себе не полохое. Привожу примеры кода на java и python:

JAVA   
public static void main(String[] args)
    {
        for (int i = 0; i < 50; i++)
        {
            System.out.print(calculate(i));
        }
    }
 
 
    public static int calculate(int position)
    {
        return calculate(0,0,position);
    }
 
    private static int calculate(int iterationNumber, int iterationPosition, int position)
    {
        if (iterationPosition == position)
        {
            return 1;
        }
        if (iterationPosition > position)
        {
            return 0;
        }
        iterationNumber++;
        iterationPosition = iterationPosition + iterationNumber;
        return calculate(iterationNumber, iterationPosition, position);
    }

Python   
def calculate(position):
    return rec_calculate(0, 0, position)
 
def rec_calculate(iter_num, iter_pos, position):
    if iter_pos > position:
        return 0
    elif iter_pos == position:
        return 1
    iter_num += 1
    iter_pos = iter_pos + iter_num
    return rec_calculate(iter_num, iter_pos, position)
 
for i in range(0,100):
    print(calculate(i), end='')

Суть идеи очень простая, мы  рекурсивно вызываем метод(функцию) на вход которого подаётся, текущий номер итерации, позиция последней итерации и искомая позиция.

Если позиция последней итерации больше искомой позиции – это значит, что мы попали в нули, и значит можно смело возвращать ноль, если позиция последней итерации равна позиции, то мы попали в единицу. В ином случае, мы не добрались до нужной нам позиции, а это значит, что необходимо увеличить номер итерации и текущую позицию на этот номер.

Если вы знаете какое-либо более быстрое решение этой задачи, то, пожалуйста, напишите его в комментарии.

Опубликовать в Google Plus
Опубликовать в LiveJournal
Опубликовать в Мой Мир
Опубликовать в Одноклассники
Опубликовать в Яндекс