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

 

l3 5700

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Соввтскик

Социалистических

Республик

Зависимое от авт. свидетельства №

3 а явлено ОЗЛ!.1960 (K 653007/28) Кл. 42m, 14 с присоединением заявки №

М111K. G 06f !

У, К 681.142(088.8) Приоритет

Опубликовано 16Х.1967. Бюллетень № 11

Дата опубликования описания 21.IX.1967

Комитет по делам изобретений н открытий прн Совете Министров

СССР

Авторы изобретения Ю, С, Павленко, И. В. Васильев, В. Г. Прибыш, И. В. Сигалов, П. T. Старостин, H А. Танцюра, И. А. Фридман и В. E. Ходоско

Заявитель

ЭЛЕКТРОННАЯ ВЫЧИСЛИТЕЛЬНАЯ МАШИНА

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

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

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

А=а,- - m+ а и+а, р+ о, где А — длина куска ткани (см); а — длина настила (см);

j, k l — номера настилов, которые принимают значения от 1 до i (наибольший номер настила) в соответствии с неравенством j (k (l;

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

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

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

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

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

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

30 уравнениях, определяющих по трем этапам

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

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

Машина содержит устройство 1 ввода, регистры 2 для запоминания исходных данных

А и а — а,, сумматор 3, схему 4 определения нулевого значения корней коэффициентов, схему 5 определения нулевого значения остатка сумматора, программирующее устройство, состоящее из блока б комбинаций и счетчика

7 величины остатка, печатающее (выводное) устройство 8 и устройство 9 управления.

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

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

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

10 пуска устройства управления начинают вырабатываться рабочие импульсы.

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

После сигнала Х сумматор очищается и в него вновь посылаются величины А, 6 и коэффициенты в новой комбинации.

Циклы решения разнятся между собой величиной 6, посылаемой в сумматор (в первом цикле 6=0, во втором б= 1 и так далее).

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

10 третьем р и втором >z коэффициентах равны нулю; на втором р=О; на третьем в сумматор посылаются сочетания из всех трех коэффициентов).

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

Схема подбора корней коэффициентов (фиг. 2) содержит: счетчики 11, 12 и 18 количества занесений корней коэффициентов m, 20 и и р соответственно; счетчики 14 и 15, фиксирующие использованные кобинации корней коэффициентов и исключающие их в дальнейшем; регистры 1б и 17, соединенные с выходами счетчиков 12 и 18 и отмечающие переход

25 в процессе решения к следующему корню коэффициента; регистры 18 и 19 для занесения в сумматор величины длины куска обратным кодом и заданной величины остатка; схемы

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

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

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

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

Второй рабочий импульс проходит через клапаны 29 и 80, записывает в сумматор величину 6 со счетчика и переводит регистр 19 в единичное состояние. Клапан 30 закрывается и

50 подготовляет открытие схем 20, 21, 22 совпадения. Выбор одной из этих схем осуществляется регистрами 1б и 17, которые открывают в данном случае схему 20. Эта схема, в свою очередь, открывает клапан Л. Следующие ра55 бочие импульсы проходят через клапаны Л и

82 на счетчик 11, подсчитывающий их количество, и одновременно на схемы занесения (выход 33), где первый коэффициент заносится на сумматор. Клапан 82 открыт постоянно и

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

На первом этапе из схемы составления уравнений постоянно поступает в виде при. знака этапа уровень (вход 84), подготовляю65 щий открытие схемы 28 совпадения.

135700

Если решение не получилось, из сумматора поступает сигнал переполнения, который открывает схему 28 совпаде ; «С целью перестройки уравнения очередной рабочий импульс в этом случае проходит через открывшуюся схему 28 совпадений в схему составления уравнений на счетчик 85 номера первого коэффициента и изменяет его значение. Следовательно, теперь ь уравнении будет участвовать следующий коэффициент. Перед началом cтедующего подбора счетчики 11, 12 и 18 количества занесения н регистры 16, 17 возвращаются в нулевое состояние. Затем вновь в сумматор заносится величина А, потом б и очередной коэффициент.

Ка?кдый раз прп получении сигнала переполнения сумматора рабочий импульс, задержанный линией <36 задержки, через схему 8 совпадений переписывает в обратном коде показания счетчиков 14 и 15 фиксации использованных комбинаций на соответствующие счетчики 11, 12 и 18 количества занесений.

На втором этапе при получении признака переполнения сумматора и сигнала признака второго этапа (вход 88) через схему 89 совпадения регистр 16 переводится в единичное состояние. Поэтому после записи в сумматор величин А и б первой откроется схема 21 совпадения, выходной импульс которой откроет клапан 40.

Очередной рабочий импульс пройдет через клапаны 40 и 41 на схемы занесения (выход

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

14, где зафиксирует единицу. Регистр 16 закроет схему 21 совпадения и откроет схему

20 совпадения.

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

88), где занесут первый коэффициент на сумматор, и на счетчик 11, подсчитывающий количество этих занесений.

Если решение не получилось, о чем свидетельствует признак переполнения сумматора, то регистр 16 вновь переведется в единичное состояние, а на счетчик 12 перепишется со счетчика 14 единица в обратном коде. После занесения на сумматор величин А и б откроется схема 21 совпадения.

Теперь нужны будут два импульса занесения второго коэффициента, прежде чем переполнится счетчик 12. Комбинация корней будет иной. Импульс с выхода счетчика 12 переведет регистр 16 в начальное состояние и добавит единицу на счетчик 14. Занесение первого коэффициента происходит обычным ооразом. Следовательно, содержимое счетчика

14 постоянно возрастает. В дальнейшем сумматор может быть переполнен еще до перебрасывания регистра 17, т. е. при занесении только второго 1<оэффпцпента, В этом случае c!IIнал переполнения сумматора откроет схему 24 совпадения, которая подготавливается к открытию постоянно поступающим пз схемы со"тавления ура»11ений признаком второго этапа (вход 88). Рабочий импульс пройдет через схему 24 в схему составления уравнени11 на счетчик 48, увели швая на единицу порядковый номер второго коэффициента. Счетчики схемы подбора корней в этом случае возвраща отся в исходное нулевое положение и подоор корней происходит в обычном порядке.

На третьем этапе прп получении признака переполнения сумматора и признака третьего этапа (входы 88, 44) выходные импульсы схем

89 и 45 совпадения переведут в eq!I!II»IIIoe состояние регистры 16 и 17. После занесения в сумматор величин А и б первой откроется схема 22 совпадения. Эта схема откроет клапан

46, и очередной рабочий импульс пройдет через клапаны 46 и 47 на схемы занесения (выход 48), где занесет третий коэффициент. Одновременно оп пройдет па счетчик 18, на который заранее оыл переписан в обратном коде нуль. Поэтому первый же импульс счета переполнит счетчик 18. Сигнал с выхода счетчика переведет регистр 17 в нулевое состояние, что обусловливает закрытие схемы совпадения 22 и открытие схемы совпадения 21.

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

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

его значение на единицу. Теперь после переписи в обратном коде показаний счетчика 15 на счетчик 18 потребуются уже два импульса до перебрасывания регистра 17, т. е. третий коэффициент будет заноситься уже два раза.

Работа остальной части схемы происходит аналогично описанному.

Постепенное накопление содержимого счетчикак а 15 п р11ведет «T3 KOAI < IIoл ожен и1о, 1 .огда сумматор переполнится уже при занесении только третьего коэффпцпента, т. е. до момента перебрасывания регистра 17. Тогда сигнал переполнения сумматора откроет схему 25 совпадений, открытие которой подготовлено постоянно поступающими из схемы составления уравнений признаками третьего этапа (вход 44). Очередной рабочий импульс пройдет через нее в схему составления уравнений ца счетчик 50, увеличивая на единицу порядковый номер третьего коэффициента. В этом случае счетчики подбора корней возвращаются в исходное нулевое положение. В дальней135700 шем подбор корней для нового уравнения будет происходить в том же порядке, что и описанный.

Схема составления диофантовых уравнений состоит из фиксирующих номера корней коэффициентов трех счетчиков 85, 48 и 50, соединенных параллельно со схемой подбора корней, и четырех регистров 51, 52, 58 и 54, два из которых фиксируют выдачу признака протекающего этапа решения в схемы подбора корней коэффициентов (на входы 84, 88, 44) и единицы в счетчик остатка (выход 55), а два других, фиксирующих порядок подбора корней коэффициентов без повторения решенных уравнений, соединены с выходами счетчиков

85, 48 и 50, и эти счетчики связаны между собой последовательно, чтобы их показания изменялись в соответствии с требованиями порядка решений и, кроме того, имеют связь через клапаны 56 и 57 переписи.

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

В исходном положении схемы на счетчике

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

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

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

25 зо

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

Импульс с выхода счетчика 43 поступает на регистр 58, переводя его в единичное состояние, при котором открываются клапаны 68 и

64. Первый рабочий импульс (который в схеме занесений заносит величину А в сумматор) через клапан 64 переписывает содержимое счетчика 85 на счетчик 43 в прямом коде и, задержанный линией 65 задер>кки, проходит через клапан 68, добавляя единицу в счетчик 48 и перебрасывая в нулевое состояние регистр 53. Таким образом, на счетчике 43 второго коэффициента до начала переписи этого коэффициента в сумматор фиксируется горядковый номер больше, чем на счетчике

85 первого коэффициента, а возвратившийся г, нулевое состояние регистр 53 обеспечивает однократную перепись и добавление единицы.

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

Сигнал с выхода этого счетчика через открытый клапан 66 поступает на выход 55 через клапан 67 и на регистр 51 и переводит его в единичное состояние, выдавая тем самым признак третьего этапа. Для изменения в уравнении, в первую очередь, номера третьего коэффициента сигналы перестройки (вход 60) уравнений поступают через сборку 68 на вход счетчика 50, увеличивая каждый раз его co,zep»«r oe на единицу. Счетчик 50 переберет все значения и сбросится в исходное состояние, а его выходной импульс поступит на вход счетчика 43, увеличивая его показания на единицу. При этом нарушится требуемый порядок следования второго и третьего коэффициентов. Для выполнения требуемого порядка в этом случае в схеме предусмотрена коррекция, осуществляемая переписью показаний счетчика 48 на счетчик 50 и добавлением в последний единицы.

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

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

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

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

Мощные импульсы, переписывающие коэффициенты с регистров исходных данных на сумматор, вырабатываются формирователями 80 трехвходовыми сборками 79.

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

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

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

1. Электронная вычислительная машина, включающая в себя устройство для ввода данных, запоминающее устройство из регистров и счетчиков, сумматор, программирующее устройство, управляющее устройство, печатающее устройство и блок питания, orëè÷àiîшаяся тем, что, с целью осуществления более рационального раскроя кусков ткани произвольной длины на полотна настила заданной длины без остатка или с минимальным остатком путем решения подбором корней коэффи5

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

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

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

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

11

12 вых уравнений, и с сумматором через клапаны, управляемые схемой составления диофантовых уравнений, сборки и формирователей импульсов.

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

5 сумматора и регистров.

1Зо700

%А 4

Редактор li. Б. Федотов Т.кред Л, Я. Бриккер Коррскто ы: М. П. Ромашова ц T. Д. Чунаева

Заказ 2980/1 Тираж 535 Подписное

1 11ИИП11 Комитета по делам изобрстений и открытий прп Совете Министров СССР

Москва, Центр, пр. Серова, д. 1

Типография, пр. Сапунова, д. 2