Фомин С. В. Системы счисления. — М. : Наука, 1964. — 44 с. — (Популярные лекции по математике ; вып. 40).

Популярные лекции

ПО МАТЕМАТИКЕ

С. В. ФОМИН

СИСТЕМЫ СЧИСЛЕНИЯ

ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ

ВЫПУСК 40

С. В. ФОМИН

СИСТЕМЫ СЧИСЛЕНИЯ

ИЗДАТЕЛЬСТВО «НАУКА»

МОСКВА 1964

511 Ф 76

УДК 511. 118

АННОТАЦИЯ

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

ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ

СОДЕРЖАНИЕ

Предисловие ........................ 4

§ 1. О круглых и некруглых числах ............ 5

§ 2. Происхождение десятичной системы счисления..... 7

§ 3. Другие системы счисления и их происхождение .... 8

§ 4. Позиционные и непозиционные системы счисления ... 11

§ 5. Арифметические действия в различных системах счисления ......................... 12

§ 6. Перевод чисел из одной системы счисления в другую . 14

§ 7. О признаках делимости................ 18

§ 8. Двоичная система................... 21

§ 9. Двоичный код в телеграфии.............. 25

§ 10. Несколько слов о вычислительных машинах...... 26

§ 11. Почему электронная машина «предпочитает» двоичную систему счисления................... 29

§ 12. Об одном замечательном свойстве троичной системы . . 32

§ 13. О бесконечных дробях................. 35

ПРЕДИСЛОВИЕ

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

В последнее время у десятичной системы появились серьезные конкуренты в лице двоичной и отчасти троичной систем, которыми «предпочитают пользоваться» современные вычислительные машины.

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

§ 1. О КРУГЛЫХ И НЕКРУГЛЫХ ЧИСЛАХ

«Из подъезда вышел человек лет около 49; пройдя по улице метров 196, он зашел в магазин, купил там две семерки яиц и пошел дальше...». Не правда ли, такое описание звучит несколько странно? Когда мы оцениваем какую-то величину—возраст человека, расстояние и т. п. — приблизительно, то мы всегда пользуемся круглыми числами и говорим обычно «метров 200», «человек лет 50» и т. п. С круглыми числами удобнее оперировать, чем с некруглыми. Например, ни для кого не составит труда умножить в уме 100 на 200, если же нужно перемножить два некруглых трехзначных числа, скажем 147 и 343, то далеко не всякий сделает это без карандаша и бумаги.

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

2548

означает, что рассматриваемое число содержит 8 единиц, 4 десятка, 5 сотен и 2 тысячи, т. е. 2548 — это

сокращенное обозначение выражения

2- 103 + 5.102 + 4. 10 + 8- 10°.

Однако можно было бы с таким же успехом представить каждое число в виде комбинации степеней не числа 10, а какого-либо другого целого числа (кроме 1), например числа 7. В этой системе, называемой «семеричной системой счисления» или «системой счисления с основанием 7», мы вели бы счет от 0 до 6 обычным образом, а число 7 приняли бы за единицу следующего разряда. Его естественно обозначить в нашей новой системе символом

10

(единица второго разряда). Чтобы не путать это обозначение с числом 10, припишем к нему индекс «7», т. е. окончательно вместо 7 будем писать

(10)7.

Единицами следующих разрядов должны служить числа

72, 73 и т. д.

Их естественно обозначить

(100) 7> (1000)7 и т. д.

Любое целое число можно скомбинировать из степеней числа 7, т. е. представить в виде

ак-7* + ак_1-7*-*+ ... +^-7 + ^,

где каждый из коэффициентов а0, au ..ak может принимать любое целое значение от 0 до 6. Как и в случае десятичной системы, естественно опускать при записи чисел в системе с основанием 7 сами степени этого основания и писать это число в виде

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

Рассмотрим пример. Число 2548 можно представить в виде

1-74 + 0.73 + 3.72 + 0.7 + 0,

т. е., в принятых нами обозначениях, в виде

(10 300)7.

Таким образом,

(2548) 10 = (10 300) 7.

Обратим внимание на то, что при пользовании этой новой «семеричной» системой записи круглыми будут совсем не те числа, которые были круглыми в десятичной системе. Например,

(147)ю - ( 300)7,

(343) ,о= (1000)7

(так как 147 = 3 • 72 и 343 = 73) ; в то же время

(100) ю= ( 202) 7,

(500) 10 = (1313)7

и т. д. Поэтому в семеричной системе умножить в уме 147 на 343 проще, чем 100 на 200. Если бы мы пользовались семеричной системой, то, несомненно, возраст 49 лет (а не 50) воспринимался бы как «круглая дата» и отмечался бы как юбилей, мы говорили бы «метров 98» или «метров 196», прикидывая расстояние на глаз (поскольку (98)ю= (200)7 и (196) 10 = (400)7 — круглые числа в семеричной системе), считали бы предметы семерками, а не десятками и т. д. Короче говоря, если бы семеричная система была общепринятой, то та фраза, с которой мы начали изложение, никого бы не удивила.

Однако на самом деле семеричная система не имеет сколько-нибудь широкого распространения и никак не может конкурировать с повсеместно распространенной десятичной системой. В чем же причина этого?

§ 2. ПРОИСХОЖДЕНИЕ ДЕСЯТИЧНОЙ СИСТЕМЫ СЧИСЛЕНИЯ

Почему именно числу 10 отведена такая привилегированная роль? Человек, далекий от этих вопросов, ответил бы, вероятно, не задумываясь, так: дело просто в том, что число 10 — круглое, на него удобно умножать любое число, поэтому удобно считать десятками, сотнями и т. д. Мы, однако, уже выяснили, что дело обстоит как раз наоборот: число 10 потому и круглое, что

оно принято за основание системы счисления. При переходе к какой-либо иной системе счисления, скажем семеричной (где оно записывается в виде (13)7), его «круглость» немедленно исчезнет.

Причины, по которым именно десятичная система оказалась общепринятой — совсем не математического характера. Десять пальцев рук — вот тот первоначальный аппарат для счета, которым человек пользовался, начиная с доисторических времен. По пальцам удобно считать от одного до десяти. Сосчитав до десяти, т. е. использовав до конца возможности нашего природного «счетного аппарата», естественно принять само число 10 за новую, более крупную единицу (единицу следующего разряда). Десять десятков составляют единицу третьего разряда и т. д. Таким образом, именно счет по пальцам рук положил начало той системе, которая кажется нам сейчас чем-то само собою разумеющимся.

§ 3. ДРУГИЕ СИСТЕМЫ СЧИСЛЕНИЯ И ИХ ПРОИСХОЖДЕНИЕ

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

Так, например, довольно широкое распространение имела двенадцатеричная система. Ее происхождение связано, несомненно, тоже со счетом на пальцах, а именно, так как четыре пальца руки (кроме большого) имеют в совокупности 12 фаланг (рис. 1), то по этим фалангам, перебирая их по очереди большим пальцем, и ведут счет от 1 до 12. Затем 12 принимается за единицу следующего разряда и т. д. В устной речи остатки двенадцатеричной системы сохранились и до наших дней: вместо того чтобы сказать «двенадцать», мы часто говорим «дюжина». Многие предметы (ножи, вилки, тарелки, носовые платки и т. п.) очень часто считают именно дюжинами, а не

Рис. 1.

десятками. (Вспомните, например, что сервиз бывает, как правило, на 12 или на 6 человек и значительно реже на 10 или на 5.) Сейчас уже крайне редко встречается слово «гросс», означающее «дюжину дюжин» (т. е. единицу третьего разряда в двенадцатеричной системе), но еще несколько десятков лет тому назад оно было довольно широко распространено, особенно в торговом мире. Дюжина гроссов называлась «масса», однако сейчас такое значение слова «масса» мало кому известно*).

Несомненные остатки двенадцатеричной системы счисления имеются у англичан — в системе мер (например, 1 фут = 12 дюймам) и в денежной системе (1 шиллинг = 12 пенсам).

Затем, что с математической точки зрения двенадцатеричная система имела бы, пожалуй, некоторые преимущества перед десятичной, поскольку число 12 делится на 2, 3, 4 и 6, а число 10 только на 2 и 5, а больший запас делителей у числа, служащего основанием системы счисления, создает известные удобства в ее использовании. К этому вопросу мы еще вернемся в § 7, в связи с признаками делимости.

В Древнем Вавилоне, культура которого, в том числе и математическая, была довольно высока, существовала весьма сложная шестидесятеричная система. Мнения историков по поводу того, как именно возникла такая система, расходятся. Одна из гипотез, впрочем не особенно достоверная, состоит в том, что произошло сме« шение двух племен, одно из которых пользовалось шестеричной системой, а другое — десятичной. Шестидесятеричная система возникла как компромисс между этими двумя системами. Другая гипотеза состоит в том, что вавилоняне считали продолжительность года равной 360 суткам, что естественно связывалось с числом 60. Однако это предположение тоже нельзя считать достаточно обоснованным: астрономические познания древних вавилонян были довольно значительны, поэтому следует думать, что погрешность, с которой они определяли

*) Хотя, возможно, именно в нем лежит корень таких употребительных выражений, как «масса дел», «масса людей» и т. п. (ср. с выражениями «тысяча дел» и т. д.).

продолжительность года, была значительно меньше, чем 5 суток. Несмотря на то, что происхождение шестидесятеричной системы остается неясным, самый факт ее существования и широкого распространения в Вавилонском государстве достаточно хорошо установлен. Эта система, как и двенадцатеричная, в какой-то степени сохранилась и до наших дней (например, в делении часа на 60 минут, а минуты — на 60 секунд и в аналогичной системе измерения углов: градус = 60 минутам, 1 минута = 60 секундам). В целом, однако, эта система, требующая шестидесяти различных «цифр», довольно громоздка и менее удобна, чем десятичная.

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

У ацтеков и майя — народов, населявших в течение многих столетий обширные области американского континента и создавших там высокую культуру, почти полностью уничтоженную испанскими завоевателями в 16— 17 вв., была принята двадцатеричная система. Та же двадцатеричная система была принята и у кельтов, населявших Западную Европу, начиная со второго тысячелетия до нашей эры. Некоторые следы двадцатеричной системы кельтов сохранились в современном французском языке: например, «восемьдесят» по-французски будет quatre-vingt, т. е. буквально «четырежды двадцать». Число 20 встречается и во французской денежной системе: основная денежная единица — франк делится на 20 су.

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

Как показывают приведенные выше примеры (их число можно было бы значительно увеличить), много-

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

§ 4. ПОЗИЦИОННЫЕ И НЕПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ

Все те системы счисления, о которых мы говорили выше, относятся к так называемым позиционным системам. В них цифры имеют различные значения в зависимости от того, на каком месте в записи числа они стоят. Например, в числе 222 двойка участвует три раза. Но самая правая из них означает две единицы, вторая справа — два десятка, т. е. двадцать, а третья — две сотни. (Здесь мы имеем в виду десятичную систему. Если бы мы пользовались какой-либо другой системой счисления, скажем с основанием р, то эти три двойки означали бы соответственно величины 2, 2р и 2р2.)

Существуют и другие — непозиционные системы счисления, построенные на иных принципах. Общеизвестный пример такой системы — так называемые римские цифры. В этой системе единица обозначается I, пять V, десять X, пятьдесят L, сто Сит. п., причем смысл каждого символа не зависит от того места, на котором он написан. Из этих символов комбинируются другие числа. Например, число 88 в этой системе запишется так:

LXXXVIIL

Здесь цифра X участвует три раза, причем каждый раз она означает одну и ту же величину — десять единиц.

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

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

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

§ 5. АРИФМЕТИЧЕСКИЕ ДЕЙСТВИЯ В РАЗЛИЧНЫХ СИСТЕМАХ СЧИСЛЕНИЯ

Для чисел, записанных в десятичной системе, мы пользуемся правилами сложения и умножения чисел «столбиком», деления «углом». Эти же правила полностью применимы и для чисел, записанных в любой другой позиционной системе.

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

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

умножения выглядит так:

0

1

2

3

4

5

0

0

0

0

0

0

0

1

0

1

2

3

4

5

2

0

2

4

10

12

14

3

0

3

10

13

20

23

4

0

4

12

20

24

32

5

0

5

14

23

32

41

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

Пользуясь этой таблицей, легко перемножать «столбиком» числа, содержащие любое количество разрядов. Например,

Деление «углом» также можно выполнять в любой системе счисления. Рассмотрим, например, такую задачу:

Разделить (120101)8 на (102)3.

Вот ее решение:

(Переведите делимое, делитель, частное и остаток в десятичную систему и проверьте правильность результата.)

Задача 1. На доске сохранилась полустертая запись

2 3—5— М—642

42 423

Выяснить, в какой системе счисления написаны слагаемые и сумма? Ответ. В семеричной.

Задача 2. Один школьный учитель на наш вопрос, много ли у него в классе учеников, ответил: «У меня в классе 100 детей, из них24 мальчика и 32 девочки». Сначала его ответ нас удивил, но потом мы поняли, что просто учитель пользовался не десятичной системой. Какую систему имел в виду учитель?

Решение этой задачи не сложно. Пусть х — основание той системы счисления, о которой идет речь. Тогда слова учителя означают следующее: у него х2 учеников, из них 2х + 4 мальчика и Зх + 2 девочки. Таким образом,

2х + 4-\-Зх + 2 = х2,

или

X2 — 5х — 6 = 0,

откуда

т. е.

хх — 6, х2 = — 1.

Так как —1 не может быть основанием системы счисления, то X = 6. Итак, ответ учителя был дан в шестеричной системе.

§ 6. ПЕРЕВОД ЧИСЕЛ ИЗ ОДНОЙ СИСТЕМЫ СЧИСЛЕНИЯ В ДРУГУЮ

Как перевести число, записанное в одной системе, например десятичной, в какую-либо другую систему, скажем семеричную? Мы уже знаем, что записать какое-либо число А в семеричной системе — это значит

представить его в виде суммы

Л = а,.7* + а,_1.7*"1+ ... -\-ах • 7 + а0.

Следовательно, чтобы найти семеричное представление числа А, надо найти коэффициенты а0, ûi, ..., ak, каждый из которых может быть какой-либо цифрой от О до 6 включительно. Разделим наше число Л на 7 (в целых числах). Остаток при этом будет равен, очевидно, а0, так как в написанном представлении числа А все слагаемые, кроме последнего, делятся на 7 нацело. Далее, возьмем частное, получившееся при делении числа А на 7, и снова разделим его на 7. Получившийся при этом новый остаток будет равен а{. Продолжая этот процесс дальше, мы найдем все цифры а0) аи ..., aky входящие в семеричное представление числа Л, в виде последовательных остатков, получающихся при описанном выше повторном делении его на 7. Рассмотрим, например, число

(3287)ю.

Разделив его на 7, получим частное 469 и остаток 4. Следовательно, в семеричной записи числа 3287 последняя цифра равна 4. Для нахождения второй цифры разделим найденное нами частное 469 снова на 7. Получим частное 67, а остаток при этом равен нулю. Следовательно, вторая цифра в семеричной записи числа 3287 есть нуль. Далее, разделив 67 на 7, получим 9 и 4 в остатке. Этот остаток 4 представляет собой третью цифру в семеричной записи числа 3287. Наконец, разделив последнее частное 9 на 7, получим остаток 2 и частное 1, Этот остаток 2 дает нам четвертую цифру в искомой записи, а частное единица (которую мы уже делить на 7, не можем) представляет собой пятую (и последнюю) цифру. Таким образом,

(3287) ю= (12404)7.

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

Ь74 + 2-73 + 4.72 + 0-7 + 4,

подобно тому, как (3287) — это сокращенная запись выражения

3-103 + 2.102 + 8.10 + 7.

Выкладки, которые мы проделали для перехода от десятичной записи числа 3287 к его представлению в семеричной системе, удобно расположить так:

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

Рассмотрим еще один пример. Записать число 100 в двоичной системе. Получаем

Т' е> .(100)ю= (1100100)2.

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

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

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

Задача. Предположим, что у нас есть весы (с двумя чашами) и гири в 1 грамм, 3 грамма, 9 граммов, 27 граммов и т. д. (по одной штуке каждого веса). Можно ли с помощью такого набора гирь взвесить любой груз с точностью до одного грамма?

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

А = {апап^х... аха0)^

т. е.

А = ап-Зп + ап_х-3"-* + ... +<V3 + a0,

где коэффициенты а0, аь ..., ап могут принимать значения 0, 1 или 2.

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

В результате мы получим запись числа А в виде суммы

A = bm.3m+bm_x-3*»-i-\- ... + ьг-3 + Ь0,

где каждый из коэффициентов 60, &ь •.., Ьт может быть равен 0, 1 или —1.

Теперь груз в А граммов положим на первую чашу весов, а гирю в 1 грамм поставим на вторую чашу, если fto53 1» и на первую чашу, если Ь0 = —1 (если bQ = О, то первую гирю мы не используем); далее, гиря весом в 3 грамма ставится на вторую чашу, если Ь\ = 1, и на

первую, если Ь\ = — 1, и т. д. Легко понять, что, расставив гири по такому принципу, мы уравновесим груз А.

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

Следовательно, (200) 10 = (21102) 3, т. е.

200 = 2 - З4 + 1 • З3 + 1 • З2 + 0 - 3 + 2.

Если же 200 переводить в троичную запись описанным выше способом, т. е. используя —1, но не используя 2, то получим

т. е.

200 = 1 - З5 — 1 . З4 + 1 • З3 + 1 - З2 + 1 .3 — 1

(справедливость последнего равенства легко проверить непосредственным подсчетом).

Таким образом, чтобы уравновесить груз в 200 граммов, положенный на чашу весов, нужно на ту же чашу положить гири в 1 грамм и 81 грамм, а на противоположную— гири в 3, 9, 27 и 243 граммов.

§ 7. О ПРИЗНАКАХ ДЕЛИМОСТИ

Существуют простые признаки, позволяющие определить, что то или иное число делится, например, на 3, на 5, на 9 и т. п. Напомним эти признаки:

1) Признак делимости на 3: число делится на 3, если сумма его цифр делится на 3. Например, число

257802 (сумма цифр 2 + 5 + 7 + 8 + 0 + 2 = 24)

делится на три, а число

125831 (сумма цифр 1+2 + 5 + 8 + 3+1= 20)

на три не делится.

2) Признак делимости на 5: число делится на 5, если его последняя цифра есть 5 или 0 (т. е. если на 5 делится число единиц его последнего разряда).

3) Признак делимости на 2 аналогичен предыдущему: число делится на 2, если йа 2 делится число единиц его последнего разряда.

4) Признак делимости на 9 аналогичен признаку делимости на 3: число делится на 9, если сумма составляющих его цифр делится на 9.

Доказательство справедливости этих признаков не представляет труда. Рассмотрим, например, признак делимости на 3. Он основан на том, что единица каждого из разрядов десятичной системы (т. е. числа 1, 10, 100, 1000 и т. д.). при делении на 3 дает остаток 1. Поэтому всякое число

(¥/i-i • • • 0i0o)io»

т. е. число

ап - \0п + ап_х - 10"-1+ ...+ах- 10 + а0,

можно записать в виде

{ап + ап_х+ ... + ах + а0)+Ву

где В делится на 3 без остатка. Отсюда видно, что число ап • 10п + ап-х • Ю"-1 + ... + ах • 10 + а0 при делении на 3 дает тот же остаток, что и число ап + ап-Х + + ... + ах + а0.

Признак делимости на 5 вытекает из того, что число 10 — основание системы счисления — делится на 5, поэтому все разряды, кроме разряда единиц, при делении на 5 обязательно дают в остатке нуль. На том же самом основан и признак делимости на 2: число четное, если оно кончается четной цифрой.

Признак делимости на 9, как и признак делимости на 3, вытекает из того, что каждое число вида 10й при делении на 9 дает в остатке 1.

Из сказанного ясно, что все эти признаки связаны с представлением чисел именно в десятичной системе

и что они, вообще говоря, неприменимы, если пользоваться системой счисления с каким-либо другим основанием, отличным от 10. Например, число 86 в восьмеричной системе записывается в виде

(126)8

(так как 86 = 82 + 2 • 8 + 6). Сумма цифр здесь равна 9, но 86 не делится ни на 9, ни на 3.

Однако для каждой позиционной системы счисления можно сформулировать свои признаки делимости на то или иное число. Рассмотрим несколько примеров.

Будем писать числа в двенадцатеричной системе и сформулируем для такой записи признак делимости на 6. Так как число 12 — основание системы счисления— делится на 6, то число, записанное в двенадцатеричной системе, делится на 6 в том и только в том случае, если на 6 делится его последняя цифра (здесь то же самое положение, что и с делимостью на 5 в десятичной системе).

Так как числа 2, 3 и 4 тоже служат делителями числа 12, то справедливы следующие признаки делимости: число, записанное в двенадцатеричной системе, делится на 2 (соответственно на 3 и на 4), если его последняя цифра делится на 2 (соответственно на 3 и на 4).

Предоставим читателю доказать следующие утверждения, относящиеся к признакам делимости в двенадцатеричной системе.

a) Число А = (апап_! ... а\а0)\2 делится на 8, если на 8 делится число (aißo)i2, образованное его двумя последними цифрами.

b) Число А = (апап_! ... ûia0)i2 делится на 9, если на 9 делится число (а^о) 12, образованное его двумя последними цифрами.

c) Число А = (апап-\ ciido) w делится на 11, если на 11 делится сумма его цифр, т. е. число ап + ап-Х + .+ ... +ûi + а0.

Сформулируем еще две задачи, связанные с делимостью чисел. 1. Число

А = (3630)р

(записанное в системе с основанием р) делится на 7. Чему равно р и какова десятичная запись этого числа,

если известно, что /?<12. Будет ли решение задачи единственным, если условие р<12 не выполнено?

Ответ, р = 7, А — (1344)ю; если же величина /? не ограничена, то решений бесконечно много, именно: за р можно принять любое число вида 7 k или 7k— 1, где k = 1, 2, ...

2. Доказать, что число

(flA-i • • • ЯА))/»

т. е. число

делится на р — 1 в том и только том случае, если на р — 1 делится сумма

ап + а>п-1 + ... + cl\ + do-

(Сравните с признаком делимости на 9 в десятичной системе и с признаком делимости на 11 в двенадцатеричной системе.)

§ 8. ДВОИЧНАЯ СИСТЕМА

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

0 + 0 = 0, 0+1 = 1, 1 + 1=(Ю)2, а таблица умножения для двоичной системы имеет вид

0

1

0

0

0

1

0

1

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

1111101000,

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

О технических применениях двоичной системы мы расскажем ниже, а сейчас рассмотрим две задачи, связанные с двоичной записью чисел.

Задача 1. Я загадал какое-то целое число от 1 до 1000. Беретесь ли вы узнать его, задав мне не более 10 вопросов, на каждый из которых я буду отвечать только «да» или «нет»? Беритесь, задача эта вполне разрешима.

Одна из возможных серий вопросов, заведомо приводящая к успеху, такова:

1-й вопрос: Разделите задуманное число на 2. Разделится ли оно без остатка? Если ответ «да», то запишем цифру нуль, если «нет», то запишем единицу (иначе говоря, мы запишем остаток от деления задуманного числа на 2).

2-й вопрос: Разделите на 2 то частное, которое получилось при первом делении. Делится ли оно без остатка? Снова при ответе «да» запишем нуль, а при ответе «нет» — единицу.

Каждый следующий вопрос будем составлять по тому же самому образцу, т. е. так: разделите на 2 то частное, которое получилось при предыдущем делении. Делится ли оно без остатка? Всякий раз мы пишем нуль при положительном ответе и единицу при отрицательном.

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

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

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

Задача 2. У меня имеется 7 табличек, каждая из которых содержит, подобно шахматной доске, 64 клетки (рис. 2). В эти клетки вписаны различные числа, от 1 до 127. Задумайте какое-либо из этих чисел и скажите, в каких таблицах (они имеют номера от 1 до 7) это число встречается. Я назову это число. Каким образом?

Вот разгадка этого несложного фокуса.

Запишем каждое из чисел от 1 до 127 в двоичной системе. Каждое из этих чисел содержит в двоичной записи не более семи цифр (в частности, 127 = = (1111111)2). Впишем данное число А в таблицу с номером k (k = 1, 2, ..., 7), если в его двоичной записи на k-м месте стоит единица, и не будем его туда вписывать, если в его двоичной записи на k-м месте стоит нуль. Например, число 57, которое в двоичной системе записывается как

0111001,

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

Можно поставить вопрос наоборот: укажите произвольное число, от 1 до 127, и я скажу, в каких табличках на рис. 2 оно есть, а в каких его нет. Для ответа

Рис. 2.

на такой вопрос достаточно перевести названное число в двоичную систему (при некотором навыке это нетрудно сделать и в уме) и назвать номера тех разрядов, в которых получится единица*).

§ 9. ДВОИЧНЫЙ КОД В ТЕЛЕГРАФИИ

Одно из сравнительно старых технических применений двоичной системы — это телеграфный код. Выпишем буквы (без «ё» и «й», но включая «—», т. е. пробел между словами), употребляющиеся в русском языке, по алфавиту и перенумеруем их подряд. Получим

Запишем номер каждой из букв в двоичной системе. Так как 25 = 32, то каждый из этих номеров представляется в ней не более чем пятью знаками. Будем писать каждый из этих номеров с помощью именно пяти знаков, добавляя, если нужно, соответствующее число нулей впереди первой значащей цифры. Получаем:

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

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

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

Телеграфный аппарат представляет собой в принципе комбинацию двух устройств: передающей части, которая служит для перевода буквы в соответствующую систему импульсов, посылаемых по линии связи, и приемного устройства, которое по заданной комбинации импульсов печатает на телеграфной ленте (или бланке) соответствующую букву*).

Применение в телеграфии именно двоичной системы связано, очевидно, с удобством превращения двоичного числа в систему электрических сигналов**).

Мы указали здесь на применение двоичной системы в сравнительно старой области техники (первые телеграфные аппараты, основанные на передаче электрических сигналов по проводам, появились в 30-х годах прошлого века). Сейчас мы рассмотрим одно из новейших применений двоичной системы — использование этой системы в вычислительных машинах. Предварительно нам придется -сказать, хотя бы в самых общих чертах о том, что представляют собой так называемые электронные вычислительные машины.

§ 10. НЕСКОЛЬКО СЛОВ О ВЫЧИСЛИТЕЛЬНЫХ МАШИНАХ

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

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

**) Наряду с описанной выше системой обозначения (кодирования) букв пятерками нулей и единиц, в телеграфии широко применяется и другая система кодирования, так называемая азбука Морзе. В принципе азбука Морзе тоже дает представление каждой буквы в виде комбинаций двух различных элементов (точек и тире); обсуждать детали этой системы мы здесь не будем.

тельную работу, появились давно. Так, например, обычные конторские счеты были известны более четырех тысяч лет тому назад. Вместе с тем подлинная «машинная математика» возникла каких-нибудь 15—20 лет назад, когда появились первые быстродействующие вычислительные машины, основанные на применении радиоэлектронной техники (радиоламп, а затем и полупроводниковых элементов). За короткий срок эта область техники достигла поразительных успехов. Современные вычислительные машины работают со скоростью в несколько десятков и даже сотен тысяч операций в секунду, другими словами, в каждую секунду такая машина выполняет столько операций, сколько опытный вычислитель, вооруженный, например, арифмометром, может выполнить за месяц работы. Появление таких машин позволило успешно решать задачи столь сложные и громоздкие, что при ручном способе счета их было бы безнадежно даже ставить. Например, для современных вычислительных машин вполне посильна такая задача, как решение системы, состоящей из нескольких сотен уравнений первой степени с таким же количеством неизвестных. Вычислитель, вооруженный карандашом и бумагой или арифмометром, не справился бы с такой задачей и за всю свою жизнь.

Когда в популярной литературе упоминают о вычислительных машинах, то часто при этом употребляют такие выражения, как «машина, решающая сложные уравнения», «машина, играющая в шахматы» или

Рис. 3. Электронная вычислительная машина «Стрела».

«машина — переводчик с одного языка на другой». При этом может создаться неправильное впечатление, что каждая такая функция — решение уравнений, игра в шахматы, перевод и т. п. выполняется некоторой специальной машиной, сконструированной именно для этой цели. На самом деле для решения разнообразных задач, как математических (решение уравнений, составление таблиц логарифмов и т. п.), так и нематематических (например, перевод), могут быть использованы одни и те же устройства, так называемые универсальные вычислительные машины. Собственно говоря, каждая такая машина может выполнять лишь некоторое, довольно ограниченное, количество различных элементарных операций: складывать и перемножать числа, хранить полученные результаты в специальном устройстве — «памяти» машины, сравнивать числа между собой, выбирая, скажем, из двух или нескольких чисел наибольшее или наименьшее и т. п. Однако решение самых разнообразных и сложных задач может быть сведено к последовательности (возможно, очень длинной) таких элементарных операций. Сама эта последовательность операций определяется программой, составляемой для каждой определенной задачи математиком-программистом. Таким образом, разнообразие задач, которые может решать универсальная вычислительная машина, есть разнообразие задаваемых этой машине программ.

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

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

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

§ 11. ПОЧЕМУ ЭЛЕКТРОННАЯ МАШИНА «ПРЕДПОЧИТАЕТ» ДВОИЧНУЮ СИСТЕМУ СЧИСЛЕНИЯ

Если мы производим вычисления вручную, то числа при этом пишутся карандашом или чернилами на бумаге. Для машины, однако, нужен какой-то иной способ фиксации тех чисел, с которыми она оперирует. Чтобы выяснить суть дела, рассмотрим сначала не вычислительную машину, а устройство, несравненно более простое — обыкновенный счетчик (электрический, газовый, счетчик такси и т. п.). Всякий такой счетчик состоит из нескольких колесиков, каждое из которых может находиться в одном из 10 положений, отвечающих цифрам от 0 до 9. Ясно при этом, что устройство, состоящее из k таких колесиков, может служить для фиксации 10* различных чисел, от 0 до 99 ... 9. Такой счетчик можно было бы использовать как своего рода счеты, т. е. применять его не только для фиксации чисел, но и для выполнения арифметических операций.

Если бы мы хотели иметь счетчик, приспособленный не к десятичной системе, а к системе с каким-то другим основанием /?, то такой счетчик следовало бы составлять из колесиков, каждое из которых имеет не 10, а р различных положений. В частности, устройство, с помощью которого можно было бы фиксировать числа, записанные в двоичной системе, должно состоять из элементов, каждый из которых имеет два возможных состояния. Само собой разумеется, что для устройства счетчика (основанного на какой-то системе счисления) нет необходимости пользоваться именно колесиками. В принципе можно сделать счетчик из каких угодно элементов, важно лишь, чтобы каждый из этих элементов имел столько устойчивых состояний, сколько единиц содержит выбранное нами основание системы счисления.

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

Для радиоэлектронных элементов (радиоламп, полупроводниковых элементов), которые в основном используются в вычислительных машинах, характерно наличие двух устойчивых состояний. Например, электронная лампа может быть «отперта» (тогда через нее идет ток) или «заперта» (ток через нее не проходит). По тому же принципу «да» или «нет» работают и полупроводниковые элементы, которые в последнее время находят все более широкое применение в вычислительной технике. Эти свойства радиоэлектронных элементов и служат основной причиной того, что именно двоичная система оказалась наиболее удобной для вычислительных машин.

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

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

скольких групп, составленных из нулей и единиц. Например, число

2593

в двоично-десятичной системе записывается так: 0010 0101 1001 ООН.

Для сравнения приведем двоичную запись этого же числа:

101011101001.

Посмотрим, как в вычислительной машине, основанной на двоичной системе счисления, реализуются арифметические операции. Основная операция, которую следует рассмотреть, — это операция сложения, так как умножение сводится к многократному сложению, а вычитание сводится к прибавлению отрицательных чисел, и, наконец, деление, сводится к повторному вычитанию. В свою очередь сложение многоразрядных чисел сводится к выполнению соответствующих действий поразрядно. Сложение двух двоичных чисел в каждом разряде может быть описано так. Пусть а — цифра, стоящая в данном разряде в первом слагаемом, Ь — цифра, стоящая в том же разряде во втором слагаемом, и с — цифра, которую нужно перенести из предыдущего разряда (где, как мы считаем, сложение уже выполнено). Произвести сложение в данном разряде — это значит указать, какая цифра должна быть записана в этом разряде в сумме и что нужно перенести в следующий разряд. Обозначим цифру, которая должна быть записана в данном разряде суммы, s, а ту величину, которую нужно перенести в следующий разряд, обозначим Так как каждая из величин а, 6, с, s и t может принимать только значения 0 или 1, то все возможные здесь варианты содержатся в следующей таблице:

а

0

1

0

0

1

1

0

1

Ь

0

0

1

0

1

0

1

1

с

0

0

0

1

0

1

1

1

s

0

1

1

1

0

0

0

1

t

0

0

0

0

1

1

1

1

Таким образом, чтобы вычислительная машина могла сложить два числа, содержащих данное фиксированное число двоичных разрядов, в ней на каждый из этих разрядов должно существовать устройство, работающее следующим образом: в этом устройстве должно быть три входа, отвечающих величинам а, & и с, и два выхода, отвечающих величинам s и t. Будем предполагать, как это обычно бывает в электронных устройствах, что единица означает наличие тока на данном входе или выходе, а нуль — его отсутствие. Рассматриваемое устройство, называемое одноразрядным сумматором, должно работать в соответствии с указанной выше таблицей, т. е. так, что если ни на один из трех входов не подается так, то его не должно быть ни на одном из выходов; если подается ток на а, но не подается на Ь и с, то должен быть ток на s и отсутствие тока на и т. д. Устройство, работающее по такой схеме, нетрудно сконструировать из электронных ламп или из полупроводниковых элементов.

§ 12. ОБ ОДНОМ ЗАМЕЧАТЕЛЬНОМ СВОЙСТВЕ ТРОИЧНОЙ СИСТЕМЫ

Для оценки пригодности той или иной системы счисления в качестве основы для конструирования вычислительной машины имеет значение, кроме простоты осуществления арифметических операций в ней, также и то, что обычно называют экономичностью системы. Под этим понимается тот запас чисел, которые можно записать в данной системе с помощью определенного количества знаков. Поясним это на примере. Чтобы в десятичной системе записать 1000 чисел (от 0 до 999), необходимо 30 знаков (по 10 цифр для каждого разряда). А в двоичной системе можно с помощью 30 знаков записать 215 различных чисел (так как для каждого двоичного разряда нужны только две цифры 0 и 1, то с помощью 30 цифр мы можем записывать числа, содержащие до 15 двоичных разрядов). Но

215 > 1000,

поэтому, имея 15 двоичных разрядов, можно записать больше различных чисел, чем с помощью 3 десятичных. Таким образом, двоичная система более экономич-

на, чем десятичная. Но какая из систем счисления самая экономичная? Для ответа на этот вопрос рассмотрим следующую конкретную задачу. Пусть в нашем распоряжении имеется 60 знаков. Мы можем, разбив их на 30 групп по 2 элемента в каждой, записать с их помощью в двоичной системе любое число, имеющее не больше 30 двоичных разрядов, т. е. в общей сложности 230 чисел. Те же 60 знаков мы можем разбить на 20 групп по 3 элемента и, пользуясь троичной системой, записать З20 различных чисел. Далее, разбив 60 знаков на 15 групп по 4 в каждой, можно применить четверичную систему и записать 415 чисел, и т. д. В частности, воспользовавшись десятичной системой (т. е. разбив все знаки на 6 групп по 10 в каждой), мы могли бы записать 106 чисел, а применив шестидесятеричную (вавилонскую) систему, можно было бы с помощью 60 знаков записать только 60 чисел. Посмотрим, какая из возможных здесь систем самая экономичная, т. е. позволяет записать с помощью данных 60 знаков наибольшее количество чисел. Иными словами, речь идет о том, какое из чисел

230, З20, 415, 512, б10, 10б, 125, 154, 203, 302, 60

наибольшее. Легко проверить, что наибольшим здесь будет число 320. Действительно, покажем сначала, что

230 < 320^

Так как 230 = (23)10 = 810, а З20 = (32) 10 = 910, то наше неравенство можно переписать в виде

810 < 910.

Но в такой форме оно очевидно. Далее,

415 = (22)15 = 230. Следовательно, в силу уже доказанного

320 > 415#

Точно так же легко проверить и справедливость следующей цепочки неравенств:

41з > 512 > 6ю > 10б > 12- > 154 > 203 > 302 > 60.

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

Этот вывод никак не связан с тем, что рассматривалось именно 60 знаков. Мы привели этот пример только потому, что 60 знаков удобно разбивать на группы по 2, 3, 4 и т. д. знаков.

В общем случае, если взять п знаков, а за основание

счисления принять некоторое число дс, то получится

разрядов, и количество чисел, которые при этом можно записать, будет равно

Рассмотрим это выражение как функцию переменного х, принимающего не только целые, но и любые (дробные, иррациональные) положительные значения. Можно найти то значение переменного х, при котором эта функция достигает максимума. Оно равно е — иррациональному числу, представляющему собой основание так называемой натуральной системы логарифмов и играющему важную роль в самых разных вопросах высшей математики*). Число е приближенно равно

2,718281828459045 ...

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

В данном случае у(х) =» хх. Производная этой функции равна

Приравняв ее нулю, получим, что

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

Ближайшее к е целое число есть 3. Оно и служит основанием наиболее экономичной системы счисления. График функций

у = (ху

изображен на рис. 4. (При этом, однако, по осям х и у взяты различные масштабы.)

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

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

Рис. 4.

§ 13. О БЕСКОНЕЧНЫХ ДРОБЯХ

До сих пор мы говорили о целых числах. От десятичной записи целых чисел естественно перейти к десятичным дробям. Для этого нужно наряду с неотрицательными степенями числа 10 (т. е. 1, 10, 100 и т. д.) рассматривать и его отрицательные степени (Ю-1, 10~2 и т. д.) и составлять комбинации, в которых участвуют как те, так и другие. Например, выражение

23,581

означает, как известно,

2 • 101 + 3 • 10° + 5. Ю-1 + 8 - Ю-2 + 1 - Ю-3

и т. п.

Различные числа удобно изображать точками на прямой. Возьмем некоторую прямую и выберем на ней определенную точку О (начало отсчета) и единицу масштаба— отрезок OA (рис. 5). Будем считать, что точка О изображает число нуль, а точка А — единицу. Отложив от точки О отрезок ÖA два, три и т. д. раз, мы получим точки, отвечающие числам два, три и т. д. Таким образом можно изобразить на прямой все целые числа. Для изображения дробных чисел, содержащих десятые, сотые и т. д., нужно делить отрезок OA на десять, сто и т. д. частей и пользоваться этими более мелкими единицами длины. Мы можем, таким образом, отметить на

прямой точки, отвечающие всевозможным числам вида

• • • я^о' Ьф2... Ъп,

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

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

Чтобы каждой точке прямой поставить в соответствие некоторую (бесконечную) десятичную дробь, поступим следующим образом. Будем, для удобства, говорить не о всей прямой, а об определенной ее части, именно об отрезке OA, принятом нами за единицу масштаба. Пусть X—некоторая точка этого отрезка. Разделим OA на 10 равных частей и занумеруем эти части цифрами от 0 до 9. Обозначим Ь\ номер того частичного

Рис. 5.

отрезка, на котором находится точка х. Разделим теперь этот маленький отрезок снова на 10 частей, перенумеруем полученные части цифрами от 0 до 9 и обозначим Ь2 номер того из этих маленьких отрезков, на котором находится точка х. Отрезок с номером Ь2 снова разделим на 10 частей и, повторив всю процедуру, получим Ь$. Будем продолжать этот процесс неограниченно, деля на каждом шаге отрезок, полученный на предыдущем шаге, на 10 частей. В результате этого мы получим последовательность цифр Ьи Ь2, ..., ЬПу ..., которую мы будем писать в виде

0, bxb2... bn ...

и называть бесконечной десятичной дробью, отвечающей точке х. Оборвав эту дробь на некотором месте, мы получим обычную (конечную) десятичную дробь 0, Ь\ Ь2 ... Ьп, определяющую положение точки X на прямой не точно, а приближенно (именно, с точностью до доли основного отрезка, если бесконечную дробь оборвать на /i-й цифре).

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

0,0999...,

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

0,1000...

Таким образом, мы получили две бесконечные дроби, отвечающие одной и той же точке. То же самое будет

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

0,125000... и 0,124999...

изображаются на прямой одной и той же точкой.

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

Введя такое ограничение, можно каждой точке отрезка OA поставить в соответствие одну-единственную, вполне определенную бесконечную десятичную дробь, причем двум разным точкам будут соответствовать две различные дроби.

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

(0, Ьф2 ...Ьп...)2

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

(0, ЬА ... £„),

т. е. число

определяющее положение рассматриваемой точки с точностью до -уг части основного отрезка.

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

В заключение рассмотрим следующую поучительную задачу. Возьмем снова отрезок ОЛ, разделим его на три равные части и выбросим среднюю часть (считая, что сами точки деления относятся к этой средней части, т. е. тоже выбрасываются; рис. 6). Далее, каждую из двух оставшихся частей опять разделим на три равные части и средние части выбросим. После этого останутся четыре маленьких кусочка, в каждом из которых мы снова выбросим среднюю треть. Будем повторять этот процесс неограниченно. Спрашивается, сколько точек отрезка OA останутся при этом невыброшенными?

На первый взгляд может показаться, что в результате такой «чистки» останутся только крайние точки О и Л. Это заключение подтверждается, казалось бы, следующим рассуждением. Подсчитаем сумму длин всех отрезков, выбрасываемых при описанном выше процессе. (Напомним, что длина всего отрезка OA принимается равной 1.) На первом шаге мы выбрасываем один отрезок длины тр на втором шаге — два отрезка по i каждый, на третьем — четыре отрезка по -<L-

Рис. 6.

каждый и т. д. Сумма длин всех выбрасываемых отрезков равна

Это — бесконечно убывающая геометрическая прогрессия с первым членом ^ и знаменателем -g . Но известной формуле ее сумма равна

Итак, сумма длин выброшенных отрезков в точности равна длине исходного отрезка ОА!

И все же, описанный выше процесс оставляет на отрезке невыброшенными кроме точек О и А еще бесконечно много точек. Чтобы убедиться в этом, сделаем следующее. Представим каждую точку единичного отрезка OA с помощью бесконечной дроби, записанной по троичной системе. Каждая такая дробь будет состоять из нулей, единиц и двоек. Я утверждаю: при описанном выше процессе «выбрасывания середин» останутся те точки, которым отвечают троичные дроби, не содержащие ни одной единицы (т. е. состоящие целиком из нулей и двоек). Действительно, на первом шаге мы выбросили среднюю треть единичного отрезка, т. е. те точки, которым отвечают троичные дроби, имеющие на первом месте единицу. На втором этапе мы в каждой из оставшихся частей снова выбрасываем среднюю треть, т. е. изгоняем дроби, у которых на втором месте стоит единица, и т. д. (При этом мы выбрасываем и такие точки, которые представляются двумя троичными дробями, если хоть одна из этих дробей содержит единицу. Например, конец первой трети отрезка OA можно представить троичной дробью

0,1000...

или

0,0222,

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

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

0,020202...,

которая представляет собой, как легко проверить, троичное разложение числа -j*).

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

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

*) Действительно, троичная дробь, 0,020202... — это 2 • 3-2 -I- 2 .3"4 + ..., а сумма этой геометрической прогрессии равна

Сергей Васильевич Фомин Системы счисления Л\., 1964 г., 44 стр. с илл.

Редактор И. Е. Морозова Техн. редактор Л. Ю. Плакше Корректор З. В. Автонеева

Сдано в набор 20/ХП 1963 г. Подписано к печати 29/1V 1964 г. Бумага 84x108/32. Физ. печ. л. 1,375. Условн. печ. л. 2,26. Уч.-изд. л. 1,85. Тираж 37 ООО экз. Т-04579. Цена книги 6 коп. Заказ № 127.

Издательство «Наука». Главная редакция физико-математической литературы Москва, В-71, Ленинский проспект, 15.

Ленинградская типография № 2 имени Евгении Соколовой «Главполиграфпром,!» Государственного комитета Совета Министров СССР по печати. Измайловский проспект, 29.

ИЗДАТЕЛЬСТВО «НАУКА»

ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ

Москва, В-71, Ленинский проспект, 15

ГОТОВЯТСЯ К ИЗДАНИЮ:

Артамонов И. Д., Иллюзии зрения. Борель Э., Вероятность и достоверность, перев. с фр.

Вентцель Е. С, Элементы динамического программирования.

Винер Н., Я — математик, перев. с англ.

Воронцов-Вельяминов Б. А., Очерки о вселенной.

Кречмар В. А., Задачник по алгебре.

Наука в космосе. Сборник статей, перев. с англ.

Постников M. М., Магические квадраты.

Селезнев Ю. А., Основы элементарной физики (для самообразования).

Сент-Дьердьи А., Введение в субмолекулярную биологию, перев. с англ.

Соминский И. С, Элементарная алгебра (дополнительный курс).

Стройк Д., Краткий очерк истории математики, перев. с англ.

Струве О. и др., Элементарная астрономия, перев. с англ.

Улам С, Нерешенные математические проблемы, перев. с англ.

Фаддеев Д. К. и Соминский И. С, Алгебра (для самообразования).

Предварительные заказы на эти книги принимают магазины Книготорга. Оформив заказ на почтовой открытке в магазине, Вы получите извещение о поступлении книги в магазин. В случае отказа в приеме предварительного заказа просим сообщить Всесоюзному объединению книжной торговли по адресу: Москва, В-71, Ленинский проспект, 15.

ИЗДАТЕЛЬСТВО «НАУКА»

ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ

Москиа, В-71, Ленинский проспект, 15

ИМЕЮТСЯ В ПРОДАЖЕ:

Архимед, Сочинения, 1958, 640 стр., 2 р. 70 к.

Беляков М. В., Атмосфера, I960, 72 стр., 11 коп.

Бронштэн В. А., Планеты и их наблюдения, 1957, 208 стр., 46 коп.

Галилей Галилео, Диалог о двух главнейших системах мира; птоломеевой и коперниковой, 1948, 380 стр., 2 р. 33 к.

Горшков Г. И., Строение земного шара, 1958, 48 стр., 8 коп.

Гриффин Д., Эхо в жизни людей и животных, 1961, 108 стр., 18 коп.

Заборенко К. Б., Радиоактивность, 1958, 80 стр., 12 коп.

Каган В. Ф., Лобачевский и его геометрия. Общедоступные очерки, 1955, 304 стр., 65 коп.

Левантовский В. И., Рассказ об искусственных спутниках, 1957, 96 стр., 16 коп.

Литцман В., Старое и новое о круге, 1960, 60 стр., 9 коп.

Литцман В., Теорема Пифагора, 1960, 114 стр., 17 коп.

Математическое просвещение, вып. 2, 1957, 320 стр., 62 коп. То же, вып. 4, 322 стр., 60 коп. То же, вып. 5, 304 стр., 64 коп. То же, вып. 6, 374 стр., 71 коп.

Книги продаются в книжных магазинах и высылаются также почтой наложенным платежом без задатка всеми республиканскими, краевыми и областными отделениями «Книга — почтой».

Цена 6 коп.

ИЗДАТЕЛЬСТВО «НАУКА»

ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ

ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ

Вып. 1. А. И. Маркушевич. Возвратные последовательности.

Вып 2. И. П. Натансон. Простейшие задачи на максимум и минимум.

Вып. 3. И. С. Соминский. Метод математической индукции.

Вып. 4. А. И. Маркушевич. Замечательные кривые.

Вып. 5. П. П. Коровкин. Неравенства.

Вып. 6. H. Н. Воробьев. Числа Фибоначчи.

Вып. 7. А. Г. Курош. Алгебраические хранения произвольных степеней.

Вып. 8. А. О. Гельфонд. Решение уравнений в целых числах.

Вып. 9. А. И. Маркушевич. Площади и логарифмы.

Вып. 10. А. С. Смогоржевский. Метод координат.

Вып. 11. Я. С. Дубнов. Ошибки в геометрических доказательствах.

Вып. 12. И. П. Натансон. Суммирование бесконечно малых величин.

Вып. 13. А. И. Маркушевич. Комплексные числа и конформные отображения.

Вып. 14. А. И. Фетисов. О доказательствах в геометрии.

Вып. 15. И. Р. Шафаревич. О решении уравнений высших степеней.

Вып. 16. В. Г. Шерватов. Гиперболические функции.

Вып. 17. В. Г. Болтянский. Что такое дифференцирование?

Вып. 18. Г. И. Миракьян. Прямой круговой цилиндр.

Вып. 19. Л. А. Люстерник. Кратчайшие линии.

Вып. 20. А. М. Лопшиц. Вычисление площадей ориентированных фигур.

Вып. 21. Л. И. Головина и И. М. Яглом. Индукция в геометрии.

Вып. 22. В. Г. Болтянский. Равновеликие и равносоставленные фигуры.

Вып. 23. А. С. Смогоржевский. О геометрии Лобачевского.

Вып. 24. Б. И. Аргунов и Л. А. Скорняков. Конфигурационные теоремы.

Вып. 25. А. С. Смогоржевский. Линейка в геометрических построениях.

Вып. 26. Б. А. Трахтенброт. Алгоритмы и машинное решение задач.

Вып. 27. В. А. Успенский. Некоторые приложения механики к матема тике.

Вып. 28. Н. А. Архангельский и Б. И. Зайцев. Автоматические цифровые машины.

Выи. 29. А. Н. Костовский. Геометрические построения одним циркулем.

Вып. 30. Г. Е. Шилов. Как строить графики.

Вып. 31. А. Г. Дорфман. Оптика конических сечений.

Вып. 32. Е. С. Вентцель. Элементы теории игр.

Вып. 33. А. С. Барсов. Что такое линейное программирование.

Вып. 34. Б. Е. Маргулис. Системы линейных уравнений.

Вып. 35. Н. Я. Виленкин. Метод последовательных приближений.

Вып. 36. В. Г. Болтянский. Огибающая.

Вып. 37. Г. Е. Шилов. Простая гамма (устройство музыкальной шкалы).

Вып. 38. Ю. А. Шрейдер. Что такое расстояние?

Вып. 39. H. Н. Воробьев. Признаки делимости.

Вып. 40. С. В. Фомин. Системы счисления.