LINEBURG


<< Пред. стр.

страница 5
(всего 7)

ОГЛАВЛЕНИЕ

След. стр. >>

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. Приведите пример числа, для которого существуют
по крайней мере две записи описанного вида с минимальным
возможным числом ненулевых цифр.
Назовём двоичную запись с использованием отрицательных
единиц минимальной формой, если в ней нет соседних ненулевых

<< Пред. стр.

страница 5
(всего 7)

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign