Возьмем машину, система команд которой точно такая же, как и в языке Brainfuck, но которая работает на ленте, в ячейки которой можно помещать любые целые числа.
В арифметических операциях нет переполнения, команда «+», поданная на положительное число, всегда даст положительный результат и т. д. Вопрос в том, можно ли работать на такой машине, какие проблемы возникнут и как их обойти.
их? Преимущества очевидны: поскольку нет переполнений, нет необходимости в длинных арифметических действиях; можно одинаково работать с массивами любой длины и т. д. Но довольно быстро мы замечаем, что наш любимый метод очистки ячейки ("[-]") не работает: если в ячейке было отрицательное значение, то программа зацикливается .
Аналогично, мы не можем свободно использовать команду копирования "[-> +<]" - it also only works for non-negative numbers. Оказывается, при программировании нужно внимательно следить за знаками содержимого ячеек (проще всего вообще не допускать появления отрицательных чисел), а если появляется число, знак которого неизвестен, работать с ним в особый путь Здесь мы рассмотрим две задачи: во-первых, мы запрограммируем оператор «if(a> b) C; else D;», где a и b неотрицательные, а C и D — некоторые действия, а во-вторых, мы научимся сбрасывать, копировать и определять знак произвольного числа.
Условный оператор.
Итак, на ленте записаны два неотрицательных числа a и b (в клетках которых мы выбираем сами).
Нам нужно сравнить эти числа и в зависимости от результата выполнить одно из действий C или D. Все использованные ячейки (включая те, в которых находились a и b) необходимо обнулить.
Перепишем оператор следующим образом:
h=1;
while(h){
if(a==0){ D; a=b=1; h=0; }
if(b==0){ C; a=b=1; h=0; }
a--; b--;
}
Если бы a и b были неотрицательными, то в такой программе не могут появиться отрицательные числа.
Чтобы реализовать оператор if(a==0) B; создайте на ленте блок из 4 ячеек «a 0 1 0» и выполните команды «[> ]> > [B> ]».
Если в начале каретка находилась на первой ячейке блока, то в конце она будет на его 4-й ячейке в любом варианте.
Программа будет выглядеть так (при условии, что курсор и цифра «а» находятся в ячейке 0, а цифра «б» — в ячейке 4):
>>+[ <<[>]>>[C-<<+>>>>[-]+<] >[<]<<[D->>+<<<<[-]+>] <->>>>-<<]Переменная h — это та, что из блока «a 0 1 0 b» — все равно после ее обнуления эффективных сравнений не будет. Программу можно немного упростить, записав ее в виде
h=1;
while(a){
if(b==0){ C; a=b=1; h=0; }
a--; b--;
}
if(h){ D; h=b=0; }
Это сработает >>>+<<< [>[>]>>[C-<<+<[-]+>>>>] <<<-<-] >[-]>>[D-]Время работы программы линейно зависит от max(a,b).
Число с неизвестным знаком
Пусть на ленте записано число а, о котором мы не знаем, положительное оно или отрицательное.Нам нужно: (1) обнулить его, (2) скопировать в другую ячейку и (3) выполнить действие F, если a> 0. Мы решим все три проблемы вместе.
Как их решить? Примерно так же, как мы ищем ненулевую ячейку на ленте машины Тьюринга, бегаем влево и вправо, пока не достигнем 0:
if(a){
x=1;
while(x){
y=2*x;
while(x){
x--; a++; b--;
if(a==0) x=y=0;
}
x=2*y;
while(y){
y--; a--; b++;
if(a==0){ F; x=y=0; }
}
}
}
Переменная a будет скопирована в b, а F будет выполняться только в том случае, если исходное значение a было положительным.
Перевод в БФ:
[>>+<<<<<+
[ [-<++>>+<]>
[->->+[>]>>
[-<<<<[-]<<[-]]
<<<<<]
<<[->++>+<<]>>
[->+>-[>]>>
[F -<<<<[-]<[-]]
<<<<<]
<]]
Время работы также линейно зависит от abs(a).
Здесь следует отметить, что в блоках if(a==0) x=y=0; карета уходит далеко от своего места и остается там.
Но это не очень важно, так как в этот момент циклы заканчиваются.
Что? Все, что можно было сделать на 8-битной машине BF, можно сделать и здесь? Увы.
Есть одна задача, с которой машина с бесконечной разрядностью не справится.
А именно очистка участка ленты.
Если нам не дать кусок, который гарантированно будет заполнен нулями, мы не сможем его создать.
Хотя я не могу этого доказать :( Теги: #brainfuck #Ненормальное программирование
-
Почему В России До Сих Пор Нет Iphone 3G?
19 Oct, 24 -
26 Июля, Deworkacy - Docops От Ростелекома
19 Oct, 24 -
Yahoo Переходит На Openid 2.0
19 Oct, 24
