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

 

5ATE, .-.. " ;::: . таад я бибтти хз,м Ь,1вч

ОЛИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Союз Советских

Социалистических

Ресоублик

Зависимое от авт. свидетельства №вЂ”

Заявлено 09,VI.1970 (№ 1448397/18-24) с присоединением заявки №вЂ”

М. Кл. 6 06f 15/32

Приоритет

Комитет оо делам изобретеиий и открытий ори Совете Микис!ров

СССР

Опубликовано 20.111.1973. Бюллсте!!ь ¹ 15

Дата опубликования описания ЗОХ.1973

УДК 681.323. (088.8) (73):519.272,621. .396.96 (088.8) Авторы изобретения

А. Б. Китнер, Е. 3. Мазур и В. И. Сигалов

Заявитель Киевский завод электронных вычислительных и управляющих машин

УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ

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

Известны, устройства для перебора. всех возмю>кных сочетаний из m элементо!в по и при постоя!нном ".íà÷åíèè а в процессе перебора,.

При решении комбинаторных задач нельзя заранее выбрать величину и такой, чтобы можно было гарантировать, что решение, получе!!ное при данном порядке сочетаний, BBляется оптимальным. Кроме того, может оказаться, что вообще невозможно получипь решение при данном порядке сочетаний.

Таким обра!зо!м, поспоянство величины: и в процессе перебо!ра ограничивает область сочетаний, что уменьшает в!озмо>кности вычислительной машины по выбору решений, Цель изобретения — обеспечение последо.вательного перебора сочетаний при всех значениях и, начиная от еди ницы.

Сущность изобретения заключается в том, что выход переноса i-ого счетчика, кроме последнего, через i-ую схему блокировки и первую (i+1)-у!то схемы «ИЛИ» соединен с входом (i+1)-oro счетчика, через i-ую схему «И» — с входом распределителя им1пульсов и через вторую i-ую схему «ИЛȻ— с входом первой i-!ой линии задержки, выход которо1! По;\кл!о !ен к схeме передачи информации нз (i+1)-îãî счетчика в i-ый счетчик и к входу второй !-ой линии задержки, выход которой через нерв!ую l-ую схему «ИЛИ» соединен с входом i-ого счетчика и через вторую (! — 1) -ую схему «ИЛИ» — с входом первой (i — 1) -ой линии задср>кки, выход переноса последнего счетчика соединен с входо!м установки начального состояния распределителя импульсов, а. вход первого счетчика через первую схему блокировки н первую схему «ИЛИ» подключен к шине входных импульсов.

H а чертеже представлена! схема п р едлагаемого устройства для перебора сочетаний, кот!оран обеспечивает перебор сочетаний прн н равном 1, 2 и 3.

Устройство состоит из трех каскадов 1, 2 и >, распределителя 4 импульсов и схемы бло20 кнровки 5.

Первый каскад 1 включает в себя счетчик б, имеющий ттт состояпи!!, cxeM) блокировки 7, две схемы «ИЛИ» 8 и 9, две линии задержки 10 и 11 и схему 12 передачи информации из счетчика 1 > второго каскада.

Второй каскад 2 содержит счетчик 18, имеющий m — состояний, схему блокировки 14, две схемы «ИЛИ» 15 и, 1б, две линии задержки 17 и !8 и схему 19 передачи инфор30 мации из счетчика 10 третьего каскада..

374606

l0

3

Третий каскад 8 содержит счетчик 20, имеющий т — 2 состояний и схему «ИЛИ» 21.

Распределитель 4 импульсов состоит из триггеров 22, 28 и 24, схем переписи: 25 и 26 на входах этих триггеров, схемы «ИЛИ» 27 и схем «И» 28, 29.

Устройство содержит также шину 80 подключения входных импульсов.

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

В начальный момент счетчики 6, 13 и 20 установлены в нулевое со стонн ие. Перед подачей серии импульсов по шине 80 на вход схемы блокировки 5 триггер 22 распределителя 4 импульсов устанавливается в «1», разрешая тем самым .начало работы.

Импульсы с шины 80 через схему блокировки 5 и схему «ИЛИ» 9 поступают на вход счетчика 6.

Импульсом переполнения является т-ый импульс, который свидетельствует о том, что перебор сочетаний из т по 1 око|нчен.

Этот импульс, пройдя через схему «ИЛИ»

8, линию задержки 10 и схему 12, обеспечивает передачу содержимого счетчика 18 в счетчик 6, а затем, пройдя через вторую линию задержки 11 и схему «ИЛИ» 9, обеспечивает прибавление единицы к содержимому счетчика 6.

Кроме того, т-ый импульс с выхода счетчика 6 поступает на вход схемы «И» 28, проходит ее на, разрешающем потенциале триггера 28, а затем через схему «ИЛИ» 27 и схему переписи 25 производит запись единицы в триггер 28. С этого момента начинается перебор сочетаний из m элементов по 2.

При этом в начальный момент в счетчике И за писан код нуля, а в счетчике 6 — .код единицы,.

Теперь всякий раз при, переполне нии счетчика 6 импульс переполнения проходит через схему блокировки 7 при разрешающем потенциале триггера 28 и, кроме того, обеспечивает передачу содержимого счетчика 18 в счетчик 6 с добавлением единицы к содержи мому последнего так, как это было о|писано выше.

Такой перебор сочетаний при и=2 продолжается до тех пор, пока состояния счетчиков

6 и 13 станут равными соответственно m u т — 1.

Следующий входной импульс приводит к появлению импульса переполнениями на выходе счетчика 18. Этот импульс переполне|ния обеспечивает передачу содержимого счетчика 20 в счетчик 18 с добавлением единицы к содержимому последнего так, как это описан о выше. KpoiMe того, с линии задержки 18 импульс поступает на вход схемы «ИЛИ» 8, что, в свою очередь, приводит к передаче содержимого счетчика 13 в счетчик 6 с добавлением единицы к содержимому по следнего.

Импульс переполнения, пройдя через схему

«И» 29 на разрешающем потенциале триггера 24, схему «ИЛИ» 27 и схему переписи

26, производит запись единицы в тр иггер 24.

С этого момента, начинается перебор сочетаний из m элементов по 8. При этом в начальный момент в счетчике 20 записан код нуля, в счетчике И вЂ” код единицы, а в счетчике 6— код двойки.

Импульс переполнения на выходе счетчика 20 появляется после того, как состояния счетчиков 6, 18 и 20 станут равными соответственно m, m — 1, m — 2. Этот импульс переполнения сипнализирует об окончании перебора сочета ний из m элементов по 8 и поэтому поступает на сброс триггеров ра спределителя 4 импульсов.

Таким образом, устройство обеспечивает последовательный перебор сочетаний при всех значевиях и, начиная от единицы.

Выходы триггеров распределителя импульсов могут анализироваться вычислительной машино|й для определения текущего значения и.

Предмет изобретения

Устрой ство для перебора сочетаний, содержащее счетчики с коэффициентами пересчета, из меняющимися на единицу, схемы, передачи информации, линии задержки, логические схемы и распределитель импульсов, отличающееся тем, что, с целью осуществления перебора всех возможных сочета ний и з т элементов по и при переменном и, выход переноса i-ого счетчика, кроме последнего, через i-ую схему блокировки и. первую (i+1)-ym схему «ИЛИ» соединен с входом (i+1)- ого счетчика, через i-ую схему «И»вЂ” с входом распределителя импульсов и через вторую l-ую схемы «ИЛИ» — с вюдом первой

1-ой линии задержки, выход которой под ключен к схеме передачи информации, из (i+1)-oro счетчика в 1-ый счетчик и к входу второй i-ой ли нии задержки, выход которой через первую i-ую схему «ИЛИ» соединен с входом 1-ого .счетчика и через вторую (i — 1)-ую схему «ИЛИ» — с входом первой (— 1)-ой линии задержки, выход переноса последнего счетчика соединен с вюдом установки начальн ого состояния распределителя импульсов, а вход первого счетчика через первую схему блокировки и первую схему

«ИЛИ» подключен к шине входных импульсов.

374606

Составитель И. Долгушева

Техред Л. Грачева

Редактор Т. Иванова

Корректор О. Усова

Заказ 1552/3 Изд. ¹ 400 Тираж 647 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР

Москва, Я-35, Раушская наб., д. 4/5

Типография, пр. Сапунова, 2