<<

стр. 2
(всего 2)

СОДЕРЖАНИЕ

Игра <Ним> являлась излюбленной темой математических
кружков в МГУ. Иногда она представлялась в виде гонки несколь-
ких пешек от одного края доски доски до другого. Читатель сам
сможет сформулировать правила игры в таком её представлении.
При игре с одной кучкой, очевидно, побеждает начинающий.
При игре с двумя кучками начинающий побеждает не всегда.
12. Докажите, что выигрывающей позицией является позиция
с двумя равными кучками. Игрок, сумевший после своего хода
попасть в такую позицию, всегда сможет выиграть.
В случае трёх и более кучек описание выигрышной позиции
не так просто. Алгоритм распознавания выигрышной позиции следу-
ющий. Нужно количество спичек в каждой кучке записать в двоичной
системе, и вычислить сумму по модулю 2 полученных двоичных
наборов (далее для краткости будем называть её ним-суммой).
Для этого вначале нужно вычислить покомпонентную сумму этих
наборов, т. е. найти сумму всех младших разрядов, потом сумму
следующих за ними разрядов (отсутствующие разряды заменяются
нулями) и т. д., и записать полученные суммы в виде (возможно,
недвоичного) набора, а потом каждую его компоненту заменить
на остаток от деления на 2. Если получится набор из одних нулей,
то позиция выигрышная.
Например, если в кучках было 3, 7, 12, 17 спичек, то поком-
понентно складывать придётся наборы
11 (=3)
+
111 (=7)
1100 (=12)
10001 (=17)
11223
Ним-сумма равна 11001, поэтому позиция является проигрыш-
ной для того, кто в неё попал после своего хода. Причина в том,
что противник может сделать ход, которым он попадёт в позицию
с нулевой ним-суммой. Для этого он может оставить в последней
кучке число спичек, равное в двоичной записи ним-суммы наборов
30
10001 и 11001, т. е. 01000. Тогда ним-сумма чисел, образующих новую
позицию, будет равна нулевому набору, так как эта сумма будет отли-
чаться от прежней суммы 11001 прибавлением к ней по модулю 2 набо-
ра 11001, что даёт в результате, очевидно, нулевой набор. Поскольку
01000=8, из последней кучки надо взять 17?8=9 спичек.
13. Докажите в общем случае, что из позиции с ненулевой
ним-суммой за один ход можно попасть в позицию с нулевой
ним-суммой, а из позиции с нулевой ним-суммой любой ход ведёт
к позиции с ненулевой ним-суммой.
Теперь ясно, что тот, кто первый попал в позицию с нулевой
ним-суммой, дальше при любой игре противника при своём ходе
опять сможет попасть в такую же позицию, и в конце концов он
возьмёт последнюю спичку.
Указанная выигрышная стратегия поддаётся для реализации даже
на специализированных машинах. Одна из таких машин была вы-
ставлена после войны в Берлине на английской выставке и с успехом
конкурировала с находящимся рядом бесплатным пивным залом.
Знаменитый английский математик Алан Тьюринг вспоминал о том,
как популярность этой машины повысилась ещё больше после
победы над тогдашним бундесминистром экономики Л. Эрхардом.
Читателю предоставляем возможность найти выигрышную
стратегию при игре ним в поддавки.
Более интересная модификация игры ним получается, если огра-
ничить число спичек, которые можно взять за один раз, например,
числом 10. Тогда интерес представляет даже игра с одной кучкой
спичек. Эту игру изобрёл в XVII веке французский математик
Баше де Мезириак, написавший кстати, одну из первых в Европе
книг по занимательной математике. Читатель может попробовать
сам придумать для неё выигрышную стратегию.

§ 11. Д. И. МЕНДЕЛЕЕВ И ТРОИЧНАЯ СИСТЕМА
Когда мы рассматривали задачу о взвешивании с помощью
гирь, мы предположили, что груз лежит на одной чашке, а гири —
на другой. Но если разрешить класть гири на обе чашки весов, то
ответ в задаче об оптимальной системе разновесок изменится. Оп-
тимальной теперь будет система из гирек с массами, образованны-
ми степенями тройки. Этой задачей интересовался Д. И. Менделеев
в бытность свою председателем Российской палаты мер и весов*).

*) Менделеев имел широкие интересы как в чистой, так и в прикладной науке.
Он занимался, например, и экономикой, и демографией, известны его исследования
об оптимальной концентрации спирта в воде при производстве водки, по просьбе
генштаба он раскрыл состав артиллерийского пороха, используемого немецкой ар-
мией. Отвечая на один вопрос Менделеева, А. А. Марков написал знаменитую ра-
боту об оценке производной многочлена через величину его максимального значе-
ния на отрезке.
31
Оказалось, что частный случай этой задачи был опубликован
в книге Баше де Мезириака в XVII веке, а ранее был известен
Фибоначчи. Спрашивалось, какое наименьшее число гирь нужно
иметь, чтобы можно было взвесить любой груз от 1 до 40 г. Опти-
мальным оказался набор гирь 1, 3, 9, 27 г. Для того чтобы взве-
сить груз в n г, надо представить число n в виде суммы a0 +3a1 +
+9a2 +27a3 , где ai =0, ±1 (i=0, 1, 2, 3). Тогда для его взвеши-
вания достаточно на чашку вместе с грузом положить все гири,
массы которых входят в эту сумму со знаком минус, а на противо-
положную чашку положить все гири, массы которых входят в эту
сумму со знаком плюс.
Но как найти такую сумму? Один из возможных способов
решения этой задачи основан на сведении её к представлению
числа n+40 в виде суммы b0 +3b1 +9b2 +27b3 , где bi =0, 1, 2
(i=0, 1, 2, 3). Мы уже знаем, что эта задача равносильна предста-
влению числа n+40 в троичной системе n+40=(b0 b1 b2 b3 )3 . Один
из алгоритмов её решения заключается в том, что на правую чашку
весов кладутся вначале самые тяжёлые гири, потом гири меньшего
веса и т. д. Например, этот алгоритм для числа 40 даёт разложение
40=27+9+3+1. Если мы уравновесили массу n+40 г, поло-
жив на чашку bi гирь массы 3i (i=0, 1, 2, 3), то перекладывая
на другую чашку по одной гире каждой массы, мы уравновесим
n г. На алгебраическом языке это означает, что будет получено
равенство n=a0 +3a1 +9a2 +27a3 , ai =bi ?1 (i=0, 1, 2, 3). Оче-
видно, что при этом ai =0, ±1 (i=0, 1, 2, 3). Верно и обратное,
а именно, из разложения n=a0 +3a1 +9a2 +27a3 , ai =0, ±1
(i=0, 1, 2, 3) можно получить разложение n+40=b0 +3b1 +9b2 +
+27b3 , bi =0, 1, 2 (i=0, 1, 2, 3). Поэтому из известной нам един-
ственности представления n+40=b0 +3b1 +9b2 +27b3 , bi =0, 1, 2
(i=0, 1, 2, 3), означающей единственность записи данного числа
в троичной системе, вытекает единственность представления n=
=a0 +3a1 +9a2 +27a3 , ai =0, ±1 (i=0, 1, 2, 3), означающая един-
ственность записи данного числа в так называемой уравновешенной
троичной системе, n=(a0 a1 a2 a3 )3 .
Эта система способна составить некоторую конкуренцию дво-
ичной системе как по простоте арифметических алгоритмов, так
и по количеству применений в математических задачах. Удобным
её свойством является то, что для изменения знака у представляе-
мого числа достаточно изменить знаки у всех его цифр.
В общем виде доказанные выше утверждения можно записать
следующим образом.
Любое целое число от ?(3n ?1)/2 до (3n ?1)/2 может быть
однозначно представлено в виде 3n?1 bn?1 +...+3b1 +b0 , где bi =
=0, ±1. Для того чтобы взвесить любой груз от 1 до (3n ?1)/2 г
за одно взвешивание, достаточно иметь гири 1, 3, 9, ..., 3n?1 г.
32
Читатель легко докажет всё это самостоятельно, если заметит,
что (3n ?1)/2=1+3+32 +...+3n?1 , другими словами, троичная
запись числа (3n ?1)/2 состоит из одних единиц.
Докажем, что меньшего количества гирь недостаточно, и пред-
ложенная система для грузов от 1 до (3n ?1)/2 г оптимальна. До-
пустим, что есть система из n?1 гирь с массами g1 , ..., gn?1 , по-
зволяющая взвесить любой из этих грузов. Это значит, что любое
число m от ?(3n ?1)/2 до (3n ?1)/2 можно представить в виде
алгебраической суммы a1 g1 +...+an?1 gn?1 , ai =0, ±1, (i=1, ...
..., n?1). Но таких сумм ровно 3n?1 , так как каждое слагаемое
входит в неё с одним из трёх возможных коэффициентов. Но 3n?1
меньше общего числа различных грузов, равного 3n .
14. Покажите, что оптимальная система гирь для взвешивания
грузов от 1 до (3n ?1)/2 определена однозначно.
15. Докажите, что для взвешивания любого груза от 1 до m г,
n?1 ?1)/2<m?(3n ?1)/2, наименьшее количество гирь рав-
(3
но n, а в случае m<(3n ?1)/2 выбор гирь неоднозначен.
Уравновешенная троичная система, кроме указанного выше
свойства, обладает ещё несколькими удобными свойствами. Напри-
мер, для выполнения округления в этой системе достаточно просто
отбросить лишние цифры. В неуравновешенной системе, даже дво-
ичной, округление выполняется не так просто. Так же просто, как
и в уравновешенной системе, производится сравнение чисел по ве-
личине, но не нужно обращать при этом внимание на знак числа.
Кстати, знак числа в этой системе определяется знаком старшей
ненулевой цифры, и не нужно использовать специальный знако-
вый бит, как в двоичной системе. А таблицы сложения, умноже-
ния и деления почти так же просты, как и в двоичной системе.
Вычитание же просто сводится к сложению со сменой знака у вы-
читаемого. При записи чисел в этой системе удобно вместо ?1
писать 1. Так как таблица умножения и деления совсем просты,
приведём только таблицу сложения:
1+1=11, 1+1=00, 1+1=11,
1+0=01, 1+0=01.
Умножение, как и деление, тоже сводится к перемене знака и сло-
жению. Другим достоинством троичной системы является то, что
запись в ней имеет длину на одну треть меньше, чем в двоичной.
Видимо, благодаря им троичная уравновешенная система была
положена в основу советского компьютера <Сетунь>, построенного
в конце 1950-х годов.
Однако широкого распространения она не получила, так как
всё же элементная база компьютеров, как того времени, так и со-
временных, остаётся двоичной, а битовое представление троичной
системы даже длиннее, чем двоичной.
33
Уравновешенная система может быть рассмотрена и для любого
натурального основания, правда, при чётном основании запись в ней
перестаёт быть однозначной. Преимуществом уравновешенных
систем является то, что в них записываются и отрицательные
числа без знака минус перед записью, а также то, что таблица
умножения в этих системах в сравнении с обычными примерно
в четыре раза короче, как отметил О. Л. Коши.
16. Запишите число (1234567890)10 в уравновешенной деся-
тичной системе счисления.
Утверждение следующей задачи на первый взгляд кажется
ложным, однако присмотритесь к ней повнимательнее.
17. Докажите, что любое ненулевое целое число имеет един-
ственное знакопеременное двоичное представление 2?0 ?2?1 +...
...+(?1)k 2?k , где ?0 <?1 <...<?k.
Десятичную запись чисел можно преобразовать в запись, со-
стоящую из цифр 0, ±1, ±2, ±3, ±4, ±5, заменяя все цифры,
большие 5 на их дополнения до 10, взятые с противоположным
знаком, и делая при этом единичный перенос в следующий раз-
ряд. Сложение и умножение таких записей можно делать так же,
как и обычных, только при этом переносы в следующие разряды
могут быть отрицательными. Оценки для числа операций при этом
не улучшатся, но сами операции в некотором смысле станут проще,
так как для их выполнения достаточно помнить таблицу умноже-
ния 5?5. Например, перемножим числа 89 и 98. Запишем первое
из них как (1 ?1 ?1), а второе — (1 0 ?2). Умножаем столбиком:

1 ?1 ?1
?
1 0 ?2
?2 2 2
1 ?1 ?1
1 ?1 ?3 2 2

К счастью, не пришлось делать переносов, но это не труднее,
чем в обычном умножении (заметим, что при умножении обыч-
ных записей этих чисел переносы чуть ли не в каждом разряде).
Осталось перевести ответ в обычную запись: (1 ?1 ?3 2 2)=8722.

§ 12. ТРОИЧНАЯ СИСТЕМА И ФОКУС ЖЕРГОННА
Троичная система удачно применяется при объяснении сле-
дующего фокуса Жергонна (французского математика XIX века).
Зритель запоминает одну из 27 карт и выкладывает их в три стоп-
ки по девять карт картинками вверх (первая карта идёт в первую
стопку, вторая — во вторую, третья — в третью, четвёртая —
34
в первую и т. д.). Фокуснику сообщается, в какой из стопок за-
думанная карта, потом стопки складываются в любом из шести
возможных порядков (не перетасовывая карты внутри стопок)
и раскладываются снова в три стопки, начиная с верхней карты,
потом складываются опять и процедура повторяется в третий раз
(каждый раз сообщается, в какую из стопок легла запомненная
карта). Фокусник каждый раз замечает, куда легла стопка с запо-
мненной картой — в верх (фокусник запоминает символ 0), в сере-
дину (символ 1), или в низ колоды (символ 2), и составляет из этих
символов трёхзначное число в троичной системе счисления, ставя
первый из замеченных символов в младший разряд, следующий
символ — во второй и последний символ — в старший разряд.
К полученному числу прибавляется единица и отсчитывается
такое количество карт, начиная с верхней карты колоды — по-
следняя из отсчитанных карт и есть запомненная зрителем.
18. Объясните фокус Жергонна.
Имеется ещё один вариант фокуса Жергонна, но с другим спо-
собом раскладки карт. Колода из 27 карт раскладывается на три
стопки в следующем порядке: первая карта — в первую стопку,
вторая — во вторую, третья — в третью, четвёртая — опять в тре-
тью, пятая — во вторую, шестая — в первую и т. д. Одна из карт
запоминается зрителем и указывается стопка, в которой она ле-
жит, и всё повторяется ещё два раза. Способ угадывания тот же
самый. Можно показывать тот же фокус и с 21 картой, но тогда
надо раскладывать карты самому и стопку с задуманной картой
всегда класть в середину колоды.
19. Докажите, что в фокусе с 21 картой после трёх перекла-
дываний задуманная карта окажется точно в середине колоды,
т. е. на 11-м месте от любого края.
Приведём ещё одну задачу, при решении которой может при-
годиться троичная система.
20. Докажите, что среди чисел от 1 до 3n ?1 можно найти
2n таких, что никакое среди них не является средним арифмети-
ческим двух других.

§ 13. НЕМНОГО ОБ ИСТОРИИ
ПОЗИЦИОННЫХ СИСТЕМ СЧИСЛЕНИЯ
Ещё средневековые математики Ближнего Востока нашли простой
подход к вычислениям с дробными числами — использование
десятичных дробей. Десятичная система попала туда, видимо,
из Индии, хотя позиционные дроби, правда не десятичные,
a шестидесятеричные, были известны ещё в древнем Шумере,
а десятичные дроби, по существу, были известны в древнем Китае.
Индейцы майя, вероятно, использовали двадцатеричную систему.
35
Здесь уместно вспомнить, что запись (bn ...b0 ,b?1 ...b?k )b в пози-
ционной системе счисления с основанием b означает число, равное
bn bn +...+b1 b+b0 +b?1 b?1 +...+b?kb?k , где bn bn +...+b1b+b0 —
его целая, а b?1 b?1 +...+b?k b?k — дробная часть. В западных
странах вместо запятой, отделяющей целую часть от дробной,
используется точка.
Почему обычно используется десятичная система? Главным
образом, в силу традиции (которая, вероятно, основывается на том,
что число пальцев на обеих руках равно обычно 10; индейцы майя,
возможно, не забыли и про ноги). Как писал Паскаль, десятичная
система ничем не лучше систем с другими основаниями. С не-
которых точек зрения более удобны другие системы. Так, много
поклонников имеет двенадцатеричная система (идущая от счёта
дюжинами и гроссами — дюжинами дюжин). Возможно, к их числу
относился и Г. Дж. Уэллс (см. его роман <Когда спящий проснётся>).
Преимущество этой системы в том, что 12 имеет больше делителей,
чем 10, что несколько упрощает деление. С этой точки зрения
ещё лучше шестидесятеричная система (но таблица умножения
в этой системе вгоняет в дрожь). Остатки от былого распростране-
ния этой системы видны в картографии и астрономии, а алгоритм
перевода из этой системы в десятичную запаян в любом кальку-
ляторе для научных расчётов (речь идёт о переводе из градусной
меры в десятичную и обратно). Кстати, первая запись дробного
числа в позиционной системе в Европе была сделана в XIII веке
Фибоначчи: корень уравнения x3 +2x2 +10x=20 он нашёл в виде
1? 26 7 42 .
Есть поклонники и у восьмеричной и шестнадцатеричной
систем. Первую из них хотел вести в Швеции Карл ХII (который,
возможно, пришёл к этой идее самостоятельно), но ряд обстоя-
тельств помешали этому прогрессивному начинанию (среди них,
вероятно, и занятость короля в военных кампаниях, в частности,
в России). Преимущество этих систем в том, что легко осуще-
ствляется перевод в двоичную систему и обратно.
Основатель теории множеств уроженец Петербурга Георг Кан-
тор предложил рассматривать системы счисления со смешанными
основаниями. Запись в таких системах выглядит так:
a3 , a2 , a1 , a0 ; a?1 , a?2 , a?3 ,
b2 , b1 , b0 ; b?1 , b?2 , b?3 ,
где bi — основания, ai — цифры, 0?ai <bi , а означает эта запись
a3 b2 b1 b0 +a2 b1 b0 +a1 b0 +a0 +a?1 /b?1 +a?2 /(b?2 ·b?1 )+...
число
Частным случаем таких систем является факториальная, ко-
торая получается при bk =k+2, b?k =k+1. Используя её, можно
любое натуральное число представить в виде an n!+...+a22!+a1 1!,
где 0?ak ?k.
36
Системы со смешанными основаниями всем известны из по-
вседневной жизни. Например, <1 неделя 2 дня 3 часа 4 минуты
1, 2, 3, 4, 56; 789
56 секунд 789 миллисекунд> равно секунд.
7, 24, 60, 60; 1000

§ 14. CХЕМА ГОРНЕРА И ПЕРЕВОД ИЗ ОДНОЙ
ПОЗИЦИОННОЙ СИСТЕМЫ В ДРУГУЮ
Использованный в бинарном методе (см. § 2) приём вычисле-
ния числа по его двоичной записи является примером более обще-
го алгоритма, называемого схемой Горнера. Схема Горнера — это
алгоритм для вычисления частного и остатка от деления много-
члена p(x) на х?a. Кратко опишем, как он устроен и как связан
с переводом числа из одной системы в другую.
Пусть дан произвольный многочлен p(x)=un xn +...+u1x+u0 .
Деление этого многочлена на x?a — это представление его в виде
p(x)=(x?a)h(x)+r, h(x)=vn?1 xn?1 +...+v1 x+v0 . Непосредствен-
но можно проверить, что коэффициенты частного можно найти
по формулам vn?1 =un , vn?2 =un?1 +avn?1 , ..., v0 =u1 +av1 ,
а остаток можно вычислить по формулам
r=u0 +av0 =u0 +a(u1 +av1 )=u0 +a(u1 +a(u2 +av2 ))=...
...=u0 +a(u1 +a(...(un?1 +aun )...)=un an +...+u1a+u0 =p(a).
Этот метод вычисления и называется схемой Горнера. Слово <схе-
ма> в названии алгоритма связано с тем, что обычно его выпол-
нение оформляют следующим образом. Сначала рисуют таблицу
2?(n+2). В левой нижней клетке записывают число a, а в верх-
ней строке — коэффициенты un , un?1 , ..., u0 многочлена p(x), при
этом левую верхнюю клетку оставляют пустой:
...
un un?1 u0
...
a
...
После этого под числом un записывают un . Далее на каждом ша-
ге последнее записанное число умножают на a, к результату при-
бавляют число, стоящее справа сверху от последнего записанного
числа, и полученную сумму записывают в клетку справа от этого числа:
...
un un?1 u0
...
vn?1 =un vn?2 =un a+un?1
a p(a)
...
Число, которое после выполнения алгоритма оказывается записан-
ным в правой нижней клетке, и есть остаток p(a) деления много-
члена p(x) на x?a. Другие числа vn?1 , vn?2 , ... нижней строки
являются коэффициентами частного.
37
Например, деление многочлена p(x)=x3 ?2x+3 на x?2
по описанному алгоритму выполняется так:

?2 ?2
1 0 3 1 0 3
1) 4)
2 2 1 2 2·2?2=2

?2 ?2
1 0 3 1 0 3
2) 5)
2 1 2 1 2 2 2·2+3=7

?2 ?2
1 0 3 1 0 3
3) 6)
2 1 1·2+0=2 2 1 2 2 7

Получаем, что
x3 ?2x+3=(x?2)(x2 +2x+2)+7.
Общее число операций, используемых в этом алгоритме,
равно n плюс число ненулевых коэффициентов у многочлена p(x)
минус единица.
Схема Горнера была на самом деле применена англичани-
ном Горнером (а ещё раньше итальянцем Руффини) для вычисле-
ния коэффициентов многочлена p(x+c) и использовалась для при-
ближённого вычисления корней многочленов*). Мы укажем неко-
торые другие её применения. Одно из них — быстрый алгоритм
перевода из двоичной системы в десятичную, предложенный Соде-
ном в 1953 году.
Сначала переведём число из двоичной системы в восьмерич-
ную. Для этого разбиваем справа налево его цифры на <тройки>
(последняя <тройка> на самом деле может быть <двойкой> или да-
же одной цифрой) и переводим их в восьмеричную систему схемой
Горнера (выполняемой устно). Например,
(1111110000)2 =(1.111.110.000)2 =(1760)8 .
Выполним перевод из восьмеричной системы в десятичную.
Пусть u=(un ...u1 )8 . На k-м шаге выполняем над полученной
на предыдущем шаге записью в десятичной арифметике действия
un ...un?k?1 ?2·un ...un?k =vn+1 ...vn?k?1

и получаем запись vn+1 ...vn?k?1 .un?k?2 ...u1 (старшие разряды мо-
гут оказаться нулевыми и в реальных вычислениях участвовать
не будут). На (n?1)-м шаге получаем десятичную запись числа u.

*) Впрочем, лежащая в её основе идея была известна Ньютону и, может быть,
даже до него.
38
Например,
1.7 6 0
?
2

?1 5.6 0
30

?1 2 6.0
252
1008
Алгоритм перевода из десятичной системы в двоичную, пред-
ложенный Розье в 1962 году, почти такой же. Сначала переводим
в восьмеричную запись. Для этого, пользуясь восьмеричной ариф-
метикой, на k-м шаге выполняем над полученной на предыдущем
шаге записью действия:
un ...un?k?1 +2·un ...un?k =vn+1 ...vn?k?1
и получаем запись vn+1 ...vn?k?1 .un?k?2 ...u1 (поначалу (n+1)-е
разряды окажутся нулевыми и в реальных вычислениях участво-
вать не будут). На (n?1)-м шаге получаем восьмеричную запись
числа u. Например,
1.9 4 5
+
2
2 3.4 5
+
46
3 0 2.5
+
604
3631
Далее переводим восьмеричное n-значное число в двоичное (вы-
числяя для каждой восьмеричной цифры двумя делениями на 2
с остатком её двоичную запись).
21. Переведите из десятичной системы в двоичную систему
число 12345678987654321.
22. Переведите из двоичной системы в десятичную систему
число 10101010101010101.

§ 15. ПРИЗНАКИ ДЕЛИМОСТИ
Рассказывая о системах счисления, нельзя обойти вниманием
признаки делимости. Напомним широко известные признаки де-
лимости в случае использования десятичной системы счисления.
Простейший из них следующий: остаток от деления некоторого
39
числа на 2n равен остатку от деления на 2n числа, записанного
последними его n цифрами. Аналогичный признак справедлив
для 5n и любого числа вида 2k 5m , где max(m, k)=n. Чуть более
сложен в применении признак делимости на 9: сумма цифр данно-
го числа имеет тот же остаток от деления на 9, что и само число.
Такой же признак справедлив и для делимости на 3.
Подобный же признак можно предложить и для делимости на чи-
сло 9...9, состоящее из n девяток: надо разбить испытуемое число
на n-разрядные блоки, начиная с младших разрядов, и всех их сло-
жить (блок, образованный старшими разрядами, может быть короче);
у полученного числа будет тот же остаток от деления, что и у ис-
ходного. Так как 99 делится на 11, то таким способом можно най-
ти и остаток от деления на 11. Учитывая, что 999 делится на 111
и, следовательно, на 37, получаем признаки делимости на эти числа.
Но есть более эффективный признак делимости на 11: надо
складывать цифры числа, начиная с младших, чередуя знаки (пер-
вая цифра берётся со знаком плюс) — полученное число имеет
тот же остаток от деления на 11, что и исходное.
Аналогичный признак делимости имеется и для числа 10...01,
запись которого, кроме двух единиц, содержит n нулей. Испытуе-
мое число разбивается на (n+1)-разрядные блоки, начиная с млад-
ших разрядов (блок, образованный старшими разрядами, может
быть короче), и все они складываются с чередующимися знака-
ми (первое число берётся со знаком плюс). Полученный результат
имеет тот же остаток от деления, что и испытуемое число. По-
скольку 1001=11·7·13, мы попутно получаем таким путём при-
знаки делимости на 7, 13, 91, 77, 143.
23. Докажите сформулированные признаки делимости.
При применении рассмотренных признаков к большим числам
получаются меньшие, но всё же достаточно большие числа, имею-
щие те же остатки от деления, что и исходные. К ним нужно при-
менить ещё раз тот же признак делимости и т. д. Часто эффектив-
ность этих признаков при применении к большим числам всё же
ненамного выше простого деления.
Есть, однако, случаи, когда только применение признаков де-
лимости позволяет найти остаток, так как непосредственное деле-
ние практически невозможно ввиду колоссальной вычислительной
сложности.
24. Найдите остаток от деления 4444444444 на 99.
Число 4444444444 состоит более чем из 200 000 цифр, и его
прямое вычисление требует порядка миллиарда операций. Правда,
кроме признаков делимости на 9 и 11, здесь надо применить и не-
которые соображения, связанные с делимостью степеней. Другой
способ решения этой задачи — применение калькулятора и бинар-
ного метода возведения в степень.
40
Полезны признаки делимости и при разгадывании ребусов,
подобных следующему.
25. Замените звёздочки на пропущенные цифры в примере
792
? ????
70??34?
Признаки делимости могут помочь в нахождении ошибки при вы-
полнении умножения больших чисел. Простейший из способов
контроля — проверка по модулю 9. Этому способу обучали ещё
в средневековых университетах: у обоих множителей находятся
остатки от деления на 9, потом исходные числа перемножаются и у
результата опять находится остаток от деления на 9, который срав-
нивается с остатком от деления на 9 произведения исходных чисел,
подлежащего проверке. Если остатки разные, то произошла ошиб-
ка. Если известно, что ошибка только в одном разряде, то мож-
но точно указать величину ошибки, но не её положение. В случае
совпадения результатов остаётся возможность одной ошибки типа
замены 0 на 9 или наоборот, а также нескольких ошибок. В этом
случае можно провести ещё аналогичную проверку по модулю 11,
которая или подтвердит существование ошибки указанного вида,
или установит наличие нескольких ошибок (или их отсутствие).

§ 16. АРИФМЕТИЧЕСКИЕ КОДЫ
Можно установить точно положение ошибки и даже исправить её,
в предположении, что она только одна. Для этого надо применить так
называемые арифметические коды. Приведём их простейший пример.
Допустим, что при перемножении десятичных чисел получи-
лось 15-разрядное число с ошибкой в одном разряде. Для нахожде-
ния величины ошибки применим проверку по модулю 9 и найдём,
что она по модулю 9 равна a. Если ошибка произошла в i-м раз-
ряде*), то величина ошибки в произведении равна a·10i?1 или
(a?9)·10i?1 , а если a=0, то или ошибки не было, или она рав-
на ±9·10i?1 . Применим проверку по модулю 31. После неё станет
известно значение ошибки b по модулю 31. Если остаток по моду-
лю 31 равен нулю, то ошибки не было.
Пусть он не равен нулю. Выпишем остатки от деления чисел
10, ..., 1015 на 31. Они равны 10, 7, 8, 18, 25, 2, 20, 14, 16,
5, 19, 4, 9, 28, 1. Заметим, что невозможно равенство по моду-
лю 31 чисел a·10i и (a?9)·10j , так как тогда при некоторых a=
=1, 2, 3, 4 и i=0, 1, ..., 14 были бы равны по модулю 31 числа
a·10i и a?9, а невозможность этого проверяется непосредственно
*) Разряды нумеруются с конца десятичной записи. Например, 3-й разряд — это
разряд сотен.
41
с помощью вычисленной выше последовательности остатков. Точ-
но также проверяется невозможность совпадения по модулю 31 чи-
сел 9·10i и (?9)·10j . Вычисляя остатки по модулю 31 у всех чисел
a·10i и (a?9)·10i при i=1, ..., 15 и сравнивая их с найденным
ранее остатком, находим значение i и точную величину ошибки a
или a?9. Аналогично поступаем в случае ошибки ±9·10i .
Приведённый пример арифметического кода иллюстрирует прин-
ципиальную возможность их построения, на первый взгляд кажущую-
ся парадоксальной. Прикладного значения при ручных вычислениях
он не имеет хотя бы потому, что, как можно проверить, проще ещё
раз перемножить эти числа, чем выполнять указанные выше операции.
Но такие алгоритмы применяют для контроля правильности
работы арифметических устройств, и этот контроль осуществляет
специальный блок в таком устройстве. В рассматриваемом случае
сложность устройства со встроенным арифметическим кодом рас-
смотренного вида увеличивается не более чем в два раза. Если
рассмотреть подобные коды с достаточно большой длиной (p?1)/2
и проверочными множителями 9 и p, где p — простое число вида
280k+31 такое, что 10(p?1)/2 при делении на p даёт остаток 1,
а 10k при k<(p?1)/2 при делении на p дают остатки, отличные
от 1 (в рассмотренном случае p равнялось 31, а k — нулю), то
сложность исправления ошибки будет мала при больших p в срав-
нении со сложностью умножения (p?1)/2-разрядных чисел.
На самом деле, на практике использовались для повышения
надёжности арифметических устройств не десятичные, как рассмо-
тренный, а двоичные коды, но они устроены подобным же образом.
26. Примените указанный арифметический код для расшиф-
ровки ребуса
9
? ??
31
??????
425021067?
Можно с помощью этого кода расшифровать и ребус, в котором
ровно в одном разряде результата имеется ошибка, но неизвестно
в каком. Тот же код можно использовать для демонстрации ариф-
метического фокуса: вы предлагаете вашему другу задумать два
не слишком больших числа, перемножить их и результат умно-
жить на якобы случайное число 279, а потом сообщить вам ответ
с одной ошибкой в каком-нибудь разряде. Используя указанный код
(если перед этим предварительно подготовить все нужные таблицы
и немного потренироваться), вы быстро укажете эту ошибку. За-
метьте, что полный перебор вариантов требует в случае 15-разряд-
ного ответа 134-кратного деления предполагаемого ответа на 279.
42
§ 17. МИНИМАЛЬНЫЕ ФОРМЫ ДВОИЧНОЙ ЗАПИСИ С ЦИФРАМИ 0 И ±1
И ПЕРВАЯ ПОПЫТКА УМЕНЬШИТЬ СЛОЖНОСТЬ УМНОЖЕНИЯ
В позиционных системах счисления с заданным основанием b
можно, кроме обычных цифр, использовать и отрицательные
цифры ?1, ?2, ..., ?(b?1). Правда, это приводит к неодно-
значности в записи чисел. Зато таким образом можно уменьшить
количество ненулевых цифр в записи и их величину. Далее в этом
параграфе мы будем рассматривать случай b=2, т. е. записи
чисел в двоичной системе с цифрами ?1, 0, 1.
27. Приведите пример числа, для которого существуют
по крайней мере две записи описанного вида с минимальным
возможным числом ненулевых цифр.
Назовём двоичную запись с использованием отрицательных
единиц минимальной формой, если в ней нет соседних ненулевых
цифр. Для этого определения не очевидна ни единственность ми-
нимальной формы, ни минимальность длины минимальной формы.
Однако и то, и другое верно, т. е. минимальная форма определе-
на однозачно и содержит наименьшее количество ненулевых цифр
среди всех возможных форм двоичной записи числа с использова-
нием отрицательных единиц.
Докажем это. Пусть A=an ...a0 — произвольная двоичная
запись числа a, т. е.
a=2n an +...+2a1 +a0 ,
где ai =0, ±1. Далее вместо ?1 будем писать 1. Обозначим че-
рез ?(A) количество ненулевых цифр в этой записи и через µ(A) —
количество пар соседних ненулевых цифр. Заметим, что
2k +2k+1 +...+2m?1 =2m ?2k ,
поэтому, выполняя в записи A следующие преобразования:

1? ??>0?,
2? 0??...? >?0...0? (n?3),
| {z } | {z }
n n?1

3? 0?(?0)...(?0)??>?0(0?)...(0?) (n?1),
| {z } | {z }
n n+1

4? 00(?0)...(?0)??>0?(0?)...(0?) (n?0),
| {z } | {z }
n n+1

5? (n?0)
?0(?0)...(?0)??>(0?)...(0?)
| {z } | {z }
n n+2
43
(где для ?=1, 1, соответственно, ?=1, 1), мы не меняем записы-
ваемого числа, не увеличиваем величин ?(A) и µ(A) и всегда умень-
шаем их сумму:

Операция µ ?

1? или µ?2
µ?1 ??1

2? µ+2?n или µ+1?n (n?3) ?+2?n

3? или µ?2
µ?1 ??1

4? µ?1 ?

5? или µ?2
µ?1 ??1


Будем выполнять эти преобразования, пока это возможно. Так
как величина ?(A)+µ(A) не может неограниченно уменьшаться, то
в конце концов получим запись числа a, в которой нельзя будет
выполнить ни одну из этих операций.
28. Докажите, что если в записи невозможно выполнить ни одну
из указанных операций, то в этой записи нигде не будет встре-
чаться соседних ненулевых цифр.
Докажем единственность минимальной формы для данного чи-
сла a. Допустим, что есть две разные минимальные формы A и B.
Тогда они заканчиваются одинаковым числом нулей в младших
разрядах, иначе, если бы одна заканчивалась k нулями, а другая
m>k нулями, то наше число делилось бы на 2m , а с другой сто-
роны, делилось бы только на 2k , но не на 2k+1 , что невозможно.
Аналогично получаем, что их последние ненулевые цифры равны,
так как в противном случае наше число имело бы при делении
на 2m+2 (где m — число нулей в конце) в остатке разные числа 2m
и 2m+2 ?2m (так как в конце одной записи стоят цифры 010...0,
а в конце другой — цифры 010...0 ввиду отсутствия пар ненуле-
вых цифр в обеих записях). Отбрасывая равные последние цифры
от обеих записей, получаем более короткие различные записи для
равных чисел. Повторяя для этих записей проведённое рассужде-
ние, получим, наконец, что число ±1 или 0 имеет две разные за-
писи, а это невозможно.
Наконец, докажем, что в минимальной форме наименьшее ко-
личество ненулевых цифр среди всех записей с отрицательными
единицами. Действительно, из любой записи можно с помощью
рассмотренных преобразований получить построенную запись (как
только что доказано, всегда одну и ту же). Но при выполнении
этих преобразований величина ?(a) не возрастала, значит, постро-
енная запись имеет значение этой величины, равное наименьшему
возможному.
44
Преобразование обычной двоичной записи числа a к мини-
мальной форме более удобно проводить следующим образом: вычи-
слить обычную двоичную запись ?n+1 ...?1 числа 3a и вычислить
обычные разности ?i?1 =?i ??i , где i=2, ..., n+1, ?i — цифры за-
писи числа a, а ?n =?n+1 =0, тогда ?n ...?1 — минимальная форма
числа a.
Минимальная форма максимум на единицу длиннее обычной
записи, но содержит не более n/2 ненулевых цифр. При смене
знака у числа меняются знаки у всех цифр его минимальной
формы. Действительно, при замене знаков всех цифр минимальной
формы числа a получается запись числа ?a, в которой нет двух
ненулевых цифр подряд. А это по определению и есть минимальная
запись числа ?a.
Одно из возможных применений указанной минимальной фор-
мы — уменьшение числа арифметических операций для возведения
в степень. Мы уже приводили конкретный пример такого примене-
ния, а сейчас сформулируем общую теорему. Далее для краткости
вместо словосочетания <число арифметических операций алгоритма>
будем писать <сложность алгоритма>.
Обозначим число ненулевых цифр в записи числа n в виде мини-
мальной формы через ?(n), а уменьшенную на единицу длину этой
записи — через ?(n). Мы используем те же обозначения, что и в обыч-
ном бинарном методе (см. § 2), но заметим, что новая функция ?(n)
может быть на единицу больше старой, зато новая функция ?(n) не мо-
жет быть больше старой, а часто меньше её, иногда почти в два раза.
Теорема. При использовании калькулятора с одной ячейкой
памяти сложность вычисления xn не превосходит
?(n)+?(n)?1.
Д о к а з а т е л ь с т в о. Используя полученную минимальную
форму, запишем n в виде суммы 2?(n) ??(n) +...+2?1 +?0 , ?i =0, ±1,
содержащей ?(n) ненулевых слагаемых. Далее, как и в обычном
бинарном методе возведения в степень, используем аналог схемы
Горнера, а цифрам ?1 сопоставляем операцию деления на основа-
ние степени. Полученное обобщение бинарного метода использует
не более ?(n) возведений в квадрат и ?(n)?1 умножений и деле-
ний. Теорема доказана.
Аналогично обычному бинарному методу можно доказать соот-
ношения ?(2n)+?(2n)=?(n)+?(n)+1, ?(n±1)??(n)+1. Из послед-
него неравенства следует, что ?(n±1)+?(n±1)??(n)+?(n)+1. Дей-
ствительно, случай n±1=n+1 рассматривается аналогично обычно-
му бинарному методу, а в случае n±1=n?1, очевидно, ?(n?1)?
??(n) и из неравенства ?(n?1)??(n)+1 следует нужная оценка.
Используя доказанное неравенство, можно аналогично обычному
бинарному методу в случае, когда содержимое ячейки памяти
45
никогда не обновляется, получить аналогичную нижнюю оценку
сложности возведения в степень ?(n)+?(n)?1. Читателю предоста-
вляется возможность самому убедится в этом.
Недостатком двоичной системы при её ручном использовании
является то, что из-за увеличения длины записи по сравнению с де-
сятичной системой соответственно возрастает и сложность умно-
жения. Использование минимальной формы позволяет уменьшить
сложность ручного умножения двоичных чисел. Опишем алгоритм
умножения, предложенный в начале 1950-х годов американским
математиком Бутом.
Для этого данные n-разрядные и m-разрядные двоичные числа
преобразуем в их минимальные формы и заметим, что эти формы
содержат не более n+1 и m+1 разрядов, причём из них не более
a=n/2+1 и b=m/2+1 ненулевых разрядов соответственно.
Сложность преобразования не превосходит 3n+3m?4. Умножая
минимальные формы с помощью школьного алгоритма, замечаем,
что число нетривиальных умножений не превосходит ab, так как
ненулевых строк будет не более b и в каждой из них нетривиальных
умножений не более a. Отметим, что каждое нетривиальное
умножение, по-существу, не сложнее нетривиального умножения
в обычной двоичной системе, и будем считать, что оно выполняется
с единичной сложностью, так же как и нетривиальное сложение
(операция нетривиальна, если оба операнда не нули). Заметим
также, что число нетривиальных сложений не превосходит (b?1)?
?(a+n?1), так как всего сложений различных строк требуется
не более b?1, а каждое из них состоит из не более чем n пе-
реносов (переносы могут быть как 1, так и ?1) и не более чем
a?1 нетривиальных сложений (в складываемых строчках имеется
не более a?1 стоящих друг под другом ненулевых цифр). Поэтому
сложность умножения не превосходит (b?1)(a+n?1)+ab?
?mn+(m+n)/2+1. Полученный результат содержит не более
n+m+2 разрядов (так как он получается при сложении m+1
не более чем (n+1)-разрядных чисел с соответствующими сдвига-
ми). Его можно преобразовать к обычной двоичной записи, сделав
не более n+m+2 операции (заменяем блоки соседних цифр вида
10...01 на соответствующие блоки вида 01...11, блоки вида 11 —
на блоки 01, блоки без отрицательных цифр оставляем без измене-
ния). Значит, полная сложность операции умножения не превосхо-
дит mn+(m+n)/2+1+3n+3m?4+n+m+2?mn+3,5(m+n).

§ 18. БЫСТРОE УМНОЖЕНИЕ МНОГОЧЛЕНОВ
Мало кто знает, что относительно недавно были открыты
гораздо более быстрые алгоритмы умножения и деления много-
значных чисел и многочленов, чем <школьные>. Первый такой
46
алгоритм придумал в 1962 году А. А. Карацуба, отвечая на вопрос
А. Н. Колмогорова. Впоследствии А. Л. Тоомом, Ф. Штрассеном
и А. Шенхаге были построены ещё более быстрые алгоритмы.
Идею метода Карацубы можно пояснить на следующем приме-
ре. Пусть перемножаются восьмизначные числа U=u1 ...u8 и V =
=v1 ...v8 . Представим их как двузначные числа в системе счи-
сления с основанием 104 : U=U1 U2 , V =V1 V2 , где U1 =u1 u2 u3 u4 ,
U2 =u5 u6 u7 u8 , V1 =v1 v2 v3 v4 , V2 =v5 v6 v7 v8 . Тогда их произведение
можно представить в следующем виде:
UV =108 U1 V1 +104 ((U1 ?U2 )(V2 ?V1 )+U1 V1 +U2 V2 )+U2V2 .
Эта формула сводит умножение восьмизначных чисел к трём
операциям умножения и шести операциям сложения-вычитания
четырёхзначных чисел (с учётом переносов в следующие разряды).
Обычный способ требует четырёх умножений и трёх сложений-
вычитаний, но так как три раза сложить четырёхзначные числа
можно быстрее, чем один раз перемножить, то метод Карацубы
уже восьмизначные числа перемножает быстрее. В общем случае он
требует для перемножения n-значных чисел по порядку не больше
nlog2 3 <n1,585 операций над цифрами.
Далее мы поговорим о сложности умножения более подробно.
Обозначим через M(n) наименьшее количество операций сло-
жения, вычитания и умножения (выполняемых над коэффициен-
тами многочленов и промежуточными числовыми результатами),
требующихся для перемножения двух многочленов степеней, мень-
ших n. Тогда справедливо неравенство
M(n)?2M( n/2 )+M( n/2 )+4 n/2 +2n?4 *). (*)
Действительно, применим равенство
(f1 x n/2 +f0 )(g1 x n/2 +g0 )=
=f1 g1 x2 n/2 +((f1 +f0 )(g1 +g0 )?f1 g1 ?f0 g0 )x n/2 +f0 g0 ,
где степени многочленов f1 и g1 меньше n/2 , а степени многочле-
нов f0 и g0 меньше n/2 , и заметим, что для вычисления произве-
дений f1 g1 , f0 g0 требуется не более M( n/2 )+M( n/2 ) операций,
для вычисления сумм f1 +f0 , g1 +g0 , f1 g1 +f0 g0 нужно не более
2 n/2 +2 n/2 ?1 операций (так как число операций равно наи-
меньшему из количеств ненулевых коэффициентов у складывае-
мых многочленов), для вычисления произведения (f1 +f0 )(g1 +g0 )
используется не более M( n/2 ) операций, для вычисления разно-
сти (f1 +f0 )(g1 +g0 )?f1 g1 ?f0 g0 достаточно n?1 операций, так как

*) Через x обозначается наибольшее целое число, не большее x (<округление
вниз>), а через x — наименьшее целое число, не меньшее x (<округление вверх>).
47
(f1 +f0 )(g1 +g0 )?f1 g1 ?f0 g0 =f1 g0 +f0 g1 , значит, степень этого мно-
гочлена равна n/2 + n/2 ?2=n?2, сложение многочленов f0 g0
и f1 g1 x2 n/2 выполняется <бесплатно>, так как они не имеют по-
добных членов, причём в их сумме отсутствует член вида x2 n/2 ?1 ,
поэтому для сложения многочленов f0 g0 +f1 g1 x2 n/2 и (f1 g0 +f0 g1 )?
?x n/2 достаточно n?2 операций. B итоге требуется дополнительно
4 n/2 +2n?4 операций.
Оценку сложности метода Карацубы можно представить в сле-
дующем виде. Если n кратно 2k , то справедливо неравенство
##A A
k M n ! + 8n ?2! ?8n+2,
! !
M(n)?3   k ! !
2 
2k
а при любом n — неравенство
35 log2 3
M(n)< n .
3
Действительно, пусть 2k m=n. Тогда неравенство
##A A
k M n ! + 8n ?2! ?8n+2,
! !
! !
M(n)?3   k  
k
2 2
доказывается индукцией по k. База (k=1) — это неравенство (*).
Шаг индукции обосновывается тем же неравенством.
Bыберем k так, чтобы 2k <n?2k+1 . Тогда, если 3·2k?1 <n, то
# Alog 3
k+1 )<3k?1 (M(4)+30)?3k?1 ·55<55 n ! 2 < 35 nlog2 3 .
!
! 
M(n)?M(2
3 3
Если же n?3·2k?1 , то
35 log2 3
M(n)?M(3·2k?1 )<3k?1 (M(3)+22)?3k?1 ·35? n .
3
29. Проверьте, что обычный способ умножения многочленов
даёт оценку M(n)?n2 +(n?1)2 .

§ 19. БЫСТРОE УМНОЖЕНИЕ ЧИСЕЛ
Перейдём теперь к умножению чисел.
Обозначим через M(n) наименьшее количество операций сло-
жения, вычитания и умножения, выполняемых над числами, мень-
шими a, требующихcя для перемножения двух n-значных чисел,
записанных в позиционной системе счисления с основанием a.
Метод умножения почти такой же, как и для многочленов.
Для примера укажем, как сделать необходимые изменения в рас-
суждениях из предыдущего параграфа.
Справедливы неравенства
M(2n)?3M(n)+19n, M(2n+1)?2M(n+1)+M(n)+17n+10.
48
Действительно, применим тождество
(f1 b n/2 +f0 )(g1 b n/2 +g0 )=
=f1 g1 b2 n/2 +(f1 g1 +f0 g0 ?(f1 ?f0 )(g1 ?g0 ))b n/2 +f0 g0 ,
где числа f1 и g1 — n/2 -разрядные, а числа f0 и g0 — n/2 -раз-
рядные и заметим, что для вычисления произведений f1 g1 и f0 g0
требуется M( n/2 )+M( n/2 ) операций, для вычисления разностей
f0 ?f1 , g0 ?g1 и суммы f1 g1 +f0 g0 требуется не более
n(1+ n/2 ? n/2 )+2( n/2 + n/2 ?1)+2( n/2 + n/2 )?1=
=4n?3+n(1+ n/2 ? n/2 )
операций, так как числа f1 g1 и f0 g0 имеют не более чем 2 n/2
и 2 n/2 разрядов соответственно, а в случае чётного n нужно ещё
2 n/2 =n операций для предварительного сравнения чисел (чтобы
не вычитать из меньшего большее). Заметим далее, что для вычисле-
ния произведения (f1 ?f0 )(g1 ?g0 ) требуется не более M( n/2 )+1
операций (одна операция для вычисления знака у произведения),
для вычисления разности f1 g1 +f0 g0 ?(f1 ?f0 )(g1 ?g0 )=f1 g0 +f0 g1
требуется не более 2 n/2 +1+2 n/2 ?1=4 n/2 операций, сложе-
ние чисел f0 g0 и f1 g1 b2 n/2 осуществляется <бесплатно> (записи
этих чисел просто объединяются в одну запись), а для сложе-
ния чисел f1 g1 b2 n/2 +f0 g0 и (f1 g0 +f0 g1 )b n/2 требуется не более
2n? n/2 +n+1?1=2n+ n/2 операций (так как число f1 g0 +f0 g1
имеет не более n+1 разрядов, а младшие n/2 разрядов числа
f0 g0 не участвуют в операциях). B итоге требуется дополнительно
4n?3+n(1+ n/2 ? n/2 )+1+4 n/2 +2n+ n/2 =7n+3 n/2 +
+n(1+ n/2 ? n/2 )?2 операций.
Остальные детали предоставляем додумать читателю.
Обозначим через Q(n) сложность возведения n-разрядного чи-
сла в квадрат и такое же обозначение будем использовать для
сложности возведения в квадрат многочлена степени n?1.
(a+b)2 ?(a?b)2
30. Используя тождество ab= , докажите для
4
случая операций с числами неравенство M(n)?2Q(n)+13n+
+O(1), а для случая операций с многочленами — неравенство
M(n)?2Q(n)+6n+4.

ПРИЛОЖЕНИЕ
ЧТО МОЖНО ВЫЧИСЛИТЬ НА СЧЁТАХ?
Воспользовавшись такой простейшей моделью вычислений, как
абак, в России называвшийся просто счётами, можно построить всё
здание современной теории алгоритмов. Разумеется, это понятие
надо немного идеализировать и придать ему, например, такой вид.
49
Пусть нам нужно вычислить данную числовую функцию
f(x1 , ..., xn ). Представим себе, что у нас есть счёты, содержащие n
<входных> спиц, на i-й из которых имеется в начальный момент
xi костяшек, одну <выходную> (первоначально пустую) спицу,
на которой будет получен результат, и некоторое количество
(первоначально пустых) <рабочих> спиц. Каждая спица состоит
на самом деле из двух половин, и пока речь шла только о левых
половинах. В правой половине каждой спицы помещается потен-
циально не ограниченный запас костяшек, и по нашему желанию
мы можем сделать в любой момент одну из двух операций: либо
передвинуть самую левую костяшку из правой половины спицы
в <рабочую> левую половину, увеличив тем самым <записанное>
в ней число на единицу, либо передвинуть крайнюю правую ко-
стяшку из <рабочей> левой половины спицы в правую <запасную>
половину, уменьшив тем самым <записанное> в левой половине
число на единицу.
Если перейти к терминологии языков программирования,
то мы здесь описали систему регистров машины, и две опера-
ции, применимые к ним — прибавление единицы и вычитание
единицы.
Сама программа вычисления на счётах (или на соответству-
ющей идеализированной машине с неограниченными регистрами)
представляет из себя диаграмму, состоящую из кружочков, в ко-
торых написаны номера спиц (регистров), после которых стоят
знаки плюс или минус, указывающие на операции, которые мы
выполняем на этих спицах (регистрах). Из кружочков со знаком
плюс выходит одна стрелка, ведущая в какой-то другой кружочек
(она указывает какую следующую операцию делать). Из кружоч-
ков со знаком минус выходит две такие стрелки. Одна из них по-
мечается специальным значком ? и используется только тогда, ко-
гда на <рабочей> половине спицы не осталось костяшек (в регистре
записан ноль). Тогда операция вычитания единицы, естественно,
не может быть выполнена, и просто делается переход к новой
вершине диаграммы по указанной стрелке. Если же на спице оста-
вались костяшки (регистр не равен 0), то операция вычитания
единицы выполняется и тоже делается переход к новой вершине
диаграммы, но, естественно, по второй стрелке. Отметим ещё,
что совсем не обязательно, чтобы разные вершины диаграммы вы-
полняли операции с разными спицами.
Теперь, чтобы такая диаграмма могла определить работающую
программу, осталось выделить в ней две стрелки — начало и конец
работы программы. Первая из них выделяется среди других стрелок
тем, что имеет конец в одной из вершин диаграммы, но не имеет
начала в вершинах диаграммы, а начинается в специальном кружке
со словом <НАЧАЛО>, а вторая, наоборот, начинается в одной
50
из вершин, но не ведёт ни в одну из вершин диаграммы, а ведёт
в кружок со словом <КОНЕЦ>.
Программа начинает работать со слова <НАЧАЛО> и заканчи-
вает, когда придёт в слово <КОНЕЦ> (но может и <зациклиться>
и никогда не закончить работу). Результатом работы программы
можно считать число, записанное на <выходном> регистре. Если
это число всегда совпадает со значением рассматриваемой функции
f(x1 , ..., xn ), в случае, если она определена при заданных значениях
переменных, и если программа всегда <зацикливается> в случае,
если эта функция не определена при заданных значениях перемен-
ных, то говорят, что программа (вычисления на счётах!) правильно
вычисляет заданную функцию.
С целью сокращения диаграмм у сложных программ можно
вместо некоторых вершин, имеющих одну выходную стрелку, ис-
пользовать не оператор прибавления единицы, а кружок с сим-
волическим обозначением какой угодно программы (называемой
в этом случае, естественно, подпрограммой).
Работу любой такой программы можно промоделировать и на ма-
шине Тьюринга, если изображать состояние абака в каждый момент
времени на ленте машины в виде массивов палочек, разделённых
пробелами. В возможность обратного моделирования поверить труд-
нее, тем не менее справедливо следующее утверждение, приводимое
без доказательства.
Класс числовых функций, вычислимых на абаке, совпадает
с классом функций, вычислимых по Тьюрингу.
А как известно, на машине Тьюринга можно промоделировать
любые компьютерные вычисления. Значит, и на счётах тоже можно!
31. Приведите пример <зацикливающейся> программы для абака.
32. Приведите пример программы, складывающей содержимое
двух регистров и помещающей результат во второй регистр одно-
временно с обнулением первого регистра.
33. Приведите пример программы, складывающей содержи-
мое двух регистров и помещающей результат во второй регистр,
но не изменяющей первый регистр (используйте вспомогатель-
ный <рабочий> регистр).
34. Приведите пример программы, перемножающей содержи-
мое двух регистров и помещающей результат в третий регистр
одновременно с обнулением первого регистра. (Используйте пре-
дыдущую программу в качестве подпрограммы.)
35. Приведите пример программы, перемножающей содержи-
мое двух регистров и помещающей результат во второй регистр
без изменения первого регистра. (Используйте вспомогательный
регистр и предыдущую программу в качестве подпрограммы.)
36. Покажите, как возводить в степень на счётах. (Используй-
те предыдущую программу в качестве подпрограммы.)
51
ЛИТЕРАТУРА
Литература по теме книжки огромна, и приводимый далее спи-
сок не претендует на полноту. В него включены некоторые источ-
ники, использованные автором при подготовки книжки, а также
расширяющие и дополняющие её. Они выбраны из числа наиболее
доступных, в том числе и по времени издания.
[1] А л ф у т о в а Н. Б., У с т и н о в А. В. Алгебра и теория чисел:
Сборник задач. — М.: МЦНМО, 2002.
[2] А н д р е е в а Е., Ф а л и н а И. Системы счисления и компью-
терные арифметика. — М.: Лаборатория базовых знаний, 1999.
[3] Б у л о с Д., Д ж е ф р и Р. Вычислимость и логика. — М.:
Мир, 1994.
[4] В а с и л ь е в Н. Б., Е г о р о в А. А. Задачи всесоюзных ма-
тематических олимпиад. — М.: Наука, 1988. — (Библиотека
математического кружка. Вып. 18).
[5] В о р о б ь ё в Н. Н. Признаки делимости. — М.: Наука,
1988. — (Популярные лекции по математике. Вып. 39).
[6] Г а л ь п е р и н Г. А., Т о л п ы г о А. К. Московские математи-
ческие олимпиады. — М.: Просвещение, 1986.
[7] Г а р д н е р М. Математические головоломки и развлечения /
Пер. с англ. Ю. А. Данилова / Под ред. Я. А. Смородинско-
го. — М.: Мир, 1999. — (Математическая мозаика. Вып. 1).
[8] Г а р д н е р М. Математические досуги / Пер. с англ. Ю. А. Да-
нилова / Под ред. Я. А. Смородинского. — М.: Мир, 2000. —
(Математическая мозаика. Вып. 2).
[9] Г а р д н е р М. Математические новеллы / Пер. с англ.
Ю. А. Данилова / Под ред. Я. А. Смородинского. — М.: Мир,
2000. — (Математическая мозаика. Вып. 3).
[10] Г а ш к о в С. Б., Ч у б а р и к о в В. Н. Арифметика, алго-
ритмы, сложность вычислений. — М.: Высшая школа, 2000.
[11] Д а д а е в Ю. Г. Теория арифметических кодов. — М.: Радио
и связь, 1981.
[12] Е л е н ь с к и й Щ. По следам Пифагора. — М.: Детгиз, 1961.
[13] К н у т Д. Искусство программирования: Пер. с англ. —
Т. 2. — М.: Вильямс, 2000.
[14] П е т ц о л ь д Ч. Код. — М.: Русская редакция Майкрософт
Пресс, 2001.
[15] С е в и д ж Д. Сложность вычислений. — М.: Факториал, 1998.
[16] С т а х о в А. П. Коды золотой пропорции. — М.: Радио
о связь, 1984.
[17] Ф о м и н С. В. Системы счисления. — М.: Наука, 1980. —
(Популярные лекции по математике. Вып. 40).
[18] Ш т е й н г а у з Г. Математический калейдоскоп: Пер.
с польск. — М.: Наука, 1981. — (Библиотечка <Квант>. Вып. 8).
52
БИБЛИОТЕКА <МАТЕМАТИЧЕСКОЕ ПРОСВЕЩЕНИЕ>

ВЫПУСК 1 ВЫПУСК 15
В. М. Т и х о м и р о в. Великие В. М. Т и х о м и р о в. Диф-
математики прошлого и их ве- ференциальное исчисление (те-
ликие теоремы. ория и приложения).
ВЫПУСК 16
ВЫПУСК 2
В. А. С к в о р ц о в. Примеры
А. А. Б о л и б р у х. Проблемы
метрических пространств.
Гильберта (100 лет спустя).
ВЫПУСК 17
ВЫПУСК 3
В. Г. С у р д и н. Пятая сила.
Д. В. А н о с о в. Взгляд на ма-
тематику и нечто из неё. ВЫПУСК 18
А. В. Ж у к о в. О числе ?.
ВЫПУСК 4
ВЫПУСК 19
В. В. П р а с о л о в. Точки Брока-
А. Г. М я к и ш е в. Элементы
ра и изогональное сопряжение.
геометрии треугольника.
ВЫПУСК 5
ВЫПУСК 20
Н. П. Д о л б и л и н. Жемчужины
И. В. Я щ е н к о. Парадоксы
теории многогранников.
теории множеств.
ВЫПУСК 6 ВЫПУСК 21
А. Б. С о с и н с к и й. Мыльные И. Х. С а б и т о в. Объёмы
плёнки и случайные блуждания. многогранников.
ВЫПУСК 7 ВЫПУСК 22
И. М. П а р а м о н о в а. Сим- А. Л. С е м ё н о в. Математика
метрия в математике. текстов.
ВЫПУСК 8 ВЫПУСК 23
В. В. Острик, М. А. Цфасман. М. А. Ш у б и н. Математиче-
Алгебраическая геометрия ский анализ для решения фи-
и теория чисел: рациональные зических задач.
и эллиптические кривые. ВЫПУСК 24
А. И. Д ь я ч е н к о. Магнитные
ВЫПУСК 9
полюса Земли.
Б. П. Г е й д м а н. Площади мно-
гоугольников. ВЫПУСК 25
С. М. Г у с е й н - З а д е. Разбор-
ВЫПУСК 10
чивая невеста.
А.Б.Сосинский. Узлы и косы.
ВЫПУСК 26
ВЫПУСК 11 К. П. К о х а с ь. Ладейные
Э. Б. В и н б е р г. Симметрия числа и многочлены.
многочленов.
ВЫПУСК 27
ВЫПУСК 12 С. Г. С м и р н о в. Прогулки
В. Г. С у р д и н. Динамика по замкнутым поверхностям.
звёздных систем.
ВЫПУСК 28
А. М. Р а й г о р о д с к и й. Хро-
ВЫПУСК 13
В. О. Б у г а е н к о. Уравнения матические числа.
Пелля. ВЫПУСК 29
С. Б. Г а ш к о в. Системы
ВЫПУСК 14
В. И. А р н о л ь д. Цепные дроби. счисления и их применение.

<<

стр. 2
(всего 2)

СОДЕРЖАНИЕ