Нормальний алгоритм Маркова для розподілу чисел
Добридень. Хотілося б поділитися з Вами дуже цікавим варіантом ненормального програмування — упорядкуванням нормальних алгоритмів Маркова. Цей варіант програмування може бути чудовим розумовим відпочинком від звичних мов та середовищ програмування. Студенти, яких я маю можливість вчити, кричать криком, що це складно, але тільки до першого своїми руками створеного робочого алгоритму, потім це перетікає в дуже цікаві алгоритмічні завдання. Власне, до теми цього посту: наше завдання написати нормальний алгоритм Маркова для поділу двох цілих чисел з точністю 4 знаки після коми(для завдання чисел користуємося унарною системою обчислення). Наприклад, вхід: / вихід: 0.25. При цьому ми маємо лише одну операцію — заміну одного підрядка у вихідному рядку на інший. Кому цікаво, що це таке і як це працює, ласкаво просимо під кат.
Нормальний алгоритм Маркова
Власне вирішення поставленого завдання
Список замін: %* на *% % на %* * на ** * на 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 p> на «порожній рядок» p на .FIN _ на .FIN FIN після підстроювання на яку замінюємо означає, що така продукція фінальна.
Написати емулятор, який дозволить емулювати роботу такого алгоритму не складе ніякої праці будь-якою з мов програмування.
В результаті для входу/шляхом рядкових перетворень отримаємо 0.25. Хто не вірить – перевірте. (Записуємо на папірці вхід, наприклад ті ж / і виконуємо вказані вище підстановки до тих пір, поки алгоритм не закінчить свою роботу (умова завершення роботи див. ще вище))P.S.Ось такий елегантний і незвичний варіант складання програм та виносу мозку.
P.P.S.Шановні панове програмісти пропоную конкурс із серії «А вам слабо?»(Дозволить напружувати мозок і відпочити від звичного програмування). Завдання просте - скласти алгоритм Маркова для множення двох звичайних дробів. Приклад: Вхід: (1/2)*(2/5) Результат повинен вийти 1/5 Якщо це буде комусь цікаво - дерзайте.
Хардкорна конфа за С++. Ми запрошуємо лише профі.