Forth
http://fforum.winglion.ru/

Приступ склероза (задача)
http://fforum.winglion.ru/viewtopic.php?f=2&t=3098
Страница 1 из 1

Автор:  gudleifr [ Ср май 04, 2016 14:26 ]
Заголовок сообщения:  Приступ склероза (задача)

Как случайным образом выбрать единицу из битовой шкалы?

Т.е. полностью заполненная единицами шкала - полная колода карт. После сдачи нескольких карт появляются нули. Как случайно вытянуть очередную карту?

Автор:  KPG [ Чт май 05, 2016 02:44 ]
Заголовок сообщения:  Re: Приступ склероза (задача)

gudleifr писал(а):
Как случайным образом выбрать единицу из битовой шкалы?

Т.е. полностью заполненная единицами шкала - полная колода карт. После сдачи нескольких карт появляются нули. Как случайно вытянуть очередную карту?

М-последовательности, как вариант.

Автор:  gudleifr [ Чт май 05, 2016 10:58 ]
Заголовок сообщения:  Re: Приступ склероза (задача)

KPG писал(а):
М-последовательности, как вариант.
???

Автор:  KPG [ Чт май 05, 2016 18:53 ]
Заголовок сообщения:  Re: Приступ склероза (задача)

gudleifr писал(а):
KPG писал(а):
М-последовательности, как вариант.
???

Простое и где то начально достаточное объяснение такое http://thebard.narod.ru/bel/10.htm
Номера отводов (для операции xor -сложения битов) при сдвиге м-последовательности нужного N-1 периода
и возможные варианты схемы приводятся в справочниках (также см. картинки по способу образования связей в регистре в i-nete
две базисные схемы http://mybiblioteka.su/3-3874.html )

Сходу не нашёл в i-nete и ещё не вспомнил у себя книгу где они приведены для 2-х базисных вариантов
суммирования битов с отводов регистра для формирования очередного бита для сдвигового регистра.

т.е. после каждого такта сдвига на отводах регистра получаем очередное число (псевдослучайное) из N-цепочки
Псевдослучайное т.к. они предсказуемы из предыдущего состояния и чем больше разрядов регистра, тем больше вариантов
разных "конфигураций номеров отводов" в типовых схемах, (8бит - это уже 255 псевдослучайных чисел и сколько то вариантов номеров отводов бит)
Начальная инициализация регистра - произвольное не 0 число.

М-последовательность хорошо используется при сигнатурном анализе неисправности логических схем (с пониманием некоторых ограничений данного метода)

P.S. Остальная теория "комбинирования" м-последовательностей согласно их свойств - это уже в книгах. :)

Автор:  gudleifr [ Чт май 05, 2016 20:40 ]
Заголовок сообщения:  Re: Приступ склероза (задача)

KPG писал(а):
...
Это все понятно, но каким местом это относится к задаче - выборе случайной 1 из разреженной шкалы?

Автор:  chess [ Чт май 05, 2016 21:02 ]
Заголовок сообщения:  Re: Приступ склероза (задача)

Код:
\ для наглядности с локальными переменными(spf4) для 32-х битной шкалы

CREATE arr 32 4 * ALLOT

\ n -- bit
: chose-bit { n \ i }
0 TO i
RANDOMIZE
32 0 DO 1 I LSHIFT n AND IF 1 I LSHIFT  arr i + ! i 4 + TO i THEN LOOP
i 4 / CHOOSE 4 * arr + @ ;

0x377754AF chose-bit

Автор:  KPG [ Чт май 05, 2016 21:09 ]
Заголовок сообщения:  Re: Приступ склероза (задача)

gudleifr писал(а):
KPG писал(а):
...
Это все понятно, но каким местом это относится к задаче - выборе случайной 1 из разреженной шкалы?

Каждый бит в шкале 0/1 имеет номер от 0...N и псевдослуайный способ это один из методов выбора без повтора "номеров" этих битов. (из "колоды" бит начально состоящей из единиц ) и пометки этих бит в 0.

P.S. Если, например, псевдослучайно начально сформировать таблицу расположения индексов этих битов,
то возможно перетусовывать "биты-номера" в этой таблице например так (формирование новой таблицы)
используя туже псевдослучайную последовательность.
На 0-ое место перемещаем номер из ячейки по текущему полученному псевдочислу. на 1ое по второму псевдочислу и.т.д.
Возможно это неплохая стратегия перетусовывания "битов-номеров"
Sorry, если не до понял проблематику вопроса (из-за сжатого описания) и необходимо какое то фикс решение. :)

Автор:  gudleifr [ Чт май 05, 2016 22:19 ]
Заголовок сообщения:  Re: Приступ склероза (задача)

chess писал(а):
...
Да, примерно, так (с поправкой на то, что шкала обычно не влезает в одну ячейку - даже в обычной колоде 36 карт). Но, если я выделяю дополнительный массив, то не нельзя ли использовать его с большей эффективностью?
И, еще, идеологическая ошибка. Разумное применение шкал - именно для хранения данных, и использовать ее в качестве входного параметра - некоторая несуразность.

KPG писал(а):
...
Речь идет не о генерации последовательности, а о ее анализе. Сгенерировать случайную перестановку - не проблема.

Страница 1 из 1 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/