Математика ЕГЭ
Русский язык ЕГЭ
Математика 5-7
Математика ОГЭ
Информатика
Физика
Обществознание
Кликните, чтобы открыть меню

16. Рекурсия

1. Вспоминай формулы по каждой теме
2. Решай новые задачи каждый день
3. Вдумчиво разбирай решения

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

Задание 1 #12092

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

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

При запуске \(F(3)\) на экране появляется один символ <<\( * \)>>. Далее никакие функции не вызываются. \(F(3) \to *\).

При запуске \(F(4)\) на экране появляется один символ <<\( * \)>>. Далее вызываются функции \(F(4 - 1 = 3)\) и \(F(4 / 2 = 2)\). Так как \(n > 2\), то смотрим на \(F(3)\) и добавляем количество символов от данной функции к количеству символов от \(F(4)\).

\(F(3) \to *\)

\(F(4) \to **\).

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

\(F(3) \to *\);

\(F(4) \to **\);

\(F(5) \to ***\) . Т.к. \(5 > 2\) печатется один символ <<\( * \)>> , а также вызывались функции \(F(4)\) и \(F(2)\). Так как \(n > 2\), то взяли кол-во символов только от \(F(4)\).

\(F(6) \to *****\). Т.к. \(6 > 2\) печатется один символ <<\( * \)>> , а также вызывались функции \(F(5)\) и \(F(3\)). Того 5 символов.

\(F(7) \to *******\). Т.к. \(7> 2\) печатется один символ <<\( * \)>> , а также вызывались функции \(F(6)\) и \(F(3)\). Того 7 символов.

Ответ: 7

Задание 2 #12093

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

Сколько символов <<\( * \)>> будет напечатано на экране при выполнении вызова \(F(9)\)?

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

При запуске F(5) появляется один символ <<\( * \)>>. Далее никакие функции не вызываются. \(F(5) \to *\).

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

\(F(5) \to *\)

\(F(6) \to *\)

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

\(F(5) \to *\)

\(F(6) \to *\)

\(F(7) \to **\).

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

\(F(8) \to ***\). Т.к. \(8 > 4\) печатется один символ <<\( * \)>> , а также вызываются функции \(F(6)\) и \(F(5)\). Получаем 3 символа.

\(F(9) \to ****\). Т.к. \(9 > 4\) печатется один символ <<\( * \)>>, а также вызываются функции \(F(7)\) и \(F(6)\). В итоге получаем 4 символа.

Ответ: 4

Задание 3 #12094

Ниже на трех языках программирования записана рекурсивная функция (процедура) \(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 \textit{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

Задание 4 #12095

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

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

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

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

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

\(F(5) \to 5\);

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

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

\(\to F(2) \to 2\).

\(F(6) \to 6\);

\(\to F(5) \to 5432\);

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

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

Следовательно, итоговая последовательность \(\to\) 6543243.

Ответ: 6543243

Задание 5 #12096

Ниже на трех языках программирования записана рекурсивная функция (процедура) \(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 \textit{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

Задание 6 #12097

Ниже на трех языках программирования записана рекурсивная функция (процедура) \(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 \textit{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\) обозначим печать числа на экране.

\(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

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