Тема 16. Рекурсия

16.02 Две функции

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

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

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

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

Подтемы раздела рекурсия

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

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

Задача 1#6316

Ниже на трёх языках программирования записан рекурсивный алгоритм F.

|--------------|----------------|-------------------------| |Python--------|C-+-+-----------|P-ascal------------------| |defF (n) : |voidF (intn ) |procedureF (n : integer );| | ifn > 1 : |{ | begin | | | | | | print(n) | if(n > 1) | if n > 1then | | F (n − 1) | { | begin | | print(n) | cout < < n; | writeln(n); | | | F (n − 1); | F (n − 1); | | | cout < < n; | writeln(n); | | | | | | | } |end | ----------------}----------------end-----------------------

Определите сумму цифр при вызове функции F(5)?

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

При вызове $F (1)$ программа ничего не выведет. Пропишем весь алгоритм, начиная с $F (2)$ :
$F (2) → 2F (1)2 = 22F (3) → 3F (2 )3 = 3223F (4) → 4F (3)4 = 432234F (5 ) → 5F (4)5 = 54322345$

$5 + 4 + 3 + 2 + 2 + 3 + 4 + 5 = 28$ И будет ответом на вопрос задачи.

Ответ: 28

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

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

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

Задача 2#6317

Ниже на трёх языках программирования записан рекурсивный алгоритм F.

|--------------|----------------|-------------------------| |Python--------|C-+-+-----------|P-ascal------------------| |defF (n) : |voidF (intn ) |procedureF (n : integer );| |print(n) |{ | begin | | | | | | ifn > 0 : |cout << n; | writeln (n); | | print(n) | if(n > 0) | if n > 0then | | F (n − 1) | { | begin | | | cout < < n; | writeln(n); | | | F (n − 1); | F (n − 1); | | | | | | | } |end | ----------------}----------------end-----------------------

Определите сколько знаков выведет программа при вызове функции F(5)?

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

При вызове $F (0)$ программа выведет 0. Пропишем весь алгоритм, начиная с $F (1)$ :
$F (1) → 11F (0) = 110F (2) → 22F (1) = 22110F (3) → 33F (2) = 3322110F (4) → 44F (3) = 443322110F (5) → 55F (4) = 55443322110$

Всего программа вывела $11$ знаков.Это - ответ на вопрос задачи.

Ответ: 11

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

Задача 3#6318

Ниже на трёх языках программирования записан рекурсивный алгоритм F.

|--------------|---------------|--------------------------| |P-ython-------|-C-+-+---------|P-ascal-------------------| |def F (n ) : | voidF(intn ) |procedureF (n : integer);| | print (n) | { | begin | | | | | | if n > 4 : | cout < < n; | writeln(n); | | F (n − 3)| if(n > 4) | if n > 4then | | F (n − 2)| { | begin | | | F (n − 3);| F (n − 3); | | | F (n − 2);| F (n − 2); | | | | | | | } |end | -----------------}--------------end-----------------------|

Определите, что выведет программа при вызове функции F(8)? Цифры запишите в той последовательности, в которой они выводятся.

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

При вызове $F (2)$ программа выведет 2, при вызове $F (3)$ программа выведет 3, при вызове $F (4)$ программа выведет 4. Пропишем весь алгоритм, начиная с $F (5)$ :
$F (5) → 5F (2)F (3) = 523F (6) → 6F (3)F (4) = 634F (7) → 7F (4)F (5) = 74523F (8) → 8F (5)F (6) = 8523634$

Программа вывела $8523634$ , это - ответ на вопрос задачи.

Ответ: 8523634

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

Задача 4#6319

Ниже на трёх языках программирования записан рекурсивный алгоритм F.

|--------------|-----------------------|--------------------------| |P ython |C + + |P ascal | |def-F-(n-) :---|voidF-(intn)-----------|procedureF--(n-: integer);| | | | | | print (n ) |{ | begin | | if n < 6 : | cout < < n < < endl;| writeln(n ); | | F(n + 1 )| if (n < 6){ | if n < 6then | | F(n ∗ 2) | F (n + 1); | begin | | | F (n ∗ 2); | F (n + 1); | | | | | | | } | F (n ∗ 2) | | |} | end | ----------------------------------------end-----------------------|

Определите, что выведет программа при вызове функции F(3)? Цифры запишите в той последовательности, в которой они выводятся.

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

При вызове $F (n ≥ 6)$ программа выведет $n$ . Пропишем весь алгоритм, начиная с конца:
$F (6) → 6 = 6F(5) → 5F (6)F(10) = 5610F (4 ) → 4F (5)F(8) = 456108F (3) → 3F (4)F (6) = 34561086$

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

Ответ: 34561086

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

Задача 5#6320

Ниже на трёх языках программирования записан рекурсивный алгоритм F.

|--------------|-----------------------|--------------------------| |P ython |C + + |P ascal | |def-F-(n-) :---|voidF-(intn)-----------|procedureF--(n-: integer);| | | | | | if n < 6 : |{ | begin | | print(n) | if (n < 6){ | if n < 6then | | F(n + 2 )| cout < < n < < endl;| begin | | F(n + 2 )| F (n + 2); | writeln(n ); | | | F (n + 2); | F (n + 2); | | | | | | | } | F (n + 2) | | |} | end | ----------------------------------------end-----------------------|

Определите сумму цифр при вызове функции F(1)?

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

При вызове $F (n ≥ 6)$ программа выведет $N OT HIN G$ . Пропишем весь алгоритм, начиная с конца:
$F (6) → N OT HIN GF (5 ) → 5F (7)F (7 ) = 5F (4) → 4F (6 )F (6) = 4F (3) → 3F (5)F (5) = 355F (2) → 2F (4)F (4) = 244F (1) → 1F (3)F (3)$

$1 + 3 + 5 + 5 + 3 + 5 + 5 = 27$ и будет ответом на вопрос задачи.

Ответ: 27

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

Задача 6#30454

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

$F (1) = ∗∗∗$ , $F(2) = ∗ ∗∗$ , $G (1) = ∗∗$ , $G (2) = ∗∗$

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

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

Посчитайте количество звездочек при выполнении вызова $F(13)$ .

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

def F(n):
    if n < 3:
        return 3
    return 3 + G(n - 1)

def G(n):
    if n < 3:
        return 2
    return F(n - 2) + 2

print(F(13))

Ответ: 23

Курсы

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

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

Задача 7#30455

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

$F (1) = ∗$ , $F(2) = ∗∗$ , $F(3) = ∗ ∗∗$ , $G (1) = ∗$ , $G (2) = ∗∗$

$F (n) = F(n − 3) +G (n− 3)+ ∗∗$ , при $n > 3$

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

Посчитайте количество звездочек при выполнении вызова $F(9)$ .

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

def F(n):
    if n < 4:
        return n
    return F(n - 3) + G(n - 3) + 2

def G(n):
    if n < 3:
        return n
    return G(n - 1) + F(n - 1)

print(F(9))

Ответ: 28

Интенсивы

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

Предыдущий раздел

Следующий раздел