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

Для предлагаемого задания эффективным будет алгоритм быстрого возведения в степень.
Так как 152 четное число, можно воспользоваться следующей формулой:
Xn=(X(n/2))2
По шагам:
1) Х2=Х*Х
2) Х4=(Х2)2
3) Х8=(Х4)2
4) Х9=Х*Х8
5) Х18=(Х9)2
6) Х19=Х*Х18
7) Х38=(Х19)2
8) Х76=(Х38)2
9) Х152=(Х76)2

Для возведения числа $$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$$