Устройство для поиска заданного числа

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК 191 9 4 С 06 Р 7/06 НОМИТЕТотнРытиям ГОСУД АРСТ 8 ЕННЫПО ИЗОБРЕТЕНИЯМПРИ ГКНТ СССР ЗОБРЕТЕНИДЕЧЕЛЬСТВУ ПИСАНИ Н АВТОРС(71) Киевский политехнический инстут им. 50-летия Великой Октябрьссоциалистической революции(56) Авторское свидетельство СССРВ 997029, кл. 6 06 Р 7/06, 1978.Авторское свидетельство СССРР 1183955, кл. С 06 Р 7/Об, 1985(54) УСТРОЙСТВО ДЛЯ ПОИСКА ЗАДАННЧИСЛА(57) Изобретение относится к вычительной технике и может быть исползовано в качестве автономного бло ГО ст сли и 29 элементов ИЛИ, элемент ИЛИ поль, триггеры 31 и 32, элементы 33-35 лока задержки, информационные входы устрой"упо-, ства 36, выход 37 "Число найдена",выход 38 "Адрес устройства", выход 39быст- "Считывание", вход 40 тактовых импуль.сов, вход 41 "Запись", вход 42 "Запуск" ,вход 43 "Адрес конца массива чихема сел", вход 44 "Адрес начала массива чинные диа-сел", выход 45 "Конец поиска" ,Позициями4 бобозначены выходы распределителя 9 импульсов, позициями 49-52. - выходы распределителя 8 импульсов, .позициями 53-55 - выходы "Больше", "Меньше" и "Равно" схемы б сравне,ния соответственно.Устройство работает следующим образом. Изобретение относится к вычи ельной технике и может быть ис вано в качестве автономного б М при поиске заданных чисел в доченном массиве.Цель изобретения - повышение действия устройства. т ок-с реме тры 1-5, еделите- И 10-12, ементы И 22 адре элемен- группы На Фиг. изображена бл устройства; на фиг. 2 - в граммы работы устройства.Устройство содержит регис схемы 6 и 7 сравнения, распр ли 8 и 9 импульсов, элементы группы элементов 13-15 И, эл 16-20, сумматор 21, счетчик саэлемент ИЛИ 23, группу 2 тов ИЛИ, элементы ИЛИ.25-27,ЗВМ при поиске заданных чисел в упорядоченном массиве. Целью изобретения является повышение быстродействия, Устройство содержит регистры1-5, схемы сравнения 6,7, распределители импульсов 8,9, элементы И 10,11,12, 16-20, группы 13, 14, 15 элементов И, сумматор 21, счетчик адреса22, элементы ИЛИ 23, 25, 26, 27, 30,группы 24, 28, 29 элементов ИЛИ,триггеры 31, 32, элементы задержкиЗЗ, 34, 35, Устройство определяет:попадает искомое число в рамки массива или нет. Если искомое число попадает в рамки массива, то за счетреализации в устройстве метода половинного деления для поиска заданногочисла достигается увеличение бь ро,действия, 2 ил.1532914В исходном состоянии в регистр 2заносится значение числа, котороетребуется найти в упорядоченном повозрастанию массиве чисел, Импульс"Запись" с входа 41 устройства про"ходит через элементы ИЛИ 26 и 27 настробкруощие входы регистров 3 и 4,записывая в нкх адрес конца массивачисел, поступающих с входов 43 и 44устройства через группы 28 и 29 элементов ИЛИ,Поиск числа начинается по импульсу "Запуск" с входа 42 устройства,который устанавливает триггер 32в единичное состояние, а триггер 31в нулевое. Тактовые импульсы с. входа 40 устройства поступают через элемент И 9, открытый сигналом с прямого выхода триггера 32 и через элемент И 18, открытый сигналом с инверсного выхода. триггера 31, на входраспределителя 9 импульсов распределители Я к 9 импульсов могут быть выполцецы на элементах задержки, обеспечквающкх синхронизацию работы устройства ). Тактовые импульсы черезэлемент И 12 на вход распределителя Яимпульсов не поступают, так как элемент И 12 закрыт нулевым логическимуровнем с прямого выхода триггера 31.Первый импульс с выхода 46 распределителя 9 импульсов разрешает про, хождение адреса конца массива с выхо, дов регистра 3 через группу 14 элес 35ментов И, который через группу 2 чэлементов ИЛИ поступает на вход регистра 5.к записывается в него по сигналу с выхода 46 распределителя 9импульсов, поступающего через элемецт ИЛИ 23 на. его стробируюприй вход,а через элемент задержки 33 - на выход 39 "Импульс считывания". По этому кмпульсу кз ЗУ ЭВМ считываетсяпоследнее число массива верхияя гра 45нкца - ВГ), которое поступает на информационные входы 36 устройства изаписывается в регистр 1, После сравнения последнего числа в массиве с искомым ца схеме 6 сравнения в завкси 50мости от состояния ее выходов возможны три варианта работы устройства,На выходе 55 "Равно" схемы 6 сравненкя появляется сигнал "1". В этомслучае он поступает на выход 37 устройсгва "Число найдено", а через элемент ИЛИ 30 на вход установки в "0"триггера 32, сигнал с прямого выходакоторого запрещает прохождение в устройство тактовых импульсов с его входа 40, а сигнал с обратного выходатриггера 32 поступает на,выход 45,"Конец поиска", Это означает, чточисло найдено и поиск окончен. На выходе "Меньше" 54 схемы 6 сравненияпоявляется сигнал "1", он проходитчерез первый элемент И 10, открытыйсигналом с выхода 46 распределителя9 импульсов, задержанного на элементе 34 задержки (задержка осуществляется на время выборки числа изпамяти и сравнения чисел на схеме сравнения 6, а также через элемент ИЛИ25, элемент И, открытый сигналом собратного выхода триггера 31, и элемент ИЛИ 30 на вход установки в "О"триггера 32, который сигналом сосвоего прямого выхода запрещает прохождение в устройство тактовых импульсов с входа 40 устройства, а сигнал с обратного его выхода поступаетна выход 45 "Конец поиска". Это значит, что искомого числа в массивенет и поиск окончен. На выходе 53"Больше" схемы 6 сравнения появляетсясигнал "1". В этом случае искомоечисло меньше последнего числа в массиве чисел и работа устройства продолжается,Аналогично описанному второй имгпульс с выхода 47 распределителя импульсов 9 обеспечивает выдачу на вы- .ход 38 "Адрес устройства." адреса начала массива, а на выход 39 "Импульссчитывания" - импульса считывания.После сравнения первого числа в массиве (нижняя граница - НГ) с искомымтоже возможны три варианта работыустройства. В первом случае, есличисла равны работа устройства ана"логична описанномуЕсли первое число массива больше искомого числа, тосигнал с выхода 53 "Больше" схемы 6сравнения через открытый элементИ 11 на второй вход его поступаетразрешающий импульс с выхода 47 распределителя 9 импульсов, задержанныйна элементе 35 задержки) поступаетаналогично описанному на выход 45"Конец поиска", В этом случае искомого числа в массиве нет и поиск окончен. Если искомое число больше пер"вого числа в массиве, то это значит,что число может быть в массиве и работа устройства продолжается,С выхода 48 распределителя 9 импульсов импульс поступает на вход5 153291 установки в "1" триггера 31, который сигналом со своего обратного выхода запрещает прохождение тактовых импульсов через элемент И 18.на вход распределителя 9 импульсов, а сигналом .со своего прямого выхода разрешает прохождение тактовых импульсов через элемент И 12 на вход распределителя 8 импульсов. Первый импульс появляется на выходе 49 распределителя 8, Этот импульс разрешает запись информации в счетчик 22, врезультате чего сумма НГ и ВГ с выходов сумматора 21 со сдвигом на один разРяд в сторону младших разрядов заносится в счетчик 22. Этот адрес является первой (в последующем - очередной) границей. Таким образом, первая граница Г определяется следующим об- О разом:Г (НГ+ВГ) /21,где Х 1 - ближайшее целое, меньшееили равное Х,После этого появляется импульс на 25выходе 50 распределителя 8, по которому разрешается прохождение границычерез группу элементов И 15 и группуэлементов ИЛИ 24 на вход регистра 5,Она записывается в него по импульсу 3 Ос выхода 50 распределителя 8, поступающего на его стробирующий вход че"рез элемент ИЛИ 23, а также черезэлемент 33 задержки на выход 39 "Импульс считывания", По этому импульсуиз ЗУ ЭВМ считывается число с адресомГ и записывается в регистр с инФормационных входов устройства 36 Первая схема сравнения осуществляетсравнение искомого числа, находящегося в регистре 2, с числом, считаннымв первый регистр 1. При этом возможны три варианта работы устройства,Считанное число равно искомому.В. этом случае появляется сигнал "Равно" на выходе 55 схемы б сравнения,по которому, аналогично описанному навыходах 37 и 45 появляются единичныесигналы.Считанное число меньше искомого,В этом случае появляется сигнал "Меньше" на выходе 54 схемы б сравнения.Этим сигналом задается суммирующийрежим счетчика 22 и открывается элемент И 17Считанное число больше искомого.В этом случае появляется сигнал "Больше" на выходе 53 схемы б сравнения,по которому задается вычитающий режим,4 бсчетчика 22 и открывается элементИ 1 б.По импульсу на выходе 5 1 распределителя 8 содержимое счетчика 22 увеличивается или уменьшается на единицув зависимости от заданного режима работы. После этого появляется импульсна выходе 52 распределителя 8, который прохрдит либо через элемент И 16,либо через элемент И 17 и стробируетзапись нового адреса либо в регистр3, либо в регистр 4. В результатеэтого в один из регистров 3 или 4осуществляется запись адреса, сФормированного в счетчике 22,Таким образом, если число, считанное из ЗУ ЭВМ, меньше искомого числа(т.е. в первой половине массива чиселискомого числа нет), то к первой границе прибавляется единица и полученный адрес записывается в регистр 4в качестве адреса нижней границы нового массива чисел, содержащего искомое число, если же число, считанноеиз ЗУ ЭВМ, больше искомого числа(т,е. во второй половине массива чисел искомого числа нет), то из первойграницы вычитается единица и полученный адрес записывается в регистр 3в качестве адреса верхней границы нового массива чисел, содержащего искомое число. Следовательно после выборки числа по адресу первой границы иего анализе, размер массива чиселуменьшается вдвое. После этого сновапоявляется импульс на выходе 49 распределителя 8, по которому Формируется вторая граница по тому же правилу.Г= (Нг+ВГ)/2 ,только одна из НГ или ВГ не равна соответствующему адресу при Формировании первой гранипы.В дальнейшем устройство работаетаналогично описанному.Если искомое число в массиве отсутствует, то наступает такой моменткогда ВГ становится меньше НГ (наединицу). Эту ситуацию Фиксирует схема 7 сравнения, выдавая сигнал насвоем выходе, когда содержимое регистра 3 меньше содержимого регистра 4.Этот сигнал через элемент ИЛИ 30 поступает на вход установки в "0" триггера 32 и на вход устройства 45,Триггер 32 сигналом со своего прямоговыхода закрывает седьмой элемент И19, запрещая прохождение в устройствотактовых импульсов с его входа 40.Таким образом, за первые два такта устройство определяет, попадает искомое число в рамки массива или нет. Если нет, то на выходе устройства 45 появляется единичный логический уровень, а на 37 единичный логический ровень отсутствует, что свидетельствует о том, что число не найдено и анализ окончен, Если искомое число опадает в рамки массива, то устройство максимум за и тактов найдет это исло, при этом на выходе устройства 38 находится его адрес, а на выхо" дах 37 и 45 появляются единичные ровни, свидетельствующие, что число айдено и анализ окончен, Если числа й массиве нет, то через и тактов на выходе устройства 45 появляется еди" ичный уровень, а на 37 единичный 1 равень отсутствует, что свидетельстует о том, что число не найдено и нализ окончен.За счет реализации в устройстве метода половинного деления для отыскивания заданного числа достигается велчение быстродействия в результате уменьшения количества обращений к ЗУ ЗБМ при поиске заданного числа.ЗОФормула изобретения Устройство для поиска заданного Числа, содержащее четыре регистра, счетчик адреса, две схемы сравнения, триггер, группу элементов И, пять элементов И, два элемента ИЛИ, элемент задержки, причем информационные входы устройства соединены с информационными входами первого регист ра, выходы разрядов которого соединены с первой группой входов первой схемы сравнения, вторая группа вхо" дов которой соединена с выходами разрядов второго регистра, информационные входы которого являются входами заданного числа устройства, выход равенство первой схемы сравнения является выходом "Число найдено" устройства и соединен с первым входом первого элемента ИЛИ, выход Больше" первой схемы сравнения соединен с первыми входами первого и второго элементов И, выход которого соединен с первым входом второго элемента ИЛИ, выход меньше первой схемы сравнения соединен с первым входом третьего элемента И, выходы разрядов третьего регистра соединены с первой группой входов второй схемы сравнения, вход "Запуск"устройства соединен с входом установки в "О" триггера, прямой выход которого соединен с первым входом четвертого элемента И, о т л и ч а ю щ е ес я тем, что, с целью повышения быстродействия, .в него введены пятый регистр, два распределителя импульсов,сумматор, вторая и третья группы эле"ментов И, второй триггер, шестой,седьмой и восьмой элементы И, третий,четвертый и пятый элементы ИЛИ; тригруппы элементов ИЛИ, второй и третийэлементы задержки, причем вход тактовых импульсов устройства соединен спервым входом пятого элемента И, второй вход которого соединен с прямымвыходом второго триггера, а выходсоединен с первым входом шестого эле-,мента И и вторым входом четвертогоэлемента И, выход которого соединенс входом первого распределителя импульсов, второй вход шестого элемента И соединен с инверснйм выходомпервого триггера и первым входомседьмого элемента И, а выход соединен с входом второго распределителяимпульсов, первый выход которого соединен с первым входом третьего элемента ИЛИ, с управляющими входамиэлементов И первой группы и черезпервый элемент задержки с вторым входом третьего элемента И, второй выход второго распределителя импульсовсоединен с вторым входом третьегоэлемента ИЛИ, с управляющими входамиэлементов И второй группы и черезвторой элемент задержки с вторым входом первого элемента И, выход которого соединен с первым входом четвертого элемента ИЛИ, второй вход которогосоединен с выходом третьего элемен .та И, а выход соединен с вторым входом седьмого элемента И, выход которого соединен с вторым входом первогоэлемента ИЛИ, третий вход которогоподключен к выходу второй схемы сравнения, а выход. соединен с входом установки в "О" второго триггера, инверсный выход которого является выходом "Конец поиска" устройства, авход установки в "1" подключен к входу "Запуск" устройства, третий выходвторого распределителя импульсов соединен с входом установки в "1" пер-.вого триггера, первый выход первогораспределителя импульсов соединен свходом разрешения записи счетчика9 153291 адреса, информационные входы которого соединены с выходами разрядов сумматора, первая группа входов которого подключена к выходам разрядов третьего регистра и к информационным вхо 5 дам элементов И первой группы, выходы которых соединены с первыми входами соответствующих элементов ИЛИ группы, . выходы которых соединены с информационными входами четвертого регистра, выходы разрядов которого являются выходами адреса устройства, а управляющий вход подключен к выходу третьего элемента ИЛИ и через третий элемент задержки соединен с выходом "Разрешение считывания" устройства, второй выход первого распределителя импульсов соединен с третьим входом третьего элемента ИЛИ, с управляющими входами элементов И третьей группы, информационные входы которых подключены к выходам разрядов счетчика адреса и к первым входам соответствующих элементов ИЛИ второй и третьей групп, вторые 25 входы которых являются соответственно адресами конца и начала массива устройства, а выходы соединены соответственно с информацюнными входами О третьего и пятого регистров, выходыразрядов которого соединены с вторымигруппами входов сумматора, второйсхемы сравнения и информационнымивходами элементов И второй группы,выходы которых соединены с вторымивходами соответствующих элементов ИЛИпервой группы, третьи входы которыхсоединены с выходами соответствующихэлементов И третьей группы, выход"Больше" первой схемы. сравнения соединен с вычитающим входом счетчикаадреса, суммирующий вход которогосоединен с выходом "Меньше" первойсхемы сравнения и с первым входомвосьмого элемента И, выход которогосоединен с первым входом пятого элемента ИЛИ, вход ".Запись" устройстваподключен к вторым входам пятогои второго элементов ИЛИ, выходы которых подключены соответственно к входам записи пятого и третьего регистров, третий выход первого распределителя импульсов соединен с счетнымвходом счетчика адреса, четвертыйвыход первого распределителя импульсов соединен с вторыми входами второго и восьмого элементов И.1532914 рректор М. Кучерявая Составитель А. Козлочолинская ТехредЛ,Олийнык еда Производственно-издательский комбинат "Патент", г. Ужгоро Гагарина, 101 аказ 8100/53 Тираж 668 Подписное.НИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС113035, Москва, Ж, Раушская наб., д. 4/5