Устройство для определения числа сочетаний Советский патент 1988 года по МПК G06F15/20 

со

О5

00

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

Цель изобретения - повышение точности.

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

: Устройство содержит вход 1 пускаS I т-разрядный регистр 2, элемент 3 за- i держки, генератор 4 тактовых импуль- : сов, т-разрядный регистр 5, блок 6 : элементов И, элемент 7 задержки, эле- : мент 8 задержки, блок 9 элементов И, : блок to вычитания, блок 11 элементов И, счетчик 12, блок 3 сравнения, i блок 1А элементов И, элемент 15 за.- держки, блок 16 элементов И, блок 17 : элементов И, блок. 18 умножения, блок I 19 элементов И, яг-разрядньй регистр . 20, блок 21 элементов И, элемент 22 задер.), блок 23 деления, блок 24 : элементов И, блок 25 элементов И, элемент 26 задержки,, га-разрядный регистр 27, выход 28 и входы 29 и 30 установки начальных значений.

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

Перед началом работы устройства производится запись в регистр 2 чис- : ла п в двоичном коде, причем log n +lira, а в регистр 5 - числа К Б дво1-ганом коде log,,, где ш Максимальная разрядность регистров .

Работа устройства начинается по команде Пуск, которая подается на вход 1 пуска. По этой команде про- изводится начальная установка блока 1,0 вычитания, блока 18 умножения, блока 23 деления, счетчика 12 и регистра 20 в нулевое состояние, а в регистр 27 записывается 1 в двоичном коде.

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

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

5

0

а К-й - в состояние, равное К) и устанавливая его в состояние i. Потенциалы двоичного кода состояния счетчика подаются на входы блоков 16, 17 и 24 элементов И.

Одновременно тактовый импульс поступает на входы элементов 7 и 8 задержки. Сигнал с выхода элемента 7,

g задержанный, в основном, на время срабатывания счетчика 12, поступает одновременно на входы блоков 6, 11, 9 и 17 элементов И и вход элемента 15- задержки. По этому сигналу двоич- ньй код числа К параллельно подается из регистра 5 через блок 9 элементов И на вход блока 13 сравнения, на второй вход которого посту- пает.двоичный код текущего состояния счетчика 12 через блок 17 элементов И. БЛОК 13 производит сравнение двух двоичных чисел. Если срабатываемые числа равны, то блок сравнения формирует сигнал, который, поступая

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

Пусть числа не равны. Тогда код числа из .регистра 2 поступает - через блок 6 элементов И на вход блока 10 вычитания, на второй вход которого подается двоичный код состояния счетчика предыдущей итерации, хранившейся в регистре 20 (на первой итерации О, записанный при начальной установке устройства). Таким образом, на выходе блока вычитания формируется потенциал, соответствующий двоичному коду разности n-(i-l) (на первой итерз ции п-0). По истечении времени, определяемого длительностью задержки i-ro тактового импульса элементом 8 задержки, разрешается прохождение двоичного кода состояния счетчика 12 с его выхода через блок 6 элементов И на вход регистра20, где он записывается. На i-й итерации импульс, задержанный на элементе 15, поступая на соответствующие входы блоков 14 и 19 элементов И, обеспечивает прохождение через них соответственно с

5 вы.хода блока вычитания двоичного кода числа n-(i-) (на первой итерации п-0) и кода, хранящегося в регистре 27, соответствующего произведению

0

5

0

5

0

П n-(l-l)„,

I I (на первой итерации I),

Eni 1

-1 i-i

равному С„, на входы блока 18 ум-

ножения. Блок умножения осущ$ств,г1Я- ет вычисление произведения С x(n-(i-l)). Одновременно импульс с выхода элемента 15 задержки поступает на вход элемента 22 задержки, где задерживается на время, определяемое в основном, временем срабатывания блока умножения. Сигнал с выхода элемента 22 задержки поступает соответственно на вход элемента 26 задерж- ки, а также на входы блоков 21 и 24 элементов И, разрешая прохождение на входы блока 23 деления с выхода блока умножения двоичного кода числа (n(i-l)) (1(п-0)) - на пер- вой итерации), а с выхода счетчика 12-кода числа i. Блок деления осуществляет деление двоичного числа Сп (n-(i-l)) на двоичное число i. Частное от деления есть число целое. В самом деле,

- (n-ai-i)-i))

„ - т- П

(i-l). i

- In-ii-ii). ,:„;

il (n-i)i

С - заведомо целое число. Этот реП

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

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

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

n-(i-ll „ коде произведение | ( -т - - -,,

,« м

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

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

Устройство для определения числа сочетаний, содержащее шесть элемен

5

е Ю , е1520 . 25

30

35 ,

4045

50

.

я

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

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

блока элементов И, 1 ыходы пятого исоединен с вторым входом десятого

восьмого блоков элементов И соедине-блока элементов И, выход которого

Hbt с первыми информационными входа-соединен с вторым информационным вхоми блоков деления и умножения соот-дом блока деления, выход которого

ветственно, отличающеесясоединен с вторым входом девятого

тем, что, с целью повьаиения точное-блока элементов И. тИ, выход седьмого блока элементов I

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