Фибоначчи на 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 звёздочек.
Вот вся программа:
,>,>++++++++[-<------<------>>]
<<[->>>++++++++++<<<]>[->>+<<]
>+>-[-<<<[-]>[-<+>]>[-<+>]
<<[->>+>>+<<<<]>>>>[-<<<<+>>>>]
<<<[->+>>+<<<]>>>[-<<<+>>>]<]
>>++++++[-<+++++++>]<<<[->>.<<]