Устройство для перебора сочетаний, размещений и перестановок Советский патент 1979 года по МПК G06F15/20 

рого триггера и первого элемента И, второй вход которого подкгаочен к первому быходу генератЬра импульсов, выход первого элемента И подключен к прямому pemcTpai сдвига, второй выход Генератора импульсов подключен к первому Входу второго элемента И, вт рой вХод которого подключен к iPTuporo триггера н второму вход/ элемента ИЛЙ| выход которого подключен ко входу генератЬра импульсов, третьи входы nejpBoro н второго триггеров черва пережлючатвЯь соединены с соответ ствующими входами регистра сдвига, вы ход второго элемевта И соединен с инверсным входом регистра сдвига, выходы зайоминакадей матрицы через последоватейиао соединенные бпсж формирова телей, хоммзггатор и блок деления подключены It выходному регистру, выходы блока управления, соединеньт с управлякяшши вхьдамн блока делешш н коммута1ч)ра. Такое устройство йе содержит элементов задержки, что позволяет осуществпят1ь перебор , размещений ч пе1р«:тйнйвок с йреышенным быст родействием . Кроме того, устройство зшрактериэуется простотой кой(5трукщга. Схема apeartaraeMOfrb устройства пре стб|Впеца на чертеже. Оно содержит запомикакшую матрицу 1 регистр сдвига 2, элементы И 3 и 4, тр гГеры 5 и б гейератор тактрВых импульсов 7, элемент ИЛИ 6, бйок формирователей 9, в которых формир отся коды элементов а| , выходной регистр 10, переключэтел)ь li, с01иму1 атор 12, блок делеиия 13. блок управления 14. Вход три гера 5 соединен с пусковой шиной устройства 15. Количество горизонтальных 1йин, а следовательно и количество разрядов ре гибгра сдвига равно Р. - - ,где j - исло элементов в членах тйхитедо вагельностн. Для перебора перестановок (так как ) все контакты коммутатора }2 аамкнутьи Для размешений А, сочеташй С размыкаются ксжтактов коммутатора 12, начиная с i) разряда. Соединения горизонтальных и вертвкашыных вши запоминающей матрицы 1 в узлах вы&оонены образом, 4to квущва, ооследовательвость комбин торныхчленов высшего шслючает в себя последовательность низшего порядка. Горизонтальные шины запоминакнцей матрицы 1 подключены к соот- ветствуюишм разрядам регистра сдвига 2, а вертикальные щииы - к входам блока формирователей 9. С выоюдов Iffct разрядов реверсивного распределителя 2 сделаны отводы, подключаемые через переключатель 11 (с помощью которого устанавливается длина последовательноста) к входам триггеров 5 и 6. Р отает устройство следующим об разом. В зависимости рт типа решаемой задачи, то есть перебора перестановок, размещений нли сочетаний, в блок деления 13 заносятся соответственно одно из чисел ( h -К )Г или %( И ti )| . В зависимости от раамёрнсхля гевероруемой устройством посйедовател1Жостя переключатель 11 устанавш1Вае1гся Si иопожение lik /2 , а is коммутаторе 12 командой с блока упре.вления 14 otKinaOf чаются разряды с номерами бсотьше 1( При подаете пускового сигнала на йшну 15 перебрасываетсй триггер 5, ГЕая , с его выхода подается на а емента И 3 и через схему ИЛИ 8 запускает генератор импульсов 7, HieTyJibfcbi isotopo го через элемент И 3 шадаютса aja вход репютра сдвига 2, кьЕЭвтая тем самым ш очередасю cpafiafbffit e его разрядов и поавление на горЯБЗсютальных шинахза1 омвна|сш1ей1мат жоы 1 сигналов, которые й стуяа от через соединения в узлаХ матршы 1 в ее эер тикальные шины на соответстйукша формирователи бпока фор1|1шрЬвателей 9.... ; При срабатываний Р регистра сдвага 2 снгнаи с выхода ётого разряда подтверждает состояние триггера 5. этот же сигнал через первую вертшсайьвухэ шину запоминающей Матрияы 1 шхяу- пит на формирователь Q,, формирователей 9 и через коммутатор 12| соответствукшшй элементу Й , коя подается в блок деления 13. Так как в режиме генерирования перестаяоыж в блоке деления 13 записана 1% то код а проходит на вход ««одного регистра 1О. При переключенЕш второго, в aeefett третьего разрядов регвстра сШзага 2, аналогичным ва вход ашсоош Ч регистра Ю пос упакп коды 8леме1ггю а иоз Поскольку на чертеже показаны замкнутыми толысо те контакты коммутато ра 12. которые соответствуют формиров J, Ъ то на выходном регастре 10 аа девять тактов переключения распределителя 2 зафиксируются члены С1 o,j Olj J 0|а О( Ol /a ajOfa при срабатывашяи девятого разряда регистра сдвига 2 сигнал через переклю чатель 11 перебросит триггер 5 в исходное состояние, снимая тем самым разрешающий сигнал С элемента И 3 и прекращая подачу импульсов на прямой вход регистра сдвига 2. Одновременно сигнал с переключател 11 перебросит триггер 6, с выхода которого, поступит разрешающий сигнал на элемент И 4, и через элемент ИЛИ 8, подтвердится запуск генератора импульсов 7. Следовательно, импульсы с выхода генератора 7 через элемент И 4 начнут поступать на реверсивный вход регистра сдбига 2- Переключе1ше разрядов регистра сдвига 2 осуществляетс при 9ТОМ в обратном порядке и согласно информавйй, записанной в матрице 1 на выходном регистре зафиксируются члены do Of . d ol oi 2 0г°2 a-i абаг: При срабатывании первого р разряда регистра сдвига 2 триггер 5 перебрасывается в исходное состояние, перебрасывая своим выходом триггер 6. В результате чего снимается разрешающий сигнал с апемента И 4 и прекращается поступление импульсов с выхода генератора 7 на ев«рсивнь1й вход регистра сдвига 2. Таким образом, на выходной регистр будет вьадана последовательность из шести членов, явлйюшаяся перестановко трёх элементов с, 01 д , . Аналогично устройство работает при II 3. В режим® генерирования размещений в блок деления 13 заносится число ( «-14 )). Работа устройства в этом режиме с сущёС1 ляется аналогично вышеописанному. Однако йа выходной регистр поступают не всё И членов генерируе- МоЙ1йесестанбвкв:; а только - , так как А J, « . , - здесь используется известная зависимость, то есть число размещений А равно числу nepecf айойок, деленное на С И - ) В этом режиме работы устройства лропускйются члены перестановки, не вхр/шошё в данное разм аение. В режиме генерирования сочетаний в блок деления 13 заносится число R (и-1 )I по аналогии с режимом генерирования размещений на выходной регистр выводятся не все И членов перестановок, а только {(..у) . то есть число сочетаний из Я элементов по Ki.cJ, .Ф о р м у л а изобретения Устройство для перебора сочетаний, размещений и перестановок, содержащее запоминающую матрицу, управляющие входы которой соединены с сооТБётб вующими выходами реверсивного регистра сдвига, генератор тактовых импульсов, элементы И, ИЛ|1, триггеры, переключатель, коммутатор, блок управления, выходной регистр, отличающеес я тем, что, с целью повышения быстродействия и упрощения устройства, ,. оно содержит блок формирователей, блок деле1шя, причем пусковая 1иина устройства соединена с первым входом первого триггера, второй вход которого подключен к первому выходу реверсивного регистра сдвига, выход первого триггера подключен к первым входам элемента ИЛИ, второго триггера и первого эле мента И, второй вход которЬгй прд- ключен к первому выходу генератора импульсов, выход первого элемента И подключен к прямому взсоду регистра сдвига. Второй выход генератора импульсов подключен к первому входу второго элемента И, второй вход которого подключен к выходу второго триггера и второму входу элемента ИЛИ выход которого подключен кр входу генератора импульсов. Третьи первого и второго триггеров через переключатель соединены с соответстувующими входами регистра сдвига, выход второго элемента И соединен с инверсН1г1М входс м регистра сдвига, выходы запоминающей матрицы через последовательно соединенные блок формирователей, коммутатор и блок деления подключены к выходному регистру, выгходы блока управления соединены с управлякшшми входами блока деления и коммутатора. Источники ввформашш, принятые во внимание п{ш экспертизе. 1.Авторское свидетельство СССР № 5251ОО, кл. Q Об Р 15/32, 25.12.74.; 2.Авторское свидетельство СССР № 525948, кл, Q 06 f 7/ОО, ОЗ.09.73.

.--;- - «.. . ,