Устройство для перебора сочетаний Советский патент 1988 года по МПК G06F17/10 

ff«

14)

Изобретение относится к вычислительной технике, может быть использовано в устройствах, решающих комбинаторные задачи, связанные с перебором сочетаний, и является усовершенствованием устройства по основному авт. св. № 1140127.

Цель изобретения - сокращение времени перебора сочетаний от С до С при , , kim.

На чертеже приведена схема устройства для перебора сочетаний.

Устройство содержит первый регист образованный из m триггеров 1, груп- Пу элементов И 2, группу элементов И 3, группу элементов ИЛИ 4, группу влементов И 5, группу элементов И 6 группу элементов 7 задержки, группу элементов ИЛИ 8, триггер 9, элемент И 10, входы 11 задания количества элментов, элемент ИЛИ 12, группу элеметов ЗАПРЕТ 13, выход 14 признака окончания работы, шину 15 входного сигнала, элементы И 16 и 17, входы 18 установки регистра, регистр 19, образованный из 1 триггеров триггер 20, элемент 21 задержки, блок 22 из 3 log ml+1 элементов И, схему 23 сравнения, вход 24 установ- кй триггера, элемент И 25, блок 26 и элементов задержки, счетчик 27, вход 28 установки счетчика, дешифратор 29, группу из га элементов И 30.

Устройство работает следующим образом.

Для полного перебора всех возможных сочетаний от С до с| при п т, , г 5: k перед началом работы уст- ройства производится установка триггера 20 в нулевое состояние, в регистр 19 по входу 18 заносится в двоичном коде число г, и в счетчик 27 по входу 28 - число , триггеры 1 устанавливаются в нулевое состояние, а затем подаются на (n-l)-e крайние справа входы 11 задания количества элементов единичные потенциалы.

Очередной импульс, поступающий по шине 15 входного сигнала, проходи через элемент И 17, открытый разрешающим потенциалом с нулевого выхода триггера 20 на счетный вход счетчика 27. Реверсивный счетчик принимает состояние i , меньшее на единицу первоначального (для первого импульса i k+l-l k). При этом, число г из регистра 19 в параллелмк м двоичном

Q

5 0 5 0

д

до

5

5

0

5

коде поступает на первый вход схемы 23 сравнения, на второй вход которой подается число i (на первом шаге ) из счетчика в параллельном двоичном коде. Если,г i, то с выхода, схемы сравнения на вход блока 22 элементов И выдается потенциал, который разрешает прохождение кода числа i (k на первом шаге) с вьгхода счетчика через блок 26 элементов задержки на вход дешифратора 29. Каждый элемент задержки блока осуществляет задержку сигнала на время работы схемы сравнения. Дешифратор, после дешифрирования кода числа i, выдает на i-e крайние справа выходы потенциалы, разрешающие прохождение через соответствующие 1-е крайние справа элементы И 30 группы импульсов, поступающих по шине 15 входного сигнала через открытый элемент И 16 и элемент 21 задержки, обеспечивающий задержку сигнала на время срабатывания блоков 22, 23, 26, 27 и 29, на соответствующие единичные входы триггера 1 .

Одновременно задержанный импульс проходит через открытый потенциалом от схемы 23 сравнения элемент И 25 на единичный вход триггера 20, устанавливая его в единичное состояние. При этом запрещается прохождение через элемент И 17 входных импульсов и разрешается их прохождение через элемент И 16 на Ьход первого элемента И 3 второй группу обеспечивая перебор всех возможных сочетаний из п по 1. Дпя перебора сочетаний из п по 1 используется метод, основанный на образовании каждого нового сочетания из предьщущего путем замены крайней справа в регистре 1 комбинации О на 10 и переписи всех единиц, расположенных правее, в крайние правые позиции. По окончании перебора с выхода элемента ИЛИ 12 поступает сигнал, который устанавливает триггер 20 в нулевое состояние. При этом разрешается прохождение входных импульсов через второй элемент И 17 и запрещается их прохождение через первьпЧ элемент И 16, чем устройство подготавливается к работе ня следующем шаге.

Таким образом, обеспечивается перебор всех ртможных сочетаний от Г

С h

г 4 k .

31

Как только выполняется условие г i, так схема сравнения прекращает формирование разрешающего потенциала, импульсы по шине 15 через открытый элемент И 17 поступают на счетный вход счетчика 27, уменьшая его состояние всякий раз на единицу. При установке счетчика в нулевое состояние на выходе 14 снимается сигнал окончания Перебора.

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

Устройство для перебора сочетаний по авт. св. № II40127, о т. л и ч а- ю щ е е с я тем, что, с целью сокращения времени перебора сочетаний от

t. k / С, (, kim, , m - кьличество элементов перебора), оно со держит второй регистр, второй триггер, элемент задержки, второй, третий и четвертый элементы И, схему сравнения, счетчик, блок элементов задержки, блок элементов И, дешифратор и пятую группу элементов И, причем выход элемента ИЛИ соединен с ну левым входом второго триггера, прямой и инверсный выхоДы которого соединены с первыми входами второго и третьего элементов И, вторые входы которых соединены с шиной входного сигнала устройства, входы установки

397936

начального состояния

второго регистра, счетчика и второго триггера которого соединеиы с одноименными входами второго регистра, счетчика и второго триггера, единичный вход которого соединен с зыходом четверто- . го элемента И, первый вход которого соединен с выходом элемента .задержки

10 и первыми входами элементов И пятой группы, вторые входы которых соединены с выходами дешифратора, входы которого соединены с выходом блока элементов И, первый вход которого

15 соединен с вторым ,входом четвертого элемента И и выходом схемы сравнения, первый вход которой соединен с выходом второго регистра, а второй вход схемы сравнения соединен с выходом 20 счетчика и входом блока элементов задержки, выход которого соединен с вто- ,рым входом блока элементов И, счетный вход счетчика соединен с входом элемента задержки-и вьЬсодом третьего

25 элемента И, выходы элементов И шятой группы соединены с единичными входами триггеров первого регистра, выход второго элемента И соединен с первыми входами первых элементов И второй и

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