Электронная вычислительная машина

135700 ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советских Социалистических РеспубликЗависимое от авт, свидетельстваа явлено 03.1.1960 (Эй 653007/28) Кл. 42 тп, 1 с присоединением заявки111 1 К 6 р нор итет Комитет по поламизобретений н открытипрн Совете МинистровСССРУ,1 К 681.142(088,8 убликовано 16 Х.1967. Бюллетень1 та опубликования описания 21.1 Х.1967 Авторыизобретения ибыш, И, В. Сигалов дман и В. Е. Ходоско С, Павленко, И. В. Васильев, В.Т. Старостин, Н, А. Танцюра, И. Заявител ОННАЯ ВЫЧИСЛИТЕЛЬНАЯ МА ин на тыре неизб.вным нулю возможных Известны электронные вычислительные машины, содержащие устройство ввода данных, запоминающее устройство, составленное из регистров и счетчиков, сумматор, программирующее и управляющее устройства, печатающее (выводное) устройство и блок питания,Предлагаемая электронная вычислительная машина предназначена для нахождения оптимального варианта разделения куска ткани произвольной длины на полотна заданной длины без остатка или с минимальным остатком.Оптимальный вариант находят решением системы диофантовых уравнений видаА=а, ти+ а, и+а, р+ о, где А - длина куска ткани (см);а - длина настила (см);, К т - номера настилов, которые принимаютзначения от 1 до(наибольший номер настила) в соответствии с неравенством 1(Й(1;ит, и, р - количество полотен од аковой длины в соответствующем стиле;6 - остатоки выбору из них решения, содержащего наименьший остаток.Каждое уравнение содержит чевестных коэффициента ит, и, р иОстаток б вначале принимают раи проводят цикл образования всех уравнений и подбора их корней. Если в результате подбора нн одно из уравнений решено не будет, то остаток б принимают равным единице и повторяют цикл. Если и в этом 5 цикле ни одно из уравнений решено не будет,то остаток вновь увеличивают на единицу длины и вновь повторяют весь цикл до получения решения. Если какое-либо из уравнений будет решено, т. е. представленные значения 10 корней коэффициентов удовлетворяют условиям уравнения, то дальнейшее решение прекращают, а результаты решения фиксируют.При прочих равных условиях предпочтениеотдают уравнению с меньшим числом коэф фициентов. Согласно этому требованию циклобразования возможных уравнений разбивают на три этапа. На первом этапе образуют уравнения, коэффициенты которых представляют собой сочетание нзэлементов по одно му; на втором этапе - уравнения, коэффициенты которых представляют собой сочетание из т элементов по два; на третьем этапе - уравнения, коэффициенты которых представляют собой сочетание из т элементов по три.25 Иными словами, для рационального раскроякусков ткани произвольной длины на полотна настила заданной длины без остатка или с минимальным остатком последовательно подбирают корни коэффициентов в диофантовых ЗО уравнениях, определяющих по трем этапамдлину очередных сочетаний из длин полотен пастила одного, двух или трех видов, укладывающихся в кусках полотен без остатка или с минимальным остатком.На фиг. 1 показана функциальная схема описываемой электронной вычислительной машины; на фиг. 2 - схема подбора корней коэффициентов; на фиг. 3 - схема составления диофантовых уравнений; на фиг, 4 - схема занесений; на фиг. 5 - схема определения нулевого значения остатка сумматора.Машина содержит устройство 1 ввода, регистры 2 для запоминания исходных данных А и а, - а сумматор 3, схему 4 определения нулевого значения корней коэффициентов, схему 5 определения нулевого значения остатка сумматора, программирующее устройство, состоящее из блока б комбинаций и счетчика 7 величины остатка, печатающее (выводное) устройство 8 и устройство 9 управления.Автоматическое выполнение заложенной в машину программы обеспечивается блоком комбинаций, последовательно образующим все сочетания из длин настилов и подставляющим в каждое уравнение все возможные количества полотен. С этой целью блок комбинаций содержит схему подбора корней коэффициентов, схему составления диофантовых уравнений по трем этапам решения уравнений и схему занесения корней коэффициентов в сумматор. Счетчик величины остатка, содержимое которого увеличивают на единицу длины, начиная от нулевого значения после окончания этапов решения, включен параллельно регистрам исходных данных и через схему определения нулевых значений корней коэффициентов подключен к сумматору. Последний соединен с управляющим устройством через схему определения нулевого значения его остатка.Машина работает следующим образом.На клавиатуре устройства ввода набирают последовательно величины а аа,. (длина настилов) и величину А (длина куска ткани). Кнопками номеров регистров эти величи. ны направляются в соответствующие регистры и там запоминаются, При нажатии кнопки 10 пуска устройства управления начинают вырабатываться рабочие импульсы. По первому импульсу в сумматор 3 (фиг.1) посылается с соответствующего регистра величина А дополнительным кодом. Затем прямым кодом посылается величина остатка 6. После этого прямым кодом определенное число раз посылается тот или иной коэффициент уравнения, причем соблюдается следующий порядок: сначала в сумматор посылается р раз третий коэффициент, потом и раз второй коэффициент, затем т раз первый коэффициент либо до момента получения в сумматоре нуля (что означает конец решения), либо до переполнения сумматора при отсутствии решения. При отсутствии решения выдается сигнал Х - переполнение сумматора. После сигнала Х сумматор очищается и внего вновь посылаются величины А, б и коэффициенты в новой комбинации.Циклы решения разнятся между собой ве 5 личиной б, посылаемой в сумматор (в первомцикле б=О, во втором б= 1 и так далее).Этапы решения разнятся между собой количеством разных коэффициентов, посылаемых в сумматор (на первом этапе корни при10 третьем р и втором гг коэффициентах равнынулю; на втором р=О; на третьем в сумматорпосылаются сочетания из всех трех коэффициентов).На каждом этапе подбор корней коэффици 15 ентов осуществляется возрастанием их величины от 1 до т, р или и,Схема подбора корней коэффициентов(фиг. 2) содержит: счетчики 11, 12 и 13 количества занесений корней коэффициентов т,20 гг и р соответственно; счетчики 14 и 15, фиксирующие использованные кобинации корнейкоэффициентов и исключающие их в дальнейшем; регистры 1 б и 17, соединенные с выходами счетчиков 12 и 13 и отмечающие переход25 в процессе решения к следующему корнюкоэффициента; регистры 18 и 19 для занесенияв сумматор величины длины куска обратнымкодом и заданной величины остатка; схемы20, 21 и 22 совпадения, управляемые регист 30 рами 1 б и 17, включаемые порознь и переклочающие цепи занесения корней коэффициента; схемы 23, 24 и 25 совпадения, связанныесо схемой составления уравнений и схемой занесения и включающие порознь цепи пере 35 стройки уравнений соответственно этапамрешения.Клапаны 2 б и 27 служат для переписи обратным кодом показаний счетчиков 14 и 15 насчетчики 11, 12 и 13 и работают одновременно40 в момент перехода к новой комбинации корней.Первый рабочий импульс проходит черезоткрытый клапан 28, заносит величину А ссоответствующего регистра на сумматор и пе 45 реводит регистр 18 в единичное состояние,Второй рабочий импульс проходит через клапаны 29 и 30, записывает в сумматор величину 6 со счетчика и переводит регистр 19 в единичное состояние. Клапан 30 закрывается и50 подготовляет открытие схем 20, 21, 22 совпадения. Выбор одной из этих схем осуществляется регистрами 1 б и 17, которые открываютв данном случае схему 20. Эта схема, в своюочередь, открывает клапан Л. Следующие ра 55 бочие импульсы проходят через клапаны Л и32 на счетчик 11, подсчитывающий их количество, и одновременно на схемы занесения (выход 33), где первый коэффициент заноситсяна сумматор. Клапан 32 открыт постоянно и60 закрывается только при переполнении сумматора сигналом Х.На первом этапе из схемы составленияуравнений постоянно поступает в виде признака этапа уровень (вход 34), подготовляю 65 щий открытие схемы 23 совпадения.Если решение не получилось, из сумматора поступает сигнал переполнения, который открывает схему 23 совпадец;, ь С целью перестройки уравцения очередной рабочий импульс в этом случае проходит через открывшуюся схему 23 совпадений в схему составления уравнений ца счетчик 35 номера первого коэффициента и изменяет его значение. Следовательно, теперь ь уравнении будет участвовать следующий коэффициент. Перед началом стедующего подбора счетчики 11, 12 и 13 количества занесения ц регистры 16, 17 возвращаются в нулевое состояние. Затем вновь в сумматор заносится величина А, потом б ц очередной коэффициент.Каждый раз прц получении сигнала переполнения сумматора рабочий импульс, задержанный линией 36 задержки, через схему 3 совпадений переписывает в обратном коде показания счетчиков 14 и 15 фиксации использованных комбинаций на соответствующие счетчики 11, 12 и 13 количества занесений.На втором этапе при получении признака переполнения сумматора и сигнала признака второго этапа (вход 38) через схему 39 совпадения регистр 16 переводится в единичное состояние. Поэтому после записи в сумматор величин А и б первой откроется схема 21 совпадения, выходной импульс которой откроет клапан 40.Очередной рабочий импульс пройдет через клапаны 40 и 41 на схемы занесения (выход 42), где занесет второй коэффициент с соответствующего регистра на сумматор и одновременно на счетчик 12, подсчитывающий количество занесений, а так как на счетчик 12 заранее был записан нуль в обратном коде, то первый же импульс вызовет его переполнение. Этот импульс переполнения поступит на регистр 16, переведет его в нулевое состояние и одновременно пройдет на счетчик 14, где зафиксирует единицу. Регистр 16 закроет схему 21 совпадения и откроет схему 20 совпадения.Последующие рабочие импульсы пройдут через клапан 31 ца схемы занесения (выход 33), где занесут первый коэффициент на сумматор, и ца счетчик 11, подсчитывающий количество этих занесений.Если решение не получилось, о чем свидетельствует признак переполнения сумматора, то регистр 16 вновь переведется в единичное состояние, а на счетчик 12 перепишется со счетчика 14 единица в обратном коде. После занесения на сумматор величин А и б откроется схема 21 совпадения.Теперь нужны будут два импульса занесения второго коэффициента, прежде чем переполнится счетчик 12. Комбинация корней будет иной, Импульс с выхода счетчика 12 переведет регистр 16 в начальное состояние и добавит единицу ца счетчик 14. Занесение первого коэффициента происходит обычным образом. Следовательно, содержимое счетчика 14 постоянно возрастает. В дальнейшем сум 10 15 20 25 30 35 40 45 50 55 60 65 матор может быть переполнен еще до перебрасывания регистра 17, т. е. прц занесении только втоосго коэффициента. В этом случае сцгцал переполнения сумматора откроет схему 24 совпадения, которая подготавливается к открытию постоянно поступающим пз схемы со"тавлецця уравнений признаком второго этапа (вход 38). Рабочий импульс пройдет через схему 24 в схему составления уравнений ца счетчик 43, увелцчцвая на единицу порядковый номер второго коэффициента. Счетчики схемы подбора корней в этом случае возвраща отся в исходное нулевое положение и подбор корней происходит в обычном порядке.На третьем этапе прц получении признака переполнения сумматора ц признака третьего этапа (входы 38, 44) выходные импульсы схем 39 и 45 совпадения переведут в единичное состояние регистры 16 ц 17, После занесения в сумматор величин А ц б первой откроется схема 22 совпадения. Эта схема откроет клапан 46, ц очередной рабочий импульс пройдет через клапаны 46 и 47 на схемы занесения (выход 48), где занесет третий коэффициент. Одновременно оц пройдет ца счетчик 13, на который заранее оыл переписан в обратном коде нуль. Поэтому первый же импульс счета переполнит счетчик 13. Сигнал с выхода счетчика переведет регистр 17 в нулевое состояние, что обусловливает закрытие схемы совпадения 22 и открытие схемы совпадения 21.Следующим импульсом в сумматор посылается второй коэффициент, и в дальнейшем работа будет происходить, как ц на втором этапе.Г 1 ри постепенном возрастании второго корня наступает такое положение, когда сигнал переполнения сумматора поступит прц занесении второго коэффициента, т. е. до перебрасывания регистра 17. В этом случае сигнал переполнения откроет схему 49 совпадения, рабочий импульс пройдет через цее на счетчик 15 использованных комбинаций и увеличит его значение на единицу. Теперь после переписи в обратном коде показаний счетчика 15 на счетчик 13 потребуются уже два импульса до перебрасывания регистра 17, т. е. третий коэффициент будет заноситься уже два раза.Работа остальной части схемы происходит аналогично описанному.Постепенное накопление содержимого счетчика 15 приведет к такому положению, когда сумматор переполнится уже при занесении только третьего коэффццпента, т. е. до момента перебрасывания регистра 17. Тогда сигнал переполнения сумматора откроет схему 25 совпадений, открытие которой подготовлено постоянно поступающими из схемы составления уравнений признаками третьего этапа (вход 44). Очередной рабочий импульс пройдет через нее в схему составления уравнений ца счетчик 50, увеличивая на единицу порядковый номер третьего коэффициента. В этом случае счетчики подбора корнец возвращаются в исходное нулевое положение. В дальнейшем подбор корней для нового уравнения будет происходить в том же порядке, что и описанный.Схема составления диофантовых уравнений состоит из фиксирующих номера корней коэффициентов трех счетчиков 35, 43 и 50, соединенных параллельно со схемой подбора корней, и четырех регистров 51, 52, 53 и 54, два из которых фиксируют выдачу признака протекающего этапа решения в схемы подбора корней коэффициентов (на входы 34, 38, 44) и единицы в счетчик остатка (выход 55), а два других, фиксирующих порядок подбора корней коэффициентов без повторения решенных уравнений, соединены с выходами счетчиков 35, 43 и 50, и эти счетчики связаны между собой последовательно, чтобы их показания изменялись в соответствии с требованиями порядка решений и, кроме того, имеют связь через клапаны 56 и 57 переписи.Регистры 51 и 52 работают последовательно, определяя строгую очередность следования этапов.В исходном положении схемы на счетчике 35 зафиксировано положение, соответствующее первому номеру коэффициента, на счетчике 43 - второму номеру коэффициента, на счетчике 50 - третьему номеру коэффициента, а регистры находятся в нулевом состоянии. Импульсы перестройки уравнений вырабатываются в схеме подбора корней коэффициентов (входы 58, 59 и 60).На первом этапе выработанный в схеме подбора корней коэффициентов импульс поступает через сборку 61 на вход счетчика 35, увеличивая его содержимое на единицу. Таким образом, счетчик 35 укажет следующий номер коэффициента, т. е, будет составлено новое уравнение, На первом этапе в уравнении участвует один коэффициент, на втором - два различных коэффициента.Для различения этапов предусмотрен регистр 52, который переключает выдачу признаков первого или второго этапа, Счетчик 35 последовательно перебирает все значения и сбрасывается в исходное состояние, т. е. испытывает все комбинации изэлементов по одному. Сигнал с выхода этого счетчика поступает на вход регистра 52 и переводит его н единичное состояние. Этим начинается второй этап. Для изменения в уравнении, в первую очередь, номера второго коэффициента, как того требует алгоритм, на втором этапе сигналы перестройки уравнений поступают через сборку 62 на вход счетчика 43, каждый раз увеличивая его содержимое на единицу. Тем самым счетчик 43 будет указывать после какдой перестройки следующий номер коэффициента. При постепенном возрастании показаний счетчика 43 оп переберет все значения и сбросится в нулевое состояние, а сигнал с его выхода поступит на вход счетчика 35, увеличивая его показания на единицу. При этом нарушится требуемый порядок следования номеров коэффициентов; на счетчике 35 ном 5 10 15 20 25 30 35 40 45 50 55 60 65 ра первого коэффициента будет зафиксирован номер больше, чем на счетчике 43 номера второго коэффициента. Для устранения этого несоответствия в схеме составления уравнений предусмотрена коррекция, осуществляемая переписью показания счетчика 35 ца счетчик 43 и добавлением к содеркимому последнего единицы,Импульс с выхода счетчика 43 поступает на регистр 53, переводя его в единичное состояцис, при котором открываются клапаны 63 и 64, Первый рабочий импульс (который в схеме занесений заносит величину А в сумматор) через клапан 64 переписывает содержимое счетчика 35 на счетчик 43 в прямом коде и, задержанный линией 65 задеркки, проходит через клапан 63, добавляя единицу в счетчик 43 и перебрасывая в нулевое состояние регистр 53. Таким образом, на счетчике 43 второго коэффициента до начала переписи этого коэффициента в сумматор фиксируется горядковый номер больше, чем на счетчике 35 первого коэффициента, а возвратившийся г, нулевое состояние регистр 53 обеспечивает однократную перепись и добавление единицы.На третьем этапе в уравнении участвуют уже три различных коэффициента. Для определения признака третьего этапа служит регистр 51. 1 ак и на предыдущих этапах, содержимое счетчика 35 номера первого коэффициента снова достигает максимального значения, и после сигнала перестройки этот счетчик также сбрасывается в исходное состояние, Сигнал с выхода этого счетчика через открытый клапан бб поступает на выход 55 через клапан 67 и на регистр 51 и переводит его в единичное состояние, выдавая тем самым признак третьего этапа. Для изменения в уравнении, в первую очередь, номера третьего коэффициента сигналы перестройки (вход 60) уравнений поступают через сборку 68 на вход счетчика 50, увеличивая каждый раз его содержимое на единицу, Счетчик 50 переберет все зна.чения и сбросится в исходное состояние, а его выходной импульс поступит на вход счетчика 43, увеличивая его показания на единицу. При этом нарушится требуемый порядок следования второго и третьего коэффициентов. Для выполнения требуемого порядка в этом случае в схеме предусмотрена коррекция, осуществляемая переписью показаний счетчика 43 на счетчик 50 и добавлением в последний единицы.Постепенно возрастающие показания счетчика 43 номера второго коэффициента снова приведут к нарушению порядка номеров первого и второго коэффициентов. Но ца третьем этапе это нарушение происходит одновременно с нарушением порядка номеров второго и третьего коэффициентов. Для последовательной коррекции номеров коэффициентов в схеме предусмотрена зависимость, позволяющая г .реписывать показания счетчика 43 номера второго коэффициента на счетчик 50 номера третьего коэфцициента только после коррек 135700 10ции номеров первого и второго коэффициентов. Эту функцию выполняет схема б 9 совпадения, разрешающая прохождение рабочих импульсов через клапаны 70 и 71 и линию задержки 72 для коррекции порядка номеров второго и третьего коэффициентов по окончашги коррекции порядка номеров первого и второго коэффициентов.Схема занесения (фиг. 4) содержит три дешифратора 78, 74 и 75, соединенные параллельно со счетчиками 85, 43 и 50 схемы составления диофантовых уравнений и через управляемые этой схемой клапаны 76, 77 и 78 с сумматором; сборки 79 и формирователи 80 импульсов.Счетчики номеров коэффициентов определяют в двоичнс м коде номер коэффициента, который должен заноситься при заданном уравнении. Дешифраторы преобразуют показания счетчиков, т. е. на одной из шин, соответствующей зафиксированному на счетчике числу, появляется высокий уровень, открывающий клапаны. Импульсы занесений поступают на клапаны со схемы подбора корней коэффициентов уравнения (выходы 88, 42 и 44 схемы). Мощные импульсы, переписывающие коэффициенты с регистров исходных данных на сумматор, вырабатываются формирователями 80трехвходовыми сборками 79.В описываемой машине имеются две схемы анализа на нуль, Одна схема предназначена для определения нулевого значения остатка сумматора, другая - для определения нулевых значений корней коэффициентов. Так как коэффициенты с входных регистров машины передаются в сумматор, то признаком нулевого коэффициента является наличие нуля в сумматоре, Обе схемы аналогичны по своему построению, поэтому описывается одна из них, например схема определения нулевого значения остатка сумматора (фиг. 5).Схема состоит из каскадных многовходовых схем совпадения 81 - 87, входы которых соединены с нулевыми выходами сумматора и входных регистров. Таким образом, на выходе 88 схемы сигнал высокого уровня появляется только в том случае, когда на нулевых выхо. дах всех разрядов сумматора оказываются высокие потенциалы, характеризующие нулевое состояние логического элемента каждого разряда (например триггера). Предмет изобретения 1. Электронная вычислительная машина, включающая в себя устройство для ввода данных, запоминающее устройство из регистров и счетчиков, сумматор, программирующее устройство, управляющее устройство, печатающее устройство и блок питания, от,гичающаяся тем, что, с целью осуществления более рационального раскроя кусков ткани произвольной длины на полотна настила заданной длины без остатка или с минимальным остатком путем решения подбором корней коэффи 5 10 15 20 25 30 35 40 45 50 55 60 65 циентов в диофантовых уравнениях, определяющих по трем этапам длину очередных сочетаний из длин полотен настила одного, двух или трех видов, укладывающихся в кусках полотен без остатка или с минимальным остатком, ее программирующее устройство выполнено в виде блока комбинаций, состоящего из схемы подбора корней коэффициентов, схемы составления дпофантовых уравнений по трем этапам решения уравнений и схемы занесения корней коэффициентов в сумматор, счетчика величины остатка, содержимое которого увеличивают на единицу длины, начиная от нулевого значения после окончания этапов решения, соединенного с блоком комбинаций и включенного параллельно к регистрам и через схему определения нулевого значения корней коэффициентов к сумматору, причем последний соединен с управляющим устройством через схему определения нулевого значения его остатка.2. Машина по п. 1, отличающаяся тем, что схема подбора корней коэффициентов состоит из трех счетчиков количества занесений корней коэффициентов, включенных параллельно к схеме занесения, двух счетчиков использованных комбинаций корней коэффициентов, соединенных входом с выходами счетчиков количества занесений и выходом с входом счетчиков количества занесений через клапаны переписи обратным кодом, двух регистров для занесения в сумматор величины длины куска обратным кодом и заданной величины остатка, двух других регистров, соединенных с выходами двух счетчиков количества занесений и отмечающих переход в процессе решения к следующему корню коэффициента, управляемых этими регистрами трех схем совпадения, включаемых порознь и переключающих пепи занесения корней коэффициентов, и трех других схем совпадения, включаемых порознь, связанных со схемой составлеция уравнений и схемой занесения и включающих цепи перестройки уравнений соответственно этапам решения.3. Машина по п. 1, отличающаяся тем, что схема составления диофантовых уравнений состоит из трех фиксирующих номера корней коэффициентов счетчиков, параллельно соединенных со схемой подбора корней коэффициентов и последовательно связанных через клапаны переписи, и последовательно работающих четырех регистров, два из которых фиксируют выдачу признака протекающего этапа решения в схему подбора корней коэффициентов и единицы в счетчик остатка, а два другие, фиксирующие порядок подбора корней коэффициентов без повторения решенных уравнений, соединены с выходами двух счетчиков, фиксирующих номера корней коэффициентов.4. Машина по пп. 1 и 3, отгичающаяся тем, что схема занесения состоит из трех дешифраторов, параллельно соединенных с тремя счетчиками из схемы составления диофантовых уравнений, и с сумматором через клапаны, управляемые схемой составления диофантовых уравнений, сборки и формирователей импульсов,5. Машина по п. 1, отличающаяся тем, что схема определения нулевого значения остатка сумматора и схема определения нулевого значения корней коэффициентов состоит каядая из каскада многовходовых схем совпадения, соединенных входами с нулевыми выходами 5 сумматора и регистров.1 Зо 700 Редактор Б. Б, федотов Текред Л, Я. Бриккер Коррскто ы: М. П, Ромашоваи Т. Д. ЧунаеваЗаказ 2980/ Тираж 535 Подписное Ц 11 ИИП 11 Комитета по делам изобрстений и открытий прп Совете Министров СССР Москва, Центр, пр. Серова, д. 4 Типография, пр. Сапунова, д. 2