powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Четверговый НАМ и сложение двоичных чисел в строках
107 сообщений из 107, показаны все 5 страниц
Четверговый НАМ и сложение двоичных чисел в строках
    #39963532
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Привет Котаны-Бротаны! В уже сложившейся традиции четверговых-пятничных топиков я публикую логическую задачу-головоломку. Задача Написать алгоритм сложения двух двоичных чисел в нотации Нормальных Алгоритмов Маркова (НАМ) Input:
Код: sql
1.
2.

"1101+111"
Output code example:
Код: sql
1.
2.
3.
4.
5.

 ->
 ->
 ...
 |->
Output result example:
Код: sql
1.
2.

"10100"
Под катом я расскажу что такое НАМ своими словамиНормальные Алгоритмы Маркова (НАМ) - представляют собой совокупность правил (rules) вида:
Код: sql
1.
2.
3.

a -> b
x -> y
которые последовательно применяются к входящей строке до тех пор пока не будет достигнyто условие применения terminal rule ( |-> ). Применение - суть строковая замена. Выражение слева от стрелки заменятеся на правое. Пример алгоритма переводящего римскую цифру в десятичное число.
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.

IX -> 9
VIII -> 8
VII -> 7
VI -> 6
V -> 5
IV -> 4
III -> 3
II -> 2
I -> 1
|->
Еще некоторы дополнения. 1) За 1 раз выполняется только 1 строкова замена. 2) Если rule сработал - то возвращаемся к самому первому rule по списку. 3) Если левое выражение от стрелки - пустое - то это означает конкатенацию к голове результирующей строки. 4) Правое выражение пустое - просто удаляем подстроку. 5) Никаких if-else,for/do while не существует. Вот. Надеюсь нормально пояснил.
Что приветстуется:
  • Ваши любые рассуждения и решения как это сделать. Сам я сейчас - не знаю как решить эту задачу. Тоесть нахожусь в одинаковых условиях с вами.
  • Любые реализации машины Маркова. С++/браузерные и теоретические.
  • Новые задачи и головоломки после того как решим эту.
Не приветсвтуется:
    вопросы из серии "зачем это надо" игнорирование алгоритмов НАМ
Некоторые подсказки которые я сам для себя нашел Иногда полезно вводить в алфавит новый символ. Какую-то звездочку. Ее можно приклеивать к строкам как вагончик и использовать для поиска. А в конце - удалить. Пример программы которая передвигает букву 'a' в конец слова.
Код: sql
1.
2.
3.
4.

*ab -> b*a
* |-> 
-> *
Input: abbbbb Output: bbbbba (обратите внимание. терминальная стрелочка стоит на второй позиции. Это важно. Если ее не там поставить - мы получим зацикливание) Некоторый формализм я сознательно скипал. Алфавиты и символы. И поэтому в литературе терминальная стрелочка может рисоваться не так. Но нам пофиг.
Просто некоторые линки https://en.wikipedia.org/wiki/Markov_algorithm Здесь есть пример перевода двоички в унарный код
Вот так. Go-go думать! Об оптимизации - не думаем. Нужно любое работающее решение.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963592
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Алгоритм: сложение в столбик
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963597
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ммм... да. Код давай.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963601
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Может вопрос-таки об умножении?
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963604
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Давайте все таки начнем со сложения.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963618
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Давайте все таки начнем со сложения.


1. двоичный код - в палки (для обоих слагаемых)
2. убрать плюс
3. палки - в двоичный код
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963640
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
+1

Одна процедура уже есть. Но мне кажется что обратная будет не так проста.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963675
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Скопипащу с вики сюда. Что б было.

Конвертер с бинарного кода в унарный.

Rule|0 -> 0||1 -> 0|0 ->

Для нашего примера.

Input:
1101+111

Output:
|||||||||||||+|||||||

Далее. Здесь надо аккуратно. Надо выкинуть плюсик но только после того
как оба слагаемых сконверчены в лесенку из палочек.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963685
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
тут наверное на ассемблере было бы прикольно напрограммировать с побитовыми операциями...
ну типа прописать в память 0 и 1
но я ассемблера не знаю :(
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963692
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Этот топик - вообще не про Ассемблер.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963725
Swa111
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
mayton,

Проверил на ограниченном наборе. Правила формирования файла rule.txt: Сначала идут тестовые образцы в формате
Тест -> Ожидаемый результат
Если ожидаемый результат начинается с @ то после него идет функция получения результата от левой части
Образцы собираются до строки <<rules>>, все оставшееся это правила.
комментарии в правилах как в VB, Пустые строки игнорируются.

запуск через run.bat

Код: vbnet
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
'Двигаем очередной знак вправо
*0= -> <*=0>
*1= -> <*=1>
0>0 -> 00>
0>1 -> 10>
1>0 -> 01>
1>1 -> 11>
'выполняем сложение
00>e -> $e0
01>e -> $e1
10>e -> $e1
11>e -> ~$e0

=1>e -> =$e1
=0>e -> =$e0

'Увеличиваем правую часть при переполнении
1~ -> ~0
0~ -> 1
=~ -> =1

'Сложение завершено идем за следующим знаком
1$ -> $1
0$ -> $0

'Забираем очередной знак
0<*=$ -> <*=0>
1<*=$ -> <*=1>
<*=$ -> 

'Двигаем символ конца расчетов
e1 -> 1e
e0 -> 0e
e+ -> @e

'Символ конца на месте, начинаем счет
@ -> <*=$

'правая часть больше левой 
<*=$ -> 

'Конец, терминальное правило так как строка заканчивается на |
e| -> 
'Затравка на первом проходе
 -> e
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963758
Swa111
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Забавная штука....

пример с хабра Нормальный алгоритм Маркова для деления чисел . Список замен немного изменен, так в этой машине символ | - служебный. Так что вместо него следует использовать #
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963797
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
1101+111 =
1000 + 100 + 100 + 10 + 1 + 1 =
1000 + 100 + 100 + 10 + 10 =
1000 + 100 + 100 + 100 =
1000 + 1000 + 100 =
10000 + 100 = 10100
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963846
Swa111
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Поправил интерпретатор, что бы символ "|" не выпадал из алфавита. Обычные пары разделяются последовательностью " -> ", терминальные пары последовательностью " |-> "
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963851
Swa111
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
В интерпретатор добавлена проверка перекрытия правил
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963859
Фотография crutchmaster
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,
Зачем нужно terminal rule я не понял.

mayton
Об оптимизации - не думаем. Нужно любое работающее решение.

Так это элементарно. Надо просто перебрать все суммы двоичных чисел в диапазоне байта в лоб.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963863
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
crutchmaster,

Ну... Я-же не создатель этого языка.

Terminal rule это чтото вроде условия выхода из рекурсии.

Часть алгоритмов без него обходятся. Ну и ладно.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963864
Фотография crutchmaster
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

А, дошло. Если оно срабатывает или достигнут конец списка, то всё заканчивается.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963883
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Swa111, спасибо. Посмотрю.

Но есть также онлайновые вычислители. Я находил несколько работающих в браузере.
И в Розетта-Код есть имплементации почти под все языки.

https://rosettacode.org/wiki/Execute_a_Markov_algorithm

Я думаю что надо собрать 1 бинарничек на сях под Windows и выложить сюда чтоб желающие пользовались.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963886
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Swa111, ты гитхабом пользуешся? Ну я имею в виду.. Учетная запись там есть? Свои репозитарии?
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963893
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Щас я расскажу свою идею. Вобщем я сложение заменил на инкремент.

Поскольку НАМ очень удобно дебажить. Весь state программы укладывается в 1 строчку
я просто покажу как я думал это решать. Пока без кода а в виде модификаций строки.


Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
# Наша исходная строка

|||||||||||||+|||||||

# Выкидываем знак плюс. Теперь число засечек уже равно сумме как в древних счётах.

||||||||||||||||||||

# Теперь нам нужен двоичный регистр сумматора. Я завожу два символа ^$ и между ними будет накапливаться 
# наш счетчик 

^$||||||||||||||||||||

# Далее. Тривиальные кейсы. Палочка транформируется сразу в двоичную единичку

^1$|||||||||||||||||||

Rules:
^$| -> ^1$

# Далее 1+1 = 2 мы фиксируем переполнение. Но перенесем чуть позже.

Rules:
^$| -> ^1$
1$| -> 2$

# Теперь перенос 2 в десятичной = 10 в двоичной

Rules:
^$| -> ^1$
1$| -> 2$
^2 -> ^10  # Это самый старший разряд
02 -> 10 # Это если двойка попалась в середине
12 -> 100 # Это если двойка попалась в середине 



Вот. Я это написал в уме сегодня ночью. И еще не проверял. Наверное там где-то есть зацикливание.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963898
Фотография crutchmaster
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

Мы сперва переводим бинарь в палочки, но как палочки перевести обратно в бинарь? Первый кусок кода его будет блокировать же.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963900
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
crutchmaster
mayton,

Мы сперва переводим бинарь в палочки, но как палочки перевести обратно в бинарь? Первый кусок кода его будет блокировать же.


Мммм.... чтоб рулы не пересекались - мы служебные символы можем ввести новые.

Например между первой и второй фазой делать

Код: sql
1.
| -> *



И дальше оперировать звездочками.

Мне символов не жалко.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963903
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Swa111, у меня твой алгоритм не сработал на вот этом эмуляторе http://www.cmcmsu.info/1course/alg.schema.nam.htm

Правильно ли я скопипастил?

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
*0= -> <*=0>
*1= -> <*=1>
0>0 -> 00>
0>1 -> 10>
1>0 -> 01>
1>1 -> 11>
00>e -> $e0
01>e -> $e1
10>e -> $e1
11>e -> ~$e0
=1>e -> =$e1
=0>e -> =$e0
1~ -> ~0
0~ -> 1
=~ -> =1
1$ -> $1
0$ -> $0
0<*=$ -> <*=0>
1<*=$ -> <*=1>
<*=$ -> 
e1 -> 1e
e0 -> 0e
e+ -> @e
@ -> <*=$
<*=$ -> 
e |-> 
-> e



В пошаговом режиме пишет Ни одно правило не применено, либо выполнено терминальное правило.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963919
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Мне символов не жалко.

Хотя да. Я думаю что Марков пожадничал. Надо было ввести в язык поняти стека и вызва процедуры или функции.
Но он наверное как и все теоретики просто что-то на бумаге хотел доказать. Типа равна ли эта хрень Машинке Тьюринга.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963944
Swa111
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
mayton,

да на гите я есть, но пользуюсь редко

на сайте не сработал наверное из за того что там ограничение на число правил, не более 20. Либо там другой синтаксис

Пошаговый расчет можно получить и в моем интерпретаторе, просто в образцах справа задай не верные результат, тогда выдаст пошаговое выполнение.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963947
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я возьму с розетты еще одну реализацию чтоб уже работала без ограничений.
Кстати это хорошо что ты добавил каменты в рулы. Я тоже расширю этот убогий
язык для такой возможности.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963990
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
палки в двоичную

0|| |0
0| 1
|| |0
| 1
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963993
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov,

спасибо Саш. Попробую.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964020
Фотография crutchmaster
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

Да дело не в *|, а в 1/0. Первая часть переводит из в палки, вторая из палок. После первого преобразования из палки в 1/0 число тут же станет палкой.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964031
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
crutchmaster,

замени палки на слеши
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964033
Фотография crutchmaster
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov,

И что?

:start
1->|
...
|->1 //goto :start

1/0 не на что заменить они должны быть в выхлопе.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964057
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
//правила
  ('+','<^>'),
  ('1<','<3'),
  ('0<','<2'),
  ('<',''),
  ('>1','3>'),
  ('>0','2>'),
  ('>',''),
  ('|2','2||'),
  ('3','2|'),
  ('2',''),
  ('^',''),
  ('0||','|0'),
  ('0|','1'),
  ('||','|0'),
  ('|','1')

//выхлоп
101+11
101<^>11
10<3^>11
1<23^>11
<323^>11
323^>11
323^3>1
323^33>
323^33
2|23^33
22||3^33
22||2|^33
22|2|||^33
222|||||^33
222|||||^2|3
222|||||^2|2|
222|||||^22|||
22|||||^22|||
2|||||^22|||
|||||^22|||
|||||^2|||
|||||^|||
||||||||
|0||||||
||0||||
|||0||
||||0
|0||0
||00
|000
1000
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964104
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Еще мысли. Утилитарные задачи. Не связанные с вычислениями а скорре так. Проблемы.

Например

1) Априорное знание алфавита. Если делать swap или движение какого-то символа в какую-то сторону
мы должны в левой части rules предусмотреть этот символ в сочетании со всеми возможными комбинациями.
Описать регулярку или мета-символ мы не можем. Господин Марков этого не предусмотрел. Следовательно
надо как-то опираться на область входных значений.

2) Утилитарные функции которые могут пригодится. Одну из них мы уже почти сделали. Это перевод
из двоички в унарность и обратно. Для комплекта хорошо-бы сделать тоже самое для десятичной.
Шестнадцатеричная из двоичной переводится тривиально. Плюс четыре базовых арифметических
операции.

Я думаю гуглёж всегда помогает - но прошу тех кто уже нагуглил - не спойлерите а дайте ребятам
возможность самим подумать. Я думаю 1-2 недели - это нормальный строк для этого топика.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964171
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

мое умножение и вычитание под спойлером, насчет деления не ясно, куда девать остаток

//умножение
('*','<^>'),
('1<','<3'),
('0<','<2'),
('<',''),
('>1','3>'),
('>0','2>'),
('>',''),
('|2','2||'),
('3','2|'),
('2',''),
('|^','^='),
('^',''),
('=|','|/='),
('=/','/='),
('|',''),
('=',''),
('0//','/0'),
('0/','1'),
('//','/0'),
('/','1')

//пример умножения
101*11
101<^>11
10<3^>11
1<23^>11
<323^>11
323^>11
323^3>1
323^33>
323^33
2|23^33
22||3^33
22||2|^33
22|2|||^33
222|||||^33
222|||||^2|3
222|||||^2|2|
222|||||^22|||
22|||||^22|||
2|||||^22|||
|||||^22|||
|||||^2|||
|||||^|||
||||^=|||
|||^==|||
||^===|||
|^====|||
^=====|||
=====|||
====|/=||
===|/=/=||
==|/=/=/=||
=|/=/=/=/=||
|/=/=/=/=/=||
|/=/=/=/=/|/=|
|/=/=/=/=/|/|/=
|//==/=/=/|/|/=
|//=/==/=/|/|/=
|///===/=/|/|/=
|///==/==/|/|/=
|///=/===/|/|/=
|////====/|/|/=
|////===/=|/|/=
|////===/|/=/|/=
|////==/=|/=/|/=
|////==/|/=/=/|/=
|////=/=|/=/=/|/=
|////=/|/=/=/=/|/=
|/////=|/=/=/=/|/=
|/////|/=/=/=/=/|/=
|/////|//==/=/=/|/=
|/////|//=/==/=/|/=
|/////|///===/=/|/=
|/////|///==/==/|/=
|/////|///=/===/|/=
|/////|////====/|/=
|/////|////===/=|/=
|/////|////===/|/=/=
|/////|////==/=|/=/=
|/////|////==/|/=/=/=
|/////|////=/=|/=/=/=
|/////|////=/|/=/=/=/=
|/////|/////=|/=/=/=/=
|/////|/////|/=/=/=/=/=
|/////|/////|//==/=/=/=
|/////|/////|//=/==/=/=
|/////|/////|///===/=/=
|/////|/////|///==/==/=
|/////|/////|///=/===/=
|/////|/////|////====/=
|/////|/////|////===/==
|/////|/////|////==/===
|/////|/////|////=/====
|/////|/////|/////=====
/////|/////|/////=====
//////////|/////=====
///////////////=====
///////////////====
///////////////===
///////////////==
///////////////=
///////////////
/0/////////////
//0///////////
///0/////////
////0///////
/////0/////
//////0///
///////0/
///////1
/0/////1
//0///1
///0/1
///11
/0/11
/111
1111


//вычитание
('-','<^>'),
('1<','<3'),
('0<','<2'),
('<',''),
('>1','3>'),
('>0','2>'),
('>',''),
('|2','2||'),
('3','2|'),
('2',''),
('|^|','^'),
('|^','|'),
('0||','|0'),
('0|','1'),
('||','|0'),
('|','1'),
('^1','.-1'), //точка означает терминальную операцию
('^','0')

//пример вычитания
101-111
101<^>111
10<3^>111
1<23^>111
<323^>111
323^>111
323^3>11
323^33>1
323^333>
323^333
2|23^333
22||3^333
22||2|^333
22|2|||^333
222|||||^333
222|||||^2|33
222|||||^2|2|3
222|||||^22|||3
222|||||^22|||2|
222|||||^22||2|||
222|||||^22|2|||||
222|||||^222|||||||
22|||||^222|||||||
2|||||^222|||||||
|||||^222|||||||
|||||^22|||||||
|||||^2|||||||
|||||^|||||||
||||^||||||
|||^|||||
||^||||
|^|||
^||
^|0
^10
-10
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964176
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov,

ого
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964195
Swa111
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Измененный алгоритм, число слагаемых может быть любым. На больших числах выигрывает по скорости счету на "счетных палочках".

Код: vbnet
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
'Закидываем сразу символ конца расчета за +
+ -> ?e

'Двигаем очередной знак вправо
0>0 -> 00>
0>1 -> 10>
1>0 -> 01>
1>1 -> 11>

'выполняем сложение
00>e -> $e0
01>e -> $e1
10>e -> $e1
11>e -> ~$e0

#1>e -> #$e1
#0>e -> #$e0

'Увеличиваем правую часть при переполнении
1~ -> ~0
0~ -> 1
#~ -> #1

'Сложение завершено идем за следующим знаком
1$ -> $1
0$ -> $0

'Забираем очередной знак
0#$ -> #0>
1#$ -> #1>

#$e |-> 

e#$ -> #$

'правая часть больше левой 
#$ -> 

'Двигаем символ конца расчетов
e1 -> 1e
e0 -> 0e

'Символ конца на месте, начинаем счет
? -> #$

'Конец
e |-> 



Пример 1+11+100+10 ==> 1010

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
+ -> ?e      : 1?e11+100+10
+ -> ?e      : 1?e11?e100+10
+ -> ?e      : 1?e11?e100?e10
e1 -> 1e     : 1?1e1?e100?e10
e1 -> 1e     : 1?11e?e100?e10
e1 -> 1e     : 1?11e?1e00?e10
e1 -> 1e     : 1?11e?1e00?1e0
e0 -> 0e     : 1?11e?10e0?1e0
e0 -> 0e     : 1?11e?100e?1e0
e0 -> 0e     : 1?11e?100e?10e
? -> #$      : 1#$11e?100e?10e
1#$ -> #1>   : #1>11e?100e?10e
1>1 -> 11>   : #11>1e?100e?10e
1>1 -> 11>   : #111>e?100e?10e
11>e -> ~$e0 : #1~$e0?100e?10e
1~ -> ~0     : #~0$e0?100e?10e
#~ -> #1     : #10$e0?100e?10e
0$ -> $0     : #1$0e0?100e?10e
1$ -> $1     : #$10e0?100e?10e
#$ ->        : 10e0?100e?10e
e0 -> 0e     : 100e?100e?10e
? -> #$      : 100e#$100e?10e
e#$ -> #$    : 100#$100e?10e
0#$ -> #0>   : 10#0>100e?10e
0>1 -> 10>   : 10#10>00e?10e
0>0 -> 00>   : 10#100>0e?10e
0>0 -> 00>   : 10#1000>e?10e
00>e -> $e0  : 10#10$e0?10e
0$ -> $0     : 10#1$0e0?10e
1$ -> $1     : 10#$10e0?10e
0#$ -> #0>   : 1#0>10e0?10e
0>1 -> 10>   : 1#10>0e0?10e
0>0 -> 00>   : 1#100>e0?10e
00>e -> $e0  : 1#1$e00?10e
1$ -> $1     : 1#$1e00?10e
1#$ -> #1>   : #1>1e00?10e
1>1 -> 11>   : #11>e00?10e
11>e -> ~$e0 : #~$e000?10e
#~ -> #1     : #1$e000?10e
1$ -> $1     : #$1e000?10e
#$ ->        : 1e000?10e
e0 -> 0e     : 10e00?10e
e0 -> 0e     : 100e0?10e
e0 -> 0e     : 1000e?10e
? -> #$      : 1000e#$10e
e#$ -> #$    : 1000#$10e
0#$ -> #0>   : 100#0>10e
0>1 -> 10>   : 100#10>0e
0>0 -> 00>   : 100#100>e
00>e -> $e0  : 100#1$e0
1$ -> $1     : 100#$1e0
0#$ -> #0>   : 10#0>1e0
0>1 -> 10>   : 10#10>e0
10>e -> $e1  : 10#$e10
0#$ -> #0>   : 1#0>e10
#0>e -> #$e0 : 1#$e010
1#$ -> #1>   : #1>e010
#1>e -> #$e1 : #$e1010
#$e ->       : 1010


110101+110 ==> 111011
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
+ -> ?e      : 110101?e110
e1 -> 1e     : 110101?1e10
e1 -> 1e     : 110101?11e0
e0 -> 0e     : 110101?110e
? -> #$      : 110101#$110e
1#$ -> #1>   : 11010#1>110e
1>1 -> 11>   : 11010#11>10e
1>1 -> 11>   : 11010#111>0e
1>0 -> 01>   : 11010#1101>e
01>e -> $e1  : 11010#11$e1
1$ -> $1     : 11010#1$1e1
1$ -> $1     : 11010#$11e1
0#$ -> #0>   : 1101#0>11e1
0>1 -> 10>   : 1101#10>1e1
0>1 -> 10>   : 1101#110>e1
10>e -> $e1  : 1101#1$e11
1$ -> $1     : 1101#$1e11
1#$ -> #1>   : 110#1>1e11
1>1 -> 11>   : 110#11>e11
11>e -> ~$e0 : 110#~$e011
#~ -> #1     : 110#1$e011
1$ -> $1     : 110#$1e011
0#$ -> #0>   : 11#0>1e011
0>1 -> 10>   : 11#10>e011
10>e -> $e1  : 11#$e1011
1#$ -> #1>   : 1#1>e1011
#1>e -> #$e1 : 1#$e11011
1#$ -> #1>   : #1>e11011
#1>e -> #$e1 : #$e111011
#$e ->       : 111011
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964209
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
101*11
101<^>11
10<3^>11
1<23^>11
<323^>11
323^>11
323^3>1
323^33>
323^33




Хм.. Это преобразование со стороны выглядит странно. Оно как будто-бы ничего не делает. Просто заменяет
одни цифры на другие. И знак * наверное можно было сохранить.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964215
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Aleksandr Sharahov

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
101*11
101<^>11
10<3^>11
1<23^>11
<323^>11
323^>11
323^3>1
323^33>
323^33




Хм.. Это преобразование со стороны выглядит странно. Оно как будто-бы ничего не делает. Просто заменяет
одни цифры на другие. И знак * наверное можно было сохранить.


Дык это легко поверить, достаточно убрать "ненужное" )
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964217
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Swa111,

правильно ли я понял, что в твоей реализации
количество правил зависит от количества бит в наибольшем слагаемом?
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964222
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov
mayton
пропущено...


Хм.. Это преобразование со стороны выглядит странно. Оно как будто-бы ничего не делает. Просто заменяет
одни цифры на другие. И знак * наверное можно было сохранить.


Дык это легко поверить, достаточно убрать "ненужное" )

Нет. Я понимаю что мы подготавливаем почву для других расчетов. Но если у нас будет 20 расчетов - нужно-ли
нам 20 алфавитов или хватит двух? По очереди менять "01" <=> "23".
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964232
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Aleksandr Sharahov
пропущено...


Дык это легко поверить, достаточно убрать "ненужное" )

Нет. Я понимаю что мы подготавливаем почву для других расчетов. Но если у нас будет 20 расчетов - нужно-ли
нам 20 алфавитов или хватит двух? По очереди менять "01" <=> "23".


Ну, мне так проще конструировать алгоритм:
мы таким образом гарантируем, что входные символы не пересекаются с выходными,
и, тем самым, при формировании результата не будет срабатываний замен из начала списка,
которые испортят всю малину.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964237
Swa111
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Aleksandr Sharahov,

Нет, число правил одинаковое для чисел любой разрядности.

Алгоритм умножения чисел в столбик. Отчасти полагается на предыдущий алгоритм сложения нескольких чисел.
всего за каких то 9949 замен может перемножить числа 1000100111111000 на 1000110101111101
Код: vbnet
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
* -> ME

'E всегда идет в конце слова
E0 -> 0E
E1 -> 1E
'где потом мельчает
E -> e

'Гонцы тоже идут в конец слова
p0 -> 0p
p1 -> 1p
P0 -> 0P
P1 -> 1P

'Мутация гонца
1Pe -> |c1e1eA
0Pe -> |c0e0eA

'грузчик тащит копию цифры на право
1|c -> |11g
0|c -> |00g

0g0 -> 00g
0g1 -> 10g
1g0 -> 01g
1g1 -> 11g

'Сбрасывает свою цыфру и идет за следующей
0ge -> ce0
1ge -> ce1
0c -> c0
1c -> c1

'передает следующему
m|c -> mp

'Гонцы
'Умножить число слева на 2
0M -> mp
1M -> mP

'Умножение на 2
pe -> w0e

'Умножитель возвращается обратно
0w -> w0
1w -> w1
mw -> M

'Стираем последнее слагаемое оно больше не нужно
q1 -> q
q0 -> q
qe -> 
M -> q


'Двигаем очередной знак вправо для сложения
0>0 -> 00>
0>1 -> 10>
1>0 -> 01>
1>1 -> 11>

'выполняем сложение
00>e -> $e0
01>e -> $e1
10>e -> $e1
11>e -> ~$e0

A1>e -> A$e1
A0>e -> A$e0

'Увеличиваем правую часть при переполнении
1~ -> ~0
0~ -> 1
A~ -> A1

'Сложение завершено идем за следующим знаком
1$ -> $1
0$ -> $0


'Забираем очередной знак
0A$ -> A0>
1A$ -> A1>


'Набор правил что бы подчистить за собой
A$e0 -> A$e
A$e -> 
eA$ -> A
A1> -> 1
A0> -> 0
A -> A$



Обновил интерпретатор, исправлена ошибка с зависанием если ни одно правило не сработало.
Добавлено:
  • вывод статистики: шагов / замен.
  • "говорливый" режим выполнения, когда каждый шаг выводится в консоль
  • поддержка комментариев с символа #.
  • вывод правил, которые ни разу не использовались.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964249
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
незамутненное преобразованиями систем счисления деление на палках
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
//деление 
  ('>|',  '|>'),
  ('>/',  '|-='),
  ('=|',  'i|='),
  ('=#',  '#|'),
  ('=',   '#|'),
  ('|i',  'i|'),
  ('|-i', '-'),
  ('|-|', '|-=|'),
  ('-|',  '-'),
  ('-i',  '-'),
  ('-#||', '.|'), //exit
  ('-#|',  '.0'), //exit
  ('',    '>')

//делим 7 на 3
|||||||/|||
>|||||||/|||
|>||||||/|||
||>|||||/|||
|||>||||/|||
||||>|||/|||
|||||>||/|||
||||||>|/|||
|||||||>/|||
||||||||-=|||
||||||||-i|=||
||||||||-i|i|=|
||||||||-i|i|i|=
||||||||-i|i|i|#|
||||||||-ii||i|#|
||||||||-ii|i||#|
||||||||-iii|||#|
|||||||-ii|||#|
||||||-i|||#|
|||||-|||#|
|||||-=|||#|
|||||-i|=||#|
|||||-i|i|=|#|
|||||-i|i|i|=#|
|||||-i|i|i|#||
|||||-ii||i|#||
|||||-ii|i||#||
|||||-iii|||#||
||||-ii|||#||
|||-i|||#||
||-|||#||
||-=|||#||
||-i|=||#||
||-i|i|=|#||
||-i|i|i|=#||
||-i|i|i|#|||
||-ii||i|#|||
||-ii|i||#|||
||-iii|||#|||
|-ii|||#|||
-i|||#|||
-|||#|||
-||#|||
-|#|||
-#|||
||

...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964254
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
немного сократил
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
//деление 
  ('/',   '|-='),
  ('=|',  'i|='),
  ('=#',  '#|'),
  ('=',   '#'),
  ('|i',  'i|'),
  ('|-i', '-'),
  ('|-|', '|-=|'),
  ('-|',  '-'),
  ('-i',  '-'),
  ('-#|', '|'),
  ('-#',  '0')

...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964261
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Но если у нас будет 20 расчетов - нужно-ли
нам 20 алфавитов или хватит двух? По очереди менять "01" <=> "23".


Кстати, легко доказать, что
если существуют НАМы для нескольких функций,
то существует НАМ для их суперпозиции.

Поэтому достаточно реализовать НАМы для унарной системы счисления,
т.к. у нас есть функции перевода в нее и обратно.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964264
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Унарное вычитание
Код: sql
1.
2.
1-1 -> -
- -> 



Input: 11111-111

Output: 11
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964267
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov
mayton
Но если у нас будет 20 расчетов - нужно-ли
нам 20 алфавитов или хватит двух? По очереди менять "01" <=> "23".


Кстати, легко доказать, что
если существуют НАМы для нескольких функций,
то существует НАМ для их суперпозиции.

Поэтому достаточно реализовать НАМы для унарной системы счисления,
т.к. у нас есть функции перевода в нее и обратно.


Я вот щас какраз думаю над композицией функций. У нас есть универсальный
аппарат. И есть уже кодовая база.

В функциональщине есть такая штука если есть f(x), g(x) функции то
f(g(x)) это некая новая функция которая последовательно применяет g а потом f.

Если бы не было терминального оператора |-> то мы могли-бы просто
копи-пастой формировать композиции алгоритмов Маркова просто
как плоский текст.

И если-бы не было пересечений алфавитов левых выражений rules.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964269
Swa111
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
перевод из десятичной в унарную

Код: vbnet
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
r1e -> ei
r0e -> eo

E0 -> 0E
E1 -> 1E
E2 -> 2E
E3 -> 3E
E4 -> 4E
E5 -> 5E
E6 -> 6E
E7 -> 7E
E8 -> 8E
E9 -> 9E

E -> e$

r00 -> 0r0
r01 -> 0r1
r0 -> r
r2 -> 1r0
r3 -> 1r1
r4 -> 2r0
r5 -> 2r1
r6 -> 3r0
r7 -> 3r1
r8 -> 4r0
r9 -> 4r1
r10 -> 5r0
r11 -> 5r1
r12 -> 6r0
r13 -> 6r1
r14 -> 7r0
r15 -> 7r1
r16 -> 8r0
r17 -> 8r1
r18 -> 9r0
r19 -> 9r1

G0e -> o
G1e -> i
G2 -> G1r0
G3 -> G1r1
G4 -> G2r0
G5 -> G2r1
G6 -> G3r0
G7 -> G3r1
G8 -> G4r0
G9 -> G4r1
G10 -> G5r0
G11 -> G5r1
G12 -> G6r0
G13 -> G6r1
G14 -> G7r0
G15 -> G7r1
G16 -> G8r0
G17 -> G8r1
G18 -> G9r0
G19 -> G9r1

i -> o|
|o -> o||
o -> 

$ |-> 

 -> GE



...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964275
Swa111
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Aleksandr Sharahov,

в делении наверное это правило лишнее
Код: plaintext
 ('-#',  '0')
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964280
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Swa111
Aleksandr Sharahov,

в делении наверное это правило лишнее
Код: plaintext
 ('-#',  '0')


так сделано по двум причинам:
1. для отладки, чтобы видеть пустой результат в мемо
2. для упрощения перевода результата в двоичную

если не требуется ни то, ни другое, то две последних строки можно заменить одной
('-#', '')
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964283
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Swa111
перевод из десятичной в унарную


а мы не гонимся за скоростью )
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
  ('|0','0||||||||||'),
  ('1', '0|'),
  ('2', '0||'),
  ('3', '0|||'),
  ('4', '0||||'),
  ('5', '0|||||'),
  ('6', '0||||||'),
  ('7', '0|||||||'),
  ('8', '0||||||||'),
  ('9', '0|||||||||'),
  ('0', '')

...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964289
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
в десятичную
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
  
  ('#9|', '#10'),
  ('9|',  '|0'),
  ('8|',  '9'),
  ('7|',  '8'),
  ('6|',  '7'),
  ('5|',  '6'),
  ('4|',  '5'),
  ('3|',  '4'),
  ('2|',  '3'),
  ('1|',  '2'),
  ('0|',  '1'),
  ('#',   '.'), //exit
  ('',    '#0')

...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964298
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
пусть дано: "1111+111"

решение:
1) преобразовываем строку на входе к виду #00#10#11#11#11#
2) далее на преобразованной строке применяем правила
"00" -> "0"
"01" -> "1"
"10" -> "1"
"#0#11#" -> "#1#0#"
"#1#11#" -> "#11#0#"

если не получилось применить ни одного из правил, то выходим из цикла

3) стираем "#" и получаем результат
10110
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964311
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mini.weblab,

Это что? Сложение в четверичной системе?

Мне кажется - первый шаг слабо обоснован.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964319
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov
Swa111
перевод из десятичной в унарную


а мы не гонимся за скоростью )
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
  ('|0','0||||||||||'),
  ('1', '0|'),
  ('2', '0||'),
  ('3', '0|||'),
  ('4', '0||||'),
  ('5', '0|||||'),
  ('6', '0||||||'),
  ('7', '0|||||||'),
  ('8', '0||||||||'),
  ('9', '0|||||||||'),
  ('0', '')


Это шикарно
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964321
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mini.weblab
пусть дано: "1111+111"

решение:
1) преобразовываем строку на входе к виду #00#10#11#11#11#
2) далее на преобразованной строке применяем правила
"00" -> "0"
"01" -> "1"
"10" -> "1"
"#0#11#" -> "#1#0#"
"#1#11#" -> "#11#0#"

если не получилось применить ни одного из правил, то выходим из цикла

3) стираем "#" и получаем результат
10110


непосредственное сложение в двоичной системе достаточно очевидно,
но реализаций могут быть десятки,
вот, например, моя реализация
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
//двоичное сложение
  ('+',   '^>'),
  ('>0',  '0>'),
  ('>1',  '1>'),
  ('>',   '#'),
  ('o#',  '#0'),
  ('o0#', '#0'),
  ('o1#', '#1'),
  ('o0',  '0o'),
  ('o1',  '1o'),
  ('i#',  '#1'),
  ('i0#', '#1'),
  ('i1#', '#2'),
  ('i0',  '0i'),
  ('i1',  '1i'),
  ('0^',  '^o'),
  ('1^',  '^i'),
  ('#', ''),
  ('02',  '10'),
  ('12',  '20'),
  ('^2',  '10'),
  ('^', '')

//пример
11+1010
11^>1010
11^1>010
11^10>10
11^101>0
11^1010>
11^1010#
1^i1010#
1^1i010#
1^10i10#
1^101i0#
1^101#1
^i101#1
^1i01#1
^10i1#1
^10#21
^1021
^1101
1101

...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964337
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Из всех систем счисления - десятичная самая неудобная для этих операций.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964339
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Саша как тебе такая идея?

Код: sql
1.
2.
3.
4.
5.
F = 8 + 8
8 = 4 + 4
4 = 2 + 2
2 = 1 + 1 = | + | = ||
1 = |
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964343
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Саша как тебе такая идея?

Код: sql
1.
2.
3.
4.
5.
F = 8 + 8
8 = 4 + 4
4 = 2 + 2
2 = 1 + 1 = | + | = ||
1 = |



идея применительно к чему?
а то у нас уже тут до фига всего.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964344
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Мне почему-то всмомнилась идея Египетского Умножения.

Тоесть взять любую систему счисления. И заменить умножение
сложением. С небольшим числом слагаемых.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964345
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Например (в десятичной)

731 * 13 = 731 * (1 + 4 + 8) = 731 + (( 731 + 731 ) + ( 731 + 731 )) + .... и т.д.

Получается как-бы такое бинарное дерево сложений. И здесь 4 * 731 разваливается на две частичные слагаемые
которые в императивных языках хорошо оптимизируются.

Вобщем в императивных языках у нас будет не 13 сложений а нечто логарифмическое.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964404
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Сделал двоичное умножение, вышло достаточно быстро:
1000100111111000*1000110101111101 = 5190 замен
1000110101111101*1000100111111000 = 6006 замен

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
//двоичное умножение
  '*',   '^>',
  '>0',  '0>',
  '>1',  '1>',
  '>',   '+0#',
  '^0',  '^',
  'o0',  '0o',
  'o1',  '1o',
  'o+',  '0+',
  'i0',  '0i',
  'i1',  '1i',
  'i+',  '<0+',
  'z0#', '=0#',
  'z1#', '=1#',
  'z=',  '=0',
  'z0=', '=0',
  'z1=', '=1',
  'z0',  '0z',
  'z1',  '1z',
  'j0#', '=1#',
  'j1#', '=2#',
  'j=',  '=1',
  'j0=', '=1',
  'j1=', '=2',
  'j0',  '0j',
  'j1',  '1j',
  'O0',  '0O',
  'O1',  '1O',
  'O+',  '+z',
  'I0',  '0I',
  'I1',  '1I',
  'I+',  '+j',
  '0<',  '<0O',
  '1<',  '<1I',
  '0^<',  '0^',
  '1^<',  '1^',
  '=',   '',
  '02',  '10',
  '12',  '20',
  '+2',  '+10',
  'x0',  'x',
  'x1',  'x',
  'x+',  '',
  '0^',  '^o',
  '1^',  '^i',
  '^<',  'x',
  '^',   'x',
  '#',   ''

//двоичное умножение, пример
       шаг  прав  формула
         0    -1  11*11
         1     0  11^>11
         2     2  11^1>1
         3     2  11^11>
         4     3  11^11+0#
         5    43  1^i11+0#
         6     9  1^1i1+0#
         7     9  1^11i+0#
         8    10  1^11<0+0#
         9    32  1^1<1I0+0#
        10    28  1^1<10I+0#
        11    30  1^1<10+j0#
        12    18  1^1<10+=1#
        13    32  1^<1I10+=1#
        14    29  1^<11I0+=1#
        15    28  1^<110I+=1#
        16    30  1^<110+j=1#
        17    20  1^<110+=11#
        18    34  1^110+=11#
        19    35  1^110+11#
        20    43  ^i110+11#
        21     9  ^1i10+11#
        22     9  ^11i0+11#
        23     8  ^110i+11#
        24    10  ^110<0+11#
        25    31  ^11<0O0+11#
        26    25  ^11<00O+11#
        27    27  ^11<00+z11#
        28    17  ^11<00+1z1#
        29    12  ^11<00+1=1#
        30    32  ^1<1I00+1=1#
        31    28  ^1<10I0+1=1#
        32    28  ^1<100I+1=1#
        33    30  ^1<100+j1=1#
        34    22  ^1<100+=21#
        35    32  ^<1I100+=21#
        36    29  ^<11I00+=21#
        37    28  ^<110I0+=21#
        38    28  ^<1100I+=21#
        39    30  ^<1100+j=21#
        40    20  ^<1100+=121#
        41    35  ^<1100+121#
        42    37  ^<1100+201#
        43    38  ^<1100+1001#
        44    44  x1100+1001#
        45    40  x100+1001#
        46    40  x00+1001#
        47    39  x0+1001#
        48    39  x+1001#
        49    41  1001#
        50    46  1001

//статистика
количество  прав    замена
         1     0     *  ^>
         0     1    >0  0>
         2     2    >1  1>
         1     3     >  +0#
         0     4    ^0  ^
         0     5    o0  0o
         0     6    o1  1o
         0     7    o+  0+
         1     8    i0  0i
         4     9    i1  1i
         2    10    i+  <0+
         0    11   z0#  =0#
         1    12   z1#  =1#
         0    13    z=  =0
         0    14   z0=  =0
         0    15   z1=  =1
         0    16    z0  0z
         1    17    z1  1z
         1    18   j0#  =1#
         0    19   j1#  =2#
         2    20    j=  =1
         0    21   j0=  =1
         1    22   j1=  =2
         0    23    j0  0j
         0    24    j1  1j
         1    25    O0  0O
         0    26    O1  1O
         1    27    O+  +z
         6    28    I0  0I
         2    29    I1  1I
         4    30    I+  +j
         1    31    0<  <0O
         4    32    1<  <1I
         0    33   0^<  0^
         1    34   1^<  1^
         2    35     =  
         0    36    02  10
         1    37    12  20
         1    38    +2  +10
         2    39    x0  x
         2    40    x1  x
         1    41    x+  
         0    42    0^  ^o
         2    43    1^  ^i
         1    44    ^<  x
         0    45     ^  x
         1    46     #  

...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964407
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Например (в десятичной)

731 * 13 = 731 * (1 + 4 + 8) = 731 + (( 731 + 731 ) + ( 731 + 731 )) + .... и т.д.

Получается как-бы такое бинарное дерево сложений. И здесь 4 * 731 разваливается на две частичные слагаемые
которые в императивных языках хорошо оптимизируются.

Вобщем в императивных языках у нас будет не 13 сложений а нечто логарифмическое.


для двоичной системы как раз и получится умножение в столбик
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964412
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Практическое применение алгоритма Маркова: сложение в столбик
Code link:
https://repl.it/repls/RepulsiveRowdyCareware
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964414
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mini.weblab,

Во-первых, там не умножение, а сложение.
Во-вторых, совсем не по Маркову.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964418
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov,
сложение поправила :)
при умножении в столбик применяется алгоритм Маркова
и при записи арифметических действий в строку тоже можно применить этот алгоритм
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964419
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mini.weblab
Aleksandr Sharahov,
сложение поправила :)
при умножении в столбик применяется алгоритм Маркова
и при записи арифметических действий в строку тоже можно применить этот алгоритм


Перенос переполнения в старший разряд - он не Марковский, а общечеловеческий )
Марковость - это (то, чего там вовсе нет):
1. задать таблицу замен,
2. взять строку с исходной формулой,
3. по Марковкому алгоритму применять замены к формуле до тех пор, пока алгоритм не остановится.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964420
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mini.weblab
Aleksandr Sharahov,
сложение поправила :)
при умножении в столбик применяется алгоритм Маркова
и при записи арифметических действий в строку тоже можно применить этот алгоритм

Как-то... переусложнено всё. Ты-же понимаешь что НАМ - это чистейшая теория.
Мозговой эксперимент. И если ты вводишь императивный язык как подпорку или
костыль что-бы НАМ улучшить то это уже совсем другой метод.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964436
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ммм... нет, я перехожу от абстракции к конкретному примеру,
и дальше показываю, что умножение в столбик тоже относится к группе алгоритмов Маркова
для этого я переписываю начальную строку, так, как мне нужно для примера, и применяю серию правил (их у меня 5)
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964446
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mini.weblab
ммм... нет, я перехожу от абстракции к конкретному примеру,
и дальше показываю, что умножение в столбик тоже относится к группе алгоритмов Маркова
для этого я переписываю начальную строку, так, как мне нужно для примера, и применяю серию правил (их у меня 5)


Давай, рассмотрим сложение двоичных чисел на примере выражения '101+11'.

Какие правила нам надо применить, чтобы последовательными
преобразованиями исходного выражения получить результирующую строку '1000' ?
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964450
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov,
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
Input string: #00#10#01#11#
00->0: #0#10#01#11#
01->1: #0#10#1#11#
10->1: #0#1#1#11#
#1#11#->#11#0#: #0#1#11#0#
#1#11#->#11#0#: #0#11#0#0#
#0#11#->#1#0#: #1#0#0#0#
Exit string: #1#0#0#0#
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964452
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mini.weblab
Aleksandr Sharahov,
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
Input string: #00#10#01#11#
00->0: #0#10#01#11#
01->1: #0#10#1#11#
10->1: #0#1#1#11#
#1#11#->#11#0#: #0#1#11#0#
#1#11#->#11#0#: #0#11#0#0#
#0#11#->#1#0#: #1#0#0#0#
Exit string: #1#0#0#0#


Давай разбираться с самого начала.
Откуда взялось это выражение '#00#10#01#11#' ?
Какое правило было применено к исходному выражению '101+11' ?
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964461
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov,

мы решаем разные задачи, в самом первом посте, я сказала, что покажу, что сложение в столбик выполняется по алгоритму Маркова.
и дальше просто идет proof of concept. :-)
я хочу сказать, а почему бы не посмотреть на проблему под другим углом. :-)
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964465
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mini.weblab
Aleksandr Sharahov,

мы решаем разные задачи, в самом первом посте, я сказала, что покажу, что сложение в столбик выполняется по алгоритму Маркова.
и дальше просто идет proof of concept. :-)
я хочу сказать, а почему бы не посмотреть на проблему под другим углом. :-)


Если смотреть под другим углом, то сложение в столбик выполняется как обычно, побитовым сложением с учетом переноса.

От того, что некоторые правила записаны стрелочками, весь алгоритм сложения не становится Марковским,
т.к. не соблюдены *все* необходимые требования.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964496
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov
м,
т.к. не соблюдены *все* необходимые требования.

1) и какие же требования не соблюдены?
а) строка есть
б) правила есть
в) все шаги алгоритма выполнены
г) конечный ответ получен
2) сложение в столбик может быть приведено к Марковскому алгоритму, нужно лишь записать строку нужным нам образом
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964519
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov,
я знаю, что решетки # это чит, но идея состоит в том, чтобы воспроизвести сложение в столбик
:-)

PS
а если число преобразовывать, и решетки убирать, то остаются 2 правила (как в твоем решении)
12->20
02->10

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
111111 + 111
0111222

12->20: 0112022
02->10: 0112102
02->10: 0112110
12->20: 0120110
12->20: 0200110
02->10: 1000110

Res: 1000110
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964525
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mini.weblab
Aleksandr Sharahov,
я знаю, что решетки # это чит, но идея состоит в том, чтобы воспроизвести сложение в столбик
:-)

PS
а если число преобразовывать, и решетки убирать, то остаются 2 правила (как в твоем решении)
12->20
02->10

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
111111 + 111
0111222

12->20: 0112022
02->10: 0112102
02->10: 0112110
12->20: 0120110
12->20: 0200110
02->10: 1000110


Res: 1000110


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

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

Речь о том, что этого всего не хватает.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964530
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov,

я знаю, что формально для решения задачи as is этого не хватает, но у меня были другие цели
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964550
Swa111
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
более шустрый алгоритм сложения и умножения в столбик

1000100111111000*1000110101111101 = 4049 замен
1000110101111101*1000100111111000 = 4386 замен

Код: vbnet
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
0t10 -> 100t
0t1 -> 10t
1g00 -> 001g
0g1 -> 10g
1g1 -> 11g
E1 -> 1E
E0 -> 0E
E -> e
s0t0t -> 00
s1t0t -> 10
1t0 -> 01t
s1t1t -> 11
1t1 -> 11t
c0 -> 0c
1g0 -> 01g
0g0000 -> 00000g
0gDe -> De0
00teS -> e0eS
00te -> e0
10teS -> e1eS
10te -> e1
11te -> ~e0
0t0000 -> 00000t
0t00 -> 000t
d0 -> 0d
0t0 -> 00t
0g00 -> 000g
0g0 -> 00g
c1 -> 1c
1gDe -> De1
0p -> p00g
1p -> p11g
d1 -> 1d
1~ -> ~0
m0 -> m
01te -> e1
0~ -> 1
s~ -> s1
D -> 0
p -> 
0ce -> p0De0eS
de -> 0e
1ce -> p1De1eS
1m -> mc
0m -> md
m1 -> m
se -> 
0s -> s0t
1s -> s1t
0eS -> s0t
me -> 
s1e -> 1
1* -> mcE
0+ -> s0tE
1+ -> s1tE
0* -> mdE
s1 -> 1
1eS -> s1t
e -> 
s0 -> s


В интерпретатор добавлен оптимизатор порядка правил. Для этого в командной строке запустите с ключам /o и /s или используйте DropAtMe(Opt).bat.
В файле все образцы должны быть с верными эталонными значениями. Образцы нужно подобрать таким образом что бы использовались все правила. Оптимизатор только переставляет правила местами для того что бы уменьшить число итераций (не замен). Если перестановка увеличила число шагов или какой либо из образцов перестал быть равным эталону то она отклоняется.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964559
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
а почему бы не сделать так:
алфавит 0,1,+
Правило:
a+b -> f(a,b)

разве это противоречило бы правилам алгоритма?
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964570
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mini.weblab
а почему бы не сделать так:
алфавит 0,1,+
Правило:
a+b -> f(a,b)

разве это противоречило бы правилам алгоритма?


Это противоречит определению НАМ:

1. НАМ - это упорядоченный набор строковых замен (некоторые замены могут иметь флаг останова).

2. НАМ начинает работу с единственной входной строки, последовательно выполняя шаги.

3. На очередном шаге НАМ просматривает список замен с самого начала и выполняет первую подходящую замену.
При этом замена в текущей строке выполняется 1 раз для первого подходящего фрагмента строки.

4. НАМ останавливается, если на очередном шаге не найдена подходящая замена
или если выполненная замена имела флаг останова.

5. Результатом работы НАМ является текущая строка в момент прекращения его работы.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964572
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mini.weblab,

поэтому когда вас просят разработать НАМ для сложения чисел в двоичной записи,
это означает, что нужно просто указать список замен.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964575
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mini.weblab
а почему бы не сделать так:
алфавит 0,1,+
Правило:
a+b -> f(a,b)

разве это противоречило бы правилам алгоритма?

Давай мы этот вопрос адресуем новому топику который ты сама создашь.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964634
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Swa111,

правильно ли я понял, что последний более быстрый вариант реализации бинарного умножения
отличается от предыдущего перестановкой замен и добавлением ускорителей, например:
0g0000 -> 00000g
0g00 -> 000g
0g0 -> 00g


P.S.
НАМы и без оптимизаций довольно трудны для понимания,
а после перестановок и вовсе теряют читаемость,
поэтому, проявляя заботу о читателях,
хочется попросить наряду с оптимизированной версией
также публиковать неоптимизированную версию алгоритма.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964668
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,
нет, спасибо, думаю, не стоит
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964713
Swa111
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Aleksandr Sharahov,

Да весь выигрыш как раз в ускорителях. При этом если считать именно число шагов по правилам то реальную помощь дает только
0t00 -> 000t.

Остальные хоть и уменьшают число замен, но увеличивают число итераций
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964719
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Беря во внимание сугубую ДОКАЗАТЕЛЬНУЮ теоретичность НАМ, я-бы предложил писать чисто-рафинированные
алгоритмы без оптимизаций. Оптимизации всегда можно предложить потом. Ценой какой-то потери читабельности.

Мне нравится вариант когда мы например "сложение" просто заменяем инкрементом с рекурсивным условием.
Это - в духе функциональщины.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964732
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Следующий вопрос.

Можем-ли мы реализовать ПОЛИЗ.

Пример:

Input:
Код: sql
1.
sqrt(7 * (3 + 1))



Output
Код: sql
1.
7 3 1 + * sqrt




При этом понимаем что плюс и минус - бинарная функция а квадратный корень - унарная.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964734
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Еще вопрос.

Можем-ли мы реализовать общий случай генерации перестановок (combinations) для любого числа символов?

Input:
Код: sql
1.
123



Output:
Код: sql
1.
2.
3.
4.
5.
6.
123
132
213
231
312
321
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964739
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

это не просто "в духе", все эти папагиглеммы и есть существо функциональщины,
доказывающее, что все, что может быть вычислено, вычислимо иммутабельным образом,
если замену видеть как атомарную операцию.
Алгорифм бежит только вперед.
А то, что обычно алгоритмом называется, представлено списком замен, которые, в обычном понимании, просто "данные".
Попом на этом сидит вся функциональщина, одновременно с декларативными прологами и последователями.
Подставив еще одну замену ты внедряешь еще одну первоклассную функцию, по сути.
Я никогда не влезал в эту тему, а на беглый взгляд вот такой вопрос заинтересовал:
В классике алгорифмы статичны в отношении списка используемых правил.
Исследовал ли кто-нибудь, и как назвал, подобные конструкции с динамически изменяемым в процессе работы алгорифма списком правил.
Есть для такого случая формализьма...
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964746
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
booby

В классике алгорифмы статичны в отношении списка используемых правил.
Исследовал ли кто-нибудь, и как назвал, подобные конструкции с динамически изменяемым в процессе работы алгорифма списком правил.
Есть для такого случая формализьма...

Я на самом деле хотел еще сильнее усугубить вопрос формализма НАМ.

Лет 15 назад мне попала в руки Книга Душкина. И она (честно говоря) надолго отбила у меня желание
изучать ФП и Хаскель в том числе. Книга - изобиловала отсылкой к математике. Ну чтобы понять сравнение
это как полезность Дональда Кнута в изучении С++. Вроде и надо. И в тоже время старина Кнут затягивает
тебя как воронка в очень занудные исследования непонятных сущностей как то машина MIX, ленточные
сортировки, и прочие абстракции которые современному разработчику вобщем не нужны. Их просто негде
применить. А если кто-то ищет другой порог вхождения то он его 100% найдет. И это будет не Кнут.

Слава богу мой хороший наставник Саша Немиш и и коммитер в Хаскель сообщество Виталий Брагилевский
немного освежили во мне желание снова посмотреть на этот язык. Я вобщем не планирую особо на нем кодить.
Нет заказов вообще. Но его изучать полезно чтобы просто понять - а зачем собсно в Scala вводили ту или иную
метафору или зачем например Java нужны streams с искусственными ограничителям.

Так вот. В главе 5.1 Основы комбинаторной логики (КЛ) Душкин приводит комбинаторы тождества (I),
канцелятор (K), коннектор (S), композитор (B), пермутатор (С) и дубликатор (W). Меня это заинтересовало.
К сожелению Душкинские примеры с неподвижной точкой и играми с базисами были для меня непонятны
с практической стороны. Я искал за что зацепиться с практики. Не смог.

И данный топик является просто пред-течей или преамбулой для другого топика который я просто обдумываю.
Обычно такой вопрос у меня вызревает долгими годами. И когда я пишу его текст - он на 80 % уже
у меня в голове готов. Я просто дополняю его линками.

Так вот. Какая связь между НАМ и КЛ. Я посчитал что если момедитировать над Марковскими правилами
то возможно я увижу какую-то мысль или связь которая меня подтолкнет к логике комбинаторов.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964748
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
booby

Попом на этом сидит вся функциональщина, одновременно с декларативными прологами и последователями.
Подставив еще одну замену ты внедряешь еще одну первоклассную функцию, по сути.

Тема пролога мне была интересна прошлой осенью. Я хотел ее применить для поиска фактов
в дата-аналитике крупного бизнеса. Но не вышло по техническим причинам. Я не смог затащить
в проект зависимость от SWI-Prolog.

И моё достижение - это формальное доказательство на Прологе того что Иисус Христос - сын божий.
Только для этого мне пришлось записать порядка несколько сотен библейских фактов о отцовстве
и наследовании.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964749
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Еще вопрос.

Можем-ли мы реализовать общий случай генерации перестановок (combinations) для любого числа символов?

Input:
Код: sql
1.
123



Output:
Код: sql
1.
2.
3.
4.
5.
6.
123
132
213
231
312
321



результат должен быть строкой с разделителем?
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964754
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov

результат должен быть строкой с разделителем?

Хм... хороший вопрос.

Если у нас будет автомат-преобразователь следующей перестановки - то это будет успех.

Код: sql
1.
2.
3.
4.
5.
Input:
231 

Output:
312



Или если надо будет ввести искусственно код состояния. Или код рекурсии - то давай введем.

Код: sql
1.
2.
3.
4.
5.
Input:
231(0)

Output:
312(1)
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964762
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
booby

В классике алгорифмы статичны в отношении списка используемых правил.
Исследовал ли кто-нибудь, и как назвал, подобные конструкции с динамически изменяемым в процессе работы алгорифма списком правил.

У меня не возникало желания изменять правила. Но очень хотелось разбить их на непересекающиеся
модули. Причем терминалка должна была бы просто переходить в другой модуль.

Пример.

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
module 1 {
  rule1 -> repl1
  rule2 |-> :goto module_2
}

module 2 {
  rule1 -> repl3
  rule2 |-> :stop
}



Разумеется это не чистый НАМ. Но это моё определённое улучшение в духе Маркова.

Надеюсь госпожа mini.weblab меня здесь поймет и не будет настаивать на имеративных
языках.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964778
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

это выглядит как чистый сахар, удобство программиста, даже если
после стопа предполагается возврат.
В общем - вопрос реализации.

Изменяемый состав правил - это программа пишет сама себя по мере функционирования,
в целях всякого дип лёрнинга и построения прочих нейросетей.
То есть, кроме накопления состава фактов ( в терминах пролога) происходит докидывание/накопление,
а то и замена, правил вывода.
Вот что-то такое я думал, когда предыдущий пост писал.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964781
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
booby,

мне кажется, японцы чего такого про пролог измышляли,
когда хавтались за него, как язык будущего искусственного интеллекта.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964782
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я тебя понял. Нет о таком я не думал. Очень напоминает eval в транслируемых языках.
И вопрос доказательства останова (к примеру) для нас становится еще более неочевидным.

Хотя я не против эксперимента если ты предложишь своё улучшение. NMA-eval.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964788
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
booby
booby,

мне кажется, японцы чего такого про пролог измышляли,
когда хавтались за него, как язык будущего искусственного интеллекта.

У меня был еще один мотиватор. Экспертные системы в роли telegram-чят ботов.

Почему я об этом задумался. Когда я посмотрел их исходники в e-commerce.
Я пришел в ужас. Интеллектом там и не пахнет. Все на if-else. И ребята
которые пишут диалоговых ботов даже слыхом не слыхали про Prolog.

Мне это показлось как минимум - обидным. Конечно я не собирался
писать своего чят бота в телеграм. Но я хотел реализовать некое теч-демо
взяв экспертную систему из 80х (ну какую-нибудь по диагностике неполадок
например автомобиля). Взять - я имею в виду "слямзить" готовую. И просто
интегрировать ее с Телеграм-Ботом и показать.

- Ребята! Вот как надо! Вот как родные!
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964808
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

Еще одна вещь которая всегда мешает НАМ - отсутствие в правилах подстановочных символов.
Например, * могла бы обозначать любой символ исходного алфавита.
Без этого для описания перемещения символа приходится использовать
вместо одного правила целую кучу - по одному для каждого символа алфавита.

И это будет проблемой при генерации перестановок,
т.к. правила зависят от исходного алфавита и, в частности, от его мощности.

А других препятствий для генерации перестановок в алфавитном порядке вроде нет.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964809
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov, согласен. Мне вот еще не хватало символа конец строки. Типа "$" в регулярках.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964810
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Aleksandr Sharahov, согласен. Мне вот еще не хватало символа конец строки. Типа "$" в регулярках.


неудобно, да, но его всегда можно самому присобачить - это все-таки решаемо
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964813
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
По поводу Пролога. Ну вот фрагмент.

Код: python
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
% Eden chronicles.

parent(god, lucifer).
parent(god, adam).
parent(god, eve).
wife(eve,adam).

parent(adam, kain).
parent(eve, kain).
parent(adam, abel).
parent(adam, sif).

% Sif genealogy

parent(sif, enos).
parent(enos, kainan).
parent(kainan,maleleil).
parent(maleleil,iared).
parent(iared,enoh2).     % TODO: Duplicate enoh?
parent(enoh2, mafusail).
parent(mafusail, lameh).
parent(lameh, noah).

.....

predecessor(X,Y) :-
   parent(X,Y).

predecessor(X,Z) :-
   parent(X,Y),
   predecessor(Y,Z).



Там где многоточие - ветхий и новый завет в моём кривом изложении. Генеалогия.

Далее остается спросить у системы

Код: sql
1.
?- predecessor(god, jesus).



И она отвечает true.

Идею я дальше не развивал. Просто мало фактов. И они - плоские. Вот если бы взять генеалогию Толкиена
или Игр Престолов то там наверное можно было описать троюродных дядей или шуринов или свояков.

Но уже было не интересно.

Интересно было другое. Интеграция такой системы с чят-ботом. По ту сторону которого сидит
обычный юзер и не знает пролог и нужен некий фронт-енд к экспертной системе чтоб
транслировать вопросы юзера в некий пролого-подобный реквест.

Например
Код: sql
1.
- Является ли Джон Сноу потомком рода Таргариенов?
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964814
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov
mayton
Aleksandr Sharahov, согласен. Мне вот еще не хватало символа конец строки. Типа "$" в регулярках.


неудобно, да, но его всегда можно самому присобачить - это все-таки решаемо


А какого еще инструментация нам не хватает чтобы присобачить к НАМ возможности
генератора перестановок и конвертера инфиксной записи в ПОЛИЗ ?

Мне вот кажется не хватает представления исходной строки как дерева. Если-бы
мы могли скобочками так группировать

Код: sql
1.
(1(2(3))



И обращяться к узлам этого дерева.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39964817
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov

Еще одна вещь которая всегда мешает НАМ - отсутствие в правилах подстановочных символов.
Например, * могла бы обозначать любой символ исходного алфавита.
...

То, что Марков по этому поводу говорит, можно примерно в таком духе изложить:

вообще, для произвольного, "обобщенного" алгорифма, подобные штуки не запрещены, до тех пор,
пока понятно, как должна сработать трансформация, переводя одно слово в сразу другое.
Но и сложность трансформации при таком разрешении становится неопределенной.

Смысл специфически нормального алгорифма в том, чтобы использовать его как модель,
по отношению к которой можно доказывать какие-то утверждения, связанные со сложностью/производительностью.

Это единственная причина, по которой нормальный алгоримф требует выписывания каждого конкретного варианта
"атомарных", не предполагающих вариативности или более мелкого деления.
Это только вопрос автомизации формального суждения о сложности получения результата.

В общем случае, для не нормальных, алгорифмов, можно и смволы-комбинаторы в правилах придумывать,
каждый из которых, вообще говоря, должен уметь быть представимым в виде нормального алгорифма.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #40028763
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Товарищ Марков умер но дело его живет.

Приятно видеть https://golang.org/doc/codewalk/markov/
...
Рейтинг: 0 / 0
107 сообщений из 107, показаны все 5 страниц
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Четверговый НАМ и сложение двоичных чисел в строках
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]