Каталог по источникам

Выбрано 4 задачи

Бинарный метод возведения в степень. Предположим, что необходимо возвести число x в степень n. Если, например, n = 16, то это можно сделать выполнив 15 умножений x¹⁶ = x^.x^....^.x, а можно обойтись лишь четырьмя:

x₁ = x^.x = x², x₂ = x₁^.x₁ = x⁴, x₃ = x₂^.x₂ = x⁸, x₄ = x₃^.x₃ = x¹⁶.

Пусть

n = 2^e₁ + 2^e₂ +...+ 2^e_r (e₁ > e₂ >...> e_r $\displaystyle \geqslant$ 0).

Придумайте алгоритм, который позволял бы вычислять xⁿ при помощи

b(n) = e₁ + $\displaystyle \nu$ (n) - 1

умножений, где $\nu$ (n) = r — число единиц в двоичном представлении числа n.

Решение

В круге радиуса 16 расположено 650 точек. Докажите, что найдется кольцо с внутренним радиусом 2 и внешним радиусом 3, в котором лежит не менее 10 из данных точек.

Решение

Представим себе большой куб, склеенный из 27 меньших кубиков. Термит садится на центр грани одного из наружных кубиков и начинает прогрызать ход. Побывав в кубике, термит к нему уже не возвращается. Движется он при этом всегда параллельно какому-нибудь ребру большого куба. Может ли термит прогрызть все 26 внешних кубиков и закончить свой ход в центральном кубике? Если возможно, покажите, каким должен быть путь термита.

Решение

Две окружности пересекаются в точках A и B. К этим окружностям проведена общая касательная, которая касается окружностей в точках C и D. Докажите, что прямая AB делит отрезок CD пополам.

Решение

Задача 58548 (#31.081)

Задача 58549 (#31.082)

Задача 58550 (#31.083)

Задача 86086 (#31.084)