16. Рекурсия

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

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

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

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

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

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

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

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

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

Задание 22 #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

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

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

Задание 23 #16065

Ниже на трех языках программирования записана рекурсивная функция (процедура) $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 - 1) & \quad \quad F(n - 1);\\ \quad begin & \quad \quad print(n) &\quad \quad printf("\%d"\ , n); \\ \quad \quad F(n - 1); & \quad \quad F(n // 2) & \quad \quad F(n / 2);\\ \quad \quad writeln(n); & & \quad \textit{\}}\\ \quad \quad\textit{F(n div $2$);} & & \textit{\}}\\ \quad end;& & \\ end. & & \\ \hline \end{array}\]

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

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

$F(1) \to 1$;

$F(2) \to $

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

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

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

$F(3) \to $

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

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

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

$F(4) \to $

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

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

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

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

Ответ: 121314121

Задание 24 #16066

Ниже на трех языках программирования записана рекурсивная функция (процедура) $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 > $2$:} & \quad \textit{if (n > $2$)\{}\\ \quad \textit{if n > $2$ then} & \quad \quad F(n - 1) & \quad \quad F(n - 1);\\ \quad begin & \quad \quad F(n // 2) &\quad \quad F(n / 2); \\ \quad \quad F(n - 1); & \quad \quad print(n) & \quad \quad printf("\%d"\ , n);\\ \quad \quad \textit{F(n div $2$);} & & \quad \textit{\}}\\ \quad \quad writeln(n);& & \textit{\}}\\ \quad end;& & \\ end. & & \\ \hline \end{array}\]

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

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

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

$F(3) \to $

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

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

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

$F(4) \to $

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

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

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

$F(5) \to $

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

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

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

$F(6) \to $

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

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

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

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

Ответ: 34536

Задание 25 #15208

Ниже на трёх языках программирования записан рекурсивный алгоритм 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\; >\; 0: & \{ & \quad begin \\ \quad\quad print(n) & \quad if\; (n\; >\; 0) & \quad\quad if\; n\; >\; 0\; then \\ \quad\quad F(n\; -\; 3) & \quad \{ & \quad\quad\quad begin \\ \quad\quad F(n-2) & \quad\quad cout\; <<\; n; & \quad\quad\quad \; \; writeln(n); \\ \quad\quad F(n-1) & \quad\quad F(n-\; 3); & \quad\quad\quad \; \; \; F(n\; -\; 3); \\ \quad \; \; \; & \quad\quad F(n\; -\; 2); & \quad\quad\quad \; \; \; F(n-2); \\ & \quad\quad F(n-1); & \quad\quad\quad \; \; \; F(n-1); \\ & \quad \} & end \\ & \} & end \\ \hline \end{array}\]

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

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

При вызове $F(0)$, $F(-1)$ и $F(-2)$ программа ничего не выведет. Пропишем весь алгоритм, начиная с $F(1)$:
$ F(1)\rightarrow 1F(-2)F(-1)F(0) = 1\\ F(2)\rightarrow 2F(-1)F(0)F(1)= 21\\ F(3)\rightarrow 3F(0)F(1)F(2) = 3121\\ F(4)\rightarrow 4F(1)F(2)F(3)= 41213121\\ $

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

Ответ: 41213121

Задание 26 #15197

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

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

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

При вызове $F(0)$ программа выведет $0$. Пропишем весь алгоритм, начиная с единицы:

$ F(1)\rightarrow 1 F(0) F(0) = 100 \\ F(2)\rightarrow 2 F(1) F(1) = 2100100 \\ F(3)\rightarrow 3 F(2) F(2) = 321001002100100\\ $

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

Ответ: 321001002100100

Задание 27 #15198

Ниже на трёх языках программирования записан рекурсивный алгоритм 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\; >\; 0: & \{ & \quad begin \\ \quad\quad print(n) & \quad if\; (n\; >\; 0) & \quad\quad if\; n\; >\; 0\; then \\ \quad\quad F(n\; -\; 1) & \quad \{ & \quad\quad\quad begin \\ \quad\quad F(n\; -\; 1) & \quad\quad cout\; <<\; n; & \quad\quad\quad \; \; \; writeln(n); \\ & \quad\quad F(n\; -\; 1); & \quad\quad\quad \; \; \; F(n\; -\; 1); \\ & \quad\quad F(n\; -1\; ); & \quad\quad\quad \; \; \; F(n\; -\; 1) \\ & \quad \} & \quad\quad\quad end; \\ & \} & \quad end; \\ \hline \end{array}\]

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

При вызове $F(0)$ программа ничего не выведет. Пропишем весь алгоритм, начиная с единицы:

$ F(1)\rightarrow 1 F(0) F(0) = 1 \\ F(2)\rightarrow 2 F(1) F(1) = 211 \\ F(3)\rightarrow 3 F(2) F(2) = 3211211\\ F(4)\rightarrow 4 F(3) F(3) = 432112113211211 \\ $

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

Ответ: 432112113211211

Курсы

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

Задание 28 #15199

Ниже на трёх языках программирования записан рекурсивный алгоритм 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\; >\; 0: & \{ & \quad begin \\ \quad\quad F(n\; -\; 1) & \quad if\; (n\; >\; 0) & \quad\quad if\; n\; >\; 0\; then \\ \quad\quad print(n) & \quad \{ & \quad\quad\quad begin \\ \quad\quad F(n\; -\; 1) & \quad\quad F(n\; -\; 1); & \quad\quad\quad \; \; \; F(n\; -\; 1); \\ & \quad\quad cout\; <<\; n; & \quad\quad\quad \; \; \; writeln(n); \\ & \quad\quad F(n\; -1\; ); & \quad\quad\quad \; \; \; F(n\; -\; 1) \\ & \quad \} & \quad\quad\quad end; \\ & \} & \quad end; \\ \hline \end{array}\]

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

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

При вызове $F(0)$ программа ничего не выведет. Пропишем весь алгоритм, начиная с единицы:

$ F(1)\rightarrow F(0) 1 F(0) = 1 \\ F(2)\rightarrow F(1) 2 F(1) = 121 \\ F(3)\rightarrow F(2) 3 F(2) = 1213121\\ F(4)\rightarrow F(3) 4 F(3) = 121312141213121\\ $

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

Ответ: 26

Интенсивы

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

...

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

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