Версия для печати
Убрать все задачи
Бинарный метод возведения в
степень.
Предположим, что необходимо возвести число
x в степень
n.
Если, например,
n = 16, то это можно сделать выполнив 15
умножений
x16 =
x . x . ...
. x, а можно обойтись
лишь четырьмя:
x1 = x . x = x2, x2 = x1 . x1 = x4, x3 = x2 . x2 = x8, x4 = x3 . x3 = x16.
Пусть
n = 2
e1 + 2
e2 +...+ 2
er (
e1 >
e2 >...>
er 
0).
Придумайте алгоритм, который позволял
бы вычислять
xn при помощи
b(
n) =
e1 +
(
n) - 1
умножений, где
(
n) =
r — число единиц в двоичном представлении числа
n.
Решение
Доказать, что из любых 27 различных натуральных чисел, меньших 100, можно
выбрать два числа, не являющихся взаимно простыми.
Решение
На прямоугольном листе клетчатой бумаги размером
m×
n клеток расположено несколько квадратов, стороны которых идут по вертикальным и горизонтальным линиям бумаги. Известно, что никакие два квадрата не совпадают и никакой квадрат не содержит внутри себя другой квадрат. Каково наибольшее число таких квадратов?
Решение
Фильтр
