Наверное, всем известна легенда о мудреце, который попросил у правителя в качестве награды за изобретение шахмат немного риса. Мудрец пожелал, чтобы на первую клетку шахматной доски положили одно зернышко риса, на вторую - в два раза больше, чем на предыдущую (два зернышка), и так далее, пока не будет заполнена вся доска. Обрадовавшись вначале, вскоре правитель понял, что попал впросак...
Что общего между этой легендой и двоичной системой счисления?
Оказывается, количество рисинок, выкладываемых на каждую из 64 клеток шахматной доски, соответствует весам разрядов двоичного числа. В самом деле, вес первого (младшего) разряда - единица, и на первую клетку кладется одно зернышко. Вес второго разряда - два, и на вторую клетку выкладывается два зернышка. Отсюда, количество зерен, которые должны быть положены на шахматную доску в качестве награды мудрецу, можно представить 64-хразрядным двоичным числом:
N = 1*263 + ... + 1*22 + 1*21 + 1*20
Поскольку ни одна клетка не должна быть пропущена, то в каждом из 64-х разрядов двоичного числа стоит 1, и это максимальное число, которое можно записать в 64 двоичных разрядах:
264-1 = 18 446 744 073 709 551 615
Заглянув в Википедию, я смог произнести это число: 18 квинтиллионов 446 квадриллионов 744 триллиона 73 миллиарда 709 миллионов 551 тысяча 615.
К слову, это число больше, чем число секунд, прошедших с момента Большого Взрыва:
13800000000 * 365.25 * 24 * 60 * 60 = 435 494 880 000 000 000
Итак, это максимальное целое число, которое можно представить в 64-хразрядном кодовом слове. Большинство изготовляемых сегодня персональных компьютеров оперируют именно 64-разрядными двоичными словами.
Но вернемся к рисовым зернам на шахматной доске.
Если присмотреться к тому, как возрастает количество зерен на доске, то мы увидим, что заполнение каждой следующей клетки удваивает общее количество зерен на доске! Точнее, удваивает и добавляет еще одно зернышко. Вот результаты заполнения нескольких клеток подряд:
| N клетки | Кол-во зерен в клетке | Всего зерен на доске |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 2 | 1 + 2 = 3 |
| 3 | 4 | 3 + 4 = 7 |
| 4 | 8 | 7 + 8 = 15 |
| 5 | 16 | 15 + 16 = 31 |
| 6 | 32 | 31 + 32 = 63 |
Так, после заполнения 5 клеток на доске 31 зерно, а после выкладывания еще 32 зерен на 6-ю клетку общее количество зерен становится 63. То есть, на каждую последующую клетку выкладывается зерен на одно больше, чем общее количество зерен на всех предыдущих клетках!
Этим эффектом мы обязаны свойствам позиционной двоичной системы счисления, которую имитирует шахматная доска с рисом. Заполняя очередную клетку, мы добавляем к сумме рисовых зерен число, равное очередной степени двойки. Это все равно, что дописывать к двоичному числу единицу в очередной разряд слева, причем все разряды числа уже содержат единицы:
| N клетки | Кол-во зерен в клетке | Всего зерен на доске |
|---|---|---|
| 1 | 1 = 12 | 1 = 12 |
| 2 | 2 = 102 | 3 = 112 |
| 3 | 4 = 1002 | 7 = 1112 |
| 4 | 8 = 10002 | 15 = 11112 |
| 5 | 16 = 100002 | 31 = 111112 |
| 6 | 32 = 1000002 | 63 = 1111112 |
Аналогичный эффект - удваивание числа плюс единица - происходит и в других позиционных системах счисления, а не только в двоичной. Например, дописав 1 слева к десятичному числу 99, получим 199, что соответствует 99 * 2 + 1. Ведь дописав единицу слева, мы прибавили 100 к 99!
Чтобы эффект 'удвоение плюс один' работал, нужно, чтобы разряды числа, к которому слева дописывается единица, имели максимально возможные в данной системе счисления значения. Тогда дописывание к числу единицы слева равносильно прибавлению к нему числа, которое на 1 больше первоначального.
А поскольку в двоичной системе счисления максимально возможное значение разряда - единица, то данный эффект работает при каждом последовательном дописывании единицы слева к двоичному числу из одних единиц. И обращает на себя внимание на шахматной доске с рисом.
Обратим внимание, что сумма весов единичных разрядов двоичного числа равна самому этому двоичному числу. Достаточно посмотреть на последний столбец вышеприведенной таблички.
Справедливость последнего наблюдения следует из известного нам представления k-разрядного числа в виде многчлена:
nk...n3n2n1 = nk*bk-1 + ... + n3*b2 + n2*b1 + n1*b0
где b - основание системы счисления, а n1, ..., nk - разряды числа. Для двоичного числа, все разряды которого имеют значение 1, многочлен превращается в сумму весов разрядов:
nk...n3n2n1 = bk-1 + ... + b2 + b1 + b0
И еще одно наблюдение над шахматной доской с рисом.
Очевидно, что количества зерен, выкладываемых на клетки доски, - члены геометрической прогрессии, где каждый следующий член в 2 раза больше предыдущего. И веса разрядов в двоичной позиционной системе счисления, и в других позиционных системах счисления, с которыми мы познакомились, - члены геометрической прогрессии.
Вес каждого следующего разряда (каждый следующий член геометрической прогрессии) равен весу предыдущего разряда (предыдущему члену), умноженному на основание системы счисления (знаменатель геометрической прогрессии):
an = an-1b
В статье Считаем до 1000... на пальцах на основе наблюдений мы научились определять количество разных значений, которые можно представить в n разрядах числа по формуле:
P = bn
Но количество разных значений, которые можно представить в n разрядах числа, равно весу n+1-го разряда. Так, в 2 разрядах десятичного числа можно представить сто разных значений, от 00 до 99:
102 = 100
И вес третьего справа разряда десятичного числа также равен 100. Изменим формулу так, чтобы она давала нам вес n-го разряда:
an = bn-1
Это, по сути, формула для получения n-го члена геометрической прогрессии, где первый элемент прогрессии (вес младшего разряда) равен 1. Полностью формула для получения n-ного члена геометрической прогрессии выглядит так:
an = a1bn-1
, где a1 - первый член прогрессии.
На этом оставляю шахматную доску с рисом мудрецу и правителю. Надеюсь, что требование мудреца было шуткой с его стороны, а правитель обладал достаточным тактом, чтобы мирно разрешить ситуацию.
Комментариев нет:
Отправить комментарий