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

 

Изобретение относится к области вьгаислительной техники и может быть использовано для упорядочения двумерных массивов чисел по строкам (столбцам ) массива. Целью изобретения является повьшение быстродействия устройства при упорядочении двумерного массива чисел по признаку невозрастания чисел йо строке. Устройство содержит блок 1 синхронизации, счетчик 2, первзгю и вторую группы блоков 3 и 4 памяти, группу ключей 5, группу блоков 6 злементов И, группу блоков 7 синхронизации, две группы элементов И 8 и 9, блок 10 выбора максимального кода, блок 11 приоритета, блок 12 элементов ИЛИ и с первого по третий элементы ИЛИ 13, 14 и 15. Перед началом работы числа исходного массива вводят в блоки 3 памяти (в каждый блок - один столбец массива)о Далее последовательно выбираются строки чисел массива и упорядочиваются при помощи блока 10 выбора максимального кода. 3 ил. сл

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИН (50 4 G 06 С 7/122 G 06 F 3 36

ОПИСАНИЕ ИЗОБРЕТЕН 8 --

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ -- «/

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

flO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4241950/24-24 (22) 12.05.87

{46) 15. 12.88. Бюл..Я 46 (72) О.Г.Алексеев, В.А.Мильков и Н.И.Ячкула

{53) 681.333 (088.8) (56) Авторское свидетельство СССР

В 690505, кл. G 06 G 7/122, 1979.

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

Ф 1249544, кл. G 06 С 7/122, 1986. (54) УСТРОЙСТВО ДЛЯ УПОРЯДОЧЕНИЯ МАС, СИВА ЧИСЕЛ (57) Изобретение относится к области вычислительной техники и может быть использовано для упорядочения двумерных массивов чисел по строкам (столбцам) массива. Целью изобретения является повьппение быстродействия устÄÄSUÄÄ 1444830 А 1 ройства при упорядочении двумерного массива чисел по признаку невозрастания чисел по строке. Устройство содержит блок 1 синхронизации, счетчик 2, первую и вторую группы блоков 3 и 4 памяти, группу ключей 5, группу блоков 6 элементов И, группу блоков 7 синхронизации, две группы элементов

И 8 и 9, блок 10 выбора максимального кода, блок 11 приоритета, блок 12 элементов ИЛИ и с первого по третий элементы ИЛИ 13, 14 и 15. Перед началом работы числа исходного массива вводят в блоки 3 памяти (в каждый блокодин столбец массива). Далее последовательно выбираются строки чисел массива и упорядочиваются при помощи блока 10 выбора максимального кода.

3 ил.

1444830

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

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

На фиг. 1 представлена функциональная схема устройства; на фиг. 2 — временная диаграмма работы блока синхронизации; на фиг. 3 — временная диаграмма работы блоков синхронизации группы.

Устройство содержит блок 1 синхронизации, счетчик 2, первую группу из

M блоков 3 памяти, где И вЂ” количество 20 чисел в строке массива, вторую группу из M блоков 4 памяти, группу из M ключей 5, группу из M блоков 6 элементов И, группу из М блоков 7 синхронизации, первую группу из M эле- 25 ментов И 8, вторую группу из И эле1ментов И 9, блок 10 выбора максимального кода, блок 11 приоритета, блок

12 элементов ИЛИ и с первого по третий элементы ИЛИ 13-15. 30

Кроме того, на фиг.1 показаны вход

16 начальной установки устройства, вход 17 пуска устройства, информационный выход 18 счетчика 2 (подключен к адресным входам всех блоков 3 4 памяти), первый выход 19 блока 1 синхронизации, второй выход 20 блока 1 синхронизации, выходы 21 группы блока 1 синхронизации, с первого по четвертый выходы 22 - 25 блока 7 синхронизации. 4О

Устройство работает следующим образом.

Пусть необходимо упорядочить по невозрастанию чисел в строках массив

1 2 4

3 1

Перед началом работы указанный мас50 сив чисел записывают в блоки 3 памяти.

При этом в первый блок 3 памяти группы по адресам 1-3 записывают соответственно числа 1,5,7 (т.е. числа первого столбца массива), во второй блок

3 памяти группы по адресам 1, 2, 3 записывают числа 2, 3, 2 и в третий блок 3 памяти группы по адресам 1, 2, 3 - числа 4, 1, 1. На вход 16 начальной установки подают импульсный сигнал единичного уровня. При этом счетчик 18 обнуляется, блок 1 синхронизации устанавливается в исходное состояние. На вход 17 пуска устройства подают импульсный сигнал единичного уровня. При этом блок i синхронизации начинает вырабатывать сигналы, предусмотренные временной диаграммой

его работы. Сигнал единичного уровня появляется на вьпсоде 20 блока 1, при этом все ключи 5 группы устанавливаются в исходное состояние, при котором их информационные входы соединены с информационными выходами, в счетчике 2 фиксируется код числа 1, блоки

3 памяти выдают на свои выходы числа первой строки массива. Одновременно появляется сигнал на первом выходе

21 группы блока 1. Через время Ò1, достаточное для выбора максимального из кодов чисел 1, 2, 4 (т.е. максимального из чисел первой строки массива), обладающего наивысшим приоритетом (в данном случае — числа 4), на выходе 19 блока 1 появляется импусный сигнал единичного уровня, который запускает третий блок 7 синхронизации группы (так как число 4 нахо" дится в третьем блоке 5 памяти), Тре-, тий блок 7 синхронизации начинает вырабатывать импульсные сигналы в соответствии с временной диаграммой работы. Сигнал появляется на выходе 21 третьего блока 7, при этом открывается третий блок 6 элементов И, и одновременно — на выходе 24 третьего блока 7, при этом третий ключ 5 размыкает свою информационную цепь (выключается). Через время Т1, достаточное для выдачи максимального числа на информационные входы блоков 4 памяти, третий блок 7 формирует сигнал на выходе 23. При этом максимальное число первой строки {число 4) заносится по адресу 0 в первый блок 4 памяти группы. Сразу после завершения процесса записи третий блок 7 синхронизации формирует сигнал на выходе 25. При этом блок 1 синхронизации снимает потенциал единичного уровня с первого выхода 21 группы и формирует его на втором выходе 21 группы. Далее работа устройства повторяется: выбирается максимальное из оставшихся чисел первой строки (1 и 2), записывается во второй, блок 4 памяти группы и т,д, 3 f4448

После того как будут упорядочены все числа первой строки массива, по очередному импульсу пуска появится сигнал на выходе 20 блока 1 синхрониза" ции. При этом счетчик 2 зафиксирует код числа 2, на выходах блоков 3 памяти группы появятся числа второй строки массива и т.д. После того как будут упорядочены числа всех строк 1О массива, при очередном пуске блока 1 синхронизации сигнал с выхода 20 переполнит счетчик 2, что будет служить признаком окончания работы устройства.

Кроме того, сигнал с выхода признака 15 переполнения остановит блок 1 синхронизации и работа устройства прекратится. При этом числа исходного массива будут упорядочены по строкам следующим. образом: 20

4 2 1

5 3 1

7 2 1

В том случае, если числа массива вводятся в блоки 3 памяти группы по строкам, устройство упорядочивает числа массива по невозрастанию в столбцах. ЗО

Следует отметить, что группы блоков 3, 4 памяти могут быть выполнены в виде матриц регистров. формула изобретения 35

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

М блоков памяти, где M — количество чисел в строке массива, группу из М 4О ключей, блок выбора максимального кода, три элемента ИЛИ, блок синхрониЬации и счетчик, о т л и ч а ю щ е ес я тем, что, с целью повышения быстродействия устройства при упорядочении двумерного массива чисел по признаку невозрастания чисел по строке, в него введены две группы из М элементов И, группа из М блоков синхронизации, группа из М блоков элемен-5 тов И, блок элементов ИЛИ и блок приоритета, причем вход начальной установки устройства подключен к входу начальной установки блока синхрониза30 4

11 1! ции и к выходу установки а 0 счетчика, информационный выход которого подключен к адрес»»ым входам всех бло" ков памяти первой и второй групп, выход К-го блока памяти первой группы (К=1,,М) подключен к информационному входу К-го ключа группы и к информационнму входу К-го блока элементов

И группы, выход которого подключен к

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

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

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

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

1444830

Составитель А.Мишин

Редактор М.Циткина Техред И,Дидык Корректор М.Максимишинец, Заказ á509/51

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

8хН пуск

Тираж 704 Подписное

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

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

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

 

Похожие патенты:

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

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

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

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

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

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

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

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

Изобретение относится к области техники, связанной с Интернет-технологиями, и в частности к системе и способу уведомления об обновлении. Технический результат заключается в обеспечении возможности динамического отслеживания многообразия сетевых ресурсов, включая те, что не поддерживают вывод RSS, и уведомления пользователей, после того как соответствующие сетевые ресурсы обновляются. Технический результат достигается за счет способа, который включает в себя этапы, на которых: выбирают (301) сетевой ресурс; извлекают (302) конкретное содержимое сетевого ресурса; сравнивают (303) дважды последовательно извлеченное конкретное содержимое сетевого ресурса; уведомляют (304) пользователей о том, что содержимое сетевого ресурса обновлено, если изменено конкретное содержимое. 2 н. и 27 з.п. ф-лы, 14 ил.

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

Изобретение относится к системам ориентации и управления движением космических аппаратов при реализации программных разворотов

Изобретение относится к автоматике и вычислительной технике и может быть использовано в системах обработки изображений и распознавания образов

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

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

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

Изобретение относится к вычислительной технике и может быть использовано при автоматизации процессов управления различными сетями

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

Изобретение относится к области вычислительной техники и может найти применение при проектировании сложных систем
Наверх