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

СООЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 19) (11 151)4 СО ОПИКАВ АНИЕ ИЗОБРЕТЕНСКОМУ СВИДЕТЕЛЬСТВУ В 19А,Ю,Корев етельство СССР Р 15/31, 1985. ПЕРЕБОРА СОЧЕТА(157) Изобретение лительной техник носится к вычиспредназначено устройствах, ре е задачи, связан етаний, и являет ием изобретения Цель иэобретени перебора сочетаиспольз ваниянаторнь шающих комб ные с переб ром с ся усоверш вон О 2 по а, с, Ф сокращение ем ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ(54) УСТРОЙСТВО ДЛЯ ний от С до с. Устройство содержит пять групп элементов И 2, 3, 5, 6, 30, две группы элементов ИЛИ 4, 8, группу элементов задервки 7, два регистра 1, 19, два триггера 9, 20, четыре элемента И 10, 16, 17, 25, элемент 21 эадервжи, схему 23 сравнения, блок 22 элементов И, блок 26 элементов задерзки, счетчик 27, шину 15 входного канала, входы 18, 24, 28 начальной установки, выход 14 признака окончания работы, дешифратор 29,.входы 11 задания количества элементов, элемент ИЛИ 12, группу элементов ЗАЛРЕТ 13, Устройство позволяет реализовать перербор всех сочеВтаний от С до С при п с К, иш, 1 с пР, ш - число элементов перебора.Изобретение относится к вычислительной технике, может быть использовано в устройствах, решающих комбинаторные задачи, связанные с перебором сочетаний, и является усовершенствованием устройства по основному авт. св. У 1140127,Цель изобретения - сокращение вре"ч кмени перебора сочетаний от С до Спри гК, и ш, Кш.На чертеже приведена схема устройства для перебора сочетаний,Устройство содержит первый регистр,образованный иэ ш триггеров 1, группу элементов И 2, группу элементовИ 3, группу элементов ИЛИ 4, группуэлементов И 5, группу элементов И 6,группу элементов 7 задержки, группуэлементов ИЛИ 8, триггер 9, элемент 20И 10, входы 11 задания количества элементов, элемент ИЛИ 12, группу элементов ЗАПРЕТ 13, выход 14 признакаокончания работы, шину 15 входногосигнала, элементы И 16 и 17, входы 2518 установки регистра, регистр 19,образованный иэ 1 1 одтп+ триггеров,триггер 20, элемент 21 задержки,блок 22 из 3 1 оК ш(+ элементов И,йсхему 23 сравнения, вход 24 установкй триггера, элемент И 25, блок 26 из11 о т+ элементов задержки, счетчик 27, вход 28 установки счетчика,дешифратор 29, группу иэ ш элементовИ 30,35Устройство работает следующим образом.Для полного перебора всех возможных сочетаний от С, до С при и сш,01К ( ш, гК перед началом работы устройства производится установка триггера 20 в нулевое состояние, в регистр 19 по входу 18 заносится в двоичном коде число г, и в счетчик 27по входу 28 - число К 1, триггеры 1 45устанавливаются в нулевое состояние,а затем подаются на (и)-е крайниесправа входы 11 задания количестваэлементов единичные потенциалы.Очередной импульс, поступающий50по шине 15 входного сигнала, проходитчерез элемент И 17, открытый разрешающим потенциалом с нулевого выхода триггера 20 на счетный вход счетчика 27. Реверсивный счетчик принимает состояние 1, меньшее на единицу55первоначального (для первого импульса =К+1 в ). При этом, исло г иэрегистра 9 в параллели пои двоичном коде поступает на первый вход схемы 23 сравнения, на второй вход которой подается число(на первом шаге 1=К) иэ счетчика в параллельном двоичном коде. Если г с , то с выхода схемы сравнения на вход блока 22 элементов И выдается потенциал, который разрешает прохождение кода числа (К на первом шаге) с выхода счетчика через блок 26 элементов задержки на вход дешифратора 29, Каждый элемент задержки блока осуществляет задержку сигнала на время работы схемы сравнения. Дешифратор, после дешифрирования кода числа , выдает на 1-е крайние справа выходы потенциалы, разрешающие прохождение через соответствующие -е крайние справа элементы И 30 группы импульсов, поступающих по шине 15 входного сигнала через открытый элемент И 16 и элемент 21 задержки, обеспечивающий задержку сигнала на время срабатывания блоков 22, 23, 26, 27 и 29, на соответствующие единичные входы триггераОдновременно задержанный импульс проходит через открытый потенциалом от схемы 23 сравнения элемент И 25 на единичный вход триггера 20, устанавливая его в единичное состояние. При этом занрещается прохождение через элемент И 17 входных импульсов и разрешается их прохождение через элемент И 16 на Вход первого элемен 1та И 3 второй группы, обеспечивая перебор всех возможных сочетаний из и по . Для перебора сочетаний из п поиспользуется метод, основанный на образовании каждого нового сочетания из предыдущего путем замены крайней справа в регистре 1 комбинации 01" на "10" и переписи всех единиц, расположенных правее, в крайние правые позиции. По окончании перебора с выхода элемента ИЛИ 2 поступает сигнал, который устанавливает триггер 20 в нулевое состояние. При этом разрешается прохождение входных импульсов через второй элемент И 17 и запрещается их прохождение через первый элемент И 16, чем устройство подготавливается к работе на следующем шаге,Таким образом, обеспечивается перебор всех воножных сочетаний от ГЬ до С" гМ13979 Как только выполняется условие г, так схема сравнения прекращает формирование разрешающего потенциала, импульсы по шине 15 через открытый элемент И 17 поступают на счетный вход счетчика 27, уменьшая его состояние всякий раз на единицу. При установке счетчика в нулевое состояние на выходе 14 снимается сигнал окончания перебора.,1 О Формула изобретения Составитель О.БерезиковаТехред Л. Сердюкова Корректор П. Король Редактор Е,Папп Заказ 2601/49 Тираж 704 ПодписноеВ 11 ИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Иосква, Ж, Раушская наб., д. 4/5 Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 Устройство для перебора сочетаний 15 по авт. св. У 1140127, о т.л и ч а" ю щ е е с я тем, что, с целью сокращения времени перебора сочетаний отВСдо С, (гК, Кт, пт, щ - количество элементов перебора), оно со держит второй регистр, второй триггер, элемент задержки, второй, третий и четвертый элементы И, схему сравнения, счетчик, блок элемЕнтов задержки, блок элементов И, дешифра тор и пятую группу элементов И, причем выход элемента ИЛИ соединен с нулевым входом второго триггера, прямой и инверсный выхоДы которого соединены с первыми входами второго и третьего элементов И, вторые входы которых соединены с шиной входного сигнала устройства, входы установки ,Р 364начального состояния второго регист" ра, счетчика и второго триггера которого соединены с одноименными входами второго регистра, счетчика и второго триггера, единичный вход которого соединен с зыходом четвертого элемента И, первый вход которого соединен с выходом элемента,задержки и первыми входами элементов И пятой группы, вторые входы которых соединены с выходами дешифратора, входы которого соединены с выходом блока элементов И, первый вход которого соединен с вторым входом четвертого элемента И и выходом схемы сравнения, первый вход которой соединен с выходом второго регистра, а второй ввод схемы сравнения соединен с выходом счетчика и входом блока элементов задержки, выход которого соединен с вто,рым входом блока элементов И, счетный вход счетчика соединен с входом элемента задержки и выходом третьего элемента И, выходы элементов И пятой группы соединены с единичными входа" ми триггеров первого регистра, выход второго элемента И соединен с первыми входами первых элементов И второй и третьей групп и нулевым входом первого триггера, выход счетчика является выходом признака окончания работы устройства.