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

 

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

СОЮЗ CORETCHHX

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

РЕСПУБЛИК

1396148 А 1 (51)4 С 06 Р 15/20

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

К А BTOPCHOMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 417411 1/24-24 (22) 10.11.86 ,(46) 15.05.88. Бюл. У 18 (72) В. А. Лукоянов и А. Ю. Корев (53) 681.323(088.8) (56) Авторское свидетельство СССР

В 1140127, кл. G 06 F 15/31, 1983.

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

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

I (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЧИСЛА

СОЧЕТАНИЙ (57) Изобретение относится к вычислительной технике и может быть использовано в устройствах, решающих комбинаторные задачи, связанные с вычислением числа сочетаний иэ и по k. Цель изобретения — повышение точности определения числа сочетаний. Устройство содержит десять блоков элементов

И 6,9,11,14,16,17,19,21,24,25, четыре регистра 2,5,20,27, генератор импульсов 4, шес ть элементов з аде ржк и

3,7,8,15>22,26, блок вычитания 10, счетчик 12, блок сравнения 13, блок умножения 18, блок деления 23, вход пуска 1, входы установки начальных значений 29,30, выход 28. Устройство к вычисляет количество сочетаний С„, являющееся всегда целым числом. ил.

1396148

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

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

Устройство содержит вход 1 пуска, ш-разрядный регис.тр 2, элемент 3 задержки, генератор 4 тактовых импульсов, m-разрядный регистр 5, блок 6 элементов И, элемент ? задержки, элемент 8 задержки, блок 9 элементов И, блок 10 вычитания, блок 11 элементов

И, счетчик 12, блок 13 сравнения, блок 14 элементов И, элемент 15 задержки, блок 16 эле. .ептов И, блок 17 элементов И, блок 18 умножения, блок

19 элементов И, пг"разрядный регистр .20, блок 21 элементов И, элемент 22 задержки, блок 23 деления, блок 24 элементов И, блок 25 элементов И, элемент 26 задержки.„ m-разрядный регистр 27, выход 28 и входы 29 и 30 установки начальных значений.

Устройство для огределения числа сочетаний работае:т спедующимобразом.

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

)1og v(+1 m а в регистр 5 — числа К

35 и и двоичном коде ) 1о 8 К +1<т, где

m — - максимальная разрядность регист-. ров.

Работа устройства начинается по команде Пуск", которая подается на вход 1 пуска. По этой команде про изводится начальная установка блока.

10 вычитания, блока 18 умножения, блока 23 деления, счетчика 12 и регистра 20 в нулевое состояние, а в регистр 27 записывается 1 в двоичном коде.

Одновременно сигнал "Пуск" через элемент 3 задержки, обеспечивающий задержку сигнала на время, необходимое для осуществления начальной установки блоков устройства, запускает генератор 4 импульсов.

Очередной импульс с выхода генератора 4 поступает на счетный вход счетчика 12, увеличивая его содержимое на единицу (первый импульс уста.— навливает его в состояние, равное 1. а К-й — в состояние, равное К) и устанавливая его в состояние i. Потенциалы двоичного кода состояния счетчика подаются на входы блоков

16, 17 и 24 элементов И.

Одновременно тактовый импульс поступает на входы элементов 7 и 8 задержки. Сигнал с выхода элемента 7, задержанный, в основном, на время срабатывания счетчика 12, поступает одновременно на входы блоков 6, 11, 9 и 17 элементов И и вход элемента

15. задержки. По этому сигналу двоичный код числа К параллельно подается из регистра 5 через блок 9 элементов И на вход блока 13 сравнения, на второй вход которого поступает двоичный код текущего состояния счетчика !2 через блок 17 элементов И. Блок 13 производит сравнение двух двоичных чисел. Если срабатываемь е числа равны, то блок сравнения формирует сигнал, который, поступая на вход останова генератора 4, запрещает генерирование тактовых импульсов. Если числа.не равны, то генератор через время, определяемое периодом следования тактовых импульсов, формирует очередной импульс, и работа устройства продолжается °

Пусть числа не равпы, Тогда код числа из регистра 2 поступает через блок 6 элементов И на вход блока 10 вычитания, на второй вход которого подается двоичный код состояния счетчика предыдущей итерации, хранившейся в регистре 20 (на первой итерации

О, записанный при начальной установке устройства) . Таким образом, на выходе блока вычитания формируется потенциал „соответствующий двоичному коду разности и-(i-1) (на первой итерации и-О) . По истечении времени, определяемого длительностью задержки

i-ro тактового импульса эпементом 8 задержки, разрешается прохождение двоичного кода состояния счетчика 12 с его выхода через блок 16 элементов

И на вход регистра20, где он записывается. На i-й итерации импульс, задержанный на элементе 15, поступая на соответствующие входы блоков 14 и 19 элементов И, обеспечивает прохождение через них соответственно с выхода блока вычитания двоичного кода числа и (1-1) (на первой итерации и-О) и кода, хранящегося в регистре

27, соответствующего произведению

1396148

1-1 г и- 1- 1) ! 1 -- — — — (на первой итерации 1), е- 1 — 1 1-1 равному С„, на входы блока 18 умножения, Блок умножения осущеcтвля» ет вычисление произведения С„ х(n-(i-1) ). Одновременно импульс с выхода элемента 15 задержки поступает на вход элемента 22 задержки, где 1О задерживается на время, определяемое, в основном, временем срабатывания блока умножения, Сигнал с выхода элемента 22 задержки поступает соответственно на вход элемента 26 задерж- 15 ки, а также на входы блоков 21 и 24 элементов И, разрешая прохождение на входы блока 23 деления с выхода блока умножения двоичного кода числа С,, (n(i-1)) (1i(п-0)) - на пер- 20 вой итерации), а с выхода счетчика

12 — кода числа i. Блок деления осуществляет деление двоичного числа

C Ä (n-(i-1)) на двоичное число

Частное от деления есть число целое. 25

В самом деле, и g i 12 «(п- ((i-1) -1) ) п-g>-12)

1 (i-1)! i п1

Й:Й:12) .— —.— = С . За (n- i) Г1! ю

С вЂ” заведомо целое число. Этот реп зультат деления в двоичном коде поступает через блок 25 элементов И, открытый по сигналу с выхода злемен- 35 та 26 задержки, на вход регистра 27, где записывается и хранится до сле" дующей итерации работы устройства.

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

Однако на К-й итерации будут выполнены все действия, описанные для

i-Й итерации, а следовательно, в регистре 27 будет накоплено в двоичном 5р и (1 12 к коде произведение P ††.--- = С„, 1 -1 равное числу сочетаний из и по К, которое можно снять на выход 28 в двоичном параллельном коде.

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

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

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

Составитель G. Березикова

Техрец И.Дидык Корректор Н. Король

- едактор A. Лежнина

Заказ 2496/50

Подписное

Тираж 704

ВПИИПИ Государственного комитета СССР по делам изобретений и открытий

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

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