Фибоначчи на Brainfuck


Захотел я написать какую-нибудь программу на Brainfuck'e, чтобы опровергнуть мнение о том, что на нём можно писать только HelloWorld. Для начала решил написать программу вычисления n-ного числа фибоначчи.
Числа фибоначчи, это числа, где каждое следующие - сумма двух предыдущих. Я использовал такой алгоритм: есть четыре переменные: a,b,c,n, где n- номер числа последовательности.
1. n=n-1
2. a=b
3. b=c
4. с=a+b
5. если n<>0, тогда к 1
6. вывод c

Теперь надо перевести этот алгоритм на Brainfuck. Как известно, в этом языке нет операций сложения, вычитания, и условного перехода, а программа представляет собой множество вложенных циклов и операций инкремента и декремента.
Для начала, сделаем алгоритм ввода числа. Команда , здесь не поможет, потому что это символьный ввод-вывод, а нам нужен числовой, которого в Brainfuck'e нет. Поэтому нам нужно его реализовать.
Для начала, введём две цифры этого числа в две первые ячейки

,>,

Теперь, нам нужно перевести эти две цифры в число.
Это можно сделать по формуле (с1-48)*10+(с2-48)
Число 48 нужно отнимать потому что цифра 1 имеет номер 49, а 49-48=1, и так со всеми цифрами.
Реализуем этот алгоритм. 
Вначале отнимем от каждого числа по 48, это можно сделать отнимая 6 от каждой ячейки 8 раз.

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

Теперь надо перенести значения едениц в ячейку n, и десятикратно количество десятков
Пускай n находится в 4-ой ячейке
Переносим десятки

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

Переносим еденицы

>[->>+<<]

Теперь, когда ввод реализован нужно реализовать алгоритм подсчёта, написанный выше.
Распределение памяти такое:
1 - a
2 - b
3 - c
4 - n
5 - temp

Для начала подсчёта, надо занести в с значение 1,

>+

а переменную n уменьшить на 1, это я установил опытным путём.

>-

Начинаем цикл, и уменьшаем n

[-

Переходим к a и очищаем её 

<<<[-]

Перемещаем b в a

>[-<+>]

Перемещаем c в b

>[-<+>]

Теперь надо реализовать сложение, это будет труднее. Будем делать так: Перемещаем из переменной a сразу в две переменные: c и Temp, потом из temp переносим обратно в а

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

Получается, мы добавили значение переменной a к переменной с не изменяя a.
Поступим также и с b

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

Теперь мы сложили a и b и сумму поместили в С.
Закроем цикл.

<]

Итак, мы реализовали алгоритм находжения n-ого числа фибоначчи. Теперь надо вывести результат.
Выводить командой . не получится, потому что это симвльный вывод, а нам нужен числовой. Но числовой вывод 
реализовать трудно, поэтому мы будем делать вывод звёздачками, тоесть, какой получился ответ, столько звёздочек и выводить.
Вначале надо занести в ячейку 5 номер символа *

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

Потом, отнимать по одному из ячейки с, при этом выводя звёздочку на экран

<<<[->>.<<]

Вот и вся программа нахождения n-ого числа фибоначчи на Brainfuck. Пользоваться ей так: Запусаем программу, вводом n, например, 

06 

Энтер нажимать не надо. После этого, на экране 

******** 

8 звёздочек.

Вот вся программа:


,>,>++++++++[-<------<------>>]
<<[->>>++++++++++<<<]>[->>+<<]
>+>-[-<<<[-]>[-<+>]>[-<+>]
<<[->>+>>+<<<<]>>>>[-<<<<+>>>>]
<<<[->+>>+<<<]>>>[-<<<+>>>]<]
>>++++++[-<+++++++>]<<<[->>.<<]
Hosted by uCoz