Сегодня ** уроке информатики обсуждали алгоритм быстрого возведения в степень. Антон был...

Question

Сегодня на уроке информатики обсуждали алгоритм быстрого возведения в степень. Антон был очень внимателен и запомнил, что алгоритм нужен для того, чтобы сократить количество операций умножения при вычислении a^n. Вместо n−1умножения, которые получаются если просто вычислить произведение a⋅a⋅a⋅…⋅a (n сомножителей) можно получить гораздо меньшее число, если действовать так: o если n кратно 2, то найдем сперва a^(n/2), а потом умножим a^(n/2) на себя o если n не кратно 2, то найдем a^(n–1), а потом умножим на a. Например, чтобы вычислить a10 хватит четырех умножений: 3. сначала найдем a^2=a⋅a, 4. потом a^4=a^2⋅a^2, 5. потом a^5=a⋅a^4, 6. и, наконец, a^10=a^5⋅a^5. Антон также запомнил, что самые "плохие" случаи для этого алгоритма — когда n на 1 меньше точной степени двойки. Теперь ему интересно узнать для какого-нибудь большого "плохого" n, а сколько умножений нужно, чтобы возвести a в степень n с помощью этого алгоритма. Помогите Антону, определите, сколько умножений сделает алгоритм для вычисления 2n, где n= 2^12–1. Любой язык

Answer 1

Никакой язык здесь не нужен. Задача математическая.

Сначала, давайте определим функции:

1) Для всех натуральных n,

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

2) Для все натуральных n,

.

Таким образом, нам требуется вычислить

Заметим, что

Т.к.

Используя математическую индукцию, легко доказать что для всех n>1,

 

Следовательно,

Comments

Подскажите сколько умножений сделает алгоритм для вычисления 2^n, где n= 2^(13)–1.

---

будет 25, если следовать решению выше

---

Хоть я и опоздал с комментарием, отвечаю: Легко доказать с помощью индукции что f(2^n)=n. Следовательно алгоритм проделает ровно n операций. В данном случае 2^(13)-1.