Forth http://fforum.winglion.ru/ |
|
поиск последовательностей битов в ячеке http://fforum.winglion.ru/viewtopic.php?f=19&t=2742 |
Страница 2 из 2 |
Автор: | Ethereal [ Сб июл 30, 2011 14:29 ] |
Заголовок сообщения: | Re: поиск последовательностей битов в ячеке |
Как всегда всё на стеке, кроме пресловутой ячейки. Последовательности некоторой длины, взятые из ячейки, по своему значению сортируются по такому принципу : К верхушке стека благодаря UMIN прилипает наименьшая последовательность, большая той, что под вершиной стека. Прилипшая последовательность обрабатывается словом SEQUENCE, проваливается под вершину стека и все начинается с начала. В итоге разные последовательности обрабатываются строго в порядке возрастания (реализована сортировка). Код: HEX 55AA55AA VALUE n \ Пресловутая ячейка 0 0 : 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 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 [ Сб июл 30, 2011 18:00 ] |
Заголовок сообщения: | Re: поиск последовательностей битов в ячеке |
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 [ Сб июл 30, 2011 22:14 ] |
Заголовок сообщения: | Re: поиск последовательностей битов в ячеке |
Ethereal писал(а): Тогда останутся последовательности длиной меньше 32-х. Их можно снабдить ведущим незначащим единичным битом. Ага, старший 1бит ограничивает длину последовательности. Кстати, чтобы решить задачу по исходному заданию, надо вывести только разные последовательности, у которых характеристика равна максимальной. Пока это не сделано. А так за 15 мксек (если TYPE отключить) все выводится. |
Автор: | Ethereal [ Вс июл 31, 2011 14:53 ] |
Заголовок сообщения: | Re: поиск последовательностей битов в ячеке |
Дык тогда решение уже некрасивое будет. Ладно, взял алгоритм сверху и тупо переделал его на два прохода. На первом проходе находится максимальная характеристика. На втором проходе выводятся все последовательности с такой характеристикой. Код: HEX 55AA55AA VALUE n \ Пресловутая ячейка 101 24 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 10101 24 |
Страница 2 из 2 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |