Автор |
Сообщение |
|
|
Заголовок сообщения: |
Re: поиск последовательностей битов в ячеке |
|
|
Дык тогда решение уже некрасивое будет. Ладно, взял алгоритм сверху и тупо переделал его на два прохода. На первом проходе находится максимальная характеристика. На втором проходе выводятся все последовательности с такой характеристикой. Код: 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
Дык тогда решение уже некрасивое будет. Ладно, взял алгоритм сверху и тупо переделал его на два прохода. На первом проходе находится максимальная характеристика. На втором проходе выводятся все последовательности с такой характеристикой. [code]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[/code]101 24 10101 24
|
|
|
|
Добавлено: Вс июл 31, 2011 14:53 |
|
|
|
|
|
Заголовок сообщения: |
Re: поиск последовательностей битов в ячеке |
|
|
Ethereal писал(а): Тогда останутся последовательности длиной меньше 32-х. Их можно снабдить ведущим незначащим единичным битом. Ага, старший 1бит ограничивает длину последовательности. Кстати, чтобы решить задачу по исходному заданию, надо вывести только разные последовательности, у которых характеристика равна максимальной. Пока это не сделано. А так за 15 мксек (если TYPE отключить) все выводится.
[quote="Ethereal"]Тогда останутся последовательности длиной меньше 32-х. Их можно снабдить ведущим незначащим единичным битом.[/quote] Ага, старший 1бит ограничивает длину последовательности. Кстати, чтобы решить задачу по исходному заданию, надо вывести только разные последовательности, у которых характеристика равна максимальной. Пока это не сделано. А так за 15 мксек (если TYPE отключить) все выводится.
|
|
|
|
Добавлено: Сб июл 30, 2011 22:14 |
|
|
|
|
|
Заголовок сообщения: |
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
[quote="chess"]Появилось замечание по поводу последовательностей из единиц и нулей. Хотя последовательность вроде является числом, но оказалось что это не так. Последовательность не сводится к одному числу. Она сводится к двум числам. Первое число это количественная характеристика последовательности. Например последовательность 0101 сводится к числу 101. Последовательность 101 сводится к тому же числу 101. Но последовательности разные. Второе число для последовательности длина( можно еще взять количество начальных нулей что будет короче). То есть 0101 это 101 100 в виде чисел, а 101 это 101 11. То есть для хранения последовательности нужны две ячейки. [/quote]Не совсем так. Последовательность длиной 32 бита всего одна и её характеристика равна числу единичных бит в ячейке. Эту последовательность можно обработать первым делом, сначала и отдельно, чтобы задать начальное значение для поиска максимальной характеристики. Тогда останутся последовательности длиной меньше 32-х. Их можно снабдить ведущим незначащим единичным битом. Тогда 0.) Можно будет последовательность хранить в одной ячейке. 1.) Более длинные последовательности всегда будут численно больше более коротких. 2.) Выводить последовательность лежащую на стеке можно как 2 BASE ! 0 <# #S #> 1- SWAP CHAR+ SWAP TYPE
|
|
|
|
Добавлено: Сб июл 30, 2011 18:00 |
|
|
|
|
|
Заголовок сообщения: |
Re: поиск последовательностей битов в ячеке |
|
|
Как всегда всё на стеке, кроме пресловутой ячейки. Последовательности некоторой длины, взятые из ячейки, по своему значению сортируются по такому принципу : К верхушке стека благодаря 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
Как всегда всё на стеке, кроме пресловутой ячейки. Последовательности некоторой длины, взятые из ячейки, по своему значению сортируются по такому принципу : К верхушке стека благодаря UMIN прилипает наименьшая последовательность, большая той, что под вершиной стека. Прилипшая последовательность обрабатывается словом SEQUENCE, проваливается под вершину стека и все начинается с начала. В итоге разные последовательности обрабатываются строго в порядке возрастания (реализована сортировка). [code]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[/code]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
|
|
|
|
Добавлено: Сб июл 30, 2011 14:29 |
|
|
|
|
|
Заголовок сообщения: |
Re: поиск последовательностей битов в ячеке |
|
|
WingLion писал(а): По порядку величины я даже не соврал... Ну вы прямо как на экзамене.
[quote="WingLion"]По порядку величины я даже не соврал...[/quote] Ну вы прямо как на экзамене. :)
|
|
|
|
Добавлено: Пт июл 29, 2011 22:07 |
|
|
|
|
|
Заголовок сообщения: |
Re: поиск последовательностей битов в ячеке |
|
|
chess писал(а): Вам сказали что максимум не 32К, а меньше. Я дал точное значение максимума (16896 ). По порядку величины я даже не соврал...
[quote="chess"]Вам сказали что максимум не 32К, а меньше. Я дал точное значение максимума (16896 ).[/quote]
По порядку величины я даже не соврал...
|
|
|
|
Добавлено: Пт июл 29, 2011 21:40 |
|
|
|
|
|
Заголовок сообщения: |
Re: поиск последовательностей битов в ячеке |
|
|
chess писал(а): Взято всего лишь по максимуму... Вам сказали что максимум не 32К, а меньше. Я дал точное значение максимума (16896 ).
[quote="chess"]Взято всего лишь по максимуму...[/quote] Вам сказали что максимум не 32К, а меньше. Я дал точное значение максимума (16896 ).
|
|
|
|
Добавлено: Пт июл 29, 2011 20:59 |
|
|
|
|
|
Заголовок сообщения: |
Re: поиск последовательностей битов в ячеке |
|
|
вопрос писал(а): Это ещё почему? если маска шире 1 бита то она не может быть 32 раза, а 32 - ширина
Взято всего лишь по максимуму... Ясен пень, что не все смещения маски/битов должны обсчитываться
[quote="вопрос"]Это ещё почему? если маска шире 1 бита то она не может быть 32 раза, а 32 - ширина [/quote]
Взято всего лишь по максимуму...
Ясен пень, что не все смещения маски/битов должны обсчитываться
|
|
|
|
Добавлено: Пт июл 29, 2011 20:55 |
|
|
|
|
|
Заголовок сообщения: |
Re: поиск последовательностей битов в ячеке |
|
|
WingLion писал(а): 32 маски x 32 положения маски x 32 проверки на самом деле 1 32 + 32 * 2/ 32 * ( 16896 )
[quote="WingLion"]32 маски x 32 положения маски x 32 проверки [/quote] на самом деле 1 32 + 32 * 2/ 32 * ( [b]16896[/b] )
|
|
|
|
Добавлено: Пт июл 29, 2011 20:54 |
|
|
|
|
|
Заголовок сообщения: |
Re: поиск последовательностей битов в ячеке |
|
|
Цитата: 32 маски x 32 положения маски x 32 проверки Это ещё почему? если маска шире 1 бита то она не может быть 32 раза, а 32 - ширина
[quote]32 маски x 32 положения маски x 32 проверки[/quote] Это ещё почему? если маска шире 1 бита то она не может быть 32 раза, а 32 - ширина
|
|
|
|
Добавлено: Пт июл 29, 2011 20:42 |
|
|
|
|
|
Заголовок сообщения: |
Re: поиск последовательностей битов в ячеке |
|
|
В данном случае, как мне кажется, надо "последовательности" определять вот так:
маска: 0000000000011111b биты: 0000000000000101b
Маска выделяет, какие биты к последовательности относятся, какие нет. Затем, для подсчета - маска и биты сдвигаются, делается
: TEST SOURCE @ bits @ XOR mask @ АND 0= IF ." совпало" ELSE ." не совпало THEN ;
а дальше - цикл по маскам, (биты маской из исходного числа выделять)... 32 маски x 32 положения маски x 32 проверки - 32K исполнений слова TEST и вместо чепяти слов - запись статистики в массив...
короче, пока неясно зачем сей изврат нужен, интерса кодить и нету...
В данном случае, как мне кажется, надо "последовательности" определять вот так:
маска: 0000000000011111b биты: 0000000000000101b
Маска выделяет, какие биты к последовательности относятся, какие нет. Затем, для подсчета - маска и биты сдвигаются, делается
: TEST SOURCE @ bits @ XOR mask @ АND 0= IF ." совпало" ELSE ." не совпало THEN ;
а дальше - цикл по маскам, (биты маской из исходного числа выделять)... 32 маски x 32 положения маски x 32 проверки - 32K исполнений слова TEST и вместо чепяти слов - запись статистики в массив...
короче, пока неясно зачем сей изврат нужен, интерса кодить и нету...
|
|
|
|
Добавлено: Пт июл 29, 2011 20:24 |
|
|
|
|
|
Заголовок сообщения: |
Re: поиск последовательностей битов в ячеке |
|
|
Появилось замечание по поводу последовательностей из единиц и нулей. Хотя последовательность вроде является числом, но оказалось что это не так. Последовательность не сводится к одному числу. Она сводится к двум числам. Первое число это количественная характеристика последовательности. Например последовательность 0101 сводится к числу 101. Последовательность 101 сводится к тому же числу 101. Но последовательности разные. Второе число для последовательности длина( можно еще взять количество начальных нулей что будет короче). То есть 0101 это 101 100 в виде чисел, а 101 это 101 11. То есть для хранения последовательности нужны две ячейки. Название 'последовательность' неудобное. Возможно существует какой-то другой термин для последовательностей, но я что-то его не обнаружил.
Появилось замечание по поводу последовательностей из единиц и нулей. Хотя последовательность вроде является числом, но оказалось что это не так. Последовательность не сводится к одному числу. Она сводится к двум числам. Первое число это количественная характеристика последовательности. Например последовательность 0101 сводится к числу 101. Последовательность 101 сводится к тому же числу 101. Но последовательности разные. Второе число для последовательности длина( можно еще взять количество начальных нулей что будет короче). То есть 0101 это 101 100 в виде чисел, а 101 это 101 11. То есть для хранения последовательности нужны две ячейки. Название 'последовательность' неудобное. Возможно существует какой-то другой термин для последовательностей, но я что-то его не обнаружил.
|
|
|
|
Добавлено: Пт июл 29, 2011 16:37 |
|
|
|
|
|
Заголовок сообщения: |
Re: поиск последовательностей битов в ячеке |
|
|
chess писал(а): Видимо последовательности для поиска надо брать не подряд, а из самого исходного числа. Интуиция не обманула. Именно так и надо. Перебор усечен по максимуму. Работает мгновенно. Код: : sumbit1 ( n -- nb1 ) C^C L1: $ 0 A=#? L2 J0= D=L\A C++ C=D\A0 L1 JMP L2: A=C ; \ число единичных бит в ячейке
: b. ( n ls -- ) ls! 2 BASE ! 32 ls - SPACES ls .0 2 SPACES 0xA BASE ! ; \ вывод результатов
: character ( n ls -- sq character ) \ поиск максимальной характеристики для заданной длины последовательности ls! nt! nt n! nt nl! 0 mch! 0 sq! 0 nq! -1 ls LSHIFT INVERT m! 32 ls - 0 DO 32 ls - 0 DO nl m AND 0<> IF n m AND nl m AND = IF nq 1+ is nq THEN n 1 RSHIFT is n ELSE LEAVE THEN LOOP nl m AND sumbit1 nq * DUP mch > IF nl m AND is sq is mch ELSE DROP THEN nt is n 0 is nq nl 1 RSHIFT is nl LOOP sq ls b. mch . CR ;
: max-seq ( n -- ) n! 32 1 DO n I character LOOP n 32 b. n sumbit1 . CR ." end" CR ; \ вывод максимальных характеристик для всех длин от 1 до 32
\ EOF : n 0x12345678 ; STARTLOG n max-seq Лог Код: 1 13 11 10 110 6 1100 4 11110 4 111100 4 1001111 5 11001111 6 110011110 6 1011001111 7 10110011110 7 101011001111 8 1010110011110 8 10101100111100 8 101011001111000 8 1000101011001111 9 10001010110011110 9 101000101011001111 10 1101000101011001111 11 11010001010110011110 11 110100010101100111100 11 1101000101011001111000 11 10001101000101011001111 12 100011010001010110011110 12 1000110100010101100111100 12 10010001101000101011001111 13 100100011010001010110011110 13 1001000110100010101100111100 13 10010001101000101011001111000 13 010010001101000101011001111000 13 0010010001101000101011001111000 13 00010010001101000101011001111000 13 end ps. А то меня уже сомнение посетило насчет способов сжатия информации без потерь. А про самое главное то я и забыл - за основу сжатия берется структура самой исходной информации.
[quote="chess"]Видимо последовательности для поиска надо брать не подряд, а из самого исходного числа.[/quote] Интуиция не обманула. Именно так и надо. Перебор усечен по максимуму. Работает мгновенно. [code]: sumbit1 ( n -- nb1 ) C^C L1: $ 0 A=#? L2 J0= D=L\A C++ C=D\A0 L1 JMP L2: A=C ; \ число единичных бит в ячейке
: b. ( n ls -- ) ls! 2 BASE ! 32 ls - SPACES ls .0 2 SPACES 0xA BASE ! ; \ вывод результатов
: character ( n ls -- sq character ) \ поиск максимальной характеристики для заданной длины последовательности ls! nt! nt n! nt nl! 0 mch! 0 sq! 0 nq! -1 ls LSHIFT INVERT m! 32 ls - 0 DO 32 ls - 0 DO nl m AND 0<> IF n m AND nl m AND = IF nq 1+ is nq THEN n 1 RSHIFT is n ELSE LEAVE THEN LOOP nl m AND sumbit1 nq * DUP mch > IF nl m AND is sq is mch ELSE DROP THEN nt is n 0 is nq nl 1 RSHIFT is nl LOOP sq ls b. mch . CR ;
: max-seq ( n -- ) n! 32 1 DO n I character LOOP n 32 b. n sumbit1 . CR ." end" CR ; \ вывод максимальных характеристик для всех длин от 1 до 32
\ EOF : n 0x12345678 ; STARTLOG n max-seq[/code]Лог [code] 1 13 11 10 110 6 1100 4 11110 4 111100 4 1001111 5 11001111 6 110011110 6 1011001111 7 10110011110 7 101011001111 8 1010110011110 8 10101100111100 8 101011001111000 8 1000101011001111 9 10001010110011110 9 101000101011001111 10 1101000101011001111 11 11010001010110011110 11 110100010101100111100 11 1101000101011001111000 11 10001101000101011001111 12 100011010001010110011110 12 1000110100010101100111100 12 10010001101000101011001111 13 100100011010001010110011110 13 1001000110100010101100111100 13 10010001101000101011001111000 13 010010001101000101011001111000 13 0010010001101000101011001111000 13 00010010001101000101011001111000 13 end[/code] ps. А то меня уже сомнение посетило насчет способов сжатия информации без потерь. А про самое главное то я и забыл - за основу сжатия берется структура самой исходной информации.
|
|
|
|
Добавлено: Чт июл 28, 2011 15:28 |
|
|
|
|
|
Заголовок сообщения: |
Re: поиск последовательностей битов в ячеке |
|
|
Поскольку необходимы повторяющиеся последовательности, из самого 4-байта достаточно брать повторяющиеся. Нужно, видимо, манипулировать исключающим ИЛИ
Сдвигая ячейку, сравнивать её побитно с собственной копией (несдвинутой)
Поскольку необходимы повторяющиеся последовательности, из самого 4-байта достаточно брать повторяющиеся. Нужно, видимо, манипулировать исключающим ИЛИ
Сдвигая ячейку, сравнивать её побитно с собственной копией (несдвинутой)
|
|
|
|
Добавлено: Чт июл 28, 2011 14:46 |
|
|
|
|
|
Заголовок сообщения: |
Re: поиск последовательностей битов в ячеке |
|
|
Попробовал полный перебор с отсечением нулевых последовательностей: Код: : sumbit1 ( n -- nb1 ) C^C L1: $ 0 A=#? L2 J0= D=L\A C++ C=D\A0 L1 JMP L2: A=C ; \ число единичных бит в ячейке
: b. ( n ls -- ) ls! 2 BASE ! 32 ls - SPACES ls .0 2 SPACES 0xA BASE ! ; \ вывод результатов
: character ( n ls -- sq character ) \ поиск максимальной характеристики для заданной длины последовательности ls! nt! nt n! 0 mch! 0 sq! 0 nq! -1 ls LSHIFT INVERT m! m 1+ 1 DO 32 ls - 0 DO J 0<> IF n m AND J = IF nq 1+ is nq THEN n 1 RSHIFT is n ELSE LEAVE THEN LOOP I sumbit1 nq * DUP mch > IF I is sq is mch ELSE DROP THEN nt is n 0 is nq LOOP sq ls b. mch . CR ;
: max-seq ( n -- ) n! 32 1 DO n I character LOOP n 32 b. n sumbit1 . CR ." end" CR ; \ вывод максимальных характеристик для всех длин от 1 до 32
\ EOF : n 0x12345678 ; STARTLOG n max-seq Лог Код: 1 13 11 10 011 6 0011 4 01111 4 001111 4 1001111 5 11001111 6 011001111 6 1011001111 7 01011001111 7 101011001111 8 0101011001111 8 00101011001111 8 000101011001111 8 1000101011001111 9 01000101011001111 9 101000101011001111 10 1101000101011001111 11 01101000101011001111 11 001101000101011001111 11 0001101000101011001111 11 10001101000101011001111 12 010001101000101011001111 12 0010001101000101011001111 12 10010001101000101011001111 13 010010001101000101011001111 13 0010010001101000101011001111 13 00100100011010001010110011110 13 001001000110100010101100111100 13 0010010001101000101011001111000 13 00010010001101000101011001111000 13
end
Ok ps. Работает около 3-х минут. Очень долго, хотя подсчет количества 1-х битов сделан на ассме. Видимо последовательности для поиска надо брать не подряд, а из самого исходного числа.
Попробовал полный перебор с отсечением нулевых последовательностей: [code]: sumbit1 ( n -- nb1 ) C^C L1: $ 0 A=#? L2 J0= D=L\A C++ C=D\A0 L1 JMP L2: A=C ; \ число единичных бит в ячейке
: b. ( n ls -- ) ls! 2 BASE ! 32 ls - SPACES ls .0 2 SPACES 0xA BASE ! ; \ вывод результатов
: character ( n ls -- sq character ) \ поиск максимальной характеристики для заданной длины последовательности ls! nt! nt n! 0 mch! 0 sq! 0 nq! -1 ls LSHIFT INVERT m! m 1+ 1 DO 32 ls - 0 DO J 0<> IF n m AND J = IF nq 1+ is nq THEN n 1 RSHIFT is n ELSE LEAVE THEN LOOP I sumbit1 nq * DUP mch > IF I is sq is mch ELSE DROP THEN nt is n 0 is nq LOOP sq ls b. mch . CR ;
: max-seq ( n -- ) n! 32 1 DO n I character LOOP n 32 b. n sumbit1 . CR ." end" CR ; \ вывод максимальных характеристик для всех длин от 1 до 32
\ EOF : n 0x12345678 ; STARTLOG n max-seq[/code] Лог [code] 1 13 11 10 011 6 0011 4 01111 4 001111 4 1001111 5 11001111 6 011001111 6 1011001111 7 01011001111 7 101011001111 8 0101011001111 8 00101011001111 8 000101011001111 8 1000101011001111 9 01000101011001111 9 101000101011001111 10 1101000101011001111 11 01101000101011001111 11 001101000101011001111 11 0001101000101011001111 11 10001101000101011001111 12 010001101000101011001111 12 0010001101000101011001111 12 10010001101000101011001111 13 010010001101000101011001111 13 0010010001101000101011001111 13 00100100011010001010110011110 13 001001000110100010101100111100 13 0010010001101000101011001111000 13 00010010001101000101011001111000 13
end
Ok[/code] ps. Работает около 3-х минут. Очень долго, хотя подсчет количества 1-х битов сделан на ассме. Видимо последовательности для поиска надо брать не подряд, а из самого исходного числа.
|
|
|
|
Добавлено: Чт июл 28, 2011 13:03 |
|
|
|