16. Рекурсивные алгоритмы —Каталог задач по ЕГЭ - Информатика БУ

Ошибка.
Попробуйте повторить позже

Задача 1#49380

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

$F (0) = 0;$

$F (n) = F(n∕2)$ , если $n > 0$ и при этом $n$ чётно;

$F (n) = 1+ F (n − 1)$ , если $n$ нечётно.

Назовите минимальное значение $n$ , для которого $F (n) = 12$ .

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

def F(n):
    if n == 0:
        return 0
    if n % 2 == 0 and n>0:
        return F(n/2)
    if n % 2 != 0:
        return 1+F(n-1)
i = 0
while F(i) != 12:
    i += 1
print(i)

Ответ: 4095

Ошибка.
Попробуйте повторить позже

Задача 2#88109

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

$F (n) = n$ , при $n > 4000$

$F (n) = F(n +2) ⋅3+ 5⋅n$ , при $n ≤ 4000$

Чему равно значение выражения $F(3988)∕F(3998)$ ?

В ответе укажите только целую часть числа.

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

def f(n):
    if n > 4000:
        return n
    return f(n + 2) * 3 + 5 * n
print(f(3988)/f(3998))

Ответ: 263

Ошибка.
Попробуйте повторить позже

Задача 3#88107

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

$F (n) = n$ , при $n < 15$

$F (n) = 2∗ F(n− 3)+ 4 + F(n− 1)$ , при $n ≥ 15$

$G (n) = 1+ 2∗ n$ , при $n ≥ 99$

$G (n) = n∗ G(n +2) +G (n∗ 2)$ , при $n < 99$

Чему равна значение выражения $F(52)− G (88)$

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

def f(n):
    if n < 15:
        return n
    return 2 * f(n - 3) + 4 + f(n - 1)
def g(n):
    if n >= 99:
        return 1 + 2*n
    return n * g(n + 2) + g(n * 2)

print(f(52) - g(88))

Ответ: -132117717082049

Ошибка.
Попробуйте повторить позже

Задача 4#88106

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

$F (n) = 1$ , если $n > 39$ ;

$F (n) = F(n ∗2)+ n +5$ , если $n <= 39$ и при этом $n$ кратно 3;

$F (n) = 1+ F (n + 4)+ 2∗ F(n+ 1)$ , если $n$ не кратно 3 и $n <= 39$ .

Назовите максимальное значение $n$ , для которого значение $F (n)$ будет кратно 3.

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

def F(n):
    if n > 39:
        return 1
    if n % 3 == 0 and n <= 39:
        return F(n * 2) + n + 5
    if n % 3 != 0 and n <= 39:
        return 1 + F(n + 4) + 2*F(n + 1)
for i in range(1000, 1, -1):
    t = F(i)
    if t % 3 == 0:
        print(i)
        break

Ответ: 39

Ошибка.
Попробуйте повторить позже

Задача 5#86295

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

$F (n) = 200$ , при $n < 200$

$F (n) = (n+ 1)⋅F (n − 4)− 10⋅(n− 2)$ , при $n ≥ 200$

$G (n) = n$ , при $n ≥ 505$

$G (n) = n2 + G (n + 4)$ , при $n < 505$

Чему равна сумма цифр выражения $F(300)− G(20)$

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

def f(n):
    if n < 200:
        return 200
    return (n + 1) * f(n - 4) - 10 * (n - 2)


def g(n):
    if n >= 505:
        return n
    return n ** 2 + g(n + 4)


print(sum(int(i) for i in str(f(300) - g(20))))

Ответ: 322

Ошибка.
Попробуйте повторить позже

Задача 6#72484

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

$F (0) = 0;$

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

$F (n) = 3+ F (n − 1)$ , если $n$ нечётно и $n > 0$ .

Назовите минимальное значение $n$ , для которого $F (n) = 21$ .

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

def F(n):
    if n == 0:
        return 0
    if n % 2 == 0 and n > 0:
        return F(n / 2) + 2
    if n % 2 != 0 and n > 0:
        return 3 + F(n - 1)
i = 0
while F(i) != 21:
    i += 1
print(i)

Ответ: 67

Ошибка.
Попробуйте повторить позже

Задача 7#72480

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

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

$G (n) = 2$ при $n = 1$

$F (n) = F(n − 1) +1 ⋅G(n − 1), при n > 1$

$G (n) = F(n − 1) − 2 ⋅G(n − 1), при n > 1$

Чему равна сумма цифр значения функции F(20)+G(10)?

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

 def F(n):
     if n == 1:
         return 1
     else:
         return F(n-1)+G(n-1)
 def G(n):
     if n == 1:
         return 2
     else:
         return F(n-1)-2*G(n-1)
 print(F(20)+G(10))

Программа выводит значение 3591153, в задании требуется найти сумму цифр этого числа: $3+ 5+ 9 + 1+ 1+ 5 + 3 = 27$ – это и будет ответ на данную задачу.

Ответ: 27

Ошибка.
Попробуйте повторить позже

Задача 8#72475

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

F(n) = n, если n $≤$ 1,

F(n) = $F(n− 1)$ + $F (n − 2)$ * n, если n > 1.

Определите значение выражения: $F (10)− F(5)$ .

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

 def F(n):
     if n <= 1:
         return n
     else:
         return F(n-1)+F(n-2)*n
 print(F(10)-F(5))

Ответ: 12100

Ошибка.
Попробуйте повторить позже

Задача 9#72470

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

$F (n) = n+ 3$ , при $n ≤ 1$

$F (n) = F(n − 3) +n + 2$ , при $n > 1$

Найдите сумму положительных целых значений $n$ при которых $F (n) < 666$ .

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

 def F(n):
     if n <= 1:
         return n+3
     else:
         return F(n-3)+n+2
 sum = 0
 for n in range(1,1000):
     if F(n)<666:
         sum+=n
 print(sum)

Ответ: 1770

Ошибка.
Попробуйте повторить позже

Задача 10#72465

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

$F (n) = n+ 2$ , при $n ≤ 1$

$F (n) = F(n − 2) +n + 3$ , при $n > 1$

Найдите количество положительных целых значений $n$ при котором $F (n) < 565$ .

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

 def F(n):
     if n <= 1:
         return n+2
     else:
         return F(n-2)+n+3
 count = 0
 for n in range(1,1000):
     if F(n)<565:
         count+=1
 print(count)

Ответ: 43

Ошибка.
Попробуйте повторить позже

Задача 11#72463

Ниже записаны две рекурсивные функции $F$ и $G$ :

$F (n) = n+ 3$ , при $n ≤ 2$

$F (n) = F(n − 1) +G (n− 2)$ , при $n > 2$

$G (n) = n+ 1$ , при $n ≤ 2$

$G (n) = G(n − 1) + F(n− 1)$ , при $n > 2$

Вычислите значение выражения $G (4) + F(5)$ .

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

def F(n):
    if n > 2:
        return F(n-1)+ G(n-2)
    else: return n+3
def G(n):
    if n > 2:
        return G(n-1) + F(n-1)
    else: return n+1
print(G(4)+F(5))

Ответ: 33

Ошибка.
Попробуйте повторить позже

Задача 12#72418

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

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

$F (n) = n+ F (n − 1)$ , если $n$ чётно,

$F (n) = 3∗ F(n− 2)$ , если $n$ нечётно.

Чему равно значение функции $F(30)$ ? Для выполнения задания можно также написать программу или воспользоваться редактором электронных таблиц.

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

 def F(n):
     if n == 1:
         return 1
     if n%2==0:
         return n + F(n-1)
     if n%2!=0:
         return 3*F(n-2)

 print(F(30))

Ответ: 4782999

Ошибка.
Попробуйте повторить позже

Задача 13#64065

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

$F (n) = n$ , при $n ≥ 20$

$F (n) = F(n +1) +F (n+ 2)$ , при $n < 20$

Чему равно значение выражения $F(5)∕∕F(15)$ ?

Примечание. Под // подразумевается деление нацело.

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

def f(n):
    if n >= 20: return n
    return f(n + 1) + f(n + 2)
print(f(5) // f(15))

Ответ: 122

Ошибка.
Попробуйте повторить позже

Задача 14#64023

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

F(0) = 0;

F(n) = F(n - 1) + 3, если n > 0 и при этом n mod 3 = 2;

F(n) = F((n - n mod 3) / 3), если n > 0 и при этом n mod 3 < 2.

Укажите наименьшее возможное n, для которого F(n) = 6. Если таких значений нет, в ответе укажите -1.

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

def f(n):
# По условию n - натуральное
    if n == 0:
        return 99999999
    elif n > 0 and n % 3 == 2:
        return f(n - 1) + 3
    elif n > 0 and n % 3 < 2:
        return f((n - n % 3) / 3)

for i in range(1000):
    if f(i) == 6:
        print(i)

Ответ: -1

Ошибка.
Попробуйте повторить позже

Задача 15#63925

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

F(n) = n, при $n ≤ 3$

F(n) = 2*n + F(n - 1), при четном n и n > 3;

F(n) = n*n + F(n - 2), при нечетном n и n > 3;

Определите количество натуральных значений n на отрезке [1; 100], при которых F(n) кратно 3.

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

def f(n):
    if n <= 3:
        return n
    elif n % 2 == 0:
        return 2 * n + f(n - 1)
    else:
        return n * n + f(n - 2)
cnt = 0
for i in range(1, 101):
    x = f(i)
    if x % 3 == 0:
        cnt += 1
print(cnt)

Ответ: 32

Ошибка.
Попробуйте повторить позже

Задача 16#63835

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

$F (n) = 2∗ n∗n + 4∗ n+ 3$ , при $n ≤ 15$

$F (n) = F(n − 1) +n ∗n + 3$ , при $n > 15$ , кратных 3

$F (n) = F(n − 2) +n − 6$ , при $n > 15$ , не кратных 3

Определите количество натуральных значений n из отрезка [1; 1000], для которых все цифры значения F(n) нечётные.

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

def f(n):
    if n <= 15:
        return 2 * n * n + 4 * n + 3
    elif n > 15 and n % 3 == 0:
        return f(n - 1) + n * n + 3
    elif n > 15 and n % 3 != 0:
        return f(n - 2) + n - 6

cnt = []
for i in range(1, 1001):
    x = f(i)
    flag = True
    while x > 0:
        if (x % 10) % 2 == 0:
            flag = False
            break
        x //= 10
    if flag:
        cnt.append(i)
print(len(cnt))

Ответ: 27

Ошибка.
Попробуйте повторить позже

Задача 17#63532

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

$F (1) = 1$

$F (2) = 3$

$F (n) = F(n − 1) ⋅F(n− 2)+ n$ при $n > 2$

Чему равно значение функции $F(7)$ ?

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

def f(n):
    if n == 1:
        return 1
    elif n == 2:
        return 3
    elif n > 2:
        return f(n - 1)*f(n - 2) + n
print(f(7))

Ответ: 413747

Ошибка.
Попробуйте повторить позже

Задача 18#63343

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

$F (n) = 5+ n + F(n+ 2)$ , если $n < 100$

$F (n) = n+ 2$ , если $n ≥ 100$

Чему равно значение выражения $F(90)− F (101)$ ?

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

def F(n):
    if n>=100: return n+2
    if n<100: return 5+n+F(n+2)
print(F(90)-F(101))

Ответ: 494

Ошибка.
Попробуйте повторить позже

Задача 19#63342

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

$F (n) = n$ , если $n ≥ 256$

$F (n) = 2⋅F (n + 3)− F(n + 4) + 3⋅n$ , если $n < 256$

Чему равно значение выражения $F(8800)∕F(250)$ ?

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

def F(n):
    if n>=256: return n
    if n<256: return 2*F(n+3)-F(n+4)+3*n
print(F(8800)/F(250))

Ответ: 5

Ошибка.
Попробуйте повторить позже

Задача 20#63341

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

$F (n) = n$ , если $n ≤ 15$

$F (n) = F(n − 15) +n ∕∕3$ , если $15 < n ≤ 25$

$F (n) = F(n − 6)$ , если $n > 25$

Чему равно значение выражения $F(20)$ ?

Примечание. Запись // означает деление нацело.

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

def F(n):
    if n<=15: return n
    if 15<n<=25: return F(n-15)+n//3
    if n>25: return F(n-6)
print(F(20))

Ответ: 11