Устройство для выбора упорядоченной последовательности данных
1. УСТРОЙСТВО ДЛЯ ШБОРА УПОРЯДОЧЕННОЙ.ПОСЛЕДОВАТЕЛЬНОСТИ ДАННЫХ , содержащее.входные регистры, дешифраторы, регистр результата, ц групп элементов И, группу элементов ИЛИ, блок анализа, состоящий из элементов ИЛИ и поразрядных узлов анализа , причем выходы каждого i-ro регистра, где i. l, 2, ... n , соединены с входами i-ro дешифратора и с информационньми входа ми элементов И i-и группы, а выходы i-ro элемента ИЛИ подключены к входам управления элементов И i-ft группы, выходы элементов И каждой j-й группы соединены с входами элементовИЛИ группы, выходы которых подключены к входам регистра результата, каждый J -ый выход каждого 1-го дешифратора соединен с J-M входом поразрядного анализа, где j 1, 2,.. ., m, (m - число разрядов сортируемых чисел) , каждый i-й выход }-го поразрядного узла анализа подключен к j-му входу ;i-ro элемента ИЛИ, а выход переносов каждого Ic-ro поразрядного узла анализа, где 1с 1, 2,... , (fti-1), соединен с входом управления (К+1)-го поразрядного узла анализа, каждый поразрядный узел анализа состоит из элементов И, п. элементов НЕ и многовходового элемента И, причем кажйый Zi-й вход поразрядного уэла а нализа подключен к первому входу,1-го элемента И, вход управления поразрядного узла анализа.соединен с в,торыми вхйдами элементов И,, каждый Ч -и вход к-го поразряд1ного узла анализа подключен через i-й элемент НЕ к
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСНИХ
РЕСПУБЛИК
3(5П 6 06 F 7/06
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ
ОПИСАНИЕ ИЗОБРЕТЕНИЯ . К ABTOPCHOMV СВИДЕТЕЛЬСТВУ (21) 3479494/18-24 (22) 28. 07. 82 (46) 07.12. 83. Бюл. Р 45 (72) В. Г. Попов и А.Х. Ганитулин (53) 681.325(088.8) (56) 1. Авторское свидетельство СССР
Р 928342, кл. 0 06 7/06, 1980.
2. Авторское свидетельство СССР
В 903864, кл. 06 7/06, 1980 (прототип).
{54)(57) 1 УСТРОИСТВО ДЛЯ BblBQPA
УПОРЯДОЧЕННОИ ПОСЛЕДОВАТЕЛЬНОСТИ ДАННЫХ, содержащее входные регистры, дешифраторы, регистр результата, я групп элементов И, группу элементов
ИЛИ, блок анализа, состоящий из элементов ИЛИ и поразрядных узлов анализа, причем выходы каждого i-rо регистра, где 1- = 1, 2, ..., соединены с входами -го дешифратора и с информационными входами элементов И i-й группы, а выходы i-ro элемента ИЛИ подключены к входам управления элементов И i-й группы, выходы элементов И каждой i-й группы соединены с входами элементов ИЛИ группы, выходы которых подключены к входам регистра результата, каждый
j -ый выход каждого 1-ro дешифратора соединен c i-û входом )-го поразрядного анализа, где j =l 2,...,а, (A - число разрядов сортируемых чисел), каждый i-й выход j-го поразрядного узла анализа подключен к .1-му входу .1-го элемента ИЛИ, а выход переносов каждого 4-го поразрядного узла анализа, где 1с = 1, 2,..., ( (tn -1), соединен с входом управления (К+3)-ro поразрядного узла анализа, каждый 4-й поразрядный узел анализа состоит из элементов И, и, элементов
НЕ и многовходового элемента И, причем кажФюй 1-й вход поразрядного узла анализа подключен к первоМу входу,i-го элемента И, вход управления поразрядного узла анализа соеди„„SU„„1059565 A нен с в,торыми вхЬдами элементов И, каждый i-й вход к-ro поразрядного узла аналиаа подключен через i-й элемент НЕ к (1 +2) -му входу (i+1), ((+2), ..., n-го элементов И и к
3-му входу многовходового элемента И, выход которого подключен к выходу переносов .g-ro поразрядного узла анализа, выход каждого i-ro элемента
И соединен с 1-м выходом k-го поразрядного узла анализа, П -й поразрядный узел анализа состоит из элементов И и (n-1)-го элемента НЕ, причем каждый. р-й вход узла, где р.=. 1, 2, ..., (n.— 1), соединен с пер- вым входом ф-ro. элемента И, вход переносов р -го поразрядного узла В анализа подкюцочен к вторык входам элементов И, каждый р-й вход m-го поразрядного узла анализа через Р --й див элемент НЕ соединен с (р +2)-м вхо- % дом (р+1), (р+2), ..., и -го элементов И,in -й вход,е-го поразрядного Я узла анализа подключен к (т+2)-му вхоцу,п-го элемента И,выход каждого .1-го элемента И.соединен -с -м выходом rn-ro поразрядного узла Ю анализа, о т л и ч а ю щ е е с я тем, что, с целью расширения его функциональных возможностей путем Q1 обеспечения воэможности получения ., улаф упорядоченного массива чисел любого размера и выдачи его на хранение, в Ql него введены блок управления,коммута. тор,P регистров результата,где 9 2 3.
Т групп элементов ЙЛИ, (t 0 ) групп элементов И, элемент
ИЛИ, группы входнни элементов И и
ИЛИ, шины Начало операции ., Начальное гашение .-и Размер масcasa, причем 1-й вход блока анализа, соединенный с выходом i-го элемента ИЛИ блака анализа, подключен к первьм управлякщим входам i-x элементов И в каждой из Р групп, информационные входы которых соединены
1059565 соединен с первым входом элемента И, второй вход которого соединен с прямым выходом триггера управления и первыми входами элементов И группы, а выход - co счетным входом счетчиt i --го элемента И группы, выход которого является т-м выходом блока управления, выход сигнала переполнения счетчика прдключен к первому входу элемента ИЛИ,.второй вход которого :соединен с шиной . .Начальное гашение I а выход элемента ИЛИ.подключен к нулевому входу триггера управления, единичный вход которого соединен с . входом установки блока управления, а инверсный выход является управляющим выходом блока управления, информационные входы блока управления подключены к установочным входам счетчика. 2. устройство по п.1, о т л и ч аю щ е е с я тем, что коммутатор содержит h групп элементов И, дешифратор, регистр, входы которого соединены с входами коммутатора, а выходы— с соответствующими входами дешифратора, .i-й выход которого подключен к первым входам 1, 2,..., -х групп элементов И, информационные входы (-й группы коммутатора подключены к вторым входам элементов И -й группыр упразляющие входы элементов И всех групп соединены с управляющим входом коммутатора. печивает формирование упорядочен ой 10 последовательности чисел из исходных, что обуславливает Его низкие функциональные воэможности. Наиболее, близким к предлагаемому по технической сущности является устройство для определения наименьшего из и чисел, содержащее последовательно соединенные входные регистры, входы которых являются информаиионныс выходами 0 -ro входного регистра, и к первому входу, -го элемента И группы входных элементов И, вторые взводы всех элементов группы входных элементов И соединены с выходом элемента ИЛИ, выход i--ro элемента группы входных элементов И соединен с первьм входом 3-ro элемента группы входных элементов ИЛИ, выход которого подключен к входу установки в нуль л -го входного регистра, -й выход блока управления подключен к в торым управляющим входам всех эле.ментов И i-й группы и к i-му входу элемента ИЛИ, выходы элементов И . -й группы из (0 ° n ) групп подключены к соответствующим входам 1-ro элемента ИЛИ группы, выходы которого соединены с информационными входами -ro регистра результата, группа информационных выходов -го регистра результата соединена с соответствующими информационными входами -й группы коммутатора, выходы которого являются информационными . выходами устройства, управляющий вход коммутатора подключен к выходу блока управления, шина, Начальное гашение соединена с входом установки блока управления, с нулевыми входами выходных регистров и с вторыми входами всех элементов группы входных элементов ИЛИ, шина ". Размер массива соединена с информационными входами коммутатора и блока.управления, который содержит триггер управления, счетчик, дешифратор, элементы И, ИЛИ, группу б элементов И, генератор импульсов, выход котЬрого Изобретение относится к автоматике и вычислительной технике и может быть исполь зова но при реали зации систем обработки данных и автоматизированных систем управления (АСУ). Известно устройство для сортировки чисел, содержащее 6,; входных регистров, где и "число анализируемых чисел, и элементы И (1). Однако данное устройство не обес2 ми входами устройства, дешифраторы, поразрядные узлы анализа и элементы ИЛИ, причем -й выход каждого -го дешифратора соединен с . -и входом I -ro поразрядного узла анализа, где 1т 1, 2,.;., и; j = 1,2, ...,rh, (rn число раз-рядов сравниваемых чисел), каждый 3-и выход j "го поразрядного узла анализа подключен к j-My" входу i-го элемента ИЛИ, а выход переносов каждого Ф-го поразрядного узла анализа, где К = 1, 2,..., (rn-1), соединен с входом управления (%+1)-го поразрядного узла анализа, каждый i;-й поразрядный узел анализа устройства состоит из и элементов И,п элементов НЕ и многовходового элемента И, причем каждый 1 -й вход узла анализа подключен к первому входу 4-го элемента И, вход управления узла 50 соединен с вторнми входами элементов и, каждый 1 -й вход узла подключен через -й элемент HE к (i+2) «му входу (1 +1), (i +2)...,, h -го элементов И и к 1-му входу многовходового элемента И,выход которого подключен 1 к выходу переносов узла, выход каждого i-ro элемента И соединен с i-м выходом узла, m,-й поразрядный узел анализа состоит из П элементов И и (и-1)-го элемента НЕ, причем каждый р-й вход узла, где p = 1, 2, (n-1), соединен с первич входом р-го элемента И, вход переносов узла подключен к вторим входам элементов И, каждыйр-й вход узла чЕрез р-й элемент НЕ соединен с (р+2) -м входом (р+1), (р+ 2), ...,;n -го элементов И, m -й вход узла подключен к (m+2)-му входу и-го элемента И, выход каждого i-го элемента И со- 20 единен с Ф-м выходом узла Г2 3. Известное устройство обеспечивает выбор одного минимального из и чисел и для формирования упорядоченной последовательности в очередном 25 цикле работы необходимо выбрать из (h-1) оставшихся чисел наименьшее число,и т.д. и при этом организовать хранение этих чисел во внешней памяти устройства. Таким образом, для g0 упорядбчения чисел требуется h циклов. Кроме того, в очередном цикле работы следует исключить из анализа выбранное в предыдущем цикле число. 11ель изобретения — РасшиРение З5 функциональных воэможностей устройства путем обеспечения воэможности получения упорядоченного массива чисел любого размера и выдачи его на хранение. Поставленная цель достигается тем, что в устройство для выбора упорядоченной последовательности данных, содержащее входные регистРыю де ифраторы Регистр резуль- 45 тата, блок анализа, состоящий из элементов ИЛИ и поразрядных узлов анализа,h групп элементов И, группу элементов ИЛИ, причем выходы каждого i ão регистра, где = 1, 2,..., М, соединены с входами 4.-го дешифратора и с информационными входами элементов И 1-й группы, а выходы 1-ro элемента ИЛИ подключены к входам управления элементов И 1-й группы, выходы элементов И каждой i --й55 группы соединены с входами элементов ИЛИ.группы, выходы которых подключены к входам регистра результата, каждый 1-й выход каждоГо l -го дешифратора соединен с ф -м входом 60 j-ro поразрядного узла анализа, . где j = 1, 2,..., m (сп — число разрядов сортируемых чисел), каждый {. — é выход j-ro поразрядного узда .анализа подключен к j -му входу 1-ro 65 элемента ИЛИ, а выход переносов каждого 4-го поразрядного узла анализа, где k= 1, 2, ..., м" 1), соединен с входом управления (Ъ+1)-го поразрядного узла анализа, каждый (I-й поразрядный узел анализа состоит из элементов И,п; элементов HE u многовходового элемента И, причем: каждый i -й вход поразрядного анализа подключен к первому входу 1-ro элемента И, вход управления поразрядного узла анализа соединен с вторыми входами элементов И, каждый i -й вход k-го поразрядного узла анализа подключен через 1 -й элемент НЕ к (1+2)-му входу (i-+1), (+2),..., . в -го элементов И и к 1-му входу многовходового элемента И, выход которого подключен к выходу переносов R-го поразрядного узла анализа выход каждого i-го элемента И соединен с 1-м- выходом t,-ro пораз . рядного узла анализа, 6 -й поразрядный узел анализа состоит из элементов И и (n-1)-ro элемента НЕ, причем каждый Р-й вход узла, где p-= 1, 2,..., (h-1), соединен с первым входом p -го элемента И, вход переносов III-го поразрядного узла анализа под.ключен к вторьи входам элементов И, каждый р-й вход m-го поразрядного узла анализа через р-.й элемент НЕ сое- . динен с (р+2)-м входом (р+1), (р+2), °, .я -го элементов И, е -й вход е-го поразрядного узла анализа подключен.к.(hi+2)-му.входу Il-ro элемента И, .выход .каждого i-го элемента И соединен с -w выходом е-го поразрядного узла анализа, введены коммутатор, блок управления, Ф регистров результата, где 0=2, 3,..., Й, Ц групп элементов ИЛИ, . (У - h ) групп элементов И, .элемент ИЛИ, .группы входных элементов И и ИЛИ шины Начало операции, !Начальное гашение и Размер массива ., причем 1-й выход блока анализа, соединенный.с выходом i-ro элемента ИЛИ блока анализа, подключен к первьм управляющим входам .1-х элементов И в .каждой из R гrрpу пlпl, инфорационные входы которых соединены с выходами 0-Io входного регистра, и к первому входу i-ãî элемента И группы входных. элементов И, вторые входы всех элементов группы входных Элементов .И соединены с выходом элемента ИЛИ, выход i-го элемента группы входных элементов И соединен с первым. входом i ão элемента группы. входных элементов ИЛИ, выход которого подключен.к входу установки в нуль l-ro входного регистра, 1 -й выход блока управления подключен к вторни управляющим входам всех элементов И -й группы и,к < -му входу элемента ИЛИ, выходы элементов И -й группы из (P.- h ) групп под1059565 ключены к соответствукщим входам j -ro элемента ИЛИ 3 группы, выходы которого соединены с информационными входами 9 -го регистра результата, группа информационных выходов -го регистра результата соединена с соответствующими информационными входами l-й группы коммутатора, выходы которого являются информационными выходами устройства, управляющий вхоД коМмутатора подключен к выходу блока управления, шина Начальное гашение соединена с входом установки блока управления, с нулевыми входами выходных регистров..и.с.вто- рыми входами всех элементов группы 15 входных элементов ИЛИ, шина Рв.змер. массива соединена с информационными входами коммутатора и блока управления, который .содержит триггер управления, счетчик, дешифратор, 2О элементы И, ИЛИ, группу а элементов И, генератор импульсов, выход кото-. рого соединен с первЫм входом элемента И, второй вход которого соединен с прямым выходом триггера 25 управления и первыми входами элементов И группы, а выход — со счетным входом счетчика, информационные выходы которого подключены к дешифратору, 1-й выход которого соединен gp с вторым входом i-го.элемента И группы, выход которого является i-м выходом блока управления, выход сигнала переполнения счетчика подключен к первому входу элемента ИЛИ, второй З5 вход которого соединен с шиной Начальное гашение, а выход элемента ИЛИ подключен к нулевому входу триггера управления, единичный вход которого соединен с входом установки блока управления, а инверсный выход является управляющим выходом блока управления, информационные входы блока управления подключены к установочным входам счетчика, Кроме того, коммутатор. содержит 45 h групп элементов И, дешифратор, регистр, входы которого соединены с входами KONMyTamopa, а выходы— с соответствующими. входами дешифра.— тора, i-й выход которого подключен 5О к первым входам 1, 2,..., -х групп элементов И, информационные входы )-й группы коммутатора. подключены к вторым входам элементов И i-й группы, управляющие входы. элементов 55 И всех групп соединены с управляю щим входом коммутатора. На фиг.1.показана блоксхема устройства; на фиг.2 - схема блока уп.равления;.на фиг.3. - схема коммута- 60 тора; на фиг.4 †схема блока анализа. Устройство содержит входные ин- формационные шины 1 -1,, входные регистры 2 -2 дешифраторы 3>-3„, 65 выходные шины 4,-4. которых подклю A чены к блоку 5 анализа, выходные шины б — б„блока анализа,n групп но и элементов И 71- 71„,..., „-, 7 и в каждой группы элементов ИЛИ 8 -8 „, л регистров 9 -9„... результата, выходные шины . 10 -10„которых подключены к коммутатору 11, и выходные шины 1 2 „- 1 2 „ус тройств а, элемент. ИЛИ 13, подключенный к вторым управляющим входам входных эле-. ментов И 14 -14.„группы,. выходы которых соединены с группой входных элементов ИЛИ 15-)-15„, шину 16 Размер массива, по которой подается информация о размере массива на выходе устройства, формируемого из h исхоцных чисел, блок 17 управления, обеспечивающий заданный режим устройства, выходные шины 18 18„ блока управления, шину 19 Йачало операции, по которой поступает сигнал запуска устройства, и шину 20 Начальное гашение, по которой поступает сигнал установки устройства в исходное состояние. Блок управления содержит выходную шину 21 . блока, элемен т ИЛИ 22, три ггер 2 3 управления, .генератор 24 импульсов элемент И 25, счетчик 26, на который принимается информация о размере выходного массива по шине 16, дешифратор 27 и ь элементов И 28 -28, Коммутатор содержит Регистр 29, на который принимается информация о раз- мере выходного массива по шине 16, дешифратор 30, обеспечивающий выдачу массива чисел, размер которого указан в регистре 29, через элементы И 31„."31 Блок анализа содержит m поразрядных узлов 32-32 анализа каждый из ко I которых, кроме rn-ro,состоит из и эле" ментов НЕ 33, многовходового элемента И 34,п элементов И 35, а, ъ -й узел 32 анализа состоит из (n-1)-х элементов НЕ 33„, -33„„„„и 6 элементов И 35 -35„„ „ ., а также и элементов ИЛИ 36. -36„ Устройство работает следующим образом. На вход устройства может быть подан масоив 1 различных по значению чисел, причем 1 < n. С помощью устройства необходимо расставить чисел в.порядке из убывания, причем Задача сводится к определению максимального числа, записи его в первый.выходной регистр и гашению того входного регистра, откуда оно передано в выходной для исключения анализа уже выбранного числа. Затем этот процесс повторяется, пока не выполнится g циклов. По завершении циклов в выходных регистрах буДет :находиться упорядоченная последова1059565 тель ность чисел, составлякщих вырезанный массив размером в чисел из исходного массива в 1 чисел, причем j < n ° ., управление формированием упорядоченного массива производится блоком управления на основе требуемого размера массива. Коммутатор обеспечивает выдачу упорядоченного массива из выходных регистров. Выбор максимального числа из массива исходных чисел в каждом цикле работы устройства производится в блоке анализа и основан на одновременном анализе одноименных выходов дешифраторов исходных чисел. Определение минимального :(максимального) числа сводится к анализу одноименных выходов дешифраторов, причем номер выхода, где имеется 20 неравнозначность или же единичные значения сигналов при равных числах, будет указывать на меньшее (большее) число. Если начать анализ с младших по номеру выходов дешифраторов, то 25 выбирается меньшее число, если со старших — то большее. Если на дешифраторы подать обратные коды чисел, то при анализе с младших выходов выбирается большее число, à со стар- 30 ших - меньшее. В предлагаемом устройстве анализ одноименных выходов дешифраторов начинается с младших выходов дешиф- 35 раторов. Поэтому если необходимо получить упорядоченную последовательность из исходных чисел возрастающую, то исходные числа следует подавать в обра ном коде, если 40 убывакщую - то в прямом коде. Причем упорядоченный массив чисел представ. ляется в том же коде, что и исходные числа. Работа устройства начинается установки входных регистров 2 -2:,, выходных регистров 9 -9„ и трйггера 23 управления блока 17 управления в нулевые состояния сигналом, поступающим по шине 20 Начальное гашение, после чего производится прием во входные регистры 2>-2„ чисел,пос тупающих по шинйм 1„-1„. По шине 16 Размер массива в .счетчик 26 блока 17 управления и в регистр 29 коммутатора.11 и подается двоичный код требуемого размера массива. По окончании приема исходных чисел сигналом, поступающим по.шине 19 Начало операции, устанавливается в единичное состояние триггер, бО 23 управления блока 17 управления. Рассмотрим дальнейшую работу устройства при следукщих условиях необходимб получить возрастающую последовательность из й,чисел; 65 наибольшее число находится в регистре 2, а наименьшее — в регистре 2 . При этих условиях исходные числа необходимо подать во входные регистры 2„-2 д в обратном коде. В счетчик 26 число принимается в дополнительном коде а в регистр 29 — в прямом. Тогда в дешифраторе 30 ком-. мутатора ll возбуждается р -й выход, разрешакщий формирование выходных сигналов на шинах 1 2„-12 „ устройства. В дешифраторе 27 блока управления возбужден выход, и, так как трИггер 23 управления находится в единичном состоянии, на выходной шкые 18 имеется единичный сигнал, разрешакщий работу элементов И 7-„,„-7 „. Одновременно в блоке 5 анализа производится анализ выходных сигналов, поступакщих по шинам 4„-4 > с дешифраторов 3 -3„. Так как найбольшее число находится в регистре 2„, то в дешифратор З„возбужден первый выход. При этом все первые выходы остальных дешифраторов нулевые, поэтому выходные единичные сигналы элементов НЕ 33:„„"-33,„ „ „разрешают прохождение сигнала через элемент И 35 „ в узле 32„ анализа. Этот сигнал поступает через элемент И 35, на выходную шину 6 „ блока 5 анализа и разрешает через группу элементов И 7 и элемент ИЛИ 8 второй группы передачу содержимого регистра 2„: в регистр 9„. результата. Этим же сигналом через элемен И 14,, на первом входе которого действует еди ничный сигнал, с выхода 18 блока 17 управления через элемент ИЛИ 13 и -элемент ИЛИ 15 производится гашение регистра 2, чем исключается выбранное уже число из дальнейшего анализа в . очередном цикле. Очередной цикл начинается по импульсу от генератора 24 импульсов, который переводит счетчик 26 в очередное состояние, по которому возбуждается выход 182 блока 17 управления. Работа по анализу и передаче числа в выходной регистр 92 производится аналогично описанной. В последнем п-м цикле меньшее число окажется в выходном регистре 9„,. По очередному импульсу ат генера-: тора 24 импульсов в блоке 17 управления триггер 23 управления устанавливается в нулевое состояние сигналом переполнения счетчика 26, поступакщим на нулевой вход триггера управления через элемент ИЛИ 22.Единичный сигнал с нулевого выхода триггера по шине 21 поступает в коммутатор 11, и на выходные шины 12„-12„ устройства через элементы .И 31. -31, передается содержимое выходных регистров 9.,-9„ по шинам 10 -10р,представлякщее собой возрастающую последовательность из н исходных чисел. 1059565 При необходимости получения убывающей последовательности из и чисел на входные шины 1 .,-1 „ус тройств а подаются числа в прямом коде. Если необходимо получить последо- 5 вательность чисел, вырезанную иэ и исходных чисел, по шине 1б подается значение размера массива, определяющего число циклов работы устройства. Работа устройства в дальнейшем не отличается от описанной эа исключени- о ем того,что в дешифраторе 30 коммутатора 11 будет возбужден выход, номер которого соответствует размеру требу- ,емого массива.В соответствии с этим будет возбуждено и необходимое число 15 выходных шин 12 устройства. Таким образом, по сравнению.с прототипом предлагаемое устройство имеет большие функциональные возможности. так как оно позволяет получить упо- Щ рядоченный массив любого размера в пределах исходного. Проведем сравнительную оценку предлагаемого устройства и базового 25 объекта, в качестве которого выбран прототип, при использовании их в вычислительных системах, где требуется структурное преобразование массивов данных. 30 Если испольэовать прототип, то для получения упорядоченного массива необходимо выполнить одинаковые действия, состоящие в передаче мас-, 35 сива чисел в устройство, причем в первом цикле чнсе 1 во втором (n -1) чисел и т.д., а в последнем цикле одно число, анализе и выборе наибольшего числа и передаче выбран- 4О ного числа в ЭВМ для заполнения упорядоченного массива. Если принять, что одно число педаеФся за один такт ЭВМ, а анализ -и передача выбранного числа в ЭВМ 45 происходят тоже за.один такт, то суммарное время формирования .упорядоченного массива аостаэляет — =(п1 +t ) ((п-1) а ) ... +(4 +1 ) = = fn+<+n+... + 2) t где - время такта ЭВМ. Воспользовавшись формулой подсчета суммы первых л членов арифметической прогрессии с „+ a„ 50= 2 и! где с „- первый член арифметической прогрессии, a>- 6-й член арифметической прогрессии, получим n(n+ 3) с> При использовании предлагаемого устройства необходимо передать массив исходных чисел в устройство за тактов ЭВМ, выполнить и циклов в устройстве по анализу и передаче выбранного числа в выходной регистр ycTðîécòsà. Тогда суммарное время формирования упорядоченного массива составит 11- =nt +ntÄ = n(t atù . (2f Сравнивая величины, получаемые :по выражениям (1) и (2), получим . выигрыш в быстродействии Е. (" alt и+ь 1 э . (3) з Пусть 1 =С, и =1о., ги Тогда по выражению (3) получим %= = =3 25, 2(1+1} 4 Из выражения (3) следует, .что с увеличением размера преобразуемого массива чисел и приведенного расчета в связи с этим применение предлагаемого устройства более цеЛесообразно, так как обеспечивается снйжение общих затрат машинного времени. 1059565 1059565 Составитель Е.Иванова Редактор A.Ðãàð Техред N.Íàäü Корректор А,Тяско Заказ 9842/53 Тираж 706 Подпис ное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д.4/5 Филиал ППП Патент ., r.JJæãîðîä, улЛ1роектная,4
