Как стать автором
Обновить

Нормальный алгоритм Маркова для деления чисел

Время на прочтение3 мин
Количество просмотров30K
Добрый день. Хотелось бы поделиться с Вами очень интересным вариантом ненормального прграммирования — составлением нормальных алгоритмов Маркова. Этот вариант программирования может служить великолепным умственным отдыхом от привычных языков и сред программирования.
Студенты, которых я имею возможность учить, кричат криком, что это сложно, но только до первого собственными руками сделанного рабочего алгоритма, потом это перетекает в очень интересные алгоритмические задачки.
Собственно, к теме этого поста: наша задача написать нормальный алгоритм Маркова для деления двух целых чисел с точностью 4 знака после запятой(для задания чисел пользуемся унарной системой исчисления). Например, вход: |/||||, выход: 0.25.
При этом у нас есть только одна операция — замена одной подстроки в исходной строке на другую. Кому интересно что это такое и как это работает — добро пожаловать под кат.


Нормальный алгоритм Маркова

Под нормальным алгоритмом Маркова будем понимать некий упорядоченный набор продукций(замен подстрок). Продукции могут быть как и обыкновенными(выполняться столько раз, сколько это возможно) так и финальными(выполняются только 1 раз и после них работа алгоритма заканчивается). Продукции выполняются начиная с первой. Если первую выполнить нельзя — делаем вторую итд. Если же после какой-либо продукции можно опять выполнить какую-то из предудущих — выполняем. Работа алгоритма закнчивается тогда, когда нет следующей для выполнения продукции и все предыдущие нельзя выполнить или после выполнения какой-нибудь финальной продукции.
Собственно решение поставленной задачи

Список замен:
%* на *%
%| на %*
*| на **
|* на t
t* на *t
t% на %t
%t на %v|
t на |
%v на ?d
?d на d?
|d на d|
? на %
*d на h
h* на oh
h% наh
h на «пустая строка»
* на «пустая строка»
d на |_
/| на -k
k| на kk
k на |+
+| на |+
- на ey
|e на e|
y на %
eo на 0o
e на «пустая строка»
|_ на .a
a. на .a
.. на .
.aaaaaaaaaa на a,.
,a на a,
.aaaaaaaaa на 9
.aaaaaaaa на 8
.aaaaaaa на 7
.aaaaaa на 6
.aaaaa на 5
.aaaa на 4
.aaa на 3
.aa на 2
.a на 1
. на 0
, на «пустая строка»
a на .a
o на p||||||||||
|p на p|
pp на p
% на u
u+ на u
u на _
|+ на |)+
) на (>
>+ на +>
+ на {
{ на |
>>>>> на =
|= на =
(= на =
( на /
p= на =<
<0 на 0<
<1 на 1<
<2 на 2<
<3 на 3<
<4 на 4<
<5 на 5<
<6 на 6<
<7 на 7<
<8 на 8<
<9 на 9<
<<<<< на$
0$ на $0
1$ на $1
2$ на $2
3$ на $3
4$ на $4
5$ на $5
6$ на $6
7$ на $7
8$ на $8
9$ на $9
=$ на .FIN
0= на =0
1= на =1
2= на =2
3= на =3
4= на =4
5= на =5
6= на =6
7= на =7
8= на =8
9= на =9
_> на «пустая строка»
0> на >0
1> на >1
2> на >2
3> на >3
4> на >4
5> на >5
6> на >6
7> на >7
8> на >8
9> на >9
p> на «пустая строка»
p на .FIN
_ на .FIN

FIN после подстроки на которую заменяем означает, что такая продукция финальная.

Написать эмулятор, который позволит эмулировать работу такого алгоритма не составит никакого труда на любом из языков программирования.

В результате для входа |/|||| путем строковых преобразований получим 0.25. Кто не верит — проверьте. (Записываем на бумажке вход, например те же |/|||| и выполняем указанные выше подстановки до тех пор пока алгоритм не закончит свою работу(условие завершения работы см. еще выше))
P.S.Вот такой элегантный и непривычный вариант составления программ и выноса мозга.

P.P.S.Уважаемые господа программисты предлагаю конкурс из серии «А вам слабо?»(Позволит понапрягать мозг и отдохнуть от привычного программирования). Задание простое — составить алгоритм Маркова для умножения двух обыкновенных дробей.
Пример: Вход: (1/2)*(2/5)
Результат должен получиться 1/5
Если это будет кому-нибудь интересно — дерзайте.
Теги:
Хабы:
Всего голосов 62: ↑53 и ↓9+44
Комментарии35

Публикации

Истории

Ближайшие события

19 августа – 20 октября
RuCode.Финал. Чемпионат по алгоритмическому программированию и ИИ
МоскваНижний НовгородЕкатеринбургСтавропольНовосибрискКалининградПермьВладивостокЧитаКраснорскТомскИжевскПетрозаводскКазаньКурскТюменьВолгоградУфаМурманскБишкекСочиУльяновскСаратовИркутскДолгопрудныйОнлайн
3 – 18 октября
Kokoc Hackathon 2024
Онлайн
24 – 25 октября
One Day Offer для AQA Engineer и Developers
Онлайн
25 октября
Конференция по росту продуктов EGC’24
МоскваОнлайн
26 октября
ProIT Network Fest
Санкт-Петербург
7 – 8 ноября
Конференция byteoilgas_conf 2024
МоскваОнлайн
7 – 8 ноября
Конференция «Матемаркетинг»
МоскваОнлайн
15 – 16 ноября
IT-конференция Merge Skolkovo
Москва
25 – 26 апреля
IT-конференция Merge Tatarstan 2025
Казань