Устройство для перебора размещений - SU1078425A1

Чертежи

Описание

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

Известно устройство для перебора размещений с повторениями, содержащее генератор импульсов, блок сравнения и счетчик 1.

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

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

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

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

Цель изобретения - упрощение устройства и повышение его быстродействия .

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

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

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

Устройство содержит генератор 1 импульсов,, сдвигающий регистр 2, накапливающий сумматор 3, блок 4 сравнения, блоки 5 и 6 сравнения, счетчики 7 и 8, блок 9 умножения, блок 10 деления, задатчики 11-13 исходной информации и блок 14 вывода результата.

, В качестве блоков 9 и 10 умножения и деления используются бло ки целочисленного умножения и деления , а в качестве блока 14 вывода результата может быть применено устройство цифровой индикации или печатающее устройство.

Задатчиками 11-13 исходной информации являются цифровые задатчики с кодовым выходом.

Генератор 1 илтульсов своим упIравляющим входом связан с выходом первого дополнительного блока б сравнения, а выходом - с входом сдвигающего регистра 2, выход которого соединен с входом накапливающего сумматора 3. Информационный выход блока 9 умножения подключен к входу сдвигающего регистра 2 W одному из входов блока 10 деления, второй вход которого подключен к выходу задатчика 11 исходной информации .

Один из входов блока 4 сравнения подключен к выходу задатчика 12 исходной информации, другой его вход соединен с выходом накапливающего сумматора 3, а выход - с входом первого счетчика 7 и управляющим входом сумматора 3.

Выход счетчика 7 соединен с входом блока 5 сравнения, другой вхо-: KOToi-X ro 11одклн)че;н к Btjxcjity 6JiOJ a 10 деления, a информационный вход последнего соединен с выходом задатчика 11 исходной информации. Управляющий вход блока 9 умножения подключен к выходу блока 5 сравнения, а его информационный вход соединен с выходом задатчика 12. / Входы блока б сравнения подключены к выходам задатчнка 13 и счет чика 8, вход которого подключен к выходу блока 5 сравЕ1ения. Один из входов блока 14 вывода результата соединен с выходом накапливающего сумматора 3, а другой его вход - с выходом блока 5 сравн ния. Устройство работает следующим образом. Перед началом работы в зависийо ти от размерности генерируемого размещения А| задатчиком 11 зада ется число п f, . задатчиком 12 число равное m , а задатчиком 13 чис ло равное п , где п , m - числа всевозмоисных размещений из п элеме тов по m . Кроме того, в блок 9 умножения и в сдвигающий регистр 2 заноситс единица. Включение устройства осуществля ется запуском генератора 1 импульсов . Первым импульсом с выхода генератора 1 импульсов осуществляется сдвиг единицы в сдвигающем регист ре 2 и по сигналу равенства нулю содержимого последнего заносится единица в накапливающий сумматор откуда содержимое последнего (т.е единица) поступает на вход устрой ва 14 вывода результата и регистри руется . Кроме тогр, содержимое накапли вающего сумматора 3 поступает на один из входов блока 4 сравнения где происходит сравнение этого зна чения с нислом равным .т , поступаю щим На другой вход блока 4 сравнения с выхода задатчика 12. Если сравниваемые значения не р мы, то по аналогии с первым тактом работы генератора 1 импульсов на вход накапливающего сумматора 3 поступает вторая единица, которая прибавляется к предыдущей, и в бло ке 4 сравнения происходит сравнение числа два с числом h , заданным задатчиком 12. Эта операция повторяется до момента сравнения значений чисел на обоих входах блока 4 сравнения. При этом на устройство 14 вывода результата поступают последователь но увеличивающиеся на единицу числа . в момент равенства срав1-1иваем з1х i на входах блока 4 сравнения чисел (через п тактов) на выходе последнего вырабатывается сигнал сравнения , который поступает на вход накапливающего сумматора 3, устанавливая его в нулевое состояние. Этим же сигналом заносится единица в счетчик 7, после чего описанный цикл работы, состоящий из п тактов, повторяется.. Количество таких циклов (определяющих число элементов первого столбца значений, регистрируемых устройством вывода) равно числу п , заданному задатчиком 11 исходной информации, и отсчитывается устройством следующим образом. Сигналы сравнения с выхода блока 4 сравнения поступают на вход счетчика 7, где суммируются, и с каждым тактом подаются на один из входов блока 5 сравнения, на другой вход которого с задатчика 11 подается число П , которое перед этим в блоке 10 деления-делится на число, поступающее с выхода блока 9 умножения . Поскольку до описываемого периода в блоке 9 умножения находилась записанная в него единица, то число п , разделенное в блоке 10 деления на единицу, остается без изменений. Когда число циклов, суммирующихся в счетчике 7, сравняется с числом п, на выходе блока 5 сравнения появится сигнал сравнения, который служит сигналом конца столбца для устройства вывода и переключения последнего для печати второго столбца. Кроме того, этим сигналом разрешается считывание блоком 9 умножения числа п , заданного задатчиком 12 исходной информации, а также заносится единица в счет«. чик 8. Работа устройства при выводе второго столбца на устройство 14 вывода результата аналогична предыдущему . Однако поскольку к этому моменту на управляющий вход блока 9 умножения с выхода блока 5 сравнения подан разрешающий сигнал, то содержимое блока 9 умножения (т.е. единица ) умножается на число п , поступающее с задатчика 12, и полученное произведение (в данном случае число h ) заносится в сдвйгаюсигй регистр 2. На выходе сдвигающего регистра 2 сигнал появляется после выполнения п тактов сдвига. Поэтому в течение первых тактов с выхода сдвигающего регистра 2 на вход накапливающего сумматора 3 сигналы не будут подаваться, в результате чего в каждом из п тактов на вход устройства 14 вывода результата будет поступать и регистрироваться едини ца, содержащаяся в сумматоре 3. По окончании п тактов с ввлхода сдвигающего регистра 2 на вход накапливающего сумматора 3 подается единица, которая прибавляется к единице, уже хранящейся в накапливающем сумматоре 3. В течение следующих л тактов на вход устройства 14 вывода результата подается число , равное двум. Затем аналогично в течение следующих h тактов выво дится на устройство 14 вывода результата число равное трем и так до числа п включительно, т.е. до момента сравнения- сигналов на обоих входах блока 4 сравнения и уста новки накапливающего сумматора 3 в нулевое состояние. Следукнций цикл работы устройства по выводу остальных элементов второго столбца аналогичен предыду щему. Число циклов при выводе элементов второго столбца равно числу -- и отсчитывается устройством ел дующим образом. Сигналы сравнения с выхода счет чика 7, поступающие на вход блокаг 5 сравнения, будут сравниваться с сигналами с выхода блока 10 деления , и так как к данному моменту н вход блока-10 деления с выхода бло ка 9 умножения подано число № , то в результате выполнения операции деления с выхода блока 9 умножения на вход блока 5 сравнения буде :П. подано число -И- , Когда число циклов, регистрируе мых счетчиком 7, достигнет числа п равного , на выходе блока 5 сра нения появится сигнал, который занесет вторую единицу в счетчик 8, переключит устройство 14 вывода ре зула.тата на следующий (третий) сто бёц и разрешит занесение единицы в блок 9 умножения. В блоке 9 умножения происходит умножение занесенного в него числа m с таким же числом, поданным на его вход перед началом вывода второго столбца. Таким образом, в блоке 9 умножения будет храниться число п п п ,. При выводе третьего столбца по аналогии с описанным число циклов и равно числу - , а при выводе последнего столбца число циклов будет равf 1 но числу - 1. Работа Устройства автоматически счетчике 8 прекращается, когда в будет число равное ,т , т.е. число. соответствукнцее заданному числу в размещении А . При этом содерж41мое счетчика 8 поступает на один из входов блока, 6 сравнения, на другой вход которого подается код числа, заданного задатчиком 13. При равенстве значений этих кодов на выходе блока 6 сравнения вырабатывается сигнал, который поступает на управлякииий вХод генератора 1 импульсов и отключает последний. Таким образом, бл.оком 14 результата будет зафиксирована последовательность элементов, представляющих собой всевозможные размещения с повторениями из п элементов по fTi , т.е. AJIJ . Каждое отдельное размещение с повторением представляет собой строку из ,т элементов, а общее число строк равно м . Работа устройства в режиме генерации размещений с повторениями А при п 3 .т 4 иллюстрируется таблицей. В таблице представлены всевозмож-; ные размещения с повторениями А А| г число которых равно 81.

Реферат

УСТРОЙСТВО ДЛЯ ПЕРЕБОРА РАЗМЕ1иЕНИЙ, содержащее генератор импульсов, блок сравнения, счетчики и блок вывода результата, о тличающееся тем, что, с целью упрощения и повышения быстродействия устройства, оно дополнительно содержит сдвигающий регистр, накапливающий сумматор, блок умножения , блок деления, блоки сравнения , задатчики исходной информа:ции , причем выход генератора импульсов подключен к входу сдвига сдвигающего регистра, информационный вход которого подключен к выходу блока умножения и к первому информационному входу блока деления , второй информационный вход которого подключен к выходу первого задатчика исходной информации, выход блока деления подключен к пepвo 1y входу первого блока сравнения , второй вход которого подключен к выходу первого счетчика, счетный вход которого подключен к второго блока сравнения и кГвходу сброса накапливающего сумматора, информационный вход которого подключен к выходу сдвигающего регистра, выход накапливающего сумматора подключен к первому входу блока вывода результата и I к первому входу второго блока сравнения , второй вход которого подклюСП чен к выходу второго задатчика исходной информации и к первому входу блока умножения, второй вход которого подключен к выходу первого блока сравнения, к второму входу блока вывода результата и к счетному входу второго счетчика, выход которого подключен к первому входу третьего блока сравнения, второй вход которого подключен к выходу третьего задатчика исходной информации, выход третьего блока сравнения подключен к входу разрешения работы генератора импульсов.

Формула