Язык Си в примерах/Степень числа: различия между версиями

Для вычисления функции <math>f(n)=a^n\,\!</math> есть рекуррентная формула:

<math>a^n = a\cdot a^{n-1}, \quad a^0 = 1.\,\!</math>

<math>a^n=\left\{\begin{matrix} a \cdots a^{n-1}, & \mbox{if }n\mbox{ is odd} \\( a^{n/2})^2, & \mbox{if }n\mbox{ is even} \end{matrix}\right.\,\!</math>

Например, если обозначть стрелочкой <math> \to \,\!</math> слово «сводится к », то при вычислении

<math>a^{12}\,\!</math> для первой рекурсии получим цепочку длины 12:

<math>a^{12} \to a^{11} \to a^{10} \to a^{9} \to a^{8} \to a^{7} \to a^{6} \to a^{5} \to a^{4} \to a^{3} \to a^{2} \to a^{1} \to a^0.\,\!</math>

<math>a^{12} \to a^{6} \to a^{3} \to a^{2} \to a^{1} \to a^{0}.\,\!</math>

Для больших n разница в длине цепочки более разительная. В частности <math>a^{10000}\,\!</math>

* Сколько шагов требуется для вычисления <math>a^{30}\,\!</math> вторым

* Покажите, что второй алгоритм выполняется за логарифмическое по n число шагов, а точнее ограничено сверху <math>2\cdot \log_2 n\,\!</math> (еще точнее: в точности равно числу знаков в двоичной записи числа n плюс число единичек в этой записи).