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

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

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

$F (n) = True$ , при $n = 1$

$F (n) = False$ , если $n$ нечетно

$F (n) = F(n∕∕2),$ иначе

Определите для скольких чисел из отрезка [2; 10000] функция вернет значение True?

Решение 1

def f1(n):
    if n == 1:
        return True

    if n % 2 == 0:
        return f1(n//2)
    else:
        return False


k = 0
for i in range(2, 10000+1):
    if f1(i):
        k += 1

print(k)

Решение 2

Если число не будет полной степенью двойки, то при последовательном делении на $2$ мы вскоре получим нечетное число (кроме $1$ ) и вернем $False$ , $True$ вернут только степени двойки в данном диапазоне, а их всего $13$ .

Ответ: 13