Пусть у нас есть число \(n\) в десятичной записи: \(n_{i_1}n_{i_2}n_{i_3} \ldots n_{i_k} \ldots n_{i_K}\). Требуется определить его последний знак (\(n_{i_K}\)). Как это сделать?
За ужином я придумал алгоритм вычисления. Конечно же, он существовал до меня, но я в области вычислительных алгоритмов полный новичок, поэтому нижеследующее рассуждение было написано с чистого листа.
(1) Сколько разрядов в числе \(n\)? Очевидно, их \(K\): \(K=\lceil \log_{10} n\rceil\). (2) Как вычислить самую левую цифру числа \(n\) (обозначим её за \(n_{i_1}\))? Очевидно, надо поделить это число на десять в степени, на единицу меньшей числа разрядов, и откинуть хвост (то есть округлить вниз до целого). (3) Как вычислить вторую справа цифру числа \(n\)? Провести ту же самую вычислительную операцию с числом \(n\) без левой цифры. (4) Как откинуть левую цифру числа \(n\) (то есть \(n_{i_1}\))? От числа \(n\) отнять произведение левой цифры и 10 в степени \(K-1\). (5) Сколько раз надо провести процедуру вычисления \(k\)-й по счёту слева цифры числа \(n\)? Очевидно, \(k\) раз.
Итак, у нас уже есть рекурсивный алгоритм. Теперь запишем всё это дело по пунктам на языке математики.
- \(K=\lceil \log_{10} n\rceil\).
- \(n_{i_1} = \left\lfloor \frac{n}{10^{\lfloor \log_{10} n \rfloor}} \right\rfloor = f(n)\).
- Для \(\mathbb{N} \ni p>1\) \(n_{i_k} = f\left( n - \sum\limits_{m=1}^{k-1} \bigl( n_{i_m} \cdot 10^{\lfloor\log_{10} n \rfloor} \bigr) \right) = g(n,k)\).
- Rightmost digit: \(n_{i_K} = n_{i_{\\lceil \log_{10} n\rceil}} = g(n,K)\) .
При этом понятно и ежу, что функция \(g(n,k)\) рекуррентна по \(k\) (требует вычисленных \(g(n,1),\ldots,g(n,K-1)\)), поэтому придётся вычислять все цифры, пока не придём к последней.
В данном алгоритме кроется страшнейшая ошибка. Если \(n_{i_k}=0\), тогда будет вычисляться следующая ненулевая цифра, поэтому число шагов будет не \(K\), а \(K-\zeta(n)\), где \(\zeta(n)\) — число нулей в числе \(n\).
И вот я думаю: неужели нет более простого и очевидного математического алгоритма вычисления правой цифры числа? Наверняка есть. Наверняка надо проверить остаток от деления на чи́сла из определённого набора.
Задание 1. Придумать подобный алгоритм на основе вычисления остатка от деления \(n\) на числа из определённого набора.
Задание 2. Придумать на основе вышеприведённого алгоритма новый метод вычисления \(n_{i_k}\), который бы выдавал 0 для \(n_{i_k}=0\) (пока что он будет выдавать следующее ненулевое \(n_{i_{k+q}}\)).
Задание 3. Придумать \(\zeta (n)\). Пока что \(\zeta(n) = K - s\), где \(s = \max \{k \leqslant K\}\), то есть количество цифр, которые мы вообще вычислили. Иными словами, \(s\) — номер шага, который выдал нам корректную последнюю цифру. Но зачем же так сложно?