Шрифт:
2. Чему равна сумма всех элементов в таблице умножения? Проверьте для b = 10.
§ 4. Некоторые задачи, связанные с системами счисления
Обсудим несколько задач, связанных с системами счисления, которые имеют отношение к выбору оснований систем счисления, удобных для машинного счета. Предположим, что мы имеем дело с обычным настольным арифмометром, который работает при помощи сцепленных числовых колес, каждое из которых имеет 10 цифр: 0, 1, … 9. Если имеется n колес, то мы можем представить все числа вплоть до
N = 99…9 (n раз), (6.4.1)
как и в (6.3.1).
Предположим теперь, что в качестве основания мы взяли число b, отличное от 10, но продолжаем рассматривать числа до N. Тогда мы должны иметь m колес, где m — целое число, удовлетворяющее условиям (6.3.2) и (6.3.3). Как и в (6.3.4). число m является целым числом, равным числу n/lg b или следующим за ним. Так как каждое колесо несет b цифр, то количество цифр, записанных на колесах, приближенно равно
D = n b/lg b.
Можно теперь спросить: какое нужно выбрать число b, чтобы получить наименьшее количество чисел, записанных на колесах? Чтобы найти наименьшее значение числа D, в формуле (6.4.2) необходимо лишь исследовать функцию
f(b) = b/lg b (6.4.3)
для различных оснований b = 2, 3, 4… С помощью таблицы логарифмов получаем значения
Последующие значения для f(b) еще больше; например, f(10) = 10, как уже отмечалось. Мы заключаем, что для таких арифмометров имеет место следующее утверждение.
Наименьшее общее число цифр на арифмометре достигается при b = 3.
Видно, что для b = 2 и b = 4 общее число цифр не на много больше; в этом смысле маленькие основания имеют преимущество.
Рассмотрим небольшое изменение этой задачи. Обычные счеты того типа, который иногда используется для обучения детей счету, имеют несколько металлических спиц с девятью [9] подвижными косточками на каждой из них, чтобы отмечать цифры чисел. С таким же успехом можно провести параллельные прямые на листе бумаги и отмечать цифры соответствующим количеством спичек, или же подобно древним начертить эти прямые на песке и отмечать цифры камешками.
Но вернемся к счетам. Если имеется n спиц и на каждой по 9 косточек, то можно представить вновь все целые числа с п знаками вплоть до числа N, записанного в (6.4.1). Теперь зададим следующий вопрос: можно ли, взяв другое основание b, сделать счеты более компактными, т. е. обойтись меньшим количеством косточек?
9
На счетах, принятых в СССР, на каждой спице располагается 10 косточек. (Прим. перев.)
При основании b количество косточек на каждой спице будет b — 1. Как и прежде, для того чтобы счеты имели ту же вместимость N, количество знаков или спиц должно определяться соотношением (6.3.4). Это дает значение
E = n/lg b (b — 1) (6.4.4)
в качестве приближения для общего количества косточек. Чтобы найти, когда это число принимает наименьшее возможное значение, мы должны исследовать функцию
g(b) = (b — 1)/lg b (6.4.5)
для различных значений числа b = 2, 3… Значение функции g(b) для небольших значений числа b даны в таблице
Для больших значений числа b функция продолжает возрастать, поэтому мы заключаем, что необходимое количество косточек на счетах будет минимально при b = 2.
Можно интерпретировать этот результат с другой точки зрения. Предположим, что мы отметили цифры нашего числа, используя спички или камешки, расположенные на прямых линиях. В десятичной системе будет от 0 до 9 отметок на каждой прямой. Это дает в среднем по 4,5 спички на каждой прямой для наугад взятых чисел; следовательно, числа с n знаками потребуют в среднем 4,5 n спичек, когда они укладываются произвольно.
Посмотрим, какое время потребуется, чтобы уложить эти спички на места. Имея в виду какое-нибудь расположение, предположим, что потребуется одна секунда, чтобы уложить одну спичку. Тогда общее время, требуемое для того, чтобы уложить все спички, будет в среднем составлять приблизительно 4,5 n секунд.