поиск последовательностей битов в ячеке

Ethereal

Как всегда всё на стеке, кроме пресловутой ячейки.
Последовательности некоторой длины, взятые из ячейки, по своему значению сортируются по такому принципу :
К верхушке стека благодаря UMIN прилипает наименьшая последовательность, большая той, что под вершиной стека. Прилипшая последовательность обрабатывается словом SEQUENCE, проваливается под вершину стека и все начинается с начала. В итоге разные последовательности обрабатываются строго в порядке возрастания (реализована сортировка).

Код:

HEX 55AA55AA VALUE n \ Пресловутая ячейка

: SEQUENCE ( mask seq i -- mask seq ) \ Вывод данных о последовательности
  >R 2 BASE !
  DUP 0 <# R@ TRUE DO # LOOP #> TYPE SPACE DECIMAL \ Вывод последовательности
  0 20 R> - 0 DO n I RSHIFT 2OVER -ROT AND = - LOOP >R \ Число повторений >R
  0 OVER BEGIN DUP >R 0< - R> 2* ?DUP 0= UNTIL \ Число единичных бит
  R> * . CR \ Перемножить Число_повторений на Число_единичных_бит и вывести
;
: SEQ ( -- )
  20 0 DO
    1 I LSHIFT 2* 1- \ Маска
    TRUE 20 I - 0 DO OVER n I RSHIFT AND UMIN LOOP \ Минимальная последовательность длины I+1
    BEGIN
      I SEQUENCE TRUE
      20 I - 0 DO
        n I RSHIFT 2OVER -ROT AND TUCK U<
        IF UMIN ELSE DROP THEN
      LOOP NIP DUP TRUE =
    UNTIL 2DROP
  LOOP
;

SEQ BYE

0 0
1 16
00 0
01 14
10 14
11 4
001 1
010 12
011 4
100 1
101 24
110 4
0010 1
0100 1
0101 20
0110 4
1001 2
1010 20
1011 6
1101 6
00101 2
01001 2
01010 16
01011 6
01101 6
10010 2
10100 2
10101 24
10110 6
11010 6
001010 2
010010 2
010100 2
010101 18
010110 6
011010 6
100101 3
101001 3
101010 18
101011 8
101101 8
110101 8
...
01010101101010100101010110101 15
01010110101010010101011010101 15
10101011010101001010101101010 15
10101101010100101010110101010 15
010101011010101001010101101010 15
010101101010100101010110101010 15
101010110101010010101011010101 16
0101010110101010010101011010101 16
1010101101010100101010110101010 16
01010101101010100101010110101010 16

Ethereal

chess писал(а):

Появилось замечание по поводу последовательностей из единиц и нулей.
Хотя последовательность вроде является числом, но оказалось что это не так.
Последовательность не сводится к одному числу. Она сводится к двум числам.
Первое число это количественная характеристика последовательности.
Например последовательность 0101 сводится к числу 101. Последовательность 101 сводится к тому же числу 101.
Но последовательности разные. Второе число для последовательности длина( можно еще взять количество начальных нулей что
будет короче).
То есть 0101 это 101 100 в виде чисел, а 101 это 101 11. То есть для хранения последовательности нужны две ячейки.

Не совсем так.
Последовательность длиной 32 бита всего одна и её характеристика равна числу единичных бит в ячейке. Эту последовательность можно обработать первым делом, сначала и отдельно, чтобы задать начальное значение для поиска максимальной характеристики. Тогда останутся последовательности длиной меньше 32-х. Их можно снабдить ведущим незначащим единичным битом. Тогда
0.) Можно будет последовательность хранить в одной ячейке.
1.) Более длинные последовательности всегда будут численно больше более коротких.
2.) Выводить последовательность лежащую на стеке можно как
2 BASE ! 0 <# #S #> 1- SWAP CHAR+ SWAP TYPE

chess

Ethereal писал(а):

Тогда останутся последовательности длиной меньше 32-х. Их можно снабдить ведущим незначащим единичным битом.

Ага, старший 1бит ограничивает длину последовательности.
Кстати, чтобы решить задачу по исходному заданию, надо вывести только разные последовательности, у которых характеристика равна максимальной. Пока это не сделано.
А так за 15 мксек (если TYPE отключить) все выводится.

Ethereal

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

Код:

HEX 55AA55AA VALUE n \ Пресловутая ячейка

0 VALUE МАКСИМУМ \ Максимальная характеристика
TRUE VALUE ПРОХОД? \ Первый или второй проход ?
: SEQUENCE ( mask seq i -- mask seq )
  1+ >R
  0 R@ 0 DO OVER I RSHIFT 1 AND + LOOP \ Число единичных бит
  0 21 R@ - 0 DO 2OVER n I RSHIFT ROT AND = - LOOP \ Число повторений
  * \ Характеристика
  DUP МАКСИМУМ = ПРОХОД? AND
  IF
    2 BASE !
    OVER 0 <# R> 0 DO # LOOP #> TYPE SPACE \ Вывод последовательности
    DECIMAL . CR \ Вывод характеристики
  ELSE
    МАКСИМУМ MAX TO МАКСИМУМ RDROP
  THEN
;
: SEQ ( -- )
  0 TO МАКСИМУМ
  BEGIN
    ПРОХОД? INVERT TO ПРОХОД?
    20 0 DO
      1 I LSHIFT 2* 1- \ Маска
      TRUE 20 I - 0 DO OVER n I RSHIFT AND UMIN LOOP \ Мин.последовательность длины I+1
      BEGIN
        I SEQUENCE TRUE
        20 I - 0 DO
          n I RSHIFT 2OVER -ROT AND TUCK U<
          IF UMIN ELSE DROP THEN
        LOOP NIP DUP TRUE =
      UNTIL 2DROP
    LOOP ПРОХОД?
  UNTIL
;

SEQ BYE

101 24
10101 24

поиск последовательностей битов в ячеке

Кто сейчас на конференции