Остановится ли? Часть II (Задача)

Условие задачи такое же, как и в предыдущей, но Вы можете использовать только язык программирования Brainf**k. Вывод программы должен содержать ровно 1 символ — ответ на вопрос («Y» или «N»).

Решение:

Будем теперь реализовывать проверку, является ли число n степенью двойки, на языке Brainf*ck. Первый этап – ввод числа. Так как ограничение довольно большое (), то хранить это число придется поразрядно.

>> ,+[>+++++++[-<------->]+>>,+]<<-<[+]

Отступим перед вводом две ячейки – они нам понадобятся в дальнейшем (вместо этого могли бы использовать две ячейки с отрицательными адресами, но в интерпретаторе bff-1.0.3.1 есть ошибка: они не заполняются нулями).

После каждой введенной цифры будем записывать специальную метку и оставлять пустую ячейку:



Метки впоследствии помогут нам точно определять границы числа. В качестве них используем единицу. Также, так как при вводе считывается код символа, а не сама цифра, для удобства вычтем код символа '0' (48).

В последнем «фиктивном» разряде будем накапливать остаток (сначала оставим ячейку пустой).



<<[<<<]>>>

После ввода «откатимся» к началу числа.

Далее идет сам алгоритм: будем целочисленно делить число на 2, пока оно не обнулится (длинная арифметика).

Начиная с первой цифры (старшего разряда):

[

[<[<<]>[->>>>]<] >>>

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

[

<[->>+<<] + >>

Перенесем цифру в пустую ячейку справа от метки, а в исходную ячейку положим резервное значение 1, чтобы в любом случае иметь возможность «откатиться» до нее.

[

->++++++++++< [->----------<<<+>-]

Пока не обнулим разряд, будем вычитать 2 и в исходную ячейку прибавлять 1.

Более детально: если удалось вычесть 2, то временно обнулим метку.

Если цифра по-прежнему больше нуля, восстановим метку и повторим:

<[<]>>[-]+ >

]

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

<<-> >>>

]

Вычтем обратно из исходной ячейки «резервную» единицу и перейдем к следующему разряду (повторим с пункта 1).

<<<[<<<]>>>

]

Достигнута последняя цифра – число поделено на 2. Если она была нечетная, то в результате мы прибавили 10 в следующий «фиктивный» разряд – в этой ячейке накапливается суммарный остаток от деления.

«Откатимся» к первой цифре числа и повторим деление (с пункта 0).

<<< +++++[-<--<++>>]<<+[>>++++++++<[>->]<[<]>-] >>+.

Когда число целиком обнулилось (не осталось ни одной метки), проверяем, чему равен накопленный остаток: если 10 (только за счет последней единицы), то n – степень двойки, выводим 'Y', если же больше – выводим 'N'.

This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at fivefilters.org/content-only/faq.php#publishers. Five Filters recommends: 'You Say What You Like, Because They Like What You Say' - http://www.medialens.org/index.php/alerts/alert-archive/alerts-2013/731-you-say-what-you-like-because-they-like-what-you-say.html