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

16. Рекурсия

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

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

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

Задание 2 #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(4)? Цифры запишите в той последовательности, в которой они выводятся.

 

При вызове \(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

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

Задание 4 #15200

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

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

 

При вызове \(F(0)\) программа ничего не выведет. Пропишем весь алгоритм, начиная с единицы:
\( F(1)\rightarrow F(0) F(0) 1 = 1 \\ F(2)\rightarrow F(1) F(1) 2 = 112 \\ F(3)\rightarrow F(2) F(2) 3= 1121123\\ F(4)\rightarrow F(3) F(3) 4= 112112311211234\\ \)

\(112112311211234\) И будет ответом на вопрос задачи.

Ответ: 112112311211234

Задание 5 #15201

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

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

 

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

\(1213124\) И будет ответом на вопрос задачи.

Ответ: 1213124

Задание 6 #15202

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

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

 

При вызове \(F(0)\) и \(F(1)\) программа ничего не выведет. Пропишем весь алгоритм, начиная с \(F(2)\):
\( F(2)\rightarrow F(1) 2 F(0)= 2\\ F(3)\rightarrow F(2) 3 F(1)= 23\\ F(4)\rightarrow F(3) 4 F(2)= 2342\\ F(5)\rightarrow F(4) 5 F(3) = 2342523\\ \)

\(2342523\) И будет ответом на вопрос задачи.

Ответ: 2342523

Задание 7 #15203

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

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

 

При вызове \(F(0)\) и \(F(1)\) программа ничего не выведет. Пропишем весь алгоритм, начиная с \(F(2)\):
\( F(2)\rightarrow 2 F(1) F(0) = 2\\ F(3)\rightarrow 3 F(2) F(1)= 32\\ F(4)\rightarrow 4 F(3) F(2)= 4322\\ F(5)\rightarrow 5 F(4) F(3) = 5432232\\ \)

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

Ответ: 21