Решение:
Будем теперь реализовывать проверку, является ли число 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
Комментариев нет:
Отправить комментарий