Комбинаторное устройство

 

Изобретение относится к области автоматики и вычислительной техники и предназначено для использования в устройствах, решающих комбинаторные задачи, связанные с определением числа сочетаний и размещений. Цель изобретения - расширение функциональных возможностей за счет определения числа размещений. Устройство содержит регистры 1, 4, 19, 22, блоки вычитания 9, умножения 17, деления 24, счетчик 11, схему 12 сравнения, коммутатор 23, триггер 29, блоки 5, 8, 10, 13, 15, 16, 18, 20, 25, 27, 30 элементов И, блок 31 элементов ИЛИ, элемент ИЛИ 26. Дополнительно к функции определения числа сочетаний элементов предлагаемое устройство определяет и число размещений. Это достигается ценою ввода в конструкцию дополнительных блоков: коммутатора, триггера, блока элементов И, блока элементов ИЛИ и элемента ИЛИ. 1 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (51) 4 с 06 F 15 20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

Il0 ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

1 (21) 4407049/24-24 (22) 08.04.88 (46) 07.11.89, Бюл, N - 41 (72) В.А.Лукоянов (53) 681.3 (088.8) (56) Авторское свидетельство СССР

У 1305702, кл. G 06 F 15/20, 1985.

Авторское свидетельство .СССР

М 1396148, кл. G 06 F 15/20, 1986. (54) KONHMHATOPHOE УСТРОЙСТВО (57) Изобретение относится к области автоматики и вычислительной техники и предназначено для использования в устройствах, решающих комбинаторные задачи, связанные с определением числа сочетаний и размещений. Цель

„„SU„„1520535 А1

2 изобретений — расширение функциональных возможностей за счет определения числа размещений. Устройство содержит регистры 1, 4, 19, 22, блоки вычитания 9, умножения 17, деления 24, счетчик 11, схему 12 сравнения, коммутатор 23, триггер 29, блоки 5,8,10,13, 15,16,18,20,25,27,30 элементов И, блок 31 элементов ИЛИ, элемент ИЛИ

26. Дополнительно к функции определения числа сочетаний элементов предлагаемое устройство определяет и число размещений Это достигается ценою ввода в конструкцию дополнительных блоков: коммутатора, триггера, блока . элементов И, блока элементов ИЛИ и элемента ИЛИ. 1 ил.

1520535

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

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

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

Устройство. содержит регистр 1, элемент 2 задержки, генератор 3 тактовых 15 импульсов, регистр 4, блок 5 элементов И, элементы 6 и 7 задержки, блок

8 элементов И, блок 9 вычитания, блок

10 элементов И, счетчик 11, схему 12 сравнения„ блок 13 элементов И, эле- 20 мент 14 задержки, блоки 15 и 16 элементов И, блок 17 умножения, блок 18 элементов И, регистр 19, блок 20 элементов И, элемент 21 задержки, регистр

22, коммутатор 23, блок 24 деления, 25 блок 25 элементов И, элемент ИЛИ 26, блок 27 элементов И, элемент 28 задержки, триггер 29, блок 30 элементов И, блок 31 элементов ИЛИ, информационные входы 32 и 33, входы 34 и 35 запуска 30 устройства на определение числа размещений и сочетаний соответственно, выход 36.

Устройство определяет число С „ сочетаний или А„ размещений из и элементов по К. Значения п,К перед началом работы устройства заносится в регистры 1 и 4 с входов 32 и 33.

Выбор задачи определяется подачей запускающего импульса на один из вхо- щ дов 34 и 35 с запоминанием режима работы на триггере 29.

Для определения числа сочетаний триггер 29 устанавливается в единичное состояние ° При этом выход блока 45

20 элементов И через коммутатор 23 подключается к входу блока 24 деления, а на другом выходе коммутатора формируется нулевой код, Блок 30 элемен-. тов И оказывается открытым для передачи информации от блока 27 элементов

И к блоку 31 элементов ИЛИ.

Запускающий сигнал, пройдя через элемент ИЛИ 26, производит начальную установку блока 9 вычитания, блока

17 умножения, блока 24 деления, счетчика 11 и регистра 19 в нулевое состояние, а в регистр 22 записывается в двоичном коде. Этот же сигнал через элемент 2 задержки запускает генератор 3.

Очередной i-импульс с выхода ге- нератора поступает на счетный вход счетчика 11, увеличивая его содержимое на единицу и устанавливая в состояние

Одновременно тактовый импульс поступает на входы элементов 6 и 7 задержки. Сигнал с выхода элемента 6, задержанный на время срабатывания счетчика 11, поступает на входы блоков 5, 8, 10 и 16 элементов И и вход элемента 14 задержки. По этому сигналу код числа I< подается из регистра

4 через блок 8 элементов И на вход схемы 12 сравнения, на второй вход которой поступает код текущего состояния счетчика 11 через блок 16 элементов И. Если сравниваемые числа равны, то схема сравнения формирует сигнал, который, поступая на вход останова генератора 3, запрещает генерирование тактовых импульсов.

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

Пусть числа не равны. Тогда код числа из регистра 1 поступает через блок 5 элементов И на вход блока 9 вычитания, на второй вход которого подается предыдущий код состояния счетчика, хранящийся в регистре 19.

Таким образом, HB выходах блока вы читания формируется код разности

n-(i-1).По истечении времени определяемого элементом 7 задержки, разрешается прохождение кода состояния счетчика 11 c его выхода через блок 15 элементов И на вход регистра 19, где он запоминается. На i-м такте им" пульс, задержанный элементом 14, поступая на управляющие входы блока- 13 и 18 элементов И, обеспечивает прохождение через них соответственно с выхода блока 9 вычитания кода числа

n"(i-1) и с выхода регистра 22 произведения -I равно числу С „ сочетаний. Это число поступает на входы блока 17 умножения. Блок умножении осуществляет вычисление произведения С „ (и-(i- 1)).

Одновременно импульс с выхода элемента 14 задержки поступает на вход элемента 21 задержки, где задерживается на время срабатывания блока умножения. Сигнал с выхода элемента 21

5 задержки поступает на вход элемента

28 задержки, а также на управляющие входы блоков 20 и 25 элементов И.

Тем самым разрешается прохождение на входы блока 24 деления с выхода блока 17 умножения через коммутатор 23 кода числа С „ (п-(i-1), а с выхода счетчика 11 — кода числа i. Частное от деления 15

n- (i-1)

С ь поступает через блоки 27, 30 и 31 в регистр 22, где хранится до следующего такта.

На К-м такте на выходе счетчика

11 образуется код состояния, соответствующий числу К, в результате чего схема 12 сравнения сформирует сигнал, 25 поступающий на вход останова генератора 3. Вместе с тем на К-м такте будут выполнены все действия, описанные для i-ro такта, а, следовательно, в регистре 22 будет накоплено произ- 30 ведение

k и- (1-1)

П вЂ” — —.— — - С

1 и которое можно снять на выходе 36.

Для определения числа размещений

35 триггер 29 устанавливается в нулевое состояние. При этом запускающий сигнал также проходит через элемент

ИЛИ 26, устанавливает блоки устройст- 40 ва в начальное состояние и через элемент 2 задержки запускает генератор

3. Дальнейшая работа устройства ана,логична описанной, за тем исключением, что результат умножения 45

С,, (n- (i-1)) поступает с выхода блока 17 умножения через блоки 20, 23 н 31 на вход регистра 22, где записывается и хранится до следующего такта. 50

Иа К-м такте на выходе счетчика

11 образуется код состояния, соответствующий числу К, в результате чего по сигналу от схемы 12 сравнения прекращается формирование тактовых им55 пульсов. Вместе с тем на К-м такте будут выполнены все действия, приводящие к получению произведения

35 6

Ъ ь

П {n-(i-1) ) = A „с записью результата в регистре 22.

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

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

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

Составитель В.Байков fexpep, Л.Сердюкова Корректор С.Черни

Редактор В..Бугренкова

Заказ 6760/51 Тираж 668 Подписное

BHHHIIH Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

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

5 к управляющему входу четвертого блока элементов И, выход четвертого элемента задержки — к управляющим входам второго и девятого блоков элементов

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

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