D. В. ГНЕДЕНКО, В. С. КОРОЛЮК, Е. Л. ЮЩЕНКО
ЭЛЕМЕНТЫ
ПРОГРАММИРОВАНИЯ
И З Д А Н И И В Т О Р О Е С Т Е Р Е О Т И П Н О Е
Д о п у щ е н о М ч н и с т е р с т п о м
в ы с ш е го и с р е д н е г о с п е ц и а л ь н о г о о б р а з о в а н и я Р С Ф С Р в к а ч е с т в е у ч е б н о г о п о с о б и я
д л я в ы с ш и х у ч е б н ы х з а в е д е н и й
<
‘І 2 ( С
j ;j
Г О С У Д А РС Т В Е Н Н О Е И ЗД А Т Е Л Ь С Т В О Ф И 311КО-М АТЕМ АТИЧЕСКОЙ ЛИ ТЕ РА Т У РЫ
М О С К В А 1 У 6 3
518 Г 56
А Н Н О Т А Ц И Я
Книга «Элементы программирования» м ож ет служить р у к о водством по программированию для цифровых автом атиче
ских машин. В ней нашли отраж ен ие исследования в области автоматизации программирования, реш ения логи ческ их задач на циф ровы х автоматических машинах, а такж е операторны й м етод, предлож енны й А . А . Ляпуновым.
Книга предназначена для студентов уни вер си тетов, втузов и м ож ет быть полезна для работников научно-нсследователь- ских институтов, занимаю щ ихся вопросами программирования.
Книга м ож ет служить учебны м пособием при подготовке кадров программистов.
Б о р и с В л а д и м и р о в и ч Г н сд ен /со , В л а д и м и р С ем ен о в и ч К о р о л ю к , Е к а т е р и н а Л о г в и н о в н а Ю щ ен ко.
Э Л ЕМ ЕН Т Ы ПРО ГРАМ М Ы РО В А Н I ІЯ М., Ф и зм атгн з, 1963 г., 318 стр. с илл.
Р еда к то р С о л о в ь е в а JI. А .
Т ех н . р едак тор М у р а ш о в а I I. Я - К ор рек тор А н д р и а н о в а Л . П.
П ечать с матриц. П о д п и сан о к печати 1/XII 1962 г. Бумага GOxOOVir;. <1»из. к е ч .-л . 21,75.
У словн. п еч . л. 21,75. У ч.-изд. л. 17,3-1. Т и р а ж 50 000 э к з. Ц ен а книги 62 коп . З а к а з Кі 1166.
Г о су да р ств ен н о е издательство ф и зи к о-м атем ати ческ ой литературы . М осква, В-71, Л енинск ий п р о сп ек т , 15.
Т и п огр аф и я Кг 2 нм. Епг. С ок олов ой У Ц В и П П Л е н с о в н а р х о за . Л е н и н г р а д , И зм а й л о в ск и й пр., 29.
От а в т о р о п ... ... 5
В в е д е н и е ...! ! ! 7
Г л р в а I. П р и н ц и п ы у с т р о й с т в а э л е к т р о н н ы х в ы ч и с л и т е л ь н ы х м а ш и н ... 13
§ 1. Вы бор системы с ч и с л е н и я ... 13
§ 2. Основные логи ческ ие операции ... 18
§ 3. Элем ентарны е электронны е с х е м ы ... 22
§ 4. П редставление чисел в машине ... 31
§ 5. Операции над числами в цифровы х м а ш и н а х ... 3 5 § 6. П ер ев од из одной системы счисления, в д р у г у ю ... 4 3 Г л а в а II. П р и н ц и п ы п р о г р а м м н о г о у п р а в л е н и я на ц и ф р о в ы х а в т о м а т и ч е с к и х м а ш и н а х ... 4 5 § 1. Принципиальная схем а Ц А А 1 ... 4 5 § 2. Элементарны е операции, выполняемые Ц А Л 1 ... 52
Г л а в а III. Э л е м е н т а р н о е п р о г р а м м и р о в а н и е . . . . ... 63
§ 1. Н еп оср едств ен н ое п р о г р а м м и р о в а н и е ... 06
§ 2. Разветвляю щ иеся п р о ц е с с ы ... 7 7 § 3. Ц иклические п р о ц е с с ы ... 8 9 § 4. Ц иклические процессы , зависящ ие от п а р а м е т р о в ... 112
§ 5. Б л ок -схем ное програм мирование и п ередача управления на п о д п р о г р а м м ы ... 139
§ 6. Ф ормирование содерж ан ия запом инаю щ его устройства . . . . 140
§ 7. Групповы е операции ... 153
Г л а в а IV. О п е р а т о р н о е п р о г р а м м и р о в а н и е ...109
§ 1. Схемы с ч е т а ...109
§ 2. Схемы п р о г р а м м ...172
§ 3. П рограммирование сложных циклических п р о ц е с с о в ... 182
§ 4. Л огически е условия в схем ах п р о г р а м м ... 218
§ 5. П рограммирование логических оп ераторов . . . : ... 225
§ 0. С одер ж ател ь ное преобр азован и е схем п р о г р а м м ...230
Г л а в а V. А д р е с н о е п р о г р а м м и р о в а н и е ... 210
§ 1. Понятие адресн ой п р о г р а м м ы ... 241
§ 2. Схемы обозр еван ия к о д о в ... 248
§ 3. Программы задач линейной а л г е б р ы ... 254
§ 4. Н еариф м етические з а д а ч и ... 201
Г л а в а VI. А в т о м а т и за ц и я п р о г р а м м и р о в а н и я ... 284
§ 1. Общий об зо р м е т о д о в ... 284
§ 2. П остроение алгоритмов операторной программирующ ей про граммы ...293
§ 3. М етод адресн ого п р о г р а м м и р о в а н и я ...298
ОГЛАВЛЕНИЕ
1*
4 ОГЛАВЛЕНИЕ
Г л а в а VII. О р г а н и за ц и я р а б о т ы н а Ц А М ... 300
§ 1. О форм ление программ на б л а н к а х ...300
§ 2. В вод программ в З У и контроль в в о д а ... 302
§ 3. П рооерка правильности работы м а ш и н ы ...303
§ 4. Отладка п р о г р а м м ... 307
П р и л о ж е н и е ... 309
Б Э С М ... ... 309
С т р е л а ... ЗШ У р а л ... 325
М - 3 ...3 3 3 К и е в ... .... ... 337 Цитированная л и т е р а т у р а ... .... J47
ОТ А В ТО Р О В
Н а с т о я щ а я книга написана на основании опыта работы а в торов на универсальны х цифровых автоматических машинах, чтения курсов лекций по программированию , проведения соот
ветствующих семинаров, руководства практикой студентов, а т а к ж е участия в проектировании новых вычислительных м а шин. Отправным пунктом д л я нашей работы был курс лекций проф. А. А. Л яп ун ова , который он читал в Московском универ
ситете. С одерж ан и е нашей книги ясно из оглавления, и на нем пет необходимости останавли ваться.
Мы будем искренне б лагодарны всем читателям, которые найдут возмож ны м прислать нам свои п ож елан и я, зам еч ан ия и у к а за н и я на зам еченны е недостатки.
Гнеденко Б. В., К о р о л ю к В. С., Ю щ енко Е. Л.
В В Е Д Е Н И Е
Прошло лиш ь немногим более десяти лет с тех пор, как была построена п ер в ая ав том ати ч еская эле ктрон н а я циф ровая машина с п рограммны м управлением, но у ж е мож но говорить с полной определенностью, что ее появление зн ам енов ал о собой решительный скачок по пути прогресса д л я большого числа н а учных н технических проблем нашего времени.
Впервые перед наукой откры лась возм ож н ость производить колоссальные по м а с ш т а б а м вычислительные работы в исклю
чительно короткие сроки. Производство вычислений диктуется практической необходимостью, и потребности в счете в о з р а стают с к а ж д ы м годом.
Д ел о в том, что любые научные и технические разработки, любое строительство — корабля, плотины, турбины, самолета, ракеты, атомного р еактора — н уж д аю тся в предварительных, зачастую очень сл ож н ы х расчетах. Порой вся их сложность со
стоит лиш ь в том, что д л я получения окончательного резуль
тата необходимо выполнить миллионы, а то и миллиарды а р и ф метических операций. Д л я примера у к а ж е м на решение систем большого числа линейных алгебраических уравнений. П ринци
п иал ьн ая сторона вопроса здесь достаточно хорошо выяснена у ж е давно, и единственная трудность, которая возникает, — это необходимость осущ ествления большого числа сложений, вычи
тании, умножений н делений. Д л я систем указан ного вида, со
д е р ж а щ и х 200— 300 неизвестных с соответствующим числом уравнений, получение ответа достигается лиш ь после производ
ства нескольких десятков миллионов э лем ен тарн ы х ари ф м ети ческих действий. Д а ж е лучш ему вычислителю, в руках которого находятся простейшие вычислительные средства — ар и ф м о метры, таб ли цы и пр., — требуются годы, а то и десятилетия напряж енного труд а д л я решения одной-едннствениой зад ач и столь простого типа. Конечно, иногда з а д а ч а д опускает ра зб и е ние на части, к а ж д а я из которых мож ет быть решена не
зависимо одна от другой. В таком случае можно значительно ускорить вычислительный процесс, поручив выполнение не
зависимы х групп операций различны м вычислителям. Однако
8 ВВЕДЕНИЕ
зач ас тую такое разбиение невозможно и вся за д а ч а требует последовательного выполнения операций.
Многие зад ач и , формальное решение которых еще совсем недавно к а з а л о с ь исключительно далеким от возможности п рактического использования из-за вычислительных трудностей, в н астоящ ее время в связи с появлением новой бы стродей
ствующей вычислительной техники удалось довести до числен
ных расчетов, а тем самым и до непосредственных применений.
В инженерной практике вычислительные трудности приводили к тому, что часто инженеры ограничивались весьма п р и б л и ж ен ны мп прикидками, а иногда и совсем отказы вались от расчетов д а ж е в тех случаях, когда имелась вполне уд овлетвори тельная теория соответствующего явления. Эго обстоятельство приво
д ило и приводит, в частности, к тому, что в практике мирятся с н еоп равданн о высокими зап ас ам и прочности; в особо ж е от
ветственных случаях прибегают к дорогостоящим экспериментам и моделированию. Применение быстродействующих вычисли
тельных машин открывает перед современной техникой не
виданны е возможности. Достаточно сказать, что лучш ие об разц ы машин сейчас способны производить десятки тысяч умножений многозначных чисел в секунду. Иными словами, м аш и на в секунду производит столько вычислений, сколько не способен произвести д а ж е опытный вычислитель за це
лый месяц работы. Эго обстоятельство не мож ет не о к а з а т ь глубокого влияния на весь комплекс технических, э ко н о м и ческих и естественных наук, стимулируя широкое и спользо
вание вычислительных методов. Внедрение этих методов позволит выбирать оптимальные варианты решения и н ж ен ер ных зад а ч и тем самым принесет огромный экономический эффект.
К а к ни велико значение повой вычислительной техники д л я производства вычислительных работ, быть может, еще больш ее значение имеет то, что быстродействующие цифровые вычисли
тельны е машины оказалось возможны м приспособить к реш е
нию з а д а ч логического характера. В качестве примера такого рода можно привести удачные попытки осуществления а в т о м а тического перевода с одного языка на другой, проводимые в С СС Р, СШ А и других странах. Оказалось, что на машину удается переложить некоторые функции интеллектуальной д е я тельности и тем самым освободить человека от монотонных мыслительных операций, соверш аемых по определенным п рав и-- лам . Особенно большие перспективы открываются в связи с ис
пользованием вычислительных машин для автоматического уп равл ен ия производственными процессами. Это н аправление п ривлекает большое число ученых и инженеров. Чтобы хар а ктер этого рода приложений был достаточно отчетливо выяснен, мы
ППЕДЕППЕ 9
приведем несколько примеров, заи м ствов ан н ы х из технической литературы.
Фирма «Сокони мобил ойл компани» исп ользовала э ле к тронную вычислительную машину д ля выбора наивыгоднейшего реж им а перегонки нефти. Исходными данны ми при этом являю тся стоимость на рынке нефтепродуктов, рабочей силы, различных м атери ал ов и ряд других факторов. Д л я составле
ния программы были предварительно математически описаны процессы каталитического крекинга, ал ки л и р о ва н и я и др. П р о грамм а, м од ели рую щ ая процесс перегонки, вклю чает в себя 6000 ком анд и чисел и осущ ествляется машиной за 9 минут, из которых 6 минут затр а ч и в аю тся па ввод в маш ину программы.
Фирма «Вест Пенн электрик», с о зд а л а электронную вычисли
тельную машину д ля выбора наиболее экономичного реж има работы энергосистемы мощностью 1300 Мет, объединяющей д е сять тепловых электростанций и одну гидростанцию. О б щ а я протяженность л и н и й ' электропередач 2500 км при н а п р я ж е ниях в 66 и 132 кв. М аш ин а используется д л я расчета опти
мального р еж и м а работы системы при учете потерь в сетях, стоимости топлива на отдельных станциях, коэффициентов по
лезного действия генераторов, раб отаю щ их д л я покрытия н а грузки, и учета других факторов, определяю щ их стоимость энергии. Полученное решение используется д л я распределения
н агрузок м еж д у станциями.
В н астоящ ее время в периодической печати появилось з н а чительное число работ, касаю щ ихся применения быстродей
ствующих вычислительных машин к автоматическому уп рав л е
нию м етал л ореж ущ и м и станками, доменным процессом, к з а д а чам государственного планирования, д л я библиографических целей и т. д. Р я д такого рода интересных и важ н ы х применений был освещен в д о к л а д а х на сессии Академии наук СССР, по
священной научным проблемам автом атизаци и производ
ства [1].
Несомненно, что в указанны х н ап рав л ен и я х исследователь
ская работа еще только начинается и д а ж е самое б лиж айш ее будущее принесет необозримые успехи. Но д л я этого необхо
д им а упорная и систематическая работа по изучению и м а т е м а тическому описанию процессов, п о д л еж ащ и х автоматизации.
Д о некоторой степени исследования этого рода п редставляю т собой новую область математической деятельности, которая требует специальной подготовки и специального н аправления мысли. Несомненно, что уже теперь нужно учесть это при о р г а низации университетского об разован ия.
Д о последнего времени человечество огромную долю своих творческих усилий з а тр а ч и в а л о на то, чтобы использовать силы природы д л я освобождения человека от однообразного утоми
1 0 В В Е Д Е Н И Е
тельного физического труда путем использования р а з н о о б р а з ных машин. Одновременно, но в сравнительно меньшей степени, человечество стремилось и к облегчению умственного труд а, к тому, чтобы переложить на те или иные приспособления часть загр у зк и интеллекта. На протяжении столетий на өтом пути у д ал о сь сделать немало. Чтобы в этом убедиться, достаточно вспомнить об изобретении книгопечатания, фотографии, зв у к о записи, счетных машин и приспособлений и многого другого.
К а ж д о е из указан ны х изобретений п ереклады вало на машины то, что раньш е способен был осуществлять лишь разум чело
в е к а — н ак а п л и в ать и п ередавать другим опыт и знания, з а п о м и нать образы и звуки, производить вычисления и т. д. Теперь мы стоим на пороге повои эпохи, когда силы природы будут использованы т а к ж е д л я увеличения интеллектуальной мощи человечества и д ля освобождения человека от утомительной однообразной умственной работы. Это даст возможность сосре
доточить творческие возможности на нерешенных проблем ах, на развитии новых направлений в науке. Электронные вычисли
тельны е машины являются в аж н ы м шагом на этом пути; п ер
вые попытки использования их в указанном направлении у ж е сд ел ан ы и оказал и сь исключительно удачными. Д а л ь н е й ш и е возможности представляются нам буквально неисчерпаемыми.
Революционизирую щ ее воздействие быстродействующих циф ровы х машин сказы вается сейчас как на изменении и н ж е нерных устройств, т а к и па установлении новых связей м е ж д у научными дисциплинами, отстоявшими друг от друга весьма д а леко в самом недавнем прошлом, а т а к ж е и в том, что они по
сл уж и л и мощным толчком д л я бурного развития новых н ау ч ных дисциплин. В первую очередь в связи со сказан н ы м н уж но упомянуть кибернетику, которую можно определить к а к науку о способах восприятия, хранения, переработки и использования и нформ ац ии в маш инах и в ж и вы х организмах. М од елирование некоторых физиологических и мыслительных процессов м ож ет о к а з а т ь существенную помощь к а к физиологии, так и технике, н априм ер при построении управляю щ их машин. К ибернетика п ризван а объединить усилия математиков, биологов, физиков, техников, психологов, экономистов и л и н г в и с т о в и с п о с о б с т в о
вать в заи м н ом у развитию соответствующих дисциплин.
С ам о собой разумеется, что быстродействующие вычисли
тельные машины оказали существенное влияние и на некоторые разделы математики. П р е ж д е всего, возник вопрос о п реп ари ровании математических задач д ля постановки их на машину.
Речь идет не только о том, чтобы свести интересующую нас з а д ачу к решению того пли иного уравнения или к уж е готовой формуле, в которую нужно лишь подставить значения аргум ен тов и произвести необходимые операции. Д л я того чтобы м а
ВВЕДЕНИЕ 11 шина могла без в м еш ательства человека пройти весь путь от начальных условий задачи до выдачи численных результатов и п рекращения вычислений, необходимо предварительно р а зл о жить процесс решения зад ач и на элементарны е операции и тем самым создать условия, при которых она мож ет автоматически в необходимом порядке, ш аг за шагом, проделать все требуе
мые операции. Здесь очень важ н о подчеркнуть слово автом ати чески, так как всякое вмеш ательство человека в огромной сте
пени за д е р ж и в а е т производство вычислений. Действительно, если машине на производство к аж д ой операции необходимы лишь десятитысячные и д а ж е стотысячные доли секунды, то че
ловеку на изменение хода вычислений нужны уже минуты. Т а ким образом, необходимо, чтобы маш ина ие только произво
дила сложение и умножение, по чтобы в ней автоматически происходил переход от одной операции к другой, «зап ом и н а
ние» результатов промежуточных вычислений, выбор чисел из
«памяти», изменение х а р а к те р а вычислений, вы дача окончатель
ных результатов, своевременное прекращ ение работы машины.
Это осущ ествляется с помощью устройства программного управления. Н ов ая м а тем атическая дисциплина, позволяю щ ая производить необходимое разбиение зад ач и на элементарные операции, т. е. составлять программу, по которой д о л ж н а р аб о тать машина, получила наименование теории п рограм м и ро
вания.
Н аш а цель — и злож и ть в настоящей книге основные идеи этой дисциплины на базе рассмотрения ка к совершенно элемен
тарных, т а к н более сложных примеров. В значительной части эти примеры заимствованы нами из практики и встречались нам при решении конкретных зад ач на быстродействующих вы
числительных машинах. Помимо изложения основ п рограмми
рования, необходимых для каж дого программиста, мы считаем необходимым познакомить читателей с новыми идеями про
грамм ирования, которые р азр а б а ты в аю тс я в настоящее время.
В частности, мы уделяем значительное внимание операторному методу програм м и рован ия, предлож енному Л. Л. Л япуновым.
Следует отметить, что в основе вычислительных процессов на машине всегда л еж и т какой-нибудь метод приближенного решения — зам ен а и нтеграла через интегральную сумму, з а мена д ифф еренциального уравнения на уравнение в конечных разностях и т. д. Весь арсенал привычных приближенны х мето
дов ан ал и за теперь пущен в ход. При этом обнаруж илось, что д а л ек о не ка ж д ы й из этих методов приспособлен к особенно
стям автоматического счета. Д л я применения ранее р а з р а б о танных методов приближенны х вычислений к работе па машине требуется их усоверш енствование и развитие. Н уж но вспомнить т а к ж е старые, д ав но забы ты е приемы приближенны х вычислений;
1 2 ВВЕДЕНИЕ
м о ж ет случиться, что некоторые из них о к а ж у тся у д а ч ными. Конечно, необходимо т а к ж е создание новых п р и б л и ж ен ных методов; эти исследования нужно форсировать хотя бы потому, что привычные подходы к ряду важ н ы х з а д а ч приводят к исключительно трудоемким вычислениям д а ж е д ля соврем ен ных машин. К таким зад а ч а м относятся, в частности, м ногомер
ные з ад ач и математической физики. Известно, например, что зад ач и , связанны е с расчетом гетерогенных атомных котлов, при приведении их к уравнениям в конечных разностях в ряде сл уч аев требуют рассмотрения сеток, содерж ащ и х миллионы узлов. О бщ ее число элементарных операций, которые при этом д о л ж н ы быть осуществлены, достигает десятков м и ллиардов.
При р а зр а б о тк е приближенных методов а н ал и за возникли но
вые зад ач и , с которыми ранее почти не приходилось в стре
чаться; в качестве примера можно указать на вопрос исследо
в ан ия устойчивости счета.
В настоящ ее время еще не установилась окончательная т е р минология д ля наименования современных вычислительных м а шин с программны м управлением. П ервоначально их н а зы в а л и электронными вычислительными машинами, подчеркивая этим то, что основными элементам и этих устройств являлись э л е к тронные приборы. Д ал ее, поскольку на смену электронным э л е ментам теперь приходят другие, к а ж етс я естественным у к а з ы вать в первую очередь на то, что эти машины являю тся не м о д елирую щ им и устройствами, а выдают цифровые результаты ; было внесено предложение н азы вать такие машины ав т о м а т и ческими быстродействующими цифровыми вычислительными м а ш и н а м и (А Б Ц В М, см. Л. Л. Л япунов и Г. А. Ш естопал [2]).
Мы п ред ла гаем их н азвать короче — цифровая автом атич еская м а ш и н а (Ц Л М), поскольку представление о быстродействии маш ины сильно меняется. Т ак 30 000— 100 000 операций в се
кунду, воспринимаемые сейчас к а к почти рекордная скорость машины, через несколько лет, когда будут построены машины с сотнями тысяч и д а ж е миллионами операций в секунду, будут к а з а т ь с я не быстродействием, а нормальной скоростью машины.
П оэтому мы сохраняем лишь д в а основных качества в н аи м е
новании машины: то, что она цифровая, и то, что она а в то м а ти чески действует.
Г Л Л В Л I
П Р И Н Ц И П Ы У С Т Р О Й С Т В А Э Л Е К Т Р О Н Н Ы Х В Ы Ч И С Л И Т Е Л Ь Н Ы Х М А Ш И Н
В настоящей гл аве рассм атриваю тся арифметические и ло
гические принципы устройства цифровых вычислительных м а шин. С техническими особенностями осущ ествления этих прин
ципов и связанны ми с ними идеями конструирования цифровых автоматических машин Щ А М ) читатель мож ет познакомиться по имеющейся литературе.
Вместе с тем следует отметить, что в н астоящ ее время еще не создана м атем атич еск ая теория конструирования Ц А М , в связи с чем одной из центральны х за д а ч современной вычи
слительной м атематики и техники явл яется развитие теории синтеза электронных вычислительных и управл яю щ и х схем.
§ 1. Выбор системы счисления
В настоящ ее время для и зображ ен и я числа употребляется весьма совершенный п о зи ционн ы й принцип записи, согласно ко
торому один и тот ж е числовой символ (ц и ф ра) имеет разл и ч ные значения в зависимости от места, которое он занимает. Т а кая система записи чисел основана на том, что некоторое число единиц, например с, объединяется в одну единицу второго р а з ряд а; объединение с единиц второго р а з р я д а составляет еди
ницу третьего р а зр я д а , и т. д. Число с носит н азван ие осн ова
н и я счисления.
В качестве основания счисления мож но взять любое целое число, большее единицы. В системе счисления с основанием с любое число а запи сы вается в виде
р~ 1
а = ± 2 (1 )
/с ~ — оо
где величины ак принимают значения 0, 1, 2, . . с— 1, а р — некоторое целое число, зав и ся щ ее от с и от а. Если ввести
обозначение (3„ = то число а мож ет быть зап и сан о в виде, несколько отличном от (1):
оо а = ±
п
- 1Число р назы вается порядком числа а (иоиятпо, что зн а ч е ние р зависит от того, какую систему счисления мы уп отреб
л я е м ). П оря док числа определяет место запятой в записи числа, а именно, з а п я т а я д о л ж н а стоять перед $1Г Х- М ножи-
СО
тель всегда заключен в полуинтервале [0,1]; он носит на-
п-
1з в ан и е мантиссы числа а.
В повседневной жизни наиболее употребительна д еся ти ч ная позиционная система счисления, в которой за основание принято число десять. Любое число в этой системе счисления, к а к это хорошо известно, может быть записано с помощью р а с полож енны х в соответствующем порядке десяти числовых з н а ков: 0 , 1, 2 , 3, 4 , 5, 6, 7, 8, 9. Например, число 429,538 я в л яе тся сокращ енной записью вы раж ен и я
4 - 102 + 2 . 101 -4-9 ♦ 10° — 5 * 10-1 Ч - З - 10~2 + 8 • 10~3- Подобны е ж е сокращенные записи мы будем впоследствии уп отреб лять д л я изображ ения чисел, записанных в позицион
ных системах счисления с другим, иедесятичным основанием.
Так, например, в восьмеричной системе счисления запись 321,57 означает, что рассматривается число
3 • 82 -f- 2 • 81 - f- 1 • 8° + 5 7 - 8 - 2.
В ряд е ка к теоретических, т а к и практических зад ач н еко
торые системы счисления, отличные от десятичной, п р ед став л я ю т известные преимущества. Так, например, д воичная си стема счисления используется в большинстве современных Ц А М к а к в силу простоты технического осуществления операций над двоичными числами, так и в силу широко откры ваю щейся при этом возможности использовать методы математической логики, в частности, исчисления высказываний. В практике работы Ц Л М применяются та к ж е и другие системы счисления — зось- меричиая, шестнадцатеричная и некоторые другие.
Отметим, что двоичная система счисления для и зображ ен и я одного и того ж е д и апазона чисел требует меньшего числа э л е ментов машины для их записи, чем десятичная. Действительно, количество чисел, имеющих п разрядов, в системе счисления с основанием с равно М = сп. Необходимое для представления этих чисел число элементов пропорционально N c — с • п. За ф н - 14 ПРИНЦИПЫ УСТРОЙСТВА э л е к т р о н н ы х в ы ч и с л и т е л ь н ы х МАШИН [г л. I
ВЫПОР СИСТЕМЫ СЧИСЛЕНИЯ 15 ксируем число М и найдем то с, при котором N c достигает ми
нимума. И з первого написанного нами равенства находим, что
In
М
п = — . In
с
Подставив это значение в в ы раж ение д л я N c, находим:
с
inМ
In
с
Л егко найти, что минимум этого в ы раж ен и я достигается при с = с = 2,71828 . . . С рассматриваемой точки зрения самой вы годной системой счисления является троичная. Д л я и зображ ен и я всех чисел от 1 до 106 в десятичной системе счисления т р е буется 60 элементов, в двоичной — 40,' а в троичной — 38. О д нако увеличение числа элементов д ля записи чисел в двоич
ной системе по сравнению с троичной невелико. Если число элементов, необходимое д ля записи в двоичной системе, об озна
чить N 2, а д ля записи в троичной — N 3, то
^ = 1 ^ 1 =N 3 6 111 2 2^ 46 Igio 1 ^ 1,0 5 6.
Троичная система счисления пе получила широкого приме
нения в цифровых маш инах в связи с трудностями конструи
рования достаточно над еж н ы х быстродействующих элементов с тремя устойчивыми состояниями. В то ж е время имеется большое число физических приборов, которые могут в опреде
ленных схемах соединений об л а д а ть д вум я устойчивыми р а з личными состояниями, — конденсаторы, электронны е лампы кристаллические триоды и др. Схемы существующих эле м ен тов, из которых составляются Ц А М , по своему существу являю тся двоичными. Конденсатор мож ет быть за р я ж е н и не зар я ж ен , л а м п а мож ет проводить или пе проводить ток.
К тому ж е двоичная система счисления предпочтительнее перед другими системами счисления б л а г о д а р я исключительной про
стоте выполнения арифметических операций н ад двоичными числами.
Некоторым неудобством двоичной системы счисления в Ц А М (как, впрочем, и всякой другой системы счисления, от
личной от десятпчноіі) является необходимость перевода ис
ходных данных из десятичной в двоичную систему при вводе их в машину и обратного перевода из двоичной системы в д е сятичную при выводе результатов вычислений. Эта необходи
мость обусловлена тем, что д есятичная система счисления является общепринятой. Однако в п одавляю щ ем большинстве зад ач объем вычислительных операций превосходит количество входных и выходных данных, которые только и п о д л еж ат
переводу из одной системы счисления в другую, и поэтому у к а занный недостаток является совершенно несущественным.
К тому ж е этот перевод зачастую производится автоматически.
Т а к как мы не предполагаем у читателя привычки к систе
мам счисления, отличным от десятичной, то для ориентировки приводим небольшую табличку записи чисел в различны х си
стемах (см. табли цу 1). При этом отметим, что поскольку в по
следней граф е мы приводим запись чисел в ш естнадцатеричной системе и в этой системе счисления долж ны быть обозначения д л я ш естнадцати цифр, то мы используем д л я обозначения нуля и первых девяти единиц обычные знаки, а д л я об озн а че
ния десяти, одиннадцати, д венадцати, тринадцати, ч еты рна
дцати и пятнадцати — соответственно знаки 0, 1, 2, 3, 4, 5 . 1G ПРИНЦИПЫ УСТР0ІІСГПЛ ЭЛЕКТРОННЫХ ВЫЧИСЛИТЕЛЬНЫХ МАШИН [ г л . I
Т а б л и ц а 1. Запись чисел в различных систем ах Системы счислении
деся
тична* | дноичипи троичная пятеричная иэсьмеричпая шестнадцате
ричная
1 1 1 1 1 1
2 10 2 2 2 2
3 и 10 . 3 3 3
4 100 11 4 4 4
5 101 12 10 5 5
G 110 20 11 0 6 .
7 111 21 12 7 7
8 1000 22 13 10 8
9 1001 100 14 И 9
10 1010 101 20 12 б
11 1011 102 21 13 1
12 IKK) 110 22 14 2
13 1101 111 23 15 3
14 1110 112 2 4 16 4
15 1111 120 3 0 17 5
16 1000 0 121 31 2 0 10
17 10001 122 32 21 11
0, 5 0,1 0 , 1 1 . . . 0 , 2 2 . . . 0,4 0,8
0,3 0 , 0 1 0 0 1 . . . 0 , 0 2 2 0 0 . . . 0 , 1 2 2 . . . 0 , 2 3 1 4 6 . . . 0 , 4 2 2 2 . . . 0 ,( 3) 0 , 0 1 0 1 . . . 0,1 0 , 1 3 1 3 . . . 0 , 2 5 2 5 . . . 0 , 5 5 . . .
При подготовке за д а ч нередко пользуются восьмеричной и шестнадцатеричной системами счисления. Переход от этих си
стем к двоичной осущ ествляется весьма просто. Действительно,
ВЫГ.ОР СИСТЕМЫ СЧИСЛЕНИЯ 17 каждыіі р а з р я д восьмеричной системы п реобразуется в неко
торое трехзначное двоичное число; точно т а к ж е каждый р а з ряд шестнадцатеричной системы преобразуется в четырехзнач
ное двоичное число. Таким образом, например, число 1175, записанное в восьмеричной системе, в двоичной системе прини
мает такой вид: 1001111101. Число 528, записанное в шестна
дцатеричной системе, в двоичной имеет такую запись:
10111001000. Д л я перехода от двоичной записи числа к восьме
ричной нужно разбить двоичную запись па группы по три цифры справа налево и ка ж д ую группу зам енить восьмеричным числом, пользуясь таблицей 1. Д л я перехода от двоичной записи к шестнадцатеричной нужно двоичную запись разбить сп рава палево па группы по четыре цифры и к аж д ую группу заменить соответствующей шестнадцатеричной цифрой. Н а п р и мер, число 11101111001, записанное в двоичной системе, в вось
меричной записи имеет вид 3571. То ж е число д л я перевода в шестнадцатеричную запись нужно предварительно записать группами по четыре цифры: 111 0111 1001; по таблице 1 нахо
дим, что в шестнадцатеричной записи это число будет выглядеть так: 779.
Нет необходимости подробно о станавл и ваться на том, что простота ука зан н ы х преобразований объясняется тем, что числа восемь и ш естн адцать являю тся целыми степенями двойки (8 = 2:j; 16 = 2 4).
Д л я того чтобы лучш е освоить двоичную систему счисления, мы вкратце изл ож и м на примерах п равила выполнения а р и ф метических операций н ад числами, представленными в двоич
ной записи. Эти п равил а ничем не отличаются от тех, которые излагаю тся в школьном курсе арифметики, только в двоичной системе таблицы сложения п умножения особенно просты.
Приведем по одному примеру на ка ж д о е арифметическое действие над двоичными числами.
Т а б л и ц а двоичного Т а б л и ц а двоичного с л о ж е н и я у м н о ж е н и я
0 - f - 0 = 0 0 + 1 = 1 1 + 0 = 1 1 -4-1 = 10
0 X 0 = 0 0 X 1 = 0 1 X 0 = 0 1 X 1 = 1
Д в о и ч н о е с л о ж е н и е Д в о и ч н о е вы ч ит ание 1010011,111
+
11001,110 1101101,1011100101,101
— 10101,111 , .-1001111,110
2 З а к . п о з . Э л ем ен т ы п р о гр а м м и р о в а н и я
\
1 8 ПРИНЦИПЫ УСТРОЙСТВА ЭЛЕКТРОННЫХ ВЫЧИСЛИТЕЛЬНЫХ МАШИН [г л. I
Д в о и ч н о е у м н о ж е н и е 11001,01 X 11,01
1100101 1100101 1100101 1010010,0001
Д в о и ч н о е д е л е н и е 10100110011 11011
~ 1011_________________1111001
10011
— 1011
10001
— 1011
01100
1011
— 0001011 1011
§ 2. Основные логические операции
Применение в электронных вычислительных м аш и нах д вои ч ной системы счисления д ает возможность использовать а п п а р а т математической логики, в частности исчисление в ы сказы ваний, при ан ал и зе и построении функциональных схем машин.
В математической логике под вы сказы ванием понимается лю бое предложение, относительно которого имеет смысл гово
рить об его истинности или ложности, например: «С егодня чет
вертое число», «человек бессмертен», «дважды два — четыре».
П редлож ен и я, которые могут быть одновременно истинными и лож н ы м и, а т а к ж е лишь частично истинными, в математической логике не рассматриваю тся. При оценке высказы ваний мы б у
дем принимать во внимание лиш ь их истинность или лож н ость, н и к ак не учитывая их конкретного содержания.
В ы сказы в ан и я мы будем обозначать заглавн ы м и буквам и латинского ал ф ави та. Если А истинно, то будем писать /1 = 1, если /1 ложно, то будем писать А = 0 . Если в ы сказы ван ие ка- кнм-то образом зависит от некоторого парам етра, то его зн а ч е ние истинности представляет собой функцию, способную прини
м ать лишь два значения: 0 или 1. В ы сказы ван ие всегда истин
ное определяет постоянную функцию, равную 1; вы сказы ван ию всегда л о ж н о м у соответствует функция, которая тождественно равн а 0. В приведенных выше примерах первое высказы вание верно только в течение двенадц ати дней в году, второе лож н о всегда, третье всегда истинно.
П ерем ен н ая величина, которая мож ет принимать лиш ь два значения, н азы вается двоичной переменной. Согласно введен
ному определению всякое высказы вание является двоичной переменной.
В современных Ц А М действия над числами (записанными в двоичной системе), передача двоичных кодов из одного блока
ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ 19 машины в другой, управление этой передачей осущ ествляются посредством устройств, которые способны находиться только в двух состояниях (этим состояниям приписываются значения О и 1). Таким образом, работа уп равл яю щ и х схем устройства передачи информации в Ц А М представима некоторыми функ
циями от двоичных переменных, которые сами т а к ж е прини
м аю т лишь два значения. Такие функции н азы ваю тся двоич
ны м и функциями.
М атем ати ческая логика изучает вопросы представления и п реобразован ия двоичных функций от двоичных аргументов по
средством некоторых логических операций, н азы ваем ы х логиче
скими связями. И з простых высказываний при помощи логиче
ских связей могут быть составлены слож н ы е высказывания, принимающие значения истинно (1) или ложно (0) в зависи
мости от значений составляю щ и х простых высказываний. Так к а к высказы вания можно р ассм атрив ать ка к двоичные пере
менные, то логические связи м еж д у в ы сказы ваниям и можно представить Как операции н ад двоичными переменными вели
чинами. Определим основные логические операции.
1. О т р и ц а и и е. Отрицание высказы вания А обозначается символом А (читается: «не /Ь>). Значение истинности вы с казы вания А определяется следующей таблицей:
О т р и ц а н и е Г = ° 0 = 1 .
Таким образом, отрицанием в ы сказы ван ия А является сложное вы сказы ван ие / 1, которое ложно, когда А истинно, и истинно, когда А ложно.
2. Л о г и ч е с к о е у м н о ж е н и е . Логическое умножение в ысказываний А и В об означается символом /1 / \ В (читается:
«А и В » ). Значение истинности логического произведения А / \ В определяется в зависимости от значений истинности в ы с к а зы в а ний /1 и В но следующей таблице:
Л о г и ч е с к о е у м н о ж е н и е 0 д о = 0 0 / \ 1 = 0 1 Д 0 = 0 1 А 1 = 1
Операция логического умножения назы вается конъ ю нкцией, а символ А —знаком конъ ю нкции.
Конъюнкция А А В двух высказы ваний представляет собой сложное высказы вание, которое истинно тогда и только тогда, когда истинны составляю щ ие его вы с казы в ан и я А и В.
