11 класс·базовый уровень

Найдите наибольшее возможное значение разности a − b.

Условие

Функция F(n), где n — неотрицательное целое число, задана следующими соотношениями:F(0) = 0;F(n) = F(n −

- 2n − 1, если n нечётно;F(n) = 4F(n / 2), если n чётно. Известно, что F(a) − F(b) = 1001. Найдите наибольшее возможное значение разности a − b.

Ответ и полный разбор откроются после входа

Как рассуждать
Решение. Для примера найдем значение F(5): $F ( 5 ) = F ( 4 ) + 9 = 4 \cdot F ( 2 ) + 9 = 4 \cdot 4 \cdot F ( 1 ) + 9 = 16 \cdot ( F ( 0 ) + 1 ) + 9 = 16 + 9 = 25$ $F ( 5 ) = F ( 4 ) + 9 = 4 \cdot F ( 2 ) + 9 = 4 \cdot 4 \cdot F ( 1 ) + 9 =$ $= 16 \cdot ( F ( 0 ) + 1 ) + 9 = 16 + 9 = 25$ $F ( 5 ) = F ( 4 ) + 9 =$ $= 4 \cdot F ( 2 ) + 9 = 4 \cdot 4 \cdot F ( 1 ) + 9 =$ $= 16 \cdot ( F ( 0 ) + 1 ) + 9 = 16 + 9 = 25$ Рассмотрим значение F(6): $F ( 6 ) = 4 \cdot F ( 3 ) = 4 \cdot ( F ( 2 ) + 5 ) = 4 \cdot F ( 2 ) + 20 = 4 \cdot 4 \cdot F ( 1 ) + 20 =$ $= 16 \cdot F ( 1 ) + 20 = 16 \cdot ( F ( 0 ) + 1 ) + 20 = 16 + 20 = 36$ $F ( 6 ) = 4 \cdot F ( 3 ) = 4 \cdot ( F ( 2 ) + 5 ) = 4 \cdot F ( 2 ) + 20 =$ $= 4 \cdot 4 \cdot F ( 1 ) + 20 = 16 \cdot F ( 1 ) + 20 =$ $= 16 \cdot ( F ( 0 ) + 1 ) + 20 = 16 + 20 = 36$ $F ( 6 ) = 4 \cdot F ( 3 ) =$ $= 4 \cdot ( F ( 2 ) + 5 ) = 4 \cdot F ( 2 ) + 20 =$ $= 4 \cdot 4 \cdot F ( 1 ) + 20 = 16 \cdot F ( 1 ) + 20 =$ $= 16 \cdot ( F ( 0 ) + 1 ) + 20 = 16 + 20 = 36$ То есть алгоритм считает квадрат числа. Составим программу на языке Python для поиска ответа. Приведём решение на языке Python.otv = 0for a in range(1000): for b in range(1000): if a2 - b2 == 1001: otv = max(otv, a-b)print(otv)

Осталось ещё 1 шаг

Бесплатно · займёт минуту