Задача к ЕГЭ по информатике на тему «одна функция» №2

Просмотров 8 Комментарии 0

Алгоритм вычисления значения функции $F (n)$ , где $n$ — целое неотрицательное число, задан следующими соотношениями:

$F(n ) = n$ , если $log2(n)$ целое число

$F(n ) = f (n − 1) + 2,$ иначе

Чему равно $f (786432)$ ?

Проанализируем, как изменяются значения на определенных значениях функции с помощью программы

def stepen(n):
    while n > 1:
        if n % 2 != 0:
            return False
        n //= 2
    return True

def f(n):
    if stepen(n):
        return n
    else:
        return f(n - 1) + 2

Заметим, что функция от степеней двойки выводит само число, а для остальных получается значение *степень двойки* + 2. И так до следующей степени двойки.

Число $2 ∗ ∗19 < 786432 < 2 ∗ ∗20,$ более того, $786432 = 2 ∗ ∗20 − 2 ∗ ∗19 ∕∕2.$ Значит, что $f (786432 ) = 2 ∗ ∗19 + (786432 − 2 ∗ ∗19 ) ∗ 2 = 1048576.$

Ответ: 1048576