Е16.25 Укажите количество таких значений n < 1 000 000 000, для которых F(n) = 2.

Администратор

4 года назад

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

F(0) = 0;
F(n) = F(n – 1) + 1, если n нечётно;
F(n) = F(n/2), если n > 0 и при этом n чётно.

Укажите количество таких значений n < 1 000 000 000, для которых F(n) = 2.

СтатГрад Вариант ИН2110301 08.02.2022 – задание №16

Показать решение...

Решение:

Решение (долго)

def f(n):
    if n==0:
        return 0
    if n%2!=0:
        return f(n-1)+1
    if n>0 and n%2==0:
        return f(n//2)
k=0
for n in range(1, 1_000_000_000):
    if f(n)==2:
        k+=1
print(k)

def f(n):

if n==0:

return 0

if n%2!=0:

return f(n-1)+1

if n>0 and n%2==0:

return f(n//2)

k=0

for n in range(1, 1_000_000_000):

if f(n)==2:

k+=1

print(k)

Решение — Каримов Минтимер Ростямович

def f(n, l):
    if n >= 1_000_000_000: return
    if l == 0: ans.add(n)
    if n % 2 == 0 and l != 0: f(n + 1, l - 1)
    f(n * 2, l)

ans = set()
f(1, 1)
print(len(ans))

def f(n, l):

if n >= 1_000_000_000: return

if l == 0: ans.add(n)

if n % 2 == 0 and l != 0: f(n + 1, l - 1)

f(n * 2, l)

ans = set()

f(1, 1)

print(len(ans))

Ответ: 435