ДООИ2003/Конкурсный тур. |
24/02/2003 |
Теоретическая задача
Число, кроме количественного значения имеет ещё форму записи, благодаря которой оно распознается человеком или компьютером. Формы записи нам известны самые различные. Например, число можно записать в обычной десятичной системе счисления, можно в двоичной. Известно, что в принципе в качестве основания системы счисления можно взять любое число. Но это далеко не все возможные способы представления чисел. Рассмотрим несколько необычных способов записи чисел.
Показательная форма записи.
Для примера будем использовать число записанное в десятичной форме. Пусть это будет число 536.
Возьмём произвольное число. Например 6. Построим следующий ряд чисел:
А0 = 6
А1 = 6 + 6 =12
А2 = 12 +12 = 24
А3 = 24 + 24 = 48
А4 = 48 + 48 = 96
А5 = 96 +96 =
192А6 = 192 + 192 = 384
Назовём эти числа цифрами. Из них почти можно сложить число 536. А именно: 384 + 96 + 48 + 6 + 2. В этом представлении только 2 не содержится в исходном ряду. Но пока мы об этом забудем, а остальное запишем цифрами. Получится так: А6 + А4 + А3 + А1. Далее, с учётом отсутствующих цифр перепишем это представление так:
1 |
0 |
1 |
1 |
0 |
0 |
1 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
Таким образом имеем двоичное представление 1011001 – семь знаков. представим оставшуюся двойку двоичным числом. Получим для представления числа 536 два числа 1011001 и 10 итого девять знаков. В то же время в двоичной системе счисления 536 = 1000011000 десять знаков. Таким образом мы выиграли один знак. Можно предположить, что для больших чисел этот выигрыш будет больше.
Представление с помощью ряда Фиббоначи
Построим ряд цифр представляющий собой ряд Фиббоначи.
А0 = 1
А1 = 2
А3 = 3
А4 = 5
А5 = 8
А6 = 13
А7 = 21
А8 = 34
А9 = 55
А10 = 89
А11 = 144
А12 = 233
А13 = 377
Из этого ряда чисел также можно составить наше число 536. А именно 536 = 377 + 144 + 13 + 2. Позиционно число можно представить так:
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
13 |
12 |
11 |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
Таким образом мы получили представление из 13 цифр. То есть, в этой системе счисления мы проиграли 3 цифры.
Факториальная форма записи
А теперь построим ряд цифр представляющий собой последовательность факториалов:
А0 = 1
А1 = 2
А2 = 6
А3 = 24
А4 = 120
Представление нашего числа на основе факториальных цифр также возможно. А именно получим следующее:
536 = 3*120 + 2*24 + 1*6 + 1*2
Запишем позиционно
11 |
10 |
1 |
1 |
0 |
4 |
3 |
2 |
1 |
0 |
Таким образом в факториальной системе мы имеем представление пятью двоичными числами общей длиной 7 знаков, выигрыш составляет 3 знака в сравнении с обычным двоичным представлением.
А теперь два теоретических вопроса:
ВОПРОС 1.
В конечном итоге все три способа представления дают двоичную форму числа. Мы для десятичного числа 536 получили три двоичных числа разной длины. Получается, что разные двоичные числа означают одно и тоже количество (ведь независимо от системы счисления число это количество). Конечно это парадокс. Попробуйте его объяснить.
ВОПРОС 2.
Видимо действительно длина числа зависит от формы представления. Как именно зависит и что означает эта зависимость вы выясните отвечая на первый вопрос. Но то, что эта зависимость есть
, не вызывает сомнений. Означает ли это, что просто выбрав систему записи числа можно сжать информацию? (настолько, чтобы выигрыш был заметен).