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

 

ОПИСАН

ИЗОБРЕТЕ

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

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

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬ (61) Дополнительное к авт. свид-в (22) Заявлено 110477 (2l) 2473384/ с присоединением заявки И(23) ПриоритетОпубликовано 050479.Бюллете

Дата опубликования описания

Государственный комитет

С С.CP

flo делам изобретений и открытий (72) Автор изобретения

В.A.Hoãàòûðåâ

Особое конструкторское бюро технической кибернетики

Ленинградского ордена Ленина политехнического института имени М.И.Калинина

{73) Заявитель (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ

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

Известно устройство для перебора сочетаний, содержащее узел блокировки, триггер, элементы ИЛИ. задержки и последовательно соединенные кольцевые счетчики (1) °

Однако с его помощью нельзя производить перебор перестановок и пере" становок с повторением.

Наиболее близким к данному изобретению по техническому решению являет- IS ся устройство, содержащее п последовательно соединенных в кольцо регистров исходных чисел, выходы которых являются выходами устройства f2)..

Однако с помощью известного устройства для перебора сочетаний нереа.лизуем перебор всевозможных перестановок кодов и перестановок с повторением.

Надежность известного устройства невысока, так как сбой, возникающий на любом такте, приводит к неправильному функционированию устройства на всех остальных тактах, вслед- Ю ствие рекуррентности перебора, организованного в нем.

Цель изобретения — упрощение устройства и повышение надежности его работы.

Поставленная цель достигается тем, что устройство содержит элемент И, дополнительный регистр, регистр сдвига, блок памяти, h-1 выходов которого соединены с установочными входами

h 1 регистров исходных чисел, начиная со второго, адресные входы блока памяти подключены к выходам регистра сдвига, выход дополнительного регистра соединен с первым входом элемента И, выход п-го регистра исходных чисел соединен с вторым входом элемента И, выходом соединенного с тактовым входом регистра сдвига, тактовые входы всех и регистров исходных чисел соединены между собой и являются тактовым входом устройства.

На чертеже представлена блок-схема устройства, которое -содержит регистр сдвига 1, элемент И 2, блок памяти 3, соединенные в кольцо регистры исходных чисел 41, 4р 4п, дополнительный регистр 5.

656057 п!

Работа устройства заключается в следующем.

Для перебора кодов al, а2, а3, ....an один иэ кодов, например, al, заносится в регистр 41и регистр 5, остальные коды а2, a3,....an занс° сятся в регистры 41, 4>, .... 4 .

Во второй разряд регистра сдвига

1 записывается единица. В блок памяти 3 заносятся перестановки кодов а2, а3,...an, кроме одной заносимой в регистры 4, 4,.... 4, т.е.

)О в блок памяти 3 заносится всего ((n-l)!) перестановок кодов.

При поступлении импульсов на вхо} ы тактовых импульсов, соединенных в кольцо регистров 4, организуется перепись содержимого регистра 4! в регистр 4;,.1, содержите последнего РегистРа 4 п пеРеписываетсЯ в первый регистр 41 до тех пор, пока в регистре 4в не образуется код,эапи-20 санный в регистре 5, в этом случае сигналам с элемента И 2 осуществляется выдача содержимого ячейки блока памяти 3, адрес которой определяется разрядом нахождения единнщн в 25 регистре сдвига 1, затем происходит сдвиг единнща в регистре 1 в следующий разряд.

Содержимое ячейки блока памяти, выданное по сигналу элемента и 2 записывается в регистры 4, 4э ° ..., 4я. В регистре 41 остается код, записанный с регистра 4н. Процесс перебора продолжается, как описано вьвж до его эаверщення,. в последнем цикле единица с последнего разряда регистра сдвига 1 будет переписана в его первый разряд.

В качестве примера рассмотрим перебор перестановок кодов

1234 40

Занесем в регистры 41 н 5, например, код 1. В блок памяти 3 запишем перестановки кодов 2 3 4 — первая 2 3 4, записывается в регистры 4. В блоке памяти 3 запишется всего (n-1)! — 45

-3<-6 перестановок кодов:

2 3 4

2 4 3

3 4 2

3 2 4 50

4 2 3

4 3 2

При переборе образуются перестановки кодов в следующем порядке: перестановки кодов б 55

1234 0

4123 0

3412 0

2341 1

1243 0

3124 0 60

4312 О

2431 1

1342 0

2134 0

4213 0 65

3421 1

1324 0

4132 0

2413 0

3241 1

1423 . 0

3142 0

2314 0

4231 1

1432 0

2I43 0

3214 0

4321 1

Итого вырабатываются все перестановки в количестве и!ю4! = 24. Через

d i обозначено наличие сигнала на выходе элемента И 2.

Перебор перестановок с повторяющимися элементами, число которых равно п

Например, если перебираются перестановки кодов

2 l 1 1 2, занесем в регистры 5, 41 код 2, а в блок памяти перестановки осталь- ных кодов 1111.,"

1112

l12l

1211

2lll число которых определяется как

Перебор кодов:

2 1 1 1 2 в этом случае производится в следующем порядке: д

21112 1

21121 0

12112 1

21211 0

12121 0

11212 1

22111 0

12211 0

11221 0

11122 1

На вто« перебор всех -З4 вЂ, — « 40 перестановок с повторяющимися элементами.

Перебор сочетаний сводится к перебору перестановок с повторениями

656057

Формула изобретения

Составитель В.Евстигнеев

Техред Л.Алферова Корректор М.Ряшко

Редактор С.Равва

Тираж 779 Подписное

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

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

Заказ 1523/39

Филиал ППП Патент, г.ужгород, ул. Проектная, 4,д случае двух типов элементов О и 1 .

Посредством предложенного устройства реализуем перебор сочетаний, перестановок и перестановок с повторяющимися элементами, в то время как известное устройство позволяет осуществить перебор только сочетаний. Предложенное устройство по сравнению с известным характеризуется повышенной надежностью, так как сбой в нем приводит к получению оши- 10 бочного результата только в период до записи в регистры, соединенные в кольцо информации снимаемой с блока памяти З,после чего восстанавливается правильное функционирование устрой-- 5 ства.

Устройство для перебора сочетаний, содержащее и последовательно соединенных в кольцо регистров исходных чисел, выходы которых являются выходами устройства, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства и повышения надежности его работы, оно содержит элемент И, дополнительный регистр, регистр сдвига, блок памяти, и-1 выходов которого соединены с установочными входами и-1 регистров исходных чисел, начиная со второго, адресные входы блока памяти подключены к выходам регистра сдвига, выход дополнительного регистра соединен с первым входом элемента И, выход Il-го регистра исходных чисел соединен со вторым входом элемента И, выходом,соединенного с тактовым входом регистра сдвига, тактовые входы всех и регистров исходных чисел соединены между собой и являются тактовым входом устройства.

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

9525100, кл. G 06 F 15/32, 1976.

2. Авторское свидетельство СССР

9446057, кл. G 06 F 7/38, 1975.