и наименьшее общее кратное чисел

№ п/п	Задания	Баллы
	Найдите НОК и НОД чисел a и b.
	Найдите НОД чисел a и b с помощью алгоритма Евклида.
	Решите задачу.
Итого:

 

Вариант	Задание 1	Задание 2	Задание 3
	192 и 240	582 и 957	Имеется 36 синих и 48 красных листов бумаги. Какое наибольшее число комплектов можно сделать из этих листов, если в каждом комплекте должно быть по одинаковому числу синих и одинаковому числу красных листов?
	1890 и 504	930 и 1085	Три школьных киоска получили по одинаковому числу тетрадей с различных торговых баз, первая из которых поставила тетради в пачках по 50 штук, вторая – по 100 штук, а третья – по 200 штук в каждой пачке. Сколько тетрадей получила каждая школа, если известно, что трем школам было отправлено менее 2000 тетрадей?
	386 и 714	672 и 111	В три магазина поступили яблоки в одинаковых ящиках. В первый магазин доставили 1800 кг яблок, во второй – 4848 кг, в третий – 2520 кг. Сколько ящиков с яблоками доставили в каждый магазин, если ящики были максимально возможной массы?
	121 и 253	121 и 473	12 июня от одной пристани отправились три парохода. Первый совершает рейс за 4 суток, второй – за 9, третий – за 6. Определите ближайшую дату, когда одновременно отправятся в новый рейс первый и второй пароходы, второй и третий и все три парохода.
	948 и 1620	242 и 583	В некоторый момент времени планеты Венера и Меркурий занимают определенное положение относительно неподвижных звезд. Через сколько суток обе планеты будут находиться снова в том же положении относительно звезд, если известно, что Меркурий делает полный оборот вокруг Солнца за 88 суток, а Венера – за 225 суток?
	3240 и 1008	169 и 195	Три школьных киоска получили по одинаковому числу тетрадей с различных торговых баз, первая из которых поставила тетради в пачках по 50 штук, вторая – по 100 штук, а третья – по 200 штук в каждой пачке. Сколько тетрадей получила каждая школа, если известно, что трем школам было отправлено менее 2000 тетрадей?
	570 и 852	306 и 255	Три автобуса одновременно отправляются с площади по трем направлениям и возвращаются обратно. Первый делает рейс за 1 ч. 52 мин. и вновь отправляется через 8 мин., второй возвращается через 1 ч. 15 мин. и отправляется вновь через 15 мин., третий возвращается через 2 ч. 30 мин. и отправляется вновь через 30 мин. Все три автобуса отправились в 7 ч. утра. В какое ближайшее время они вновь одновременно отправятся с площади?
	344 и 946	1224 и 748	В три магазина поступили яблоки в одинаковых ящиках. В первый магазин доставили 1800 кг яблок, во второй – 4848 кг, в третий – 2520 кг. Сколько ящиков с яблоками доставили в каждый магазин, если ящики были максимально возможной массы?

ДОПОЛНИТЕЛЬНЫЙ МАТЕРИАЛ

 

О круглых и некруглых числах

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

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

2·103 + 5·102 + 4·10 + 8·100.

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

Единицами следующих разрядов должны служить числа 7², 7³ и т.д. Их естественно обозначать

(100)₇, (1000)₇ и т.д.

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

,

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

,

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

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

,

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

(10300)7.

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

(2548)₁₀ = (10300)₇.

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

(147)₁₀ = (300)₇,

(343)₁₀ = (1000)₇

(так как 147 = 3 · 7² и 343 = 7³); в то же время

(100)₁₀ = (202)₇,

(500)₁₀ = (1313)₇

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

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

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

Почему именно числу 10 отведена такая привилегированная роль? Человек, далекий от этих вопросов, ответил бы, вероятно, не задумываясь, так: дело просто в том, что число 10 – круглое, на него удобно умножать любое число, поэтому удобно считать десятками, сотнями и т.д. Мы, однако, уже выяснили, что дело обстоит как раз наоборот: число 10 потому и круглое, что оно принято за основание системы счисления. При переходе к какой-либо иной системе счисления, скажем, семеричной (где оно записывается в виде (13)₇), его «круглость» немедленно исчезает.

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

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

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

 

 

 

Рис. 1

 

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

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

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

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

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

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

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

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

Позиционные и непозиционные системы

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

a_k · p^k + a_{k- 1} · p^{k- 1}+... + a ₁· p + a₀.

Далее такое число сокращенно записывается в виде

(a_k a_{k- 1} … a ₁ a₀) _p.

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

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

LXXXVIII.

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

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

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

Игра «ним» (игра в три кучки спичек)

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

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

Для решения этой задачи удобно воспользоваться двоичной системой. Пусть в трех кучках лежат, соответственно, а, b и с спичек. Запишем числа a, b и с в двоичной системе:

а = а_т · 2^т + а_{т- 1}· 2^{т- 1}+... + а ₁· 2 + а ₀,

b = b_т · 2^т + b_{т- 1}· 2^{т- 1}+... + b ₁· 2 + b ₀,

с = с_т · 2^т + с_{т- 1}· 2^{т- 1}+... + с ₁· 2 + с ₀.

Мы можем при этом считать, что в каждой записи имеется одно и то же число разрядов, дописав, если нужно, впереди соответствующее число нулей у тех чисел, в которых было меньше знаков, чем в других. Таким образом, каждая из цифр а₀, b₀, с₀,..., а_т, b_т, с_т может быть равна 0 или 1, причем из цифр а_т, b_т и с_т хотя бы одна (но не обязательно все) отлична от нуля. Игрок, делающий первый ход, может заменить одно из чисел (a, b или с) любым меньшим числом. Предположим, что он решил взять спички из первой кучки, т.е. изменить число а. Это означает, что будут изменены какие-то из цифр а₀, а ₁..., а_т. Аналогично, взяв спички из второй кучки, игрок изменит хоть одну из цифр b₀, ..., b_m, a взяв спички из третьей кучки, он изменит хоть одну из цифр с ₀,..., с_т.

Рассмотрим теперь суммы

а_т + b_т + с_т, а_{т -1}+ b_{т -1}+ с_{т- 1},..., а₀ + b₀ + с₀. (*)

Каждая из этих сумм может быть равна 0, 1, 2 или 3. Если хоть одна из этих сумм нечетна (т.е. равна 1 или 3), то игрок, делающий первый ход, может обеспечить себе выигрыш. Действительно, пусть а_k + b_k + c_k – первая (считая слева направо) из сумм (*), являющаяся нечетной. Тогда хотя бы одна из трех цифр а_k, b_k и c_k равна 1. Пусть, например, а_к = 1. При этом условии играющий может взять из первой кучки такое количество спичек, чтобы коэффициенты а_m,..., a_{k+ 1} не изменились, величина а_k стала равной нулю, а каждый из коэффициентов
a_{k- 1},..., a₀ принял бы то значение (0 или 1), которое желательно для играющего, делающего ход. Таким образом, из первой кучки можно взять такое количество спичек, чтобы и все суммы

а_{k- 1}+ b_{k- 1}+ c_{k- 1},..., a₀ + b₀ + c₀

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

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

Нетрудно сообразить, что тройки чисел, благоприятствующие второму игроку, встречаются достаточно редко, так что при правильной игре и случайном выборе чисел a, b и с выигрывать будет, как правило, первый игрок. Например, если у нас имеется 10 спичек (a + b + с = 10), то существует 9 способов распределить их на три кучки. Из них 8 обеспечивают выигрыш первому игроку и только один – второму.

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

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

– А Б В Г Д Е Ж З И К Л М Н О П Р

0 1 2 3 4 5 6 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.

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

– ~ 0 0 0 0 0

А ~ 0 0 0 0 1

Б ~ 0 0 0 1 0

Я ~ 1 1 1 1 1.

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

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

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

Двоичная система – хранительница тайн

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

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

Естественно поставить такой вопрос: «А существует ли система шифровки, безусловно гарантирующая сохранение тайны, или же достаточно искусный дешифровщик может, в принципе, прочесть любое шифрованное сообщение?»

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

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

 

 

Рис. 2

 

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

 

0 + 0 = 0, 1 + 0 = 0 + 1 = 1, 1 + 1 = 0,

 

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

Весь процесс может быть описан следующей схемой:

1) текст + гамма = шифрованный текст;

2) шифрованный текст + гамма = текст + гамма + гамма = текст.

Нетрудно понять, что человек, имеющий в руках зашифрованный таким образом текст, но не имеющий соответствующей гаммы, принципиально не может узнать его содержание, точно так же, как ничего нельзя сказать о величине X, если известна лишь величина суммы X+Y и сказано, что У – какое-то совершенно произвольное неизвестное нам число.

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

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

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

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

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

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

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

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

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

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

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

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

в двоично-десятичной системе записывается так:

0010 0101 1001 0011.

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

10100010001.

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

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

 

a

b

c

s

t

 

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

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

 

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

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