УСТРОЙСТВО для ПЕРЕБОРА СОЧЕТАНИЙ Советский патент 1973 года по МПК G06F17/10 

1

Изо|бретени.е относится к вычислительной техни1ке и может быть применено, например, в вы;чи1слителы1ы,х машииа.х, решающих КОМ:бииатор.иые задачи.

Известны, устройства для перебора всех возможиъгх сочетаинй из т элеменТ)01В по п при постоя1нном З-начеиии я в nipouecce перебора:.

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

Такнм o6pai30iM, постоянство величияы: п в процессе перебора огра П1Ичи.вает область сочетаний, что уме-иьша ет вюзможности вычислительной машины по выбору решений.

Цель нзобр,етения - обеспечение последовательного перебора сочетаний при всех значениях п, вачИНая от еди1ницы.

Сущность изобрете.ння заключа.ется в том, что выход переноса г-ого счетчюса, к.рО:ме последнего, через г-ую схему блокировки и первую (/+l)-yao схемы «ИЛИ соединен с вхоДО|М (/-|-1) счетчика, через i-ую схему «И - с входом распределит1еля импульсов и через вторую г-ую схему «ИЛИ - с входом первой i-ой линии задержки, выход

которой подключен к схеме передачи информации из (г-|-1)-ого счетчн1ка в i-ый счетчик и к входу второй /-ой лн.нии задержки, которой через первую г-ую схему «ИЛИ соединен с входом i-oro счетчика к через вторую (/-1)-ую схему с входом пер1вой (i-1)-ой линии задержки, вы.ход переноса последнего счетч,ика соедиашИ с BXOiДО1М ycTaiHOBKH начального состоя:ния распре0делителя и.мпульсов, а. вход первого счетчика через первую схему блокировки и первую схе-му «ИЛИ п од колюч с н к ши;не В;ходны х импульсов. На чертеже представлена схема предлагаемого устройства для перебора сочетаний, которая обеспечнвает перебор сочетаний при п, равном 1, 2 и 3.

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

Первый каскад / включает в себя счетчик 6, имеющий т состояний, схему блокировки 7, две схемы «11ЛИ 8 И 9, две ли:нии задержки /О и // и схему /2 передачи формадии из счетчика 13 второго каскада. Второй каскад 2 содержит счетчик 13, имеющий m-1 состояний, схему блокировки 14, две схемы. «ИЛИ /5 и, /б, две лииии задержки 17 и 18 .и схему 19 передачи информация из счетчика 10 третьего каскада,.

0 Третий каскад 3 содержит счетчик 20, имеющий т-2 состояний и схему «ИЛИ 21. Распределитель 4 Импульсов состоит из триггеров 22, 23 и 24, схем переписи- 25 и 26 на входах этих триггеров, схемы «ИЛИ 27 и схем «И 28, 29. Устройство содержит также ши.ну 30 подключеиия ВХОДиьгх импульсов. Устройство ра|ботает следующим образом. В На|4аль:ный момент счетчики 6, 13 и 20 установлены в нулевое состоящие. Перед подачей серии импульсов по щи-не 30 на вход схемы блокировки 5 триггер 22 распределителя 4 импульсов устанавлив.ается в «1, разрешая тем самы-м начало работы. Импульсы с щины 30 через схему блокировки 5 и схему «ИЛИ 9 поступают на вход счетчика 6. Импульсом переполнения является т-ъш импульс, который свидетельствует о том, что перебор сочетаний из т по 1 окончен. Этот имнульс, П1ройдя через схему «ИЛИ 8, линию задержки 10 и схему 12, обеспечивает передачу содержимого счетчика 13 в счетчик б, а затем, пройдя через вторую линию задержки Id и схему «ИЛИ 9, обеспечивает прибавление единицы к содержимому счетчика 6. Кроме того, т-ый импульс с выхода счетчика 6 поступает па вход схемы «И 28, проходит ее на. разрешающем потенциале триггера 23, а затем через схему «ИЛИ 27 и схему переписи 25 производит запись единицы в триггер 23. С этого момента на.чи-нается перебор сочетаний иэ т элементов по 2. При этом в начальный момент в счетчике 13 затиса.н код нуля, а в счетчике 6 - код единицы. Теперь всякий раз при: переполнении счетчика 6 импульс переполнения проходит через схему блокировки 7 при разрешающем потенциале триггера 23 и, кроме того, обеспечивает передачу содержимого счетчика 13 в счетчи,к 6 с добавлением единицы к содержи мому последнего так, мак это было отисано выще; Такой перебор сочетаний при п 2 продолжается до тех пор, пока состояния счетчиков 6 и 13 станут равными соответственно т и Следующий входной импульс приводит к появлению импульса переполнения на выходе счетчика 13. Этот импульс переполнения обеспечивает передачу содержимого счетчика 20 в счетчик 13 с добавлением единицы к содержимому последнего так, как это описано выше. KpoiMe того, с линии задержки 18 имцульс поступает на вход схемы «ИЛИ 8, что, в свою очередь, приводит к передаче Содержимого счетчика 13 в счетчик 6 с добавлением единицы к содержимому последнего. Импульс переполнения, пройдя через схему «И 29 на разрещающем потенциале триггера 24, схему «ИЛИ 27 и схему переписи 26, производит запись единицы в триггер 24. С этого момента; начинается перебор сочетаний из т элементов по 3. При этом в начальНЫЙ1 момент в счетчике 20 записан код нуля, в счетчике /5-код единицы, а в счетчике 6- код двойки. Имнульс переполнения на вы.ходе счетчика 20 появляется после того, как состояния счетчиков 6, 13 И 20 станут равными соответственно т, т-1, т-2. Этот импульс переполнения сигнализирует об окончании перебора сочетаний из m элементов по 3 и поэтому поступает на сброс триггеров распределителя 4 импульсов. Таким образом, устройство обеспечивает последовательный перебор сочетаний при всех зща(4ен1иях п, начиная- от единицы. Выходы триггеров раснределителя импульсов могут анализироватъся вьтислительной мащиной для определения текущего значения п. Предмет изобретения Устройство для перебора сочетаний, содержащее счетчики с коэффициентами пересчета, изменяющимися на единицу, схемы, передали информации, линии задерж1ки, логические схемы и распределитель импульсов, отличающееся тем, что, с целью осуществления перебора всех возможных сочетаний ив т элементов по п при переменном п, выход переноса t-oro счетчика, кроме последнего, через г-ую схему блокировки и. первую (г+1)-у|ю схему «ИЛИ соединен с входом (г-|-1)-ого счетчика, через z-ую схему «И - с входом распределителя импульсов и через вторую г-ую схемы входом первой г-ой линии задержки, выход которой под ключен к схеме передачи информации, из (г+1)-ого счетчика в /-ый счетчик и к входу второй f-ой линии задержки, выход которой через первую г-ую схему соединен с входом г-ого счетчика и через вторую (/-1)-ую схему «ИЛИ - с входом первой (г-1)-ой линии задержки, выход переноса последнего счетчика соединен с вхюдом устаHOBiKH начального состояния раснределителя импульсов, а вход первого счетчика через первую схему блокировки и первую схему «ИЛИ подключен к щине входных импульсов.

3D