Задание 15 Параграф 5 ГДЗ Босова 11 класс (Информатика)

1. Постройте эффективный алгоритм возведения числа $$x$$ в степень $$n=152$$.

Для возведения числа $$x$$ в степень $$152$$ удобно использовать алгоритм быстрого возведения в степень. Так как $$152$$ — чётное число, применяем правило:

$$x^n = \left(x^{n/2}\right)^2$$

Последовательно получаем:

1. $$x^2 = x \cdot x$$
2. $$x^4 = \left(x^2\right)^2$$
3. $$x^8 = \left(x^4\right)^2$$
4. $$x^9 = x \cdot x^8$$
5. $$x^{18} = \left(x^9\right)^2$$
6. $$x^{19} = x \cdot x^{18}$$
7. $$x^{38} = \left(x^{19}\right)^2$$
8. $$x^{76} = \left(x^{38}\right)^2$$
9. $$x^{152} = \left(x^{76}\right)^2$$

Такой способ требует значительно меньше умножений, чем последовательное перемножение $$x$$ сто пятьдесят два раза.

Ответ

Эффективный алгоритм: быстрое возведение в степень по схеме $$x^{152} = \left(\left(\left(\left(\left(\left(\left(\left(x^2\right)^2\right)^2 \cdot x\right)^2 \cdot x\right)^2\right)^2\right)^2\right)^2$$