16. Рекурсия

Рекурсивные алгоритмы в программировании (страница 2)

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

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

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

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

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

Это старая версия каталога задач

Нажмите для перехода на новую версию

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

Задание 8 #15227

Ниже на трёх языках программирования записан рекурсивный алгоритм F. \[\begin{array}{ | l | l | l |} \hline Python & C++ & Pascal \\ \hline def\; F(n): & void\; F(int\; n) & procedure\; F(n:\; integer); \\ \quad if\; n\; <\; 10: & \{ & \quad begin \\ \quad\quad F(n\; +\; 6) & \quad if\; (n\; <\; \; 10)\; \{ & \quad if\; n\; <\; 10\; then \\ \quad\quad F(n\; +\; 3) & \quad\quad F(n\; +\; 6); & \quad \; begin \\ \quad\quad print(n) & \quad\quad F(n\; +\; 3); & \quad\quad \; \; \; F(n\; +\; 6); \\ & \quad cout\; <<\; n\; <<\; endl; & \quad\quad \; \; \; F(n\; +\; 3) \\ & \quad \} & \quad\quad writeln(n); \\ & \} & \quad \; end \\ & & end \\ \hline \end{array}\] Определите, что выведет программа при вызове функции F(1)? Цифры запишите в той последовательности, в которой они выводятся.

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

При вызове $F(n\geq10)$ программа выведет $NOTHING$. Пропишем весь алгоритм, начиная с конца:
$ F(10)\rightarrow NOTHING\\ F(9)\rightarrow F(15)F(12)9 = 9\\ F(8)\rightarrow F(14)F(11)8 = 8 \\ F(7)\rightarrow F(13) F(10)7= 7 \\ F(6)\rightarrow F(12)F(9)6= 96 \\ F(5)\rightarrow F(11) F(8) 5= 85\\ F(4)\rightarrow F(10)F(7) 4= 74 \\ F(3)\rightarrow F(9)F(6) 3= 9963 \\ F(2)\rightarrow F(8)F(5) 2= 8852 \\ F(1)\rightarrow F(7)F(4) 1= 7741 \\ $

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

Ответ: 7741

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

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

Задание 9 #15228

Ниже на трёх языках программирования записан рекурсивный алгоритм F. \[\begin{array}{ | l | l | l |} \hline Python & C++ & Pascal \\ \hline def\; F(n): & void\; F(int\; n) & procedure\; F(n:\; integer); \\ \quad if\; n\; <\; 10: & \{ & \quad begin \\ \quad\quad F(n\; +\; 3) & \quad if\; (n\; <\; \; 10)\; \{ & \quad if\; n\; <\; 10\; then \\ \quad\quad print(n) & \quad\quad F(n\; +\; 3); & \quad \; begin \\ \quad\quad F(n\; +\; 3) & \quad cout\; <<\; n\; <<\; endl; & \quad\quad \; \; \; F(n\; +\; 3); \\ & \quad\quad F(n\; +\; 3); & \quad\quad writeln(n); \\ & \quad \} & \quad\quad \; \; \; F(n\; +\; 3) \\ & \} & \quad \; end \\ & & end \\ \hline \end{array}\] Определите, что выведет программа при вызове функции F(3)? Цифры запишите в той последовательности, в которой они выводятся.

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

При вызове $F(n\geq10)$ программа выведет $NOTHING$. Пропишем весь алгоритм, начиная с конца:
$ F(10)\rightarrow NOTHING\\ F(9)\rightarrow F(12)9F(12)= 9\\ F(8)\rightarrow F(11)8F(11) = 8 \\ F(7)\rightarrow F(10)7F(10)= 7 \\ F(6)\rightarrow F(9)6F(9)= 969 \\ F(5)\rightarrow F(8)5F(8)=858 \\ F(4)\rightarrow F(7)4F(7)=747\\ F(3)\rightarrow F(6)3F(6)= 9693969 \\ $

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

Ответ: 9693969

Задание 10 #15229

Ниже на трёх языках программирования записан рекурсивный алгоритм F. \[\begin{array}{ | l | l | l |} \hline Python & C++ & Pascal \\ \hline def\; F(n): & void\; F(int\; n) & procedure\; F(n:\; integer); \\ \quad if\; n\; <\; 5: & \{ & \quad begin \\ \quad\quad print(n) & \quad if\; (n\; <\; \; 5)\; \{ & \quad if\; n\; <\; 5\; then \\ \quad\quad F(n\; *\; 2) & \quad cout\; <<\; n\; <<\; endl; & \quad \; begin \\ \quad\quad F(n\; *\; 2) & \quad\quad F(n\; *\; 2); & \quad\quad writeln(n); \\ & \quad\quad F(n\; *\; 2); & \quad\quad \; \; \; F(n\; *\; 2); \\ & \quad \} & \quad\quad \; \; \; F(n\; *\; 2) \\ & \} & \quad \; end \\ & & end \\ \hline \end{array}\] Определите, что выведет программа при вызове функции F(1)? Цифры запишите в той последовательности, в которой они выводятся.

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

При вызове $F(n\geq5)$ программа выведет $NOTHING$. Пропишем весь алгоритм, начиная с конца:
$ F(5)\rightarrow NOTHING\\ F(4)\rightarrow 4F(8)F(8)= 4\\ F(3)\rightarrow 3F(6)F(6) = 3 \\ F(2)\rightarrow 2F(4)F(4)= 244 \\ F(1)\rightarrow 1F(2)F(2)= 1244244 \\ $

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

Ответ: 1244244

Задание 11 #15230

Ниже на трёх языках программирования записан рекурсивный алгоритм F. \[\begin{array}{ | l | l | l |} \hline Python & C++ & Pascal \\ \hline def\; F(n): & void\; F(int\; n) & procedure\; F(n:\; integer); \\ \quad if\; n\; <\; 9: & \{ & \quad begin \\ \quad\quad print(n) & \quad if\; (n\; <\; 9)\; \{ & \quad if\; n\; <\; 9\; then \\ \quad\quad F(n\; *\; 3) & \quad cout\; <<\; n\; <<\; endl; & \quad \; begin \\ \quad\quad F(n\; *\; 2) & \quad\quad F(n\; *\; 3); & \quad\quad writeln(n); \\ \quad\quad F(n+1) & \quad\quad F(n\; *\; 2); & \quad\quad \; \; \; F(n\; *\; 3); \\ & \quad\quad F(n+1); & \quad\quad \; \; \; F(n\; *\; 2); \\ & \quad \} & \quad\quad \; \; \; F(n+1) \\ & \} & \quad \; end \\ & & end \\ \hline \end{array}\] Определите, что выведет программа при вызове функции F(3)? Цифры запишите в той последовательности, в которой они выводятся.

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

При вызове $F(n\geq9)$ программа выведет $NOTHING$. Пропишем весь алгоритм, начиная с конца:
$ F(9)\rightarrow NOTHING\\ F(8)\rightarrow 8F(24)F(16)F(9)= 8\\ F(7)\rightarrow 7F(21)F(14)F(8) =78 \\ F(6)\rightarrow 6F(18)F(12)F(7)= 678\\ F(5)\rightarrow 5F(15)F(10)F(6)= 5678 \\ F(4)\rightarrow 4F(12)F(8)F(5) = 485678\\ F(3)\rightarrow 3F(9)F(6)F(4) = 3678485678 \\ $

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

Ответ: 3678485678

Задание 12 #15231

Ниже на трёх языках программирования записан рекурсивный алгоритм F. \[\begin{array}{ | l | l | l |} \hline Python & C++ & Pascal \\ \hline def\; F(n): & void\; F(int\; n) & procedure\; F(n:\; integer); \\ \quad if\; n\; <\; 9: & \{ & \quad begin \\ \quad\quad F(n\; *\; 3) & \quad if\; (n\; <\; 9)\; \{ & \quad if\; n\; <\; 9\; then \\ \quad\quad print(n) & \quad\quad F(n\; *\; 3); & \quad \; begin \\ \quad\quad F(n\; *\; 2) & \quad cout\; <<\; n\; <<\; endl; & \quad\quad \; \; \; F(n\; *\; 3); \\ \quad\quad F(n+1) & \quad\quad F(n\; *\; 2); & \quad\quad writeln(n); \\ & \quad\quad F(n+1); & \quad\quad \; \; \; F(n\; *\; 2); \\ & \quad \} & \quad\quad \; \; \; F(n+1) \\ & \} & \quad \; end \\ & & end \\ \hline \end{array}\] Определите сумму цифр при вызове функции F(3)?

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

При вызове $F(n\geq9)$ программа выведет $NOTHING$. Пропишем весь алгоритм, начиная с конца:
$ F(9)\rightarrow NOTHING\\ F(8)\rightarrow F(24)8F(16)F(9)= 8\\ F(7)\rightarrow F(21)7F(14)F(8) =78 \\ F(6)\rightarrow F(18)6F(12)F(7)= 678\\ F(5)\rightarrow F(15)5F(10)F(6)= 5678 \\ F(4)\rightarrow F(12)4F(8)F(5) = 485678\\ F(3)\rightarrow F(9)3F(6)F(4) = 3678485678 \\ $

$3+6+7+8+4+8+5+6+7+8=62$ и будет ответом на вопрос задачи.

Ответ: 62

Задание 13 #16064

Ниже на трех языках программирования записана рекурсивная функция (процедура) $F$. \[\begin{array}{| l | l | l |} \hline \textbf{Pascal} & \textbf{Python} &\textbf{C}\\ \hline \textit{procedure F(n: integer);} & \textit{def F(n):} & \textit{void F(int n) \{} \\ \textit{begin} &\quad \textit{if n > 0:} & \quad \textit{if (n > 0) \{}\\ \quad \textit{if n > 0 then} & \quad \quad F(n - 2) & \quad \quad F(n - 2);\\ \quad begin & \quad \quad print(n) &\quad \quad printf("\%d"\ , n) \\ \quad \quad F(n - 2); & \quad \quad F(n - 3) & \quad \quad F(n - 3);\\ \quad \quad writeln(n); & & \quad \textit{\}}\\ \quad \quad F(n - 3); & & \textit{\}}\\ \quad end;& & \\ end. & & \\ \hline \end{array}\]

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

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

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

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

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

$F(3) \to $

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

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

$F(4) \to $

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

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

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

$F(5) \to $

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

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

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

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

Ответ: 1352

Курсы

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

Задание 14 #16062

Ниже на трех языках программирования записана рекурсивная функция (процедура) $F$. \[\begin{array}{| l | l | l |} \hline \textbf{Pascal} & \textbf{Python} &\textbf{C}\\ \hline \textit{procedure F(n: integer);} & \textit{def F(n):} & \textit{void F(int n) \{} \\ \textit{begin} &\quad \textit{print(n)} & \quad printf("\%d"\ , n);\\ \quad \textit{write(n);} & \quad \textit{if n > $4$:} & \quad \textit{if (n > $4$) \{}\\ \quad \textit{if n > $4$ then} & \quad \quad F(n - 3) & \quad \quad F(n - 3);\\ \quad begin & \quad \quad F(n - 2) &\quad \quad F(n - 2); \\ \quad \quad F(n - 3); & & \quad \textit{\}}\\ \quad \quad F(n - 2); & & \textit{\}}\\ \quad end; & & \\ end. & & \\ \hline \end{array}\] Что выведет программа при вызове $F(7)$? В ответе запишите последовательность выведенных цифр слитно (без пробелов).

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

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

$F(1) \to 1$; $F(2) \to 2$; $F(3) \to 3$; $F(4) \to 4$.

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

$F(5) \to 5$;

$\to F(2) \to 2$;

$\to F(3) \to 3$.

$F(6) \to 6$;

$\to F(3) \to 3$;

$\to F(4) \to 4$.

$F(7) \to 7$;

$\to F(4) \to 4$;

$\to F(5) \to 523$.

Следовательно, итоговая последовательность $\to 74523$.

Ответ: 74523

Интенсивы