Версия для печати
Убрать все задачи
Бинарный метод возведения в
степень.
Предположим, что необходимо возвести число
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.
Решение
В круге радиуса 16 расположено 650 точек. Докажите, что
найдется кольцо с внутренним радиусом 2 и внешним радиусом 3, в котором лежит не менее 10 из данных точек.
Решение
Представим себе большой куб, склеенный из 27 меньших кубиков. Термит садится на центр грани одного из наружных кубиков и начинает прогрызать ход. Побывав в кубике, термит к нему уже не возвращается. Движется он при этом всегда параллельно
какому-нибудь ребру большого куба. Может ли термит прогрызть все 26 внешних кубиков и закончить свой ход в центральном кубике? Если возможно, покажите, каким должен быть путь термита.
Решение
Две окружности пересекаются в точках A и B.
К этим окружностям проведена общая касательная, которая касается
окружностей в точках C и D.
Докажите, что прямая AB делит отрезок CD пополам.
Решение
Фильтр
