ГДЗ по информатике, 11 класс, Босова, номер 5.15: Основные сведения об алгоритмах
Информатика — Босова Л.Л., Босова А.Ю.
Анна Соколова, преподаватель информатики Шпаргача обновлено 8 сентября 2026
Условие
Постройте эффективный алгоритм возведения числа x в степень n=152.
Номер как в учебнике. Условие — полный пересказ редакции: те же пункты, числа и факты, не цитата из книги.
Пошаговое решение
Для возведения числа в степень эффективным способом используется метод бинарного возведения в степень (или метод последовательных квадратов). Его суть заключается в том, что вместо n-1 умножений мы используем всего около log2n/2 операций. Сначала нужно представить показатель степени n=152 в двоичном виде.
Разложим число 152 на сумму степеней двойки: 152=128+16+4+4? Нет, давайте проверим внимательно. 128+16=144, остаток 152-144=8. Значит, 152=128+16+8. В двоичной записи это будет выглядеть так: 100110002. Это означает, что нам нужны степени x8, x16 и x128. Алгоритм вычисления состоит из двух частей: получения нужных степеней через последовательное возведение в квадрат и их перемножения.
Пошаговый алгоритм:
- Инициализируем переменную результата res=1 и текущей степени cur=x.
- Просматриваем биты числа 152 справа налево (от младших к старшим):
- Бит 0 (число 1): четное, пропускаем. cur=cur2 (x2).
- Бит 1 (число 2): четное, пропускаем. cur=cur2 (x4).
- Бит 2 (число 4): четное, пропускаем. cur=cur2 (x8).
- Бит 3 (число 8): нечетное. Умножаем результат: res=res×cur (x8). Обновляем степень: cur=cur2 (x16).
- Бит 4 (число 16): нечетное. Умножаем результат: res=res×cur (x8×x16=x24). Обновляем степень: cur=cur2 (x32).
- Бит 5 (число 32): четное. Пропускаем. Обновляем степень: cur=cur2 (x64).
- Бит 6 (число 64): четное. Пропускаем. Обновляем степень: cur=cur2 (x128).
- Бит 7 (число 128): нечетное. Умножаем результат: res=res×cur (x24×x128=x152).
Проверка количества операций: Мы выполнили 7 возведений в квадрат и 3 умножения на текущую степень. Всего 10 операций умножения. Для сравнения, наивный алгоритм потребовал бы 151 умножение. Эффективность очевидна.
Алгоритм бинарного возведения в степень: разложить 152 в двоичный вид (10011000), последовательно возводить x в квадрат и умножать на результат при наличии единицы в соответствующем разряде.
В условии требуется построить эффективный алгоритм. Стандартным решением для таких задач является метод быстрого возведения в степень. Важно правильно разложить число 152: 152 / 2 = 76 (0), 76 / 2 = 38 (0), 38 / 2 = 19 (0), 19 / 2 = 9 (1), 9 / 2 = 4 (1), 4 / 2 = 2 (0), 2 / 2 = 1 (0), 1 / 2 = 0 (1). Читаем снизу вверх: 10011000. Степени двойки: 23=8,24=16,27=128. Сумма: 8+16+128=152. Все верно.
Как решение?
Двойная оценка: понятность и подробность. Можно выбрать одно или оба.
У вас другое условие?
Загрузите фото — учтём ваши числа и редакцию.
Частые вопросы
Это точный номер 5.15 из моего учебника?
Номер совпадает с учебником «Информатика», Босова Л.Л., Босова А.Ю.. Формулировка — пересказ редакции, не дословная цитата. Если в вашей редакции другие числа — загрузите фото.
Какой ответ в задании 5.15?
Краткий ответ: Алгоритм бинарного возведения в степень: разложить 152 в двоичный вид (10011000), последовательно возводить x в квадрат и умножать на результат при наличии единицы в соответствующем разряде.
Как пользоваться этим разбором?
Сначала прочитайте условие и чертёж, затем шаги решения по порядку и сверьте свой ход с кратким ответом внизу.
Какой учебник имеется в виду?
«Информатика», Босова Л.Л., Босова А.Ю.. Проверьте часть, год и автора на обложке. Тема в учебнике: § 5. Основные сведения об алгоритмах.
Можно ли списать ответ без решения?
Лучше сначала решить самостоятельно, а разбор использовать для проверки хода и поиска ошибки.