Question

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

Answer 1

Ответ:

(см. объяснение)

Объяснение:

Решая задачу "в лоб", нам потребовалось бы умножить число само на себя ровно 147 раз. Это много, потому попробуем оптимизировать алгоритм. Заметим, что $147_{10}=10010011_{2}$, а $x^{147}=x^{128}\times x^{16}\times x^2\times x^1$. Изначально имеем число $x$. Пусть $y=147$ - степень. Пусть $res=1$ - наш будущий ответ. На каждой итерации цикла будем умножать $x$ сам на себя, а $y$ целочисленно делить на 2. При этом заметим, что когда $y\%2>0$, то нам надо умножить текущий результат $r$ на $x$. Таким образом, всего за 8 итераций (вместо 147!) мы можем возвести некоторое число в степень 147.

Покажем, как написать это на C++:

#define ll long long

ll bpow(ll x, ll y) {

   ll r = 1;

   while (y > 0) {

       if (y % 2 > 0) {

           r *= x;

       }

       x *= x;

       y /= 2;

   }

   return r;

}

Задание выполнено!

Answer 2

Конечно, для возведения числа x в степень n можно использовать различные методы, чтобы сделать процесс более эффективным.

Один из наиболее эффективных алгоритмов возведения числа в степень - это метод быстрого возведения в степень (также известный как метод "возведения в степень за логарифмическое время").

Этот алгоритм основан на идее разложения степени числа на бинарный вид. Например, для числа 3 в степени 13:

- 13 (десятичное) = 1101 (бинарное)

Алгоритм заключается в следующем:

1. Начинаем с результатa, равного 1. 2. Проходим по бинарной записи степени числа, начиная с самого младшего бита. 3. Каждый раз, когда мы встречаем единицу в бинарной записи, мы умножаем результат на основание в степени, соответствующей позиции бита. 4. Затем увеличиваем основание в степени вдвое (с каждым шагом умножаем его на само себя), переходя к следующему биту.

Таким образом, количество умножений зависит от числа установленных битов в бинарной записи числа степени.

Для нахождения количества умножений при возведении числа x в степень n=147, нужно представить число 147 в двоичной системе:

147 (десятичное) = 10010011 (бинарное)

В данном случае, если применить метод быстрого возведения в степень, то количество умножений будет равно количеству установленных единиц в бинарной записи числа степени. В числе 147 в бинарной записи 1 встречается 4 раза.

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