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

Задачи

Страница: << 460 461 462 463 464 465 466 >> [Всего задач: 4557]

Задача 60902

Темы:	[	Теория алгоритмов (прочее)	]
Темы:	[	Двоичная система счисления	]

Сложность: 3+
Классы: 8,9,10

Бинарный метод возведения в степень. Предположим, что необходимо возвести число 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.

Прислать комментарий

Решение

Задача 61332

Темы:	[	Производная и касательная	]
Темы:	[	Примеры и контрпримеры. Конструкции	]

Сложность: 3+
Классы: 10,11

Метод Ньютона (см. задачу 9.77) не всегда позволяет приблизиться к корню уравнения f (x) = 0. Для многочлена f (x) = x(x - 1)(x + 1) найдите начальное условие x₀ такое, что f (x₀) $\ne$ x₀ и x₂ = x₀.