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

 

ОПИСАНИ Е

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДИ ЕЛЬСТВУ

238238

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

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

Республик

Зависимое от авт. свидетельства ¹

Заявлено 19.1Х.1967 (№ 1184860/18-24) Кл. 42птз, 15/32

Л1П1с, 6 06f

УД1<, 681.325.67(088.8) Комитет по делам изобретений и откРытий при Совете Министров

СССР

Опубликовано 20Л11.1969. Бюллетень № 9

Дата опубликования описания 18.VII.1969

С .)1 1 Т. 1,",„г1".

В, И. Чабан и P. В. Дмитришин

Авторы изобретения.эая;витель

УСТРОЙСТВО ДЛЯ 11 ЕР ЕБОРА СОЧЕТАНИЙ с присоединением заявки ¹

Приоритет—

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

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

«ИЛИ». Выход переноса 1-го счетчика соединен со,входом (i+1)-го счетчика н с сдинич- 15 ным входом i-го триггера, передачи, единичный выход которого соединен со входом l-го формирователя. Выход формирователя соединен с первым входом i-й схемы, передачи, вторые входы, которой соединены с выходами (i+1)-го 20 счетчика, а выходы — с установочными входами триггеров 7-го счетчика. Выход формирователя через линию задержки и схему «ИЛИ» соединен со счетным входом i-го счетчика. Нулевой .выход l-го триггера передачи соединен 25 с первым входом (i — 1)-й схемы «И», выход которой соединен со входом установки нуля (i — 1)-го триггера передачи, а второй вход соединен с соответствующими входами схем «И» первой группы и с выходом генератора импуль- 30 ссв передачи, блокнрук, ций вход которого соединен с единичным вь1ходом триггера. Един1гчный вход триггера соединен с выходом кинп-рслс, Вход которого соединен с вы. Одом г1срвого формирователя нм:1ульсов .передачи, счстный вход i-го с icт-111ка через схему «I!ЛИ» сссдннсн с зыходом -й схемы «I >>, >первый вход которой соединен с единичным выходом

i-lî триггера установки, а второй в од сосдинсн с соответствующими вхсдамн второй групп ы с х е м << I I >> н с В ы х О д 0. 1 0 л О к а ф с р м н р О В а и н я серий импульсов. Едннн нный вход i-го триггера установки соединен с выходом:-н схемы

< II», псрвый вход которой соединен с единичным выходом (7 — 1) -го триггера установки, а второй вход объсд;шсн с соответствующими входам:l третьей группы схем «11» и через ieблока формирования серий импульсов.

Это позволяет Осущсств;1ть перебор всех всзможны; сочетании нз 777 по 71, что реализуется в одноврсмснном налH÷iiH сигнала на а выходах из пт для каждого О 1стання.

На чертеже приведена функциональная сх"ма предлагаемого устройства.

Основным.. *элсментамн устройства являются счет-1нкн 1 — 4, 1;Оличсст110 которых равно и„,..., 11оэффицнснты псресчста с:1етчнков 1 — 4 разнятся на единицу и умсньн1аются от 771 „, „

До 777.m, 11,„,„-+1.Выход каждого прсдыдуще238238 го счетчика соединен со входом последующего.

Счетчики снабжены дешифраторами состояний (на чертеже не показаны). Одинаковые разряды Всех дешифраторов обьединены схемами

«ИЛИ» 5, 6, 7, сигналы которых через выходные усилители 8, 9, 10 подаются на выходные шины 11, 12, 18 устройства, количество которых равно m „,. Ячсйки 14, 15, 16, подключенные к выходным шинам,:позволяют визуя.lbHo фиксировать выходные сигналы.

Триггеры управления l7, 18, 19 и схемы совпадения «И» 20, 21, 22 па их входах и выходах служат для засылки в счетчики исходных данны,(. Засылка п или и определяется положением тумолера 28. Серии импульсов, осущестВляющие установку п и m (назовем их п-серия

;: )и-серия), вырабатыва1отся с,помощью счетчика 24 ооратного счета, ключа 25, формирователя импульсов 26 и схемы совпадения 27, на которую заведены выходы всех триггеров счег)пка 24. Ячейка индикации 28, подключенная к выходу схемы «И» 27, сигнализирует об окончании п- или m-cepuu.

Первичные импульсы, используемые как для решения задачи, так и для установки исходных

Jau))lola, вырабатываются генератором 29 тактовых импульсов. Тумблер 80 осуществляет подачу их в рабочую цепь или в цепь устаНО;(и пс: одпых Jauullx. 1-1ажатием кнопки 81 так говые им11у.",ücû подяlотся ня схему форхlи р()ва:1ия и — и )и-серии.

110: оду работы устройства необходимо послед я)1тc.1ьно 1тередявять содер)1(имое ВышестО)lщего сч(.Г Iпкя В нижестоящий, ITQ Выполняется схемами переда ги 8- — 84, управляемыми тр11ггерами:псредячи 85 — 87 через формирователи 88 — 40. Выходные импульсы послед1(их через лини.1 задеря(ки 41 — 48 .подаются также на входы тех счет1иков 1 4, .в которые был передан код из Вышестоящего счетчика.

Выход каждого счетчика 1 4 соединен с единичным Входом соответствующего триггера передачи 85 — 8/, а Выход, первого счетчика, кроме того, 1ерез с; ему «ИЛИ» 44 — с триггером 45 и через кипп-реле 46 — с триггером 4i управления переда)ами. Кипи-реле задержиВает сигнал на время, необходимое для переносов из счетчика в счетчик. Триггер 47 управляет генератором 48 импульсов перед)1ч11, имгг;льсы с которого через схемы «И» 49 и 50 ) подаются на нулевые входы триггерсв 85 — >7 и осущесгвляют последовательный сброс носледних в порядке уменьшения их номеров. 1)а

Второй вход схем «Й» 49 — 50 подаегся сигнал с нулевого выхода вышестоящего триггера nepедачн 85 — 87.

Управляемый триггером 45 ключ 51 пропу.скает или не пропускает тактовые импульсы на вход счетчика 1. Если при данном выходном сочетании образуется дерево графа, на вход «ответ Д» поступает сигнал, и триггер

45 сбрасывается в «0». Кнопкой 52 устройство запускается вручную.

Триггер 58 и дифференцирующая цепочка 54, подключенная к первой выходноп шине, 5

4 осуществляют останов устройства после перебора всех сочетаний, о чем сигнализирует ячейка 55 индикации «конец».

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

Вначале все триггеры и счетчики сбрасыва1отся в нулевое положение (цепи сброса на чертеже не показаны). Тумблер 80 переключается в положение «установка данных».

С пульта в счетчик 24 заносится в двоичном коде число и. Тумблер 28 .переключается в,положение п, Схема 27 выдает на ключ 25 çàïðeщающпй потенциал в том случае, если счетчик 24 установится в .нуль.

Г1ри нажатии кнопки 81 импульсы генератора 29 подаются на ключ 25, который открыт, тяк как счетчик 24 содержит число )z. Формирователь 26 выдает на счетчики 1 — 4 и триггеры управления 17 — 19 импульсы. Эти же им,1»ульсы поступают на счетчик 24, который с приходом и-го импульса установится в «0», а схема 27 занрет ключ 25. 1 аким образом,.на выходе формирователя 26 образуется серия

Iia п импульсов. На счетчик 1 через схему

«ИЛИ» 56 поступают все импульсы, и он устанавливается в cocTQBHue )г. На и-м выходе его дешифратора появляется сигнал.

На счетчик 2 .первый импульс и-серии не проходит, так как на схему «И» 57 триггер 19

Выдает запрет. Первый импульс, поступающий через схему «И» 22, на которую заведен разрешающий потенциал с нулевого выхода триггера 19, устанавливает этот триггер в «1». Все последующие импульсы на счетчик 2 будут поступать через схему «И» 57 и схему «ИЛИ»

58. Первый импульс снимает разрешение со схемы «И» 22, и 1риггер 19 останется в uî Ioженин «!». Откроется схема «И» 21, и второй имнульс перебросит триггер 18 в «1». Импульсы, начвная с третьего, будут:поступать на

-aåT÷uê 8. Третий импульс установит в положение «1» следующий триггер и т. д. С окончанием п-серии состояния счетчиков 1 — 4 будут отличаться на единицу.

Счетчики от )I-}-1 до )I,„,, oñòaþòñÿ в нулеьом состоянии, и входы их закрыты. На перзы-. и выходах устройства имеются сигналы, образующие первое сочета ние. Если )и=пг то ввод данных на этом заканчивается, если

l:åò, то требуется пастроить счетчики по парамлру m. Для этого тумблер 28 устанавливается в положение m, в счетчик 24 заносится число mÄ...„— m и нажимается кнопка 81. Формируется т-серия, все импульсы которой поступают на входы первых п счетчиков. На выходах устройства происходит сдвиг первого ссчетания вправо на (m „,.„„— m) разрядов.

Выходы, расположенные левее полученного сочегания, В дальнейшем не используются.

После этого тумблер 80 ставится в положение

«работа», и устройство готово к решению задачи.

Нажатием кнопки 52 триггер 45 устанавливается в положение «1» и открывает ключ 51, Импульсы генератора 29 через схему «ИЛИ»

56 поступают на счетчик I, на выходе начи238238

10,нают просчитываться первые комбинации: 1, 2, З...n — 1, и; 1,2,3...n — 1, и+1; 1, 2,3...

n — 1, n+2 и т. д. После того как образуется комбинация 1, 2, 3... n — 1, m, на выходе счетчика 1 появится импульс первноса, постулаюший на вход счетчика 2. Этот же импульс сбрасывает триггер 45 в нулевое положение и подача импульсов на счетчик 1 прекращается.

1 ритгер передачи 87 уста!Навливается в «1».

Через отрезок времени, необходимый для переносов всех счетчиков (наихудшие случаи), кипп-реле 4б устанавливает в «1» триггер 47, который запускает генератор 48 импульсов ле.редачи. его импульсы поступают на,нулевые входы всех триггеров 85 — 87, так как схемы

«И» 49 — 50 на их входах послс первого пере.нося открыты. Но в состоянии «1» находится только триггер 87, и с его выхода снимаегся импульс, воздействующий через формирователь 40 на схему передачи 84, которая передает содержимое счетчика 2 в счетчик 1. Через отрезок времени, необходимый для передачи, на схему «ИЛИ» 5б из линии задержки 48 поступит импульс и увеличит содержимое счетчика 1 на единицу. Образуется, выходная комбинация 1, 2, 3 ... n — 2, и, n+1. После этого через линию задержки 59 на триггер 45 поступит импульс и установит его в «1». Открывается .ключ 51, и импульсы генератора 29 снова поступают на счетчик 1. Если возникает перенос од!повременно из нескольких счетчиков, то соответствующие им триггеры передаги 85 — 87 установятся в «1». Импульсы генератора 48 будут сбрасывать их .поочередно сверху вниз. Произойдет последовательная передача содержимого верхних счетчиков в нижние с добавлснием единицы в последние на каждом такте .передачи.

Если да!Нное сочетание образует дерево графа, то на триггер 45 со входа «отвод Л»;поступает импульс, который устанавливает его в «О».

Работа устройства приостановится, и если для регистрации сочетаний, образующих деревья, используется цифропечатающий механизм (LIAM), то запуск устройства,для дальнейшей работы осуществляется ответным импульсом ,конца печати,,поступающим на вход «ответ

ЦМП» (если регистрация производится оператором, то кнопкой 52). Счетчик б0 .подсчитывает количество деревьев.

После перебора всех сочетаний устройство должно оста!повиться. Это осуществляется следующим образом. Последнее сочетание соответствует наличию сигнала в старших разрядах,всех задействованных счетчиков. Последующий тактовый импульс устанавливает эти счетчики в «0». В результате передач, если

55 были задействованы все счетчики, llли благодаря персно:у ". (и+1)-й счетчик, который до

ЭТОГО НЯХОДИЛСЯ В Н1 10 BOÌ СОСТОЯ!1!! И, На П OPFoll выходной шине появл lcTcя сигнал. которвй через дифференц :1рующую цепо1ку icT;l-!

1явливает триггер 58 в «1». Сигнал с его нулсвсго выхода сбрасывает триггер 45 в «0», и

1 лlOч 51 ЗBкрывя ется. Ячcйка индикац1111 <<конец», 55 связанна,l с триггером 8 сигнализирует 0 конце работы.

Предмет изобретения

Устройство для перебора c0÷còàíèé, содержащее счет

СХСМЫ, ОтЛиЧаЮЩЕЕСЯ TC I, ЧТО В НСМ ПОСЛЕДОВЯГЕЛЬНО СОСДИНЕНЫ С IPT1ИКИ C Озч)фИЦИСHTBми пересчета, разнящимися на единицу, сооТгстствующие вы: оды дсшифраторов которы.; соединоны со входами схем «11Л11», выход переноса i-го счетчика соединен со входом (!+1) -го счетчика и с единичным входом 1-го триггера передачи, един!Ичный выход которого соединен со входом 1-10 формирователя, выход формирователя соединси с .первым входом I-u с смы передачи, вторые входы которой соединены с выходами (+1)-го счет ика, Я ullxoды — с установочными входами триггеров 1-го счетчика, выход формировагсля через лин!Ио

",äcp>I<,!

i-го счетчика через схему «ИГ1И» соединен с выходом I-й схемы «II», .первый вход которой соединен с единичным выходом !-го триггера установки, а второй вход соединен с соотBQTcTBующими входами второй группы схем

«И» и с выходом блока формирования серий импульсов, единичный вход I-го триггера уcTBHODI