Устройство для решения комбинаторных задач
Изобретение относится к вычислительной технике и может быть использовано при создании специализированных устройств обработки информации. Целью изобретения является расширение класса решаемых задач за счет обеспечения возможности вычисления биноминальных коэффициентов и их сумм. Устройство содержит триггер, генератор импульсов, генератор M - разрядных двоичных последовательностей с неубывающим числом единиц, включающий тактовый вход, M - загрузочных триггеров и разрядные триггеры, элемент И, два коммутатора, счетчик и вход запуска устройства. 2 ил.
СОЮЗ СОВЕТСНИХ
СОЦИАЛИСТИЧЕСНИХ
РЕСПУБЛИК (g))g С 06 F 15/20
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К А BTOPCHOMY СВИ4ЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ НОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И OTHPbtTHRM
ПРИ ГКНТ СССР (21) 4 /22223/24 (22) 31. 05. 89 (46) 23.08 „91. Бюл. М -31 (/2) Владимирский политехнический институт (/1) В.Ф,Романов и В С,Туляков (53) 681.3(088,.8) (56) Липский В,. Комбинаторика для программистов. — M.: Мир, 1988, с. 39, 40.
Авторское свидетельство СССР
М 12/542/, кл,. G 06 Р 7/38, 1985.
Изобретение относится к вычислительной технике и может быть использовано при создании специализированных устройств обработки информации.
Цель изобретения — расширение класса решаемых задач за счет обеспечения возможности вычисления и суммирования биномиальных коэффициентов.
На фиг,1 представлена функциональная схема устройства; на фиг,2 конкретный вариант ее выполнения для
m=4 с функциональной схемой генератора двоичных последовательностей с неубывающим числом единиц.
Ключом к достижению цели служит тот факт, что смена числа единиц с
k-1 íà k в выходном коде генератора
5U 1672466 А1
2 (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ КОМБИHAT0P HhtX ЗАДАЧ (5/) Изобретение относится к вычислительной технике и может быть испольэовано при создании специализированных устройств обработки информации. Целью изобретения является расширение класса решаемых задач за счет обеспечения возможности вычисления биномиальных коэффициентов и их сумм. Устройство содержит триггер, генератор импульсов, генератор m-разрядных двоичных последовательностей с неубывающим числом единиц, включающий тактовый вход, m загрузочных триггеров и разрядные триггеры, элемент И, два коммутатора, счетчик и вход запуска устройства. 2 ил., 1 табл. двоичных последовательностей, т.е. переход от сочетаний "из m no k-1" к 0 сочетаниям из m no k происходит .одновременно с установкой значения
"О" на выходе k ãо загрузочного триггера (загрузочного триггера k-го регистра). Устройство содержит триг- 0
rep 1, генератор 2 импульсов, гене- Ch ратор 3 m-разрядных двоичных последовательностей с неубывающим числом единиц, включающий тактовый вход 4, m загрузочных триггеров 5 и разрядные триггеры 6, элемент И /, первый
8 и второй 9 коммутаторы, счетчик 10, . вход 11 запуска устройства, генератор 3 двоичных последовательностей содержащий, (фиг,2) загрузочные триггеры
16/2466
5, разрядные триггеры 6, элементы ИЛИ
12, элементы И 13.
Устройство работает следующим образом.
В исходном состоянии устройства три гер 1 находится в нулевом состоянии, поэтому генератор 2 импульсов заблокирован. Коммутатор 8 соединяет инверс(ь(й выход (.-го загрузочного 10 три. гера генератора 3 с вторым входом эпеме;та И, коммутатор 9 соединяет инверсный выход )-го загрузочного три. гера генер.>(те>ра 3 с вх(дом устаHoBKH I Hk k> p-.> в нулевое состояние (;.= 1,2,. ° .,(>;-1, т=2,3,...,щ; 1с )) .
При поступлении сигнала на вход
11 запуска устройства триггер 1 переходит в единичное состояние, генератор 3 двоичных последовательностей чстзнан.(тивает(.>- в начальное состояние, пр(кот >р зи на вчходах эагрузочнь к триггepc в присутствуют значения на «ьг э,",ах разрядных тригге>1 11 р(в в; е;. Сгьстр. т> — значения О 25 (цепи начально,:(установки не показань(,(. С выхода генератора 2 поступают та . > о;з;,> ..;:г(„.лье((на тактовый в. .од 4 гене", атора 3, который вырабатывает на г.(ходах, ..нные кодовые комбинации
,/ г не-тд, ающим ч» л:>и единт ц„11ри этапы э.., ...н:: в(".;:д-, . -.ждог. х-го загэузочного триггера, где i=1,2, ...m и>.:ен>(ется "!" иа "0" на прямом и сoo"èeòственно " 0" на "1" на инверс35 ном .: оде) в тот момент, когда начинае:.ся перебор кодовых комбинаций, что,q. тветстпует началу счета сочетания Г., С момента .>зменения состояния k-ro загрузочного триггера с его инверсного вь(.ода через коммутатор 8 на второй вход элемента И поступает сигнал "1, и тактовь>е импульсы проходят на сч тчик 10. Счет заканчивается при .зменении сост>яния -ro за- 45 груз зчнс го триггера (j ) k) поскольку в этот момент с его инверсного выхода сигнал "1" через ко((мутатор 9 пос:упит на вход установки -риггера 1 в нулевое состояние. В результате в счетчике, 10 будет зафиксирован код, равный С, Отметим, что в тече- . >е н ние всего периода счета коммутаторы
8 и 9 находятся в фиксированных позициях.
При,подключении к элементу И и к входу обнуления триггера 1 соответственно двух загрузочных триггеров с последовательными номерами k и k+1 в счетчике 10 будет зафиксировано к число, Сщ, т.е. биномиальный коэф =" к фициент С . Максимальная вычисляемая сумма биномиальных коэффициентов рави на, С = 2 — 2, так как в вычисле1а! ние не включаются тривиальные коэфо (д фициенты С,„ = С = 1 (известно, что
У5
С = 2 ). В качестве коммутато =о ров 8 и 9 использованы т-позиционные переключатели.
В таблице приведены в виде двоичных массивов все 16 состояний генератора 3 для я=4 (фиг.2), которые последовательно сменяют друг друга по тактам (левый столбец массива вь>ходы загрузочных триггеров; остальные элементы,образую>тие треугольную матрицу — выходы разрядных триггеров). Выходы генератора 3 формируются как диэьюнкции значений элементов в разрядных столбцах. Из таблицы видно, что состояние:-ах" ого загрузочного триггера изменяется за время полного цикла только один раэ, отмечая перехо к началу счета С с
fTl ! (Оным k формула изобретения
Устройство для решения комбинаторных задач, содержащее генератор импульсов, вход запуска которого соединен с выходом триггера, а выход - с тактовым входом m-разрядного генератора двоичных последовательностей с неубь(вак>щим числом единиц и выполненного на группе загрузочных и группе разрядных триггеров, элементах И, ИЛИ, элемент И, вход установки триггера в "1" является входом запуска устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения класса решаемых задач за счет обеспечения возможности вычисления и суммирования биномиальных коэффициентов, в него введены первый и второй коммута" торы и счетчик, вход которого подключен к выходу элемента И, а выход является выходом устройства, причем первый вход элемента И соединен с выходом генератора импульсов, инверсный выход каждого i ro загрузочного триггера генератора двоичных последоват> ."ьностей (где i 1,2,...,m) под16/2466 ключен соответственно через первый И и через второй коммутатор — к вхокоммутатор к второму входу элемента ду обнуления триггера.
Сочетания Число сочетаний
Состояния с -!
Иэ 4 па О
С,-4
Иэ 4 по
С 6
Ф
С 4
Ъ
Иэ 4 по 3
С 1
Ф
Иэ 4 по 4! о о о о ! о о о ! о о ! о
O 1 O O O
I 000
1ОО ! о оо!оо о!оо оо ! о ооо!о
00 1 О
O1O
0 0 0 0 1
О О О l
О О 1
О 1 оо!оо
1 000
100 ! о
ООО1О
100 ! о
00001 оо!о
010 ! о
100 ! о
00001 о 1оо оо
1 О
00001
000 1
010 ! о
0000!
100 ! О
00 1 О ! О О
1 0
0000 1
ООО!
001
1 О
00001
1 О
О О О О 1 о о о
100 H$4 IIO 2 ! о
lh!24hh
Составитель В.Романов
Техред JJ.Серд окова Корректор О.Кравцова
Редактор В.!(анко
Заказ 2841 Тираж 381 Подлисное
ВНИ11П11 Государственного комитетз по изобретениям и открытиям лри ГКНТ СССР
113035, ..!осхв,з, iN-35, Раушская наб,, д, 4/5
Производственно-издательскии комбинат Пятенr",,г. Ужгород, ул. Гагарина, 101