ЭЛЕКТРОННАЯ ВЫЧИСЛИТЕЛЬНАЯ МАШИНА Советский патент 1961 года по МПК G06F15/00 G06F15/20 G06F9/00 

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

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

Оптимальный вариант находят решением системы диофантовых уравнений вида

Л ау ш + а rt + Cj р + (Т,

где А-длина куска ткани (см);

а - длина настила (см); J, k, I - номера настилов, которые принимают значения от 1 до t (наибольший номер настила) в соответствии с неравенством / fe /;

т, п, р-количество полотен одинаковой длины в соответствующем настиле; б - остаток

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

Каждое уравнение содержит четыре неизвестных коэффициента т, п, р и 8.

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

корней коэффициентов удовлетворяют условиям уравнения, то дальнейшее решение прекращают, а результаты решения фиксируют.

При прочих равных условиях предпочтение отдают уравнению с меньшим числом коэффициентов. Согласно этому требованию цикл образования возмол ных уравнений разбивают на три этапа. На первом этапе образуют уравнения, коэффициенты которых представляют собой сочетание из г элементов по одному; на втором этапе - уравнения, коэффициенты которых представляют собой сочетание из i элементов по два; на третьем этапе - уравнения, коэффициенты которых представляют собой сочетание из i элементов по три.

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

длину очередных сочетании из длин нолотен настила одкого, двух или трех видов, укладывающихся в кусках нолотен без остатка или с минимальным остатком.

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

Машина содержит устройство 1 ввода, регистры 2 для запоминания исходных данных Л и «1-О; , сумматор 3, схему 4 определения нулевого значения корней коэффициентов, схему 5 определения нулевого значения остатка сумматора, нрограммируюшее устройство, состоящее из блока 6 комбинаций и счетчика 7 величины остатка, нечатающее (выводное) устройство 8 и устройство 9 унравления.

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

Машина работает следующим образом.

На клавиатуре устройства ввода набирают последовательно величины «ь «2 ... о,- (длина настилов) и величину А (длина куска ткани). Кнопками номеров регистров эти величины направляются в соответствующие регистры и там запоминаются. При нан.атии кнопки 10 пуска устройства управления начииают вырабатываться рабочие имнульсы.

По первому импульсу в сумматор 3 (фиг. 1) посылается с соответствующего регистра величина А дополнительным кодом. Затем прямым кодом посылается величина остатка б. После этого прямым кодом определенное число раз посылается тот или иной коэффициент уравнения, причем соблюдается следующий порядок: сначала в сумматор посылается р раз третий коэффициент, потом п раз второй коэффициент, затем т раз первый коэффициеит либо до момента получения в сумматоре нуля (что означает конец решения), либо до нереполнения сумматора при отсутствии решения. При отсутствии решения выдается сигнал S - нереполнение сумматора.

После сигнала 2 сумматор очищается и в него вновь посылаются величины А, б и коэффициенты в новой комбинации. Циклы решения разнятся между собой величиной б, посылаемой в сумматор (в первом цикле 6 0, во втором и так далее).

Этапы решения разнятся между собой количеством разных коэффициентов, посылаемых в сумматор (на первом этапе корни при

третьем р и втором п коэффициентах равны нулю; на втором , на третьем в сумматор посылаются сочетания из всех трех коэффициентов) . На каждом этапе подбор корней коэффициентов осуществляется возрастанием их величины от 1 до т, р или п.

Схема иодбора корней коэффициентов (фиг. 2) содержит: счетчики //, 12 и 13 количества занесений корней коэффициентов т,

п и /3 соответственно; счетчики 14 и 15, фиксирующие использованные кобинации корней коэффициентов и исключающие их в дальнейшем; регистры 16 и 17, соединенные с выходамн счетчиков 12 и 13 н отмечающие переход

в процессе решения к следующему корню коэффициента; регистры 18 н 19 для занесения в сумматор величины длины куска обратным кодом и заданной величины остатка; схемы 20, 21 и 22 совпадения, унравляемые регнстрами 16 и 17, включаемые норозиь н переключающие цени занесения корней коэффициента; схемы 23, 24 и 25 совпадения, связанные со схемой составления уравнений и схемой занесения и включающие порознь цепи перестройки уравнений соответственно этапам решения.

Клапаны 26 и 27 служат для переписи обратным кодом показаний счетчиков 14 и 15 на счетчики 11, 12 и 13 и работают одновременно

и момент перехода к новой комбинации корней.

Первый рабочий импульс проходит через открытый клапан 28, заносит величину А с соответствующего регистра на сумматор н переводит регистр 18 в единичиое состояние. Второй рабочий импульс проходит через клапаны 29 и 30, записывает в сумматор величину б со счетчика н переводит регистр 19 в единичное состояние. Клапан 30 закрывается и

подготовляет открытие схем 20, 21, 22 совпадения. Выбор одной из этих схем осуществляется регистрами 16 и 17, которые открывают в данном случае схему 20. Эта схема, в свою очередь, открывает клапан 31. Следующие рабочие имнульсы проходят через клапаны 31 и 32 на счетчик 11, подсчитывающий их количество, и одновременно на схемы занесения (выход 33, где первый коэффициент заносится на сумматор. Клапан 32 открыт постоянно и

.закрывается только при переполнении сумматора сигналом Е.

На первом этапе из схемы составления уравнений постоянно поступает в виде признака этапа уровень (вход 34), нодготовляюЕсли решение не получилось, из сумматора поступает сигнал переполнения, который открывает схему 23 совпадеп; -;). С целью перестройки уравнения очередной рабочий импульс R этом случае проходит через открывшуюся схему 23 совпадений в схему составления уравнений на счетчик 35 номера первого коэффициента и изменяет его значение. Следовательно, теперь в уравнении будет участвовать следующий коэффициент. Перед началом следующего подбора счетчики //, 12 и 13 количества занесения и регистры 16, 17 возвращаются в нулевое состояние. Затем вновь в сумматор заносится величина Л, потом б и очередной коэффициент.

Каждый раз при получении сигнала нереполнеиня сумматора рабочий импульс, задержанный линией 36 задержки, через схему 37 совпадений переписывает в обратном коде показания счетчиков 14 и 15 фиксации использованных комбинаций на соответствующие счетчикн //, 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 постоянно возрастает. В дальнейшем сумматор может быть переполнен еще до переорасыванпя регистра 17, т. е. при занесении только вторсто коэффициента. В этом случае сигнал переполнения сумматора откроет схему 24 5 совпадения, которая подготавливается к открытию постоянно поступающим из схемы составления уравнений признаком второго этапа (вход 38. Рабочий импульс пройдет через схему 24 в схему составления уравнений на 0 счетчик 43, увеличивая на еднницу порядковый номер второго коэффициента. Счетчики схемы подбора корней в этом случае возвраидаются в исходное нулевое положение и подбор корг1ей нроисходит в обычном порядке. 5 На третьем этапе при получении признака переполнения сумматора и признака третьего этана (входы 38, 44 выходные импульсы схем 39 и 45 совпадения переведут в едииичное состояние регистры 16 и 17. После занесения в 0 сумматор величии Л и б первой откроется схема 22 совпадения. Эта схема откроет клапан 46, и очередной рабочий импульс пройдет через клапапы 46 и 47 на схемы занесения (выход 48, где занесет третий коэффициент. Одновремеино он пройдет на счетчик 13, на который заранее был переписан в обратном коде нуль. Поэтому первый же шшульс счета переполиит счетчик 13. Сигиал с выхода счетчика переведет регистр 17 в нулевое состояние, что 0 обусловливает закрытие схемы совпадения 22 и открытие схемы совпадения 21.

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

При постепенном возрастаиии второго корня настуиает такое положение, когда сигнал переполнения сумматора поступит при занесении второго коэффициента, т. е. до иеребра0 сывания регистра 17. В этом случае сигнал нереполнения откроет схему 49 совпадеи1 я, рабочий импульс пройдет через нее на счетчик 15 использованных комбинаций и увеличит его значеиие на единицу. Теперь после пере5 писи в обратном коде показаний счетчика 15 на счетчик 13 потребуются уже два импульса до перебрасывания регистра 17, т. е. третий коэффициент будет заноситься улче два раза. Работа остальной части схемы происходит 0 аналогичио описанному.

Постеиенное накопление содержимого счетчика 15 приведет к такому положению, когда сумматор нереполнится уже при заиесеиии только третьего коэффициента, т. е. до момен5 та иеребрасывания регистра 17. Тогда сигнал переполнения сумматора откроет схему 25 совиадений, открытие которой подготовлено постоянно поступающими из схемы составления уравнений призиаками третьего этапа 60 (в.ход 44. Очередной рабочий импульс пройдет через иее в схему составления уравнений на счетчик 50, увеличивая на единицу порядковый номер третьего коэффициента. В этом случае счетчики подбора корней возвращают65 ся в исходное нулевое положение. В дальнейшем подбор корней для нового уравнения будет происходить в том же порядке, что и описанный.

Схема составления диофантовых уравнений состоит из фиксирующих номера корней коэффициентов трех счетчиков 35, 43 и 50, соединенных параллельно со схемой подбора корней, и четырех регистров 51, 52, 53 и 54, два из которых фиксируют выдачу признака протекающего этапа решения в схемы подбора корней коэффициентов (на входы 34, 38, 44) и единицы в счетчик остатка (выход 55), а два других, фиксирующих порядок подбора корней коэффициентов без повторения решенных уравнений, соединены с выходами счетчиков 35, 43 и 50, и эти счетчики связаны между собой последовательно, чтобы их показания изменялись в соответствии с требованиями порядка решений и, кроме того, имеют связь через клапаны 56 и 57 переписи.

Регистры 51 и 52 работают последовательно, определяя строгую очередность следования этапов.

В исходном положении схемы на счетчике 55 зафиксировано положение, соответствующее первому номеру коэффициента, на счетчике 43 - второму номеру коэффициента, на счетчике 50 - третьему номеру коэффициента, а регистры находятся в нулевом состоянии. Импульсы перестройки уравнений вырабатываются в схеме подбора корней коэффициентов (входы 58, 59 и 60.

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

Для различения этапов предусмотрен регистр 52, который переключает выдачу признаков первого или второго этапа. Счетчик 35 последовательно перебирает все значения и сбрасывается в исходное состояние, т. е. испытывает все комбинации из / элементов по одному. Сигнал с выхода этого счетчика поступает на вход регистра 52 и переводит его в единичное состояние. Этим начинается второй этап. Для изменения в уравнении, в первую очередь, номера второго коэффициента, как того требует алгоритм, на втором этапе сигналы перестройки уравнений поступают через сборку 62 на вход счетчика 43, каждый раз увеличивая его содержимое на единицу. Тем самым счетчик 43 будет указывать после каждой перестройки следующий номер коэффициента. При постепенном возрастании показаний счетчика 43 ои переберет все значения и сбросится в нулевое состояние, а сигнал с его выхода поступит на вход счетчика 35, увеличивая его показания на единицу. Нри этом нарушится требуемый порядок следования номеров коэффициентов: на счетчике 35 номера первого коэффициента будет зафиксирован номер больше, чем на счетчике 43 номера второго коэффициента. Для устранения этого несоответствия в схеме составления уравнений предусмотрена коррекция, осуществляемая переписью показания счетчика 35 на счетчик 43 и добавлением к содержимому последнего единицы.

Импульс с выхода счетчика 43 поступает на

регистр 53, переводя его в единичное состояние, при котором открываются клапаны 63 и 64. Первый рабочий имнульс (который в схеме занесений заносит величину А в сумматор) через клапан 64 переписывает содержимое счетчика 35 на счетчик 43 в прямом коде и, задержаниый линией 65 задержки, прохо,дит через клапан 63, добавляя единицу в счетчик 43 и перебрасывая в нулевое состояние регистр 53. Таким образом, на счетчике 43

второго коэффициента до начала перениси этого коэффициента в сумматор фиксируется порядковый номер больше, чем на счетчике 55 первого коэффициента, а возвратившийся Б нулевое состояние регистр 55 обеспечивает

однократную перепись и добавление единицы. На третьем этапе в уравнении участвуют уже три различных коэффициента. Для определения признака третьего этапа служит регистр 51. Как и на предыдущих этапах, содержимое счетчика 55 номера первого коэффициента снова достигает максимального значения, и после сигнала перестройки этот счетчик также сбрасывается в исходное состояние. Сигнал с выхода этого счетчика через открытый клапан 66 поступает на выход 55 через клапан 67 и на регистр 51 и переводит его в единичное состояние, выдавая тем самым признак третьего этапа. Для изменения в уравнении, в первую очередь, номера третьего

коэффициента сигналы перестройки (вход 60) уравнений поступают через сборку 68 на вход счетчика 50, увеличивая каждый раз его содержимое на единицу. Счетчик 50 переберет все значения и сбросится в исходное состояние, а его выходной импульс поступит на вход счетчика 43, увеличивая его показания на единицу. При этом нарушится требуемый порядок следования второго и третьего коэффициентов. Для выполнения требуемого порядка

в этом случае в схеме предусмотрена коррекция, осуществляемая переписью показаний счетчика 43 на счетчик 50 и добавлением в последний единицы. Постепенно возрастающие показания счетчика 43 номера второго коэффициента снова приведут к нарушению порядка номеров первого и второго коэффициентов. Но на третьем этапе это нарушение происходит одновремепно с нарушением порядка номеров второго и

третьего коэффициентов. Для последовательной коррекции номеров коэффициентов в схеме предусмотрена зависимость, позволяющая г феписывать показания счетчика 43 номера второго коэффициента на счетчик 50 номера

ции номеров первого и второго коэффициентов. Эту функцию выполняет схема 69 совпадения, разрешающая прохождение рабочих импульсов через клапаны 70 и 71 и линию задержки 72 для коррекции порядка номеров второго и третьего коэффициентов по окончании коррекции порядка номеров первого и второго коэффициентов.

Схема занесения (фиг. 4) содержит три дешифратора 73, 74 и 75, соединенные параллельно со счетчиками 35, 43 и 50 схемы составления диофантовых уравнений и через управляемые этой схемой клапаны 76, 77 и 7S с сумматором; сборки 79 и формирователи 80 импульсов.

Счетчики номеров коэффициентов определяют в двоичном коде номер коэффициента, который должен заноситься при заданном уравнении. Дешифраторы преобразуют показания счетчиков, т. е. на одной из шин, соответствуюшей зафиксированному на счетчике числу, появляется высокий уровень, открывающий клапаны. Импульсы занесений поступают на клапаны со схемы подбора корней коэффициентов уравнения (выходы 33, 42 и 44 схемы). Мощные импульсы, переписывающие коэффициенты с регистров исходных данных на сумматор, вырабатываются формирователями 80 с трехвходовыми сборками 79.

В описываемой машине имеются две схемы анализа на нуль. Одна схема предназначена для определения нулевого значения остатка сумматора, другая - для определения нулевых значений корней коэффициентов. Так как коэффициенты с входных регистров машины передаются в сумматор, то признаком нулевого коэффициента является наличие нуля в сумматоре. Обе схемы аналогичны по своему построению, поэтому описывается одна из них, например схема определения нулевого значения остатка сумматора (фиг. 5).

Схема состоит из каскадных многовходовых схем совпадения 81-87, входы которых соединены с нулевыми выходами сумматора и входных регистров. Таким образом, на выходе 88 схемы сигнал высокого уровня появляется только в том случае, когда на нулевых выходах всех разрядов сумматора оказываются высокие потенциалы, характеризуюшие нулевое состояние логического элемента каждого разряда (например триггера).

Предмет изобретения

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

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

3.Машина по п. 1, отличающаяся тем, что схема составления диофантовых уравнений состоит из трех фиксирующих номера корней коэффициентов счетчиков, параллельно соединенных со схемой подбора корней коэффициентов и последовательно связанных через клапаны переписи, и последовательно работающих четырех регистров, два из которых фиксируют выдачу признака протекающего этапа рещения в схему подбора корней коэффициентов и единицы в счетчик остатка, а два другие, фиксирующие порядок подбора корней коэффициентов без цовторения рещенных уравнений, соединены с выходами двух счетчиков, фиксирующих номера корней коэффициентов.

4.Мащина по пп. 1 и 3, отличающаяся тем, что схема занесения состоит из трех дешифраторов, параллельно соединенных с тремя счетчиками из схемы составления диофантовых уравнений, и с сумматором через клапаны, управляемые схемой составления диофантовых уравнений, сборки и формирователей импульсов. 5. Машина по п. 1, отличающаяся тем, что 5 схема определения нулевого значения остатка сумматора и схема определения нулевого значения корней коэффициентов состоит каждая из каскада многовходовых схем совпадения, соединенных входами с нулевыми выходами сумматора и регистров,

/

МП