В 11 задании проверяется умение анализировать рекурсивные алгоритмы.
Рассмотрим на примере:
Решаю по алгоритму, написанному на языке Паскаль.
Что описано в алгоритме:
При вызове функции F(n) на экран выводится число n, затем если n>=3, то идет вызов функции F(n div 2) - т.е. целая часть от деления числа n на 2. И затем вызов функции F(n-1).
Выполним алгоритм при начальном вызове функции F(5).
F(5)= 5 F(2) F(4) (При вызове функции F(5) на экран выводится число 5, затем, т.к. 5>3, то идет вызов функции F(5 div 2) = F(2) - т.е. целая часть от деления числа 5 на 2. И затем вызов функции F(5-1) = F(4)).
В вызове F(5) есть еще два вызова процедуры F(2) и F(4). Проведем для них тот же алгоритм.
F(2) = 2 (При вызове функции F(2) на экран выводится число 2, затем т.к. 2<3, то вызова функций F(2 div 2) и F(2-1) не происходит)
F(4) = 4 F(2) F(3) (При вызове функции F(4) на экран выводится число 4, затем, т.к. 4>3, то идет вызов функции F(4 div 2) = F(2) - т.е. целая часть от деления числа 4 на 2. И затем вызов функции F(4-1) = F(3))
F(2) у нас уже есть.
F(3) = 3 F(1) F(2) (При вызове функции F(3) на экран выводится число 3, затем т.к. 3=3, то идет вызов функции F(3 div 2) = F(1) - т.е. целая часть от деления числа 3 на 2. И затем вызов функции F(3-1) = F(2))
Вызов функции F(1) = 1, т.к. 1<3.
Возвращаемся к началу:
F(5)= 5 F(2) F(4) = 5 2 4 F(2) F(3) = 5 2 4 2 3 F(1) F(2) = 5 2 4 2 3 1 2.
Это и есть ответ. Записываем БЕЗ ЗАПЯТЫХ ТОЧНО В ТАКОМ ПОРЯДКЕ.
Рассмотрим еще один пример:
Ниже на пяти языках программирования (я беру только один) записаны две рекурсивные функции (процедуры) F и G:
Сколько символов "*" будет напечатано на экране при выполнении вызова F(42)?
Рассмотрим, что происходит при вызове данных функций:
При вызове функции F(n) на экран выводится символ "*" и курсор переходит на следующую строку.
Далее, если n делится без остатка на 5, то происходит вызов функции G(n-5), если при таком делении есть остаток, то выполняется вызов функции F(n-3).
При вызове функции G(n) при условии что n>0 выполняется вызов функции F(n-1).
Вроде бы запутано, на самом деле ничего сложного.
F(42) = *F(39) (При вызове F(42) печатается символ *, затем, т.к. 42 делится на 5 с остатком, выполняется вызов F(42-3) = F(39).
F(39) = *F(36) (При вызове F(39) печатается символ *, затем, т.к. 39 делится на 5 с остатком, выполняется вызов F(39-3) = F(36).
F(36) = *F(33) (При вызове F(36) печатается символ *, затем, т.к. 36 делится на 5 с остатком, выполняется вызов F(36-3) = F(33).
F(33) = *F(30) (При вызове F(33) печатается символ *, затем, т.к. 33 делится на 5 с остатком, выполняется вызов F(33-3) = F(30).
F(30) = * G(25) (При вызове F(30) печатается символ *, затем, т.к. 30 делится на 5 без остатка, выполняется вызов G(30-5) = G(25).
G(25) = F(24) (При вызове G(25) т.к. 25>0, выполняется вызов F(24)
F(24) = * F(21) (При вызове F(24) печатается символ *, затем, т.к. 24 делится на 5 с остатком, выполняется вызов F(24-3) = F(21).
F(21) = *F(18) (При вызове F(21) печатается символ *, затем, т.к. 21 делится на 5 с остатком, выполняется вызов F(21-3) = F(18).
F(18) = *F(15) (При вызове F(18) печатается символ *, затем, т.к. 18 делится на 5 с остатком, выполняется вызов F(18-3) = F(15).
F(15) = * G(10) (При вызове F(15) печатается символ *, затем, т.к. 15 делится на 5 без остатка, выполняется вызов G(15-5) = G(10).
G(10) = F(9) (При вызове G(10) т.к. 10>0, выполняется вызов F(9)
F(9) = * F(6) (При вызове F(9) печатается символ *, затем, т.к. 9 делится на 5 с остатком, выполняется вызов F(9-3) = F(6).
F(6) = * F(3) (При вызове F(6) печатается символ *, затем, т.к. 6 делится на 5 с остатком, выполняется вызов F(6-3) = F(3).
F(3) = *F(0) (При вызове F(3) печатается символ *, затем, т.к. 3 делится на 5 с остатком, выполняется вызов F(3-3) = F(0).
F(0) = *G(-5) (При вызове F(0) печатается символ *, затем, т.к. 0 делится на 5 без остатка, выполняется вызов G(0-5) = G(-5).
Вызова G(-5) не происходит, т.к. -5 < 0.
Считаем "звездочки". У меня получилось 13. Это и есть ответ.
Если остались вопросы, пишите в комментариях. Обязательно отвечу. Если нужно разобрать конкретный пример, также - в комментарии.
Читайте также: Задание 1, Задание 2, Задание 3, Задание 4, Задание 5, Задание 6, Задание 7, Задание 8, Задание 9, Задание 10, Задание 12, Задание 13, Задание 14, Задание 15, Задание 18, Задание 19, Задание 22, Задание 16, Задание 17, Задание 20, Задание 21, Задание 23, Задание 24, Задание 25, Задание 26, Задание 27.