В этой статье я покажу вам, как отсортировать циферки с помощью Brainfuck.
Вы вводите цифры (каждая цифра не должна встречаться более 255 раз, при 8bit версии интерпретатора), после программа, если ее можно так назвать, выводит их по возрастанию.
Это будет реализация сортировки подсчётом, которая работает следующим образом:
1. Считывается число k.
2. В массиве A увеличиваем A[k] на единицу.
3. Повторяем шаги 1 и 2, пока не закончатся числа на входе.
4. Выводим A[i] раз число i, где i — это возможные значения чисел k.
Будем считывать символы, пока не получим перевод строки(ascii 10)
Теперь нам нужно сдвинуть указатель на значение, которое мы считали.
После этого указатель будет на ячейке, равному изначальному значению символа, который мы вводили. Все ячейки, начиная с первой, заканчивая той, перед которой указатель, будут наполнены единицами — это поможет нам вернуться к нулевой ячейке.
Ну а теперь пора увеличить значение ячейки, согласно второму шагу алгоритма.
Примечание: сдвиг на 10 ячеек не случаен, подумайте, что будет без него.
Далее перемещаемся на нулевую ячейку.
Итак, что у нас получилось, реализовав первые три шага алгоритма.
Осталось самое главное: вывести отсортированные цифры.
Но где же находятся наши цифры?
ASCII код '0' равен 48.
После считывания мы отнимали 10, затем ещё 28.
Считанное значение мы перемещали на первую ячейку.
Но перед увеличением ячейки мы переходили на 10 ячеек вперёд.
48 — 10 — 28 + 1 + 10 = 21
Значит количество нулей будет лежать в 21ой ячеек, количество единиц в 22ой и т.д.
Присвоим двадцатой ячейке значение 48 (это ascii код нуля).
Выводим значение предыдущей ячейки столько раз, какое значение в текущей ячейки.
Присваиваем текущей ячейке значение предыдущей + 1.
Делаем так для каждой цыфры.
Вот весь код
Таким нехитрым способом мы отсортировали цифры.
Несложно модифицировать код, чтобы сортировались почти любые символы, либо выводить цифры по убыванию. Использую эту идею можно сортировать не только цифры, но и 2ух — 3ех значные числа, возможно, позже я напишу об этом.
Спасибо за внимание.
Вы вводите цифры (каждая цифра не должна встречаться более 255 раз, при 8bit версии интерпретатора), после программа, если ее можно так назвать, выводит их по возрастанию.
Это будет реализация сортировки подсчётом, которая работает следующим образом:
1. Считывается число k.
2. В массиве A увеличиваем A[k] на единицу.
3. Повторяем шаги 1 и 2, пока не закончатся числа на входе.
4. Выводим A[i] раз число i, где i — это возможные значения чисел k.
Приступим
Будем считывать символы, пока не получим перевод строки(ascii 10)
,----- -----
[
----- ----- ----- ----- ----- --- уменьшаем значение ячейки на 28
*тут будет работа со введенными данными*
,----- -----
]
Теперь нам нужно сдвинуть указатель на значение, которое мы считали.
[->+<]> перемещаем значение нулевой ячейки в первую
[
[->+<] перемещаем значение из i-ой ячейки в i + 1
+>- увеличиваем i-ую ячейку, переходим в следующую ячейку, уменьшаем её
]
После этого указатель будет на ячейке, равному изначальному значению символа, который мы вводили. Все ячейки, начиная с первой, заканчивая той, перед которой указатель, будут наполнены единицами — это поможет нам вернуться к нулевой ячейке.
Ну а теперь пора увеличить значение ячейки, согласно второму шагу алгоритма.
>>>>> >>>>> + <<<<< <<<<<
Примечание: сдвиг на 10 ячеек не случаен, подумайте, что будет без него.
Далее перемещаемся на нулевую ячейку.
<[-<] спасибо единичкам, которые мы оставляли
Итак, что у нас получилось, реализовав первые три шага алгоритма.
,----------
[
----- ----- ----- ----- ----- ---
[->+<]>
[
[->+<]
+>-
]
>>>>> >>>>> + <<<<< <<<<<
<[-<]
,----- -----
]
Вывод ответа
Осталось самое главное: вывести отсортированные цифры.
Но где же находятся наши цифры?
ASCII код '0' равен 48.
После считывания мы отнимали 10, затем ещё 28.
Считанное значение мы перемещали на первую ячейку.
Но перед увеличением ячейки мы переходили на 10 ячеек вперёд.
48 — 10 — 28 + 1 + 10 = 21
Значит количество нулей будет лежать в 21ой ячеек, количество единиц в 22ой и т.д.
Присвоим двадцатой ячейке значение 48 (это ascii код нуля).
Выводим значение предыдущей ячейки столько раз, какое значение в текущей ячейки.
Присваиваем текущей ячейке значение предыдущей + 1.
Делаем так для каждой цыфры.
>>>>> >>>>> >>>>> >>>>> переходим на 20ую ячейку
++++++++ ++++++++ ++++++++ ++++++++ ++++++++ ++++++++ увеличиваем ячейку до 48
>[<.>-] <[->+<]>+ выводим, переходим к следующей ячейке
>[<.>-] <[->+<]>+
>[<.>-] <[->+<]>+
>[<.>-] <[->+<]>+
>[<.>-] <[->+<]>+
>[<.>-] <[->+<]>+
>[<.>-] <[->+<]>+
>[<.>-] <[->+<]>+
>[<.>-] <[->+<]>+
>[<.>-] выводим девятки, и наконец программа завершается
Итог
Вот весь код
,----------
[
----- ----- ----- ----- ----- ---
[->+<]>
[ [->+<] +>-]
>>>>> >>>>> + <<<<< <<<<<
<[-<]
,----- -----
]
>>>>> >>>>> >>>>> >>>>>
++++++++ ++++++++ ++++++++ ++++++++ ++++++++ ++++++++
>[<.>-] <[->+<]>+
>[<.>-] <[->+<]>+
>[<.>-] <[->+<]>+
>[<.>-] <[->+<]>+
>[<.>-] <[->+<]>+
>[<.>-] <[->+<]>+
>[<.>-] <[->+<]>+
>[<.>-] <[->+<]>+
>[<.>-] <[->+<]>+
>[<.>-]
Таким нехитрым способом мы отсортировали цифры.
Несложно модифицировать код, чтобы сортировались почти любые символы, либо выводить цифры по убыванию. Использую эту идею можно сортировать не только цифры, но и 2ух — 3ех значные числа, возможно, позже я напишу об этом.
Спасибо за внимание.