Устройство для перебора сочетаний

 

СООЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (11) А2 (51)4 G 06 F

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (61) 1140127 (21) 4143537/24-24 (22) 10.11,86 (46 ) 23.05.88. Бюл. !(19 (72) В.А.Лукоянов, А.Ю.Корев и Б.С.Старшинов (53) 681.31(088.8) (56) Авторское свидетельство СССР

Ф 1140127, кл. G 06 F 15/31, 1985. (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ (57) Изобретение относится к вычислительной технике и предназначено для использования в устройствах, решающих комбинаторные задачи, связанные с перебором сочетаний, и является усовершенствованием изобретения по а. с. Ф II40127. Дель изобретениясокращение времени перебора сочетаний от С до С„с. Устройство содержит пять групп элементов И 2, 3, 5, 6, 30, две группы элементов ИЛИ 4, 8, группу элементов задервки 7, два регистра 1 » два триггера 9, 20, четыре элемента И 10» 17 25, элемент 21 эадервжи, схему 23 сравнения, блок 22 элементов И, блок 26 элементов задержки, счетчик 27, шину 15 входного канала, входы 18, 24, 28 начальной установки, выход 14 признака окончания работы, дешифратор

29,.входы ll задания количества элементов, элемент ИЛИ 12, группу элементов ЗАПРЕТ 13, Устройство позволяет реализовать перербор всех соче t k таний от С„до С„при п i k, n m, 1 с пт, m — число элементов перебора.

1 ил, 1397936

Изобретение относится к вычислительной технике, может быть использовано в устройствах, решающих комбинаторные задачи, связанные с перебором сочетаний, и является усовершенствованием устройства по основному авт. св. II 1140127.

Цель изобретения — сокращение вреч К мени перебора сочетаний от С„ до С„ при rck, и ш, kcm.

На чертеже приведена схема устройства для перебора сочетаний.

Устройство содержит первый регистр, образованный иэ m триггеров 1, груп- 15 пу элементов И 2, группу элементов

И 3, группу элементов ИЛИ 4, группу элементов И 5, группу элементов И 6, группу элементов 7 задержки, группу элементов ИЛИ 8, триггер 9, элемент 20

И 10, входы 11 задания количества элементов, элемент ИЛИ 12, группу элементов ЗАПРЕТ 13, выход 14 признака окончания работы, шину 15 входного сигнала, элементы И 16 и 17, входы 25

18 установки регистра, регистр 19, образованный иэ 1 1од тп(+! триггеров, триггер 20, элемент 21 задержки, блок 22 ea ) log m(+I элементов И, и схему 23 сравнения, вход 24 установ- 30 кй триггера, элемент И 25, блок 26 из

lloyd ò(+1 элементов задержки, счетчик 27, вход 28 установки счетчика, дешифратор 29, группу иэ m элементов

И 30.

Устройство работает следующим образом.

Для полного перебора всех возможных сочетаний от С, до С„ при и 4-m, k

1.1

k

Очередной импульс, поступающий

50 по шине 15 входного сигнала, проходит через элемент И 17, открытый разрешающим потенциалом с нулевого выхода триггера 20 на счетный вход счетчика 27. Реверсивный счетчик принимает состояние i, меньшее на единицу

55 первоначального (для первого импульса i=k+1 †1). При этом, исло r иэ регистра 9 в параллели и< и двоичном коде поступает на первый вход схемы

23 сравнения, на второй вход которой подается число i (на первом шаге

i=k) иэ счетчика в параллельном двоичном коде. Если r c i, то с выхода схемы сравнения на вход блока 22 элементов И выдается потенциал, который разрешает прохождение кода числа (k на первом шаге) с выхода счетчика через блок 26 элементов задержки на вход дешифратора 29. Каждый элемент задержки блока осуществляет задержку сигнала на время работы схемы сравнения. Дешифратор, после дешифрирования кода числа i, выдает на

i-e крайние справа выходы потенциалы, разрешающие прохождение через соответствующие -е крайние справа элементы И 30 группы импульсов, поступающих по шине 15 входного сигнала через открытый элемент И 16 и элемент 21 задержки, обеспечивающий задержку сигнала на время срабатывания блоков 22, 23, 26, 27 и 29, на соответствующие единичные входы триггера 1.

Одновременно задержанный импульс проходит через открытый потенциалом от схемы 23 сравнения элемент И 25 на единичный вход триггера 20, устанавливая его в единичное состояние.

При этом занрещается прохождение через элемент И 17 входных импульсов и разрешается их прохождение через элемент И 16 на Вход первого элемен7 та И 3 второй группы, обеспечивая перебор всех возможных сочетаний из и по i. Для перебора сочетаний из п по используется метод, основанный на образовании каждого нового сочетания из предыдущего путем замены крайней справа в регистре 1 комбинации 01 на "10" и переписи scex единиц, расположенных правее, в крайние правые позиции. По окончании перебора с выхода элемента ИЛИ !2 поступает сигнал, который устанавливает триггер

20 в нулевое состояние. При этом разрешается прохождение входных импульсов через второй элемент И 17 и запрещается их прохождение через первый элемент И 16, чем устройство подготавливается к работе на следующем шаге, Таким образом, обеспечивается пе1 ребор всех во ножных сочетаний оТ Г

Ь до С„", r l.

l 3979

Как только выполняется условие

r y i, так схема сравнения прекращает формирование разрешающего потенциала, импульсы по шине 15 через открытый элемент И 17 поступают на счетный вход счетчика 27, уменьшая

его состояние всякий раз на единицу.

При установке счетчика в нулевое состояние на выходе 14 снимается сигнал окончания перебора., 10 формула изобретения

Ф

Составитель О. Березикова

Техред Л. Сердюкова Корректор Н, Король

Редактор Е.Папп

Заказ 2601/49 Тираж 704 Подпи с но е

В11ИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Иосква, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

Устройство для перебора сочетаний 1В по авт ° св. У 1140127, о т.л и ч аю щ е е с я тем, что, с целью сокращения времени перебора сочетаний от

В

С„до С„, (r

36

4 начального состояния второго регист" ра, счетчика и второго триггера которого соединены с одноименными входами второго регистра, счетчика и второго триггера, единичный вход которого соединен с зыходом четвертого элемента И, первый вход которого соединен с выходом элемента, задержки и первыми входами элементов И пятой группы, вторые входы которых соединены с выходами дешифратора, входы которого соединены с вцходом блока элементов И, первый вход которого соединен с вторым входом четвертого элемента И и выходом схемы сравнения, первый вход которой соединен с выходом второго регистра, а второй ввод схемы сравнения соединен с выходом счетчика и входом блока элементов saдержки, выход которого соединен с вто,рым входом блока элементов И, счетный вход счетчика соединен с входом элемента задержки и въйсодом третьего элемента И, выходы элементов И пятой группы соединены с единичными входа" ми триггеров первого регистра, выход второго элемента И соединен с первыми входами первых элементов И второй и третьей групп и нулевым входом первого триггера, выход счетчика является выходом признака окончания работы устройства.