Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 [3] 4 5   вперед  Ctrl      все
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
Swa111
Aleksandr Sharahov,

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


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

если не требуется ни то, ни другое, то две последних строки можно заменить одной
('-#', '')

Сообщение было отредактировано: 30 май 20, 00:57
30 май 20, 00:57    [22142555]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
Swa111
перевод из десятичной в унарную


а мы не гонимся за скоростью )
+
  ('|0','0||||||||||'),
  ('1', '0|'),
  ('2', '0||'),
  ('3', '0|||'),
  ('4', '0||||'),
  ('5', '0|||||'),
  ('6', '0||||||'),
  ('7', '0|||||||'),
  ('8', '0||||||||'),
  ('9', '0|||||||||'),
  ('0', '')
30 май 20, 01:13    [22142560]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
в десятичную
+
  
  ('#9|', '#10'),
  ('9|',  '|0'),
  ('8|',  '9'),
  ('7|',  '8'),
  ('6|',  '7'),
  ('5|',  '6'),
  ('4|',  '5'),
  ('3|',  '4'),
  ('2|',  '3'),
  ('1|',  '2'),
  ('0|',  '1'),
  ('#',   '.'), //exit
  ('',    '#0')
30 май 20, 01:35    [22142567]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mini.weblab
Member

Откуда:
Сообщений: 1027
пусть дано: "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
30 май 20, 03:08    [22142581]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
mini.weblab,

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

Мне кажется - первый шаг слабо обоснован.
30 май 20, 09:02    [22142602]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Aleksandr Sharahov
Swa111
перевод из десятичной в унарную


а мы не гонимся за скоростью )
+
  ('|0','0||||||||||'),
  ('1', '0|'),
  ('2', '0||'),
  ('3', '0|||'),
  ('4', '0||||'),
  ('5', '0|||||'),
  ('6', '0||||||'),
  ('7', '0|||||||'),
  ('8', '0||||||||'),
  ('9', '0|||||||||'),
  ('0', '')

Это шикарно
30 май 20, 10:25    [22142622]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
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>'),
  ('>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
30 май 20, 10:40    [22142626]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Из всех систем счисления - десятичная самая неудобная для этих операций.
30 май 20, 12:14    [22142645]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Саша как тебе такая идея?

F = 8 + 8
8 = 4 + 4
4 = 2 + 2
2 = 1 + 1 = | + | = ||
1 = |
30 май 20, 12:15    [22142647]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mayton
Саша как тебе такая идея?

F = 8 + 8
8 = 4 + 4
4 = 2 + 2
2 = 1 + 1 = | + | = ||
1 = |


идея применительно к чему?
а то у нас уже тут до фига всего.
30 май 20, 12:50    [22142655]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Мне почему-то всмомнилась идея Египетского Умножения.

Тоесть взять любую систему счисления. И заменить умножение
сложением. С небольшим числом слагаемых.
30 май 20, 12:54    [22142656]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Например (в десятичной)

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

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

Вобщем в императивных языках у нас будет не 13 сложений а нечто логарифмическое.
30 май 20, 13:00    [22142658]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
Сделал двоичное умножение, вышло достаточно быстро:
1000100111111000*1000110101111101 = 5190 замен
1000110101111101*1000100111111000 = 6006 замен

+
//двоичное умножение
  '*',   '^>',
  '>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     #  
30 май 20, 16:35    [22142743]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mayton
Например (в десятичной)

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

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

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


для двоичной системы как раз и получится умножение в столбик
30 май 20, 16:48    [22142748]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mini.weblab
Member

Откуда:
Сообщений: 1027
Практическое применение алгоритма Маркова: сложение в столбик
Code link:
https://repl.it/repls/RepulsiveRowdyCareware

Сообщение было отредактировано: 30 май 20, 17:16
30 май 20, 17:12    [22142754]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mini.weblab,

Во-первых, там не умножение, а сложение.
Во-вторых, совсем не по Маркову.
30 май 20, 17:18    [22142756]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mini.weblab
Member

Откуда:
Сообщений: 1027
Aleksandr Sharahov,
сложение поправила :)
при умножении в столбик применяется алгоритм Маркова
и при записи арифметических действий в строку тоже можно применить этот алгоритм
30 май 20, 17:22    [22142760]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mini.weblab
Aleksandr Sharahov,
сложение поправила :)
при умножении в столбик применяется алгоритм Маркова
и при записи арифметических действий в строку тоже можно применить этот алгоритм


Перенос переполнения в старший разряд - он не Марковский, а общечеловеческий )
Марковость - это (то, чего там вовсе нет):
1. задать таблицу замен,
2. взять строку с исходной формулой,
3. по Марковкому алгоритму применять замены к формуле до тех пор, пока алгоритм не остановится.
30 май 20, 17:30    [22142761]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
mini.weblab
Aleksandr Sharahov,
сложение поправила :)
при умножении в столбик применяется алгоритм Маркова
и при записи арифметических действий в строку тоже можно применить этот алгоритм

Как-то... переусложнено всё. Ты-же понимаешь что НАМ - это чистейшая теория.
Мозговой эксперимент. И если ты вводишь императивный язык как подпорку или
костыль что-бы НАМ улучшить то это уже совсем другой метод.
30 май 20, 17:32    [22142762]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mini.weblab
Member

Откуда:
Сообщений: 1027
ммм... нет, я перехожу от абстракции к конкретному примеру,
и дальше показываю, что умножение в столбик тоже относится к группе алгоритмов Маркова
для этого я переписываю начальную строку, так, как мне нужно для примера, и применяю серию правил (их у меня 5)
30 май 20, 17:56    [22142782]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mini.weblab
ммм... нет, я перехожу от абстракции к конкретному примеру,
и дальше показываю, что умножение в столбик тоже относится к группе алгоритмов Маркова
для этого я переписываю начальную строку, так, как мне нужно для примера, и применяю серию правил (их у меня 5)


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

Какие правила нам надо применить, чтобы последовательными
преобразованиями исходного выражения получить результирующую строку '1000' ?
30 май 20, 18:18    [22142794]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mini.weblab
Member

Откуда:
Сообщений: 1027
Aleksandr Sharahov,

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#
30 май 20, 18:29    [22142802]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mini.weblab
Aleksandr Sharahov,

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' ?
30 май 20, 18:33    [22142804]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mini.weblab
Member

Откуда:
Сообщений: 1027
Aleksandr Sharahov,

мы решаем разные задачи, в самом первом посте, я сказала, что покажу, что сложение в столбик выполняется по алгоритму Маркова.
и дальше просто идет proof of concept. :-)
я хочу сказать, а почему бы не посмотреть на проблему под другим углом. :-)
30 май 20, 18:55    [22142813]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mini.weblab
Aleksandr Sharahov,

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


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

От того, что некоторые правила записаны стрелочками, весь алгоритм сложения не становится Марковским,
т.к. не соблюдены *все* необходимые требования.
30 май 20, 19:08    [22142818]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 [3] 4 5   вперед  Ctrl      все
Все форумы / Программирование Ответить