Устройство для перебора сочетаний — SU 656057 (original) (raw)
ОПИСАН ИЗОБРЕТЕ Союз Советских Социалистических Республик) Заявлено 110477 (21) 2473384 с присоединением заявк Государственный комитет С С.СР ио делам изобретений и открытий) Автор етениа В.А.Богатырев Особое конструкторское бюро технической кибернетикиЛенинградского ордена Ленина политехнического института имени М.И.Калинина 3) Заявите(54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАН н я - упрощение уе надежности ег тем,представлена блок-схекоторое -содержит 1, элемент И 2, блок иненные в кольцо регистл 41 4 фрегистр 5 ертежеойствасдвиг3, соеддных чтельный ма уст регист памяти ры исх дополн о устройства воэникаюводит к неванию устройтактах, вслед- ЮНадежность известно невысока, так как сбой щий на любом такте, пр правильному функциониро ства на всех остальныхИзобретение относится к вычислительной технике и может быть применено в специализированных вычислительных машинах, предназначенных для решения задач переборного характера.Известно устройство для перебора сочетаний, содержащее узел блокировки, триггер, элементы ИЛИ. задержки и последовательно соединенные кольцевые счетчики 11Однако с его помощью нельзя производить перебор перестановок и пере" становок с повторением.Наиболее близким к данному изобретению по техническому решению являет ся устройство, содержащее п последовательно соединенных и кольцо регистров исходных чисел, выходы которых являются выходгми устройства 12.Однако с помощью известного устройства для перебора сочетаний нереа.лизуем перебор всевозможных перестановок кодов и перестановок с повторением,вие рек перебора, оргаизованноЦель и стройства и о работы.Поставленная цель достигается что устройство содержит элемент И, дополнительный регистр, регистр сдвига, блок памяти, Ьвыходов которого соединены с установочными входами Ьрегистров исходных чисел, начиная со второго, адресные входы блока памяти подключены к выходам регистра сдвига, выход дополнительного регистра соединен с первым входом элемента И, выход и-го регистра исходных чисел соединен с вторым входом элемента И, выходом соединенного с тактовым входом регистра сдвига,тактовые входы всех и регистров исходных чисел соединены между собой и являются тактовым входом устроЯ- ства.656057 44 Работа устройства заключаетсяв следующем.Для перебора кодов а 1, а 2, аЗ,ан один иэ кодов, например, а 1,заносится в регистр 41 и регистр 5,остальные коды а 2, аЗ,ап занс сятся в Регистры 4 ф 4 в4 п5Во второй разряд регистра сдвига1 записывается единица. В блок памяти 3 заносятся перестановки кодова 2, аЗ,ап, кроме одной заносимой в регистры 4, 4 ,. 4 п , т.е.(и) перестановок кодов.При поступлении импульсов на вхо)1 Ы таКтОВЫХ НМПУЛЬСОВа СОЕДИНЕННЫХв кольцо регистров 4, организуетсяперепись содержимого регистра 4;в регистр 4;1, содержиьюе последнего Регистра 4переписывается впервый регистр 44 до тех пор, покав регистре 4не образуется код,эаписанный в регистре 5, в этом случаесигналом с элемента И 2 осуществляется выдача содержимого ячейки блокапамяти 3, адрес которой определяется разрядом нахождения единицы в 25регистре сдвига 1, затем происходитсдвиг единнща в регистре 1 в следующий разряд.Содержимое ячейки блока памяти,выданное по сигналу элемента и 2записывается в регистры 4, 4 эр4 п. В регистре 41 остается код,записанный с регистра 4 н 1, Процессперебора продолжается, как описановьвж до его эаверщення,. в последнемцикле единица с еследнего разрядарегистра сдвига 1 будет переписанав его первый разряд,В качестве примера рассмотримперебор перестановок кодов1234 40Занесем в регистры 41 н 5, например,код 1.В блок памяти 3 эапнщем перестановки кодов 2 3 4 - первая 2 3 4,записывается в регистры 4. В блокепамяти 3 запишется всего (н) - 45-31-6 перестановок кодов:2 3 42 4 33 4 23 2 4 50423432При переборе образуются ререстановки кодов в следующем порядке:перестановки кодов б 551234 04123 О3412О2341 11243 О3124 0 604312 О2431 11342 О2134 О4213 0 65 3421 11324 04132 О2413 О3241 11423 . О3142 О2314 О4231 11432 О2143 О3214 О4321 1Итого вырабатываются все перестановки в количестве ив 4 : 24. Через б в 1 обозначено наличие сигнала на выходе элемента И 2. Перебор перестановок с повторяющимися элементамив число которых равно п пп;где и; - число элементов 1-го рода,организуется также как и для перестановок, так как один иэ кодов эаноеится в регистры 44 , 5, а переста.нонки остальных кодов заносятсяв блок памяти 3, выдача содержимогосоответствующих строк которой производится при наличии сигнала элемента И 2, вырабатываемого при наличиив регистре 411 кода, совпадающегос кодом храннмьая в регистре 5.Например, если перебираются перестановки кодов21112,занесем в регистры 5, 44 код 2, ав блок памяти перестановки осталь-ных кодов 1111,"1112112112112111,число которых определяется как Перебор кодов:2 1 1 1 2в этом случае производится в следующем порядке:д21112 121121 О12112 121211 О12121 О11212 122111 О12211 О11221 О11122 1На етое перебор всех -р в , - и 10еперестановок с повторяющимися элементами.Перебор сочетаний сводится к перебору перестановок с повторениями656057 Формула изобретения ель В,Евстигнеев.Алферова Корректор М.Ряшк Состав Техред Редактор С,Ра Тираж 779 ЦНИИПИ Государстве по делаЮ изобре 3035, Москва, Ж, Подписноеного комитета СССРений и открытийаушская наб., д.4/5 Заказ 1523 3 ПП Патент, г.ужгород, ул. Проектная, 4 Фил Л случае двух типов элементов 0 и 1.Посредством предложенного устройства реализуем перебор сочетаний, перестановок и перестановок с повторяющимися элементами, в то время как известное устройство позволяет осуществить перебор только сочетаний. Предложенное устройство по сравнению с известным характеризуется повышенной надежностью, так как сбой в нем приводит к получению оши О бочного результата только в период до записи в регистры, соединенные в кольцо, информации снимаемой с блока памяти З,после чего восстанавливается правильное функционирование устрой" 16 ства. Устройство для перебора сочетаний, содержащее и последовательно соединенных в кольцо регистров исходных чисел, выходы которых являются выходами устройства, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства и повышения надежности его работы, оно содержит элемент И, дополнительный регистр, регистр сдвига, блок памяти, ивыходов которого соединены с Установочными входами ирегистров исходных чисел, начиная со второго, адресные входы блока памяти подключены к выходам регистра сдвига, выход дополнительного регистра соединен с первым входом элемента И, выход и-го регистра исходных чисел соединен со вторым входом элемента И, выходом,соединенного с тактовым входом регистра сдвига, тактовые входы всех и регистров исходных чисел соединены между собой и являются тактовым входом устройства.Источники информации, принятые во внимание при экспертизе1. Авторское свидетельство СССР 9525100, кл. 6 06 Р 15/32, 1976.2. Авторское свидетельство СССР 9446057, кл. С 06 Р 7/38, 1975.