Устройство для решения комбинаторных задач

 

Изобретение относится к вычислительной технике и может быть использовано при создании специализированных устройств обработки информации. Целью изобретения является расширение класса решаемых задач за счет обеспечения возможности вычисления биноминальных коэффициентов и их сумм. Устройство содержит триггер, генератор импульсов, генератор 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