Комбинаторное устройство Советский патент 1989 года по МПК G06F7/06 G06F7/38 

л

СП Ю

О

ел оэ ел

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

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

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

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

выход 36.

1

Устройство определяет число С ,, сочетаний или А размещений из п элементов по К. Значения п,К перед началом работы устройства заносится в регистры 1 и 4 с входов 32 и 33. Выбор задачи определяется подачей запускающего импульса на один из вхо- дов 34 и 35 с запоминанием режима работы на триггере 29.

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

Запускаюищй сигнал, пройдя через элемент ШМ 26, производит начальную

через элемент 2 задержки запускает генератор 3.

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

Одновременно тактовый импульс поступает на входы элементов 6 и 7 задержки. Сигнал с выхода элемента 6, задержанный на время срабатывания счетчика 11, поступает на входы блоков 5, 8, 10 и 16 элементов И и вход элемента 14 задержки. По этому сигналу код числа К подается из регистра 4 через блок 8 элементов И на вход схемы 12 сравнения, на второй вход которой поступает код текущего состояния счетчика 11 через блок 16 элементов И. Если сравниваемые числа равны то схема сравнения формирует сигнал, которьш, поступая на вход останова генератора 3, запрещает генерирование тактовых импульсов. 1

Если числа не равны, то генератор

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

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

п - (1-1)

Изобретение относится к области автоматики и вычислительной техники и предназначено для использования в устройствах, решающих комбинаторные задачи, связанные с определением числа сочетаний и размещений. Цель изобретения - расширение функциональных возможностей за счет определения числа размещений. Устройство содержит регистры 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 ил.

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

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

Одновременно импульс с выхода элемента 14 задержки поступает на вход элемента 21 задержки, где задерживается на время срабатывания блока ум- . Сигнал с выхода элемента 21 задержки поступает на вход элемента 28 задержки, а также на управляющие входы блоков 20 и 25 элементов И. Тем самым разрешается прохождение на входы блока 24 деления с выхода блока 17 умножения через коммутатор 23 кода числа С п (n-(i-l), а с выхода счетчика 11 - кода числа i. Частное от деления

.Hiiiil)..

i

г I

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

20

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

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

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

входом блока умножения, выход второго регистра соединен с информационным д5 входом десятого блока элементов И,

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

тора 3. Вместе с тем на К-м такте будут выполнены все действия, описанные для такта, а, следовательно, в регистре 22 будет накоплено произведение

i n-(i-l) k

I, ь ,

tsl 1

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

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

50

55

ход первого элемента задержки соединен с пусковым входом генератора тактовых импульсов, выход которого подключен к счетному входу счетчика и к входам второго и третьего элементов задержки, вьйсод второго элемента задержки подключен к управляющим вхоП (n-(i-l)) Л , с записью результата в регистре 22.

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

Комбинаторное устройство, содержащее четыре регистра, блок вычитания, блок умножения, блок деления, счетчик, схему сравнения, десять блоков

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

0

5 И, выход счетчика подключен к инфор- мационным входам четвертого, пятого

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

5

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

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