Тема 16. Рекурсивные алгоритмы

16.01 Одна функция

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела рекурсивные алгоритмы

Решаем задачи

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

Задача 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$ .

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

Решение динамикой:

f = [0]*4097
for n in range(1, 4097):
    if n == 0:
        f[n] = 0
    elif n > 0 and n % 2 == 0:
        f[n] = f[n//2]
    else:
        f[n] = 1 + f[n-1]
    if f[n] == 12:
        print(n)

Решение рекурсией:

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  # Начинаем проверять числа с 0
while F(i) != 12:  # Пока не нашли нужное число i
    i += 1  # Увеличиваем его на 1
print(i)

Ответ: 4095

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

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

Задача 2#5971

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

$F(1) = 1$ , $F (2) = 2$ , $F (3 ) = 4$ ;
$F (n) = 5 ⋅ F (n − 1) + 3 ⋅ F (n − 3)$ , при $n > 3$ .

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

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

Решение руками:

Данная в условии формула $F(n ) = 5 ⋅ F (n − 1) + 3 ⋅ F(n − 3)$ называется рекурретной. Это означает, что значение функции от некоторого аргумента зависит от значения функций от других аргументов. Так, чтобы найти значение $F (n)$ , нужно найти значение $F (n − 1)$ и $F (n − 3)$ , а чтобы найти найти значение $F (n − 1)$ , нужно найти значение $F (n − 1 − 1 )$ и $F (n − 1 − 3)$ (аналогично для $F (n − 3)$ ) и так далее (до момента, пока аргумент функции не станет меньше или равен 3, так как для таких аргументов значение функции известно из условия).

Нам даны значения функции для $n = 1, 2, 3$ , найдем значение функции $F(5)$ :

$F(5) = 5 ⋅ F (4) + 3 ⋅ F (2)$ ;

Значение $F (4 )$ нам неизвестно, найдем его:

$F(4) = 5 ⋅ F (3) + 3 ⋅ F (1) = 20 + 3 = 23$ ;

Подставим найденное значение в $F (5)$ :

$F(5) = 5 ⋅ 23 + 3 ⋅ 2 = 115 + 6 = 121$ .

Решение программой:

def f(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    if n == 3:
        return 4
    else:
        return 5 * f(n - 1) + 3 * f(n - 3)

print(f(5))

Ответ: 121

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

Задача 3#5972

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

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

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

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

Решение руками:

Данная в условии формула $F(n ) = F (n − 1) + 3 ⋅ F(n − 2 )$ называется рекурретной. Это означает, что значение функции от некоторого аргумента зависит от значения функций от других аргументов. Так, чтобы найти значение $F (n)$ при $n > 2$ , нужно найти значение $F (n − 1)$ и $F (n − 2)$ , а чтобы найти найти значение $F(n − 1)$ , нужно найти значение $F (n − 1 − 1)$ и $F (n − 2 − 1)$ (аналогично с поиском значения $F(n − 2)$ ) и так далее (до момента, пока аргумент функции не станет меньше или равен 2, так как для таких аргументов значение функции известно из условия).

Найдем значение функции $F (6)$ :

$F(6) = F (5) + 3 ⋅ F (4)$ ;

$F(5) = F (4) + 3 ⋅ F (3)$ ;

$F(4) = F (3) + 3 ⋅ F (2)$ ;

$F(3) = F (2) + 3 ⋅ F (1) = 2 + 3 = 5$ ;

$F(4) = F (3) + 3 ⋅ F (2) = 5 + 6 = 11$ ;

$F(5) = F (4) + 3 ⋅ F (3) = 11 + 15 = 26$ ;

$F(6) = F (5) + 3 ⋅ F (4) = 26 + 33 = 59$ .

Решение программой:

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

print(f(6))

Ответ: 59

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

Задача 4#5975

Ниже на трех языках программирования записана рекурсивная функция (процедура) $F$ .

|------------------------|-----------------|------------------| |Pascal |Python |C | |procedure-F(n:-integer);|def-F(n):--------|void-F(int-n){----| | | | | |begin | if n > 2: | if (n > 2){ | | if n > 2 then | print("∗ " ,)| printf("∗" ,); | | begin | F(n − 1 ) | F (n − 1); | | writeln("∗" ,); | F(n ∕∕2) | F (n∕2 ); | | F (n − 1); | | } | | | | | | F (n div 2 ); | |} | | end; | | | -end.----------------------------------------------------------

Сколько символов « $∗$ » будет напечатано на экране при выполнении вызова $F(7)$ ?

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

Решение руками:

Данная рекурсивная функция останавливается, если $n$ принимает значение 2 или меньше. Следовательно, начнем выполнение функции, когда $n = 3$ . С помощью стрелочки $→$ обозначим печать символа на экране.

При запуске $F (3)$ на экране появляется один символ « $∗$ ». Далее никакие функции не вызываются. $F (3) → ∗$ .

При запуске $F (4)$ на экране появляется один символ « $∗$ ». Далее вызываются функции $F (4 − 1 = 3)$ и $F (4∕2 = 2)$ . Так как $n > 2$ , то смотрим на $F(3)$ и добавляем количество символов от данной функции к количеству символов от $F (4)$ .

$F(3) → ∗$

$F(4) → ∗∗$ .

Далее действуем по тому же принципу, возвращаясь к предыдущим значениям и добавляя количество символов к текущему:

$F(3) → ∗$ ;

$F(4) → ∗∗$ ;

$F(5) → ∗ ∗ ∗$ . Т.к. $5 > 2$ печатется один символ « $∗$ » , а также вызывались функции $F (4)$ и $F (2)$ . Так как $n > 2$ , то взяли кол-во символов только от $F (4)$ .

$F(6) → ∗ ∗ ∗ ∗ ∗$ . Т.к. $6 > 2$ печатется один символ « $∗$ » , а также вызывались функции $F(5)$ и $F (3$ ). Того 5 символов.

$F(7) → ∗ ∗ ∗ ∗ ∗ ∗ ∗$ . Т.к. $7 > 2$ печатется один символ « $∗$ » , а также вызывались функции $F(6)$ и $F (3)$ . Того 7 символов.

Решение программой:

def f(n):
    if n > 2:
        print("*")
        f(n - 1)
        f(n // 2)

print(f(7))

Осталось посчитать, сколько таких символов "*"вывела программа.

Получаем ответ: $7.$

Ответ: 7

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

Задача 5#5976

Ниже на трех языках программирования записана рекурсивная функция (процедура) $F$ .

|------------------------|-----------------|------------------| |Pascal |Python |C | |procedure-F(n:-integer);|def-F(n):--------|void-F(int-n)-{---| | | | | |begin | if n > 4: | if (n > 4) { | | if n > 4 then | print("∗ " ,)| printf("∗" ,); | | begin | F(n − 2 ) | F (n − 2); | | writeln("∗" ,); | F(n − 3 ) | F (n − 3); | | F (n − 2); | | } | | | | | | F (n − 3); | |} | | end; | | | -end.----------------------------------------------------------

Сколько символов « $∗$ » будет напечатано на экране при выполнении вызова $F (9)$ ?

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

Решение руками:

Данная рекурсивная функция останавливается, если $n$ принимает значение 4 или меньше. Следовательно, начнем выполнение функции, когда $n = 5$ . С помощью стрелочки $→$ обозначим печать символа на экране.

При запуске F(5) появляется один символ « $∗$ ». Далее никакие функции не вызываются. $F (5) → ∗$ .

При запуске $F (6)$ появляется один символ « $∗$ ». Далее вызываются функцит $F (6 − 2 = 4)$ и $F (6 − 3 = 3)$ . Так как $n > 4$ , то функции $F (4)$ и $F (3)$ не вызываются.

$F(5) → ∗$

$F(6) → ∗$

При запуске $F (7)$ появляется один символ « $∗$ ». Далее вызываются функцит $F (7 − 2 = 5)$ и $F (7 − 3 = 4)$ . Так как $n > 4$ , то смотрим только на $F (5)$ и добавляем количество символов от данной функции к количеству символов от $F(7)$ .

$F(5) → ∗$

$F(6) → ∗$

$F(7) → ∗∗$ .

$F(8) → ∗ ∗ ∗$ . Т.к. $8 > 4$ печатется один символ « $∗$ » , а также вызываются функции $F (6 )$ и $F (5)$ . Получаем 3 символа.

$F(9) → ∗ ∗ ∗∗$ . Т.к. $9 > 4$ печатется один символ « $∗$ », а также вызываются функции $F (7)$ и $F (6)$ . В итоге получаем 4 символа.

Решение программой:

def f(n):
    if n > 4:
        print("*")
        f(n - 2)
        f(n - 3)

print(f(9))

Осталось посчитать, сколько таких символов "*"вывела программа.

Получаем ответ: $4.$

Ответ: 4

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

Задача 6#5977

Ниже на трех языках программирования записана рекурсивная функция (процедура) $F$ .

|-------------------------|--------------|----------------------| |Pascal |Python |C | |procedure-F(n:-integer);-|def F-(n):----|void-F(int n-){-------| | | | | |begin | if n > 0: | if (n > 0){ | | if n > 0 then | F (n − 1) | F (n − 1); | | begin | print(n) | printf("%d " , n);| | F(n − 1 ); | F (n∕∕2) | F (n∕2); | | writeln(n); | | } | | | | | | F(n div 2); | |} | | end; | | | -end.-----------------------------------------------------------|

Что выведет программа при вызове $F (4)$ ? В ответе запишите последовательность выведенных цифр слитно (без пробелов).

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

Решение руками:

Рассмотрим последовательно, что будет выводится на экран, начиная с $F (1)$ . С помощью стрелочки $→$ обозначим печать числа на экране.

$F(1) → 1$ ;

$F(2) →$

$→ F (1) → 1$ (Выводится число, которое было получено от $F (1)$ );

$→ n → 2$ (Выводится текущее значение $n$ );

$→ F (1) → 1$ (Выводится число, которое было получено от $F (1)$ ).

$F(3) →$

$→ F (2) → 121$ (Выводится число, которое было получено от $F(2)$ );

$→ n → 3$ (Выводится текущее значение $n$ );

$→ F (1) → 1$ (Выводится число, которое было получено от $F (1)$ ).

$F(4) →$

$→ F (3) → 12131$ (Выводится число, которое было получено от $F (3)$ );

$→ n → 4$ (Выводится текущее значение $n$ );

$→ F (2) → 121$ (Выводится число, которое было получено от $F(2)$ ).

Следовательно, итоговая последовательность $→ 121314121$ .

Решение программой:

def f(n):
    if n > 0:
        f(n - 1)
        print(n)
        f(n // 2)

print(f(4))

Запишем последовательность чисел, которые вывела программа, в ответ.

Получаем: $121314121.$

Ответ: 121314121

Курсы

Всё необходимое для достижения цели

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

Задача 7#6306

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

$F(0) = 1$

$F(1) = 2$

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

Определите значение $F (6).$

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

def f(n):
    if n == 0:
        return 1
    if n == 1:
        return 2
    if n > 1:
        return f(n - 1) * f(n - 2) - f(n - 2)

print(f(6))

Ответ: 1

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

Задача 8#6307

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

$F(0) = 1$

$F(1) = 2$

$F(2) = 3$

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

Определите значение $F (5).$

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

Решение программой:

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

print(f(5))

Получаем ответ: $− 9.$

Решение руками:

Нам даны $F(0)$ , $F (1)$ , $F(2)$ . Используем их, чтобы подставить в формулу:

$F(0) F(3) = F (2) − F (1) = 3 − 2 = 1$

$F(1) F(4) = F (3) − F (2) = 1 − 3 = − 2$

$F(5) = F (4)F(2) − F (3) = (− 2)3 − 1 = − 8 − 1 = − 9$

$− 9$ и пишем в ответ.

Ответ: -9

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

Задача 9#6308

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

$F(0) = 1$

$F(1) = 3$

$F(2) = 3$

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

Определите значение $F (4).$

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

Решение руками:

Нам даны $F(0)$ , $F (1)$ , $F(2)$ . Используем их, чтобы подставить в формулу:

$F(3) = F (1) ⋅ F(2)F(0) + F (1) = 3 ⋅ 3 + 3 = 12$

$F(1) 3 F(4) = F (1) ⋅ F(3) + F (2) = 3 ⋅ 12 + 3 = 5187$

$5187$ и пишем в ответ.

Решение программой:

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

print(f(4))

Получаем ответ: $5187.$

Ответ: 5187

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

Задача 10#6309

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

$F(1) = 2$

$F(2) = 3$

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

Определите значение $F (4).$

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

Решение руками:

Нам даны $F(1)$ , $F (2)$ . Подставим их в формулу:

$F(3) = 2 ⋅ F (2)F(1) + 2 = 2 ⋅ 32 + 2 = 18 + 2 = 20$

$F(2) 3 F(4) = 2 ⋅ F (3) + 2 = 2 ⋅ 20 + 2 = 16000 + 2 = 16002$

$16002$ и пишем в ответ.

Решение программой:

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

print(f(4))

Получаем ответ: $16002.$

Ответ: 16002

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

Задача 11#6310

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

$F(− 1) = 1$

$F(0) = 1$

$F(n ) = F (n − 1) ⋅ F (n − 1) + F (n − 1) + F (n − 2)$ . При $n > 0$ .

Определите значение $F (3).$

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

Решение руками:

Нам даны $F(− 1)$ , $F (0)$ . Подставим их в формулу:

$F(1) = F (0) ⋅ F(0) + F (0) + F (− 1) = 1 + 1 + 1 = 3$

$F(2) = F (1) ⋅ F(1) + F (1) + F (0) = 9 + 3 + 1 = 13$

$F(3) = F (2) ⋅ F(2) + F (2) + F (1) = 169 + 13 + 3 = 185$

$185$ и пишем в ответ.

Решение программой:

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

print(f(3))

Получаем ответ: $185.$

Ответ: 185

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

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

Задача 12#6311

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

$F(0) = 2$

$F(1) = 3$

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

Определите значение $F (5).$

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

Решение руками:

В условии нам даны $F (0)$ и $F (1)$ . Используем их для решения задачи:

$F(2) = F (0) ⋅ F(1) + 2 = 2 ⋅ 3 + 2 = 8$

$F(3) = F (1) ⋅ F(2) + 3 = 3 ⋅ 8 + 3 = 24 + 3 = 27$

$F(4) = F (2) ⋅ F(3) + 4 = 8 ⋅ 27 + 4 = 220$

$F(5) = F (3) ⋅ F(4) + 5 = 27 ⋅ 220 + 5 = 5945$

$5945$ и будет ответом на вопрос задачи.

Решение программой:

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

print(f(5))

Получаем ответ: $5945.$

Ответ: 5945

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

Задача 13#6312

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

$F(1) = 2$

$F(n ) = n ⋅ n + F(n − 1)$ . При $n > 1$ .

Определите значение $F (7).$

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

Решение руками:

В условии нам дано $F (1)$ . Подставим его значение в формулу для решения задачи:

$F(2) = 2 ⋅ 2 + F (1) = 4 + 2 = 6$

$F(3) = 3 ⋅ 3 + F (2) = 15$

$F(4) = 4 ⋅ 4 + F (3) = 16 + 15 = 31$

$F(5) = 5 ⋅ 5 + F (4) = 25 + 31 = 56$

$F(6) = 6 ⋅ 6 + F (5) = 36 + 56 = 92$

$F(7) = 7 ⋅ 7 + F (6) = 49 + 92 = 141$

$141$ и будет ответом на вопрос задачи.

Решение программой:

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

print(f(7))

Получаем ответ: $141.$

Ответ: 141

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

Задача 14#6313

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

$F(0) = 1$

$F(1) = 2$

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

Определите значение $F (6).$

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

Решение руками:

В условии нам даны $F (0)$ , $F (1)$ , $F (2)$ . Используем их значения для решения задачи:

$F(2) = F (1) ⋅ 1 + F (0) = 2 + 1 = 3$

$F(3) = F (2) ⋅ 2 + F (1) = 3 ⋅ 2 + 2 = 8$

$F(4) = F (3) ⋅ 3 + F (2) = 8 ⋅ 3 + 3 = 27$

$F(5) = F (4) ⋅ 4 + F (3) = 108 + 8 = 116$

$F(6) = F (5) ⋅ 5 + F (4) = 116 ⋅ 5 + 27 = 607$

$607$ и будет ответом на вопрос задачи.

Решение программой:

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

print(f(6))

Получаем ответ: $607.$

Ответ: 607

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

Задача 15#6314

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

$F(0) = 1$

$F(1) = 2$

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

Определите значение $F (5).$

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

Решение руками:

В условии нам даны $F (0)$ , $F (1)$ . Так давайте используем их для решения задачи:

$F(2) = 3 ⋅ F (1) + F (0) = 6 + 1 = 7$

$F(3) = 4 ⋅ F (2) + F (1) = 28 + 2 = 30$

$F(4) = 5 ⋅ F (3) + F (2) = 150 + 7 = 157$

$F(5) = 6 ⋅ F (4) + F (3) = 942 + 30 = 972$

$972$ и будет ответом на вопрос задачи.

Решение программой:

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

print(f(5))

Получаем ответ: $972.$

Ответ: 972

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

Задача 16#6345

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

$F(− 1) = 0$
$F (0) = 1$
$F (1) = 1$
$F (n) = F (n − 1) ⋅ F (n − 2) − F (n − 3),$
при $n > 1.$

Определите значение $F (6).$

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

Решение руками:

Нам даны $F(− 1),$ $F (0)$ и $F (1 )$ . Используем их и подставляем в формулу:

$F (2) = F (1) ⋅ F (0) − F(− 1) = 1$

$F(3) = F (2) ⋅ F(1) − F (0) = 0$

$F(4) = F (3) ⋅ F(2) − F (1) = − 1$

$F(5) = F (4) ⋅ F(3) − F (2) = − 1$

$F(6) = F (5) ⋅ F(4) − F (3) = 1$

$1$ и будет ответом на задание.

Решение программой:

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

print(f(6))

Получаем ответ: $1.$

Ответ: 1

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

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

Задача 17#6354

Процедура $F (n)$ совершает следующие действия:

Вывод на экран значения $n$
Если $n ≥ 5$ , вызов следующих процедур: $F (n − 1)$ ; $F (n − 2)$ ; $F (n − 3)$

Что выведет программа при вызове $F (6)$ ? В ответе запишите последовательность выведенных цифр слитно (без пробелов).

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

Решение руками:

Рассмотрим последовательно, что будет выводится на экран, начиная с $F(1)$ . Пока $n < 5$ другие функции вызываться не будут. С помощью стрелочки $→$ обозначим печать числа на экране.

$F(1) → 1$ ; $F (2 ) → 2$ ; $F (3) → 3$ ; $F (4) → 4$ .

Далее при $n ≥ 5$ дополнительно будут вызываться функции. Мы будем возвращаться каждый раз к предыдущим значениям и добавлять числа в последовательность:

$F(5) → 5$ ;

$→ F (4) → 4$ ;

$→ F (3) → 3$ ;

$→ F (2) → 2$ .

$F(6) → 6$ ;

$→ F (5) → 5432$ ;

$→ F (4) → 4$ ;

$→ F (3) → 3$ .

Следовательно, итоговая последовательность $→$ 6543243.

Решение программой:

def f(n):
    print(n)
    if n >= 5:
        f(n - 1)
        f(n - 2)
        f(n - 3)

print(f(6))

Получаем ответ: $6543243.$

Ответ: 6543243

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

Задача 18#6355

Процедура $F (n)$ совершает следующие действия:

(| F (n - 2) { n > 0 : В ыво д n |( F (n - 3)

Что выведет программа при вызове $F (5)$ ? В ответе запишите последовательность выведенных цифр слитно (без пробелов).

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

Решение руками:

$F(1) → 1$ (Выводится только текущее значение $n$ , другие функции не вызываются);

$F(2) → 2$ (Выводится только текущее значение $n$ , другие функции не вызываются);

$F(3) →$

$→ F (1) → 1$ (Выводится число, которое было получено от $F (1)$ ;

$→ n → 3$ (Выводится текущее значение $n$ ).

$F(4) →$

$→ F (2) → 2$ (Выводится число, которое было получено от $F (2)$ );

$→ n → 4$ (Выводится текущее значение $n$ );

$→ F (1) → 1$ (Выводится число, которое было получено от $F (1)$ ).

$F(5) →$

$→ F (3) → 13$ (Выводится число, которое было получено от $F(3)$ );

$→ n → 5$ (Выводится текущее значение $n$ );

$→ F (2) → 2$ (Выводится число, которое было получено от $F (2)$ ).

Следовательно, итоговая последовательность $→ 1352$ .

Решение программой:

def f(n):
    if n > 0:
        f(n - 2)
        print(n)
        f(n - 3)

print(f(5))

Получаем ответ: $1352.$

Ответ: 1352

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

Задача 19#6356

Процедура $F (n)$ совершает следующие действия:

(| F(n - 1) { n > 2 : F(n // 2) |( Вы вод n

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

Данная рекурсивная функция останавливается, если $n$ принимает значение 2 или меньше. Следовательно, начнем выполнение функции, когда $n = 3$ .

С помощью стрелочки $→$ обозначим печать символа на экране.Рассмотрим последовательно, что будет выводится на экран, начиная с $F (3)$ :

$F(3) →$

$→ F (2) → ∘$ (От данного значения нет вывода числа на экран);

$→ F (1) → ∘$ (От данного значения нет вывода числа на экран);

$→ n → 3$ (Выводится текущее значение $n$ ).

$F(4) →$

$→ F (3) → 3$ (Выводится число, которое было получено от $F (3)$ в предыдущем шаге);

$→ F (2) → ∘$ (От данного значения нет вывода числа на экран);

$→ n → 4$ (Выводится текущее значение $n$ ).

$F(5) →$

$→ F (4) → 34$ (Выводится число, которое было получено от $F(4)$ в предыдущем шаге);

$→ F (2) → ∘$ (От данного значения нет вывода числа на экран);

$→ n → 5$ (Выводится текущее значение $n$ ).

$F(6) →$

$→ F (5) → 345$ (Выводится число, которое было получено от $F(5)$ в предыдущем шаге);

$→ F (3) → 3$ (Выводится число, которое было получено от $F (3)$ );

$→ n → 6$ (Выводится текущее значение $n$ ).

Следовательно, итоговая последовательность $→ 34536$ .

Ответ: 34536

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

Задача 20#6363

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

$F(− 1) = 0$

$F(0) = 1$

$F(1) = 1$

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

Определите значение $F (6).$

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

Решение руками:

Нам даны $F(− 1),$ $F (0)$ и $F (1 )$ . Используем их и подставляем в формулу:

$F(2) = F (1) ⋅ F(0) − F (− 1) = 1$

$F(3) = F (2) ⋅ F(1) − F (0) = 0$

$F(4) = F (3) ⋅ F(2) − F (1) = − 1$

$F(5) = F (4) ⋅ F(3) − F (2) = − 1$

$F(6) = F (5) ⋅ F(4) − F (3) = 1$

1 и будет ответом на задание.

Решение программой:

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

print(f(6))

Получаем ответ: $1.$

Ответ: 1