Пользователь
0,0
рейтинг
17 декабря 2010 в 20:22

Разработка → Нормальный алгоритм Маркова для деления чисел из песочницы

Добрый день. Хотелось бы поделиться с Вами очень интересным вариантом ненормального прграммирования — составлением нормальных алгоритмов Маркова. Этот вариант программирования может служить великолепным умственным отдыхом от привычных языков и сред программирования.
Студенты, которых я имею возможность учить, кричат криком, что это сложно, но только до первого собственными руками сделанного рабочего алгоритма, потом это перетекает в очень интересные алгоритмические задачки.
Собственно, к теме этого поста: наша задача написать нормальный алгоритм Маркова для деления двух целых чисел с точностью 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
Если это будет кому-нибудь интересно — дерзайте.
@Dimon_pl
карма
23,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (34)

  • +4
    А где же объяснение, как это работает?
    • +1
      Обычная грамматика, все просто и понятно. Есть набор правил. В любом варианте Вам можно выбрать только одно следующее правило. И так пока не разберете все выражение.
      • 0
        Сначала подумал так же, что и правда, чего объяснять — грамматика же! Однако зайдя на википедию и почитав, понял, что такого алгоритма я еще на практике не реализовывал. Поэтому присоединяюсь к комментарию верхнего уровня — было бы неплохо добавить описание работы алгоритма на основе данных правил грамматики, пусть статья будет законченной(гуглить я умею).
        • 0
          Ну, алгоритм не читал, но сам много задачек решил в унарной системе на алгоритме Маркова, постараюь объяснить примерно, как обычно (и вроде бы здесь так же) это выполняется:
          Сначала, собственно, добавляем разделить в конце слова предложения (например, "=" ), потом начинается анализ каждого символа слева, что нибудь с ним делается, исходя из условаия (читай: на что — нибудь заменяется) и переносится вправо, при этом ставится флаг на отработанной цифре. Флаг — это доп. символ справа от цифры ("*" например). А перенос осуществляется банальной заменой |* на *|.
          Ну а условия осуществляютяс расстановкой разнообразных флагов (символов).
          • 0
            Итак, анализируем слева направо. Немного запутался с переносами — все же мы только заменяем текущую анализируемую позицию или еще и переносим на правый конец? Что еще не понятно — как определяется сколько символов под читающей головкой анализировать? С помощью условий? Например:
            h* на oh
            h% на h
            h на «пустая строка»
            Читаем символ, если это h, читаем еще один символ, анализируем его и если это не * и не %, возвращаем его обратно на входную ленту? И правильно ли я понимаю, что во входной алфавит входят все три варианта — h*, h% и h?
            Понимаете, хочется формального описания, с грамматиками я знаком и суть я и так схватил. Поэтому автору плюсанул в карму, подождем пока, может дополнит статью.
            • +1
              Как определять сколько символов под читающей головкой анализировать?
              Допустим, есть эмулятор маркова, который заменяет по грамматике, в которой правила описываются видом AA -> BB
              Он каждый ход просматривает все инструкции сверху и ищет во ВСЕЙ строке первое совпадение с левой частью инструкции. Тоесть ищет AA и заменяет его на BB. Допустим входное слово ppAApp, после прохождения оно станет понятное дело ppBBpp.

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

              Главное это порядок инструкций, ведь Марков каждый шаг все инструкции проверяет заново.

              Входной алфавит — это один набор символов, а дополнительные (терминальные) символы в инструкции нужны только для саомго алгоритма.

              Если я не так вас понял, прошу извинить.
              • 0
                Вы правильно меня поняли, спасибо за разъяснения! Мой кругозор расширен!
                В теории алгоритм достаточно простой, на практике же, как мне кажется, нехорошо, что непонятно сколько символов надо анализировать+сложность составления правил в нужном порядке. Интересно, где он применяется в реальной жизни? Или только академический интерес?
        • 0
          Никто и не говорит, что описание здесь излишне. Грамматика понятна тем, кто с ней работал. Тем же кто интересуется, необходимо описание на человеческом языке. Поднимите кармы автору, чтобы он подправил статью. Будет хороший мануал для начинающих.
      • НЛО прилетело и опубликовало эту надпись здесь
        • 0
          Мне этот алгоритм показался похож на преобразователь с магазинной памятью, только который проходится по цепочке несколько раз. Конечно, это не он, тут более сложный принцип анализа входной цепочки получается и преобразователь работает один раз.
          • НЛО прилетело и опубликовало эту надпись здесь
  • +10
    В блоге «Ненормальное программирование» нормальный алгоритм Маркова — это нормально или ненормально?..
    • 0
      Ваш вопрос не совсем нормальный, ненормальность нормальности алгоритма Маркова заключается в ненормальном программировании для нормальных нужд, где использование нормальных или ненормальных принципов полностью отвечает нормальности автора, а так же степени ненормальности руоводства, поставившего кажущуюся с виду нормальную задачу. Вот такие дела.
      • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    А где пошаговая реализация преобразования?
  • +2
    Может лучше поместить статью в раздел:
    habrahabr.ru/blogs/algorithm/
    ?
  • +2
    Экстремалы. Надо с чего-нибудь попроще начинать, например, с двоичного умножения. Десятичная система это бессмысленное усложнение.
  • 0
    Выглядит как машина Тьюринга, вид сбоку. По крайней мере, представление числа в виде последовательности из N «палочек» сильно напоминает университетские упражнения: «А сейчас, дети, пишем программу для перемножения двух чисел».
    • 0
      не удивительно, нам в курсе Теории Алгоритмов и то и то давали :)
      • 0
        >неудивительно
        self fix
  • НЛО прилетело и опубликовало эту надпись здесь
  • +5
    |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||/||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| = 3.1415

    250077 шагов
    • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    >… упорядоченный набор продукций (замен подстрок). Продукции могут быть как и обыкновенными…

    Таким псевдорусским можно мозг выносить и без Маркова
  • +2
    реализация алгоритма

    на перле
    codepad.org/ZSI3WRuM

    реализация на с++
    codepad.org/GcE27qcN
  • 0
    Автор, спасибо. Надо бы как-нибудь прочитать про цепи Маркова.
  • 0
    На правах автора хотелось бы попробовать ответить на большинство комментариев сразу.
    Если есть надобность расширить описание как это происходит с удовольствием сделаю это.
    А где пошаговая реализация преобразования? -> Я подумал что очень много текста осилит далеко не каждый и пытался сделать этот пост максимально лаконичным.

    К исходной строке вначале тоже ничего добавлять не нужно.
    Зачем может быть нужно такое программирование в реальной жизни — задачи сложного символьного интегрирования и дифференциирования в системах компьютерной алгербы(как разработчику одной из таких систем приходится сталкиваться).

    Остается открым вопрос, есть ли сильные духом кто попробует выполнить задание из P.P.S поста?
  • 0
    > h% наh

    В списке замен нужна замена.
  • +1
    Онлайн интерпретатор, если кто искал.
  • 0
    Написал, не сложно. Но простите, а чем он нормальный? :)
  • +2
    Это кажется тот самый Марков, который после Октябрьской Революции (переворота), когда у него из прихожей похитили галоши, писал Ленину, что теперь вследствие этого не может посещать ВУЗ и учить студентов математике. Вождь Мирового Пролетариата не прошел мимо простого профессора и немедленно отвлекись от наступления Юденича и писем к Американским рабочим, тут же написал мандат на возврат галош профессору. И тот же самый матрос, который обчистил профессорскую прихожую, пожал плечами и обчистил соседнюю, вернув галоши Маркову. При этом обе они оказались на одну ногу, о чем профессор немедленно снова писал Вождю. У того видно с Юденичем было совсем неотложно, да и Американское рабочие ждать уже больше не могли, и он на письмо Маркова не ответил. Кажется это подтвердило справедливость Марковских цепочек, а его самого избавило от многих неприятностей в будущем, которым подверглись другие математики, которые не переписывались лично с Ильичом.
  • +2
    экспериментальным путем было выявлено, что лучше "_ на 0.FIN", чем "_ на .FIN"

    codepad.org/3v0Mw0c9
    реализация на Хаскеле \(^^)/

    что порождает сразу такие забавные примеры, как:

    markov_bin2un = markov bin2unD
    markov_div_un = markov un_divD
    markov_div_bin x y = markov_div_un ( markov_bin2un x ++ "/" ++ markov_bin2un y )

    *Main> markov_bin2un «1111»
    "|||||||||||||||"
    *Main> markov_div_un "||/|||"
    «0.6666»
    *Main> markov_div_bin «11» «111»
    «0.4285»
  • 0
    У меня получилась 41 команда. Последовательность действий такая: 1) переводим числитель в десятичную с/с; 2) приписываем к нему справа 4 нуля; 3) переводим его обратно в унарную с/с; 4) выполняем целочисленое деление в унарной с/с; 5) переводим результат в десятичную с/с (с правильной установкой точки). Шаги 1 и 5 выполняются одними и теми же командами. Сам алгоритм:
    / :: AB
    |A :: A|
    A :: X
    0| :: 1
    1| :: 2
    .....
    8| :: 9
    9| :: |0
    .| :: |.
    X| :: X1
    B :: 0000CD
    1* :: 0
    2* :: 1
    .....
    9* :: 8
    0* :: *9
    X0 :: X
    XC :: [empty]
    C :: *C| 
    +P :: |+
    P| :: |P
    |D| :: DP
    DP :: D|+
    D| :: Z
    Z| :: Z
    ZP :: Z
    Z+ :: X0.0000|Q
    Q+ :: |Q
    Q :: [empty]
    X. :: 0. [FIN]
    X :: [empty] [FIN] 

    Выполняется, правда, подольше, но автором задача наискорейшего выполнения и не ставилась :)

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.