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

Союз Советских Социалистических Республик,гч е Ль 1448397/18-24) 5/ Заявле 09,71.1 исоедицецпем заявки рио тет Комитет по делам зобретеиий и открытий(73):519.272,6 396.96 (088.8) при Совете Мииисгров СССР. Китиер, Е аяшгт Киевский завод электронных вычислительных вляющих маши СОЧЕТАН СТРОЙСТВО ДЛЯ ПЕРЕ каскадов 1, 2 иов и схемы бло 25 Изобретение относится к вычислительной технике и может быть применено, например, в вычислительлгых машинах, решающих комбицаторцые задачи.Известны, устройства для перебора всех возможных сочетаний из ггг элемецтов по гг при постояивом значелгии а в процессе перебора,.При решении комбииатхорцых задач нельзя зараогее выбрать величину гг такой, чтобы можно было гарантировать, что решение, получсипое при данном порядке сочетаний, является оптимальным. Кроме того, моокет оказаться, что вообще невозможно получипь решецие нри данном порядочке сочетаний,Таким образом, постояцство величины. гг в процессе перебора ограничивает область сочетаций, что уменьшает возможности вычислительной машины по выбору решений,Цель изобретения - обеспечение последовательного перебора сочетаний при всех зцачециях и, начиная от едицицы.Сущность изобретения заключается в том, что выхюд переноса г-ого счетчика, кроме последнего, через г-ую схему блокировки и первую (г+1)-упо схемы ИЛИ соединен с входом (г+1) -ото счетчика, через г-ую схему И - с входом распределителя им 1 тульсов и через вторую г-ую схему ИЛИ - с входом первой гчой линии задержки, выход которой подключен и схеме передачи информации цз (г+1)-ого счетчцка в г-ый счетчики к входу второй г-ой линии задержки, выходкоторой через первую г-ую схему ИЛИ со 5 едицец с входом г-ого счетчика и через вторую (г - 1) -ую схему ИЛИ - с входомпервой (г - 1) -ой линии задержки, выход перецоса последнего счетчика соединен с входом установки начального состояния распре 10 делителя импульсов, а, вход первого счетчика через первую схему блокировки ц первуюсхему ИЛИ подключен к шине входцыхимпульсов,На чертеже представлена схема предлагаемого устройства для перебора сочетаний,которая обеспечивает перебор сочетаний прцгг, равном 1, 2 и 3.Устройство состоит из трех3, распределителя 4 импульс20 кцровки 5Первый каскад 1 включает в себя счетчик б, цметогций ггг состояний, схему блокировки 7, две схемы ИЛИ 8 и 9, две линиизадержки 10 и 11 и схему 12 передачи информации из счетчика И второго каскада,Второй каскад 2 содержит счетчик 13, имеющий ггг -состояний, схему блокировки 14,две схемы ИЛИ 15 и; 1 б, две линии задержки 17 и 8 и схему 19 передачи ицфор 30 мации из счетчика 10 третьего каскада.5 10 15 20 25 30 35 40 45 50 55 3Третий каскад 3 содержит счетчик 20,имеющий и - 2 состояний и схему ИЛИ 21.Распределитель 4 импульсов состоит изтриггеров 22, 23 и 24, схем переписи 25 и 26на входах этих триггеров, схемы ИЛИ 27и схем И 28, 29.Устройство содержит также шину 30 подключения входных импульсов.Устройство работает следующим образом.В начальный момент счетчики 6, 13 и 20установлены в нулевое состонние, Перед подачей серии импульсов по шине 30 на входсхемы блокировки 5 триггер 22 распределителя 4 импульсов устанавливается в 1, разрешая тем самым начало работы.Импульсы с шины 30 через схему блокировки 5 и схему ИЛИ 9 поступают на входсчетчика 6.Импульсом переполнения является т-ыйимпульс, который свидетельствует о том, чтоперебор сочетаний из т по 1 окончен.Этот импульс, пройдя через схему ИЛИ8, линию задержки 10 и схему 12, обеспечивает передачу содержимого счетчика 13 всчетчик 6, а затем, пройдя через вторую линию задержки 11 и схему ИЛИ 9, обеспечивает прибавление единицы к содержимомусчетчика 6,Кроме того, т-ый импульс с выхода счетчика 6 поступает на вход схемы И 28, проходит ее на, разрешающем потенциале триггера 23, а затем через схему ИЛИ 27 исхему переписи 25 производит запись единицы в триггер 23. С этого момента начинается перебор сочетаний из и элементов по 2.При этом в начальный момент в счетчике 13записан корд нуля, а в счетчике 6 - код единицы,.Теперь всякий раз при, переполнении счетчика 6 импульс переполнения проходит черезсхему блокировки 7 при разрешающем потенциале триггера 23 и, кроме того, обеспечивает передачу содержимого счетчика 13 всчетчик 6 с добавлением единицы к содержиьмому последнего так, как это было описановыше.Такой перебор сочетаний при и=2 продолжается до тех пор, пока состояния счетчиков6 и 13 станут равными соответственно т ит - 1,Следующий входной импульс приводит кпоявлению импульса переполнениями на выходе счетчика 13. Этот импульс переполненияобеспечивает передачу содержимого счетчика 20 в счетчик 13 с добавлением единицык содержимому последнего так, как это описано выше. Кроме того, с линии задержки 18импульс поступает на вход схемы ИЛИ 8,что, в свою очередь, приводит к передаче содержимого счетчика 13 в счетчик 6 с добавлением единицы к содержимому последнего. Импульс переполнения, пройдя через схему И 29 на разрешающем потенциале триггера 24, схему ИЛИ 27 и схему переписи 26, производит запись единицы в триггер 24. С этого момента, начинается перебор сочетаний из т элементов по 3, При этом в начальный момент в счетчике 20 записан код нуля, в счетчике 13 - код единицы, а в счетчике 6 - код двойки,Импульс переполнения на выходе счетчика 20 появляется после того, как состояния счетчиков 6, 13 и 20 станут равными соответственно т, т - 1, т - 2, Этот импульс переполнения сипнализирует об окончаниии перебора сочетаний из т элементов по 3 и поэтому поступает на сброс бриггеров распределителя 4 импульсов.Таким образом, устройство обеспечивает последовательный перебор сочетаний при всех значевиях и, начиная от единицы.Выходы триггеров распределителя импульсов могут анализироваться вычислительной машиной для определения текущего значения и. Предмет изобретенияУстройство для перебора сочетаний, содержащее счетчики с коэффициентами пересчета, изменяющимися на единицу, схемы, передачи информации, линии задержки, логические схемы и распределитель импульсов, отличающееся тем, что, с целью осуществления перебора всех возможных сочетаний из т элементов по и при переменном и, выхорд переноса 1-ого счетчика, кроме последнего, через 1-ую схему блокировки и. первую (1+1) -ую схему ИЛИ соединен с входом (1+1)-ого счетчика, через 1-ую схему И - с входом распределителя импульсов и через вторую г-ую схемы ИЛИ - с вюдом первой г-ой линии задержки, выход которой подключен к схеме передачи информации, из (1+1)-ого счетчика в ю-ый счетчик и к входу второй г-ой линии задержки, выход которой через первую 1-ую схему ИЛИ соединен с входом 1-ого счетчика и через вторую (1 - 1) -ую схему ИЛИ - с входом первой (с - 1) -ой линии задержки, выход переноса последнего счетчика соединен с вюдом установки начального состояния распределителя импульсов, а вход первого счетчика через первую схему блокировки и первую схему ИЛИ подключен к шине входных импуль. сов.Редактор Т. Иванова Корректор О. Усова Типография, пр, Сапунова, 2 Заказ 1552/3 Изд. И 400 Тираж 647 ПодписноеЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР Москва, Ж-З 5, Раушская наб., д. 4/5