Задание по алгоритмам Покажите, что для любого числа длина его двоичной записи не более че
в четыре раза превосходит длину его десятичной записи. Чему примерно рав
но отношение этих длин для очень больших чисел?

Предыдущий
вопрос Следующий
вопрос

Пусть у нас есть произвольное число n. Представим это число в десятичной и двоичной системах счисления. Пусть десятичное представление числа n имеет длину k, а двоичное представление числа n имеет длину m.

Тогда можно записать неравенство
m ≤ log2(n) + 1
k ≤ log10(n) + 1.

Так как log2(n) = log10(n) / log10(2), то, подставив это в первое неравенство, получим
m ≤ (log10(n) + 1) / log10(2) + 1
m ≤ 4 * log10(n) + 4.

Таким образом, для любого числа n длина его двоичной записи не превышает длины его десятичной записи более чем в четыре раза.

Для очень больших чисел отношение длин двоичной и десятичной записей будет стремиться к константе, примерно равной 4.