Цитата(kolesnle @ 12.12.2013, 15:52  ) | | А почему так получилось? |
А давайте я Вам процитирую (лучше я всё равно не сформулирую) из книги Шкляровский, Ченцов, Яглом "Избранные задачи и теоремы элементарной математики", 1978 года издания, задача номер 104:| Цитата |
Сколько и каких цифр понадобится для того, чтобы записать все целые числа от 1 до 100 000 000 включительно?
|
Ответ:| Цитата |
Рассмотрим сначала все целые числа от 0 до 99 999 999; при этом те из этих чисел, которые имеют меньше восьми цифр, дополним слева нулями так, чтобы они стали восьмизначными. Мы будем иметь 100 000 000 восьмизначных чисел, для записи которых нам потребуется, очевидно, 800 000 000 цифр. При этом здесь каждая из 10 цифр будет использована равное число раз, поскольку все они совершенно равноправны (нуль может стоять на первом месте точно так же, как и всякая другая цифра). Следовательно, каждая цифра будет у нас использована 80 000 000 раз.
Теперь подсчитаем, сколько здесь будет лишних нулей (т.е. нулей, приписанных спереди чисел, имеющих меньше восьми цифр). Однозначных чисел (не считая нуля) имеется всего девять, двузначных чисел 99-9=90, трехзначных чисел 999-99=900, и т.д. Так как к однозначной цифре мы приписали слева семь нулей (не считая цифр первого числа, которое у нас записывалось так: 00 000 000) будет равно:
7*9 + 6*90 + 5*900 + 4*9000 + 3*90000 + 2*900000 + 1*9000000 = 11 111 103
Припишем теперь 1 слева первого числа 00 000 000; при этом мы получим все целые числа от 1 до 100 000 000. Мы видим, что для записи этих чисел требуется 80 000 000 двоек, троек, и т.д. до девяток, 80 000 001 единиц (одну лишнюю единицу мы приписали слева числа 00 000 000) и 80 000 000 - 11 111 103 = 68 888 897 нулей. |
Все это наводит на размышления по поводу 10^16. В конце концов всё сводится к циклу по разрядности числа N (то есть максимум 16 итераций!) при аккуратном программировании. |
