Сколько потребуется умножений для возведения числа x в степень n=147, если построить для этого эффективный алгоритм?

Ответ:

Используем алгоритм быстрого возведения в степень (binary exponentiation).

Разложим показатель:
147₁₀ = 10010011₂ = 128 + 16 + 2 + 1.

В этом случае:

• количество бит (длина записи) = 8

• число единиц в двоичной записи = 4

Теперь считаем операции:

1. Возведение через последовательное возведение в квадрат требует $8 - 1 = 7$ умножений на квадрат (squaring).

2. Дополнительные умножения для “включения” нужных степеней (где стоят единицы), кроме первой единицы: $4 - 1 = 3$.

Итого:
7 + 3 = 10 умножений.

Ответ: потребуется 10 умножений.