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

16. Рекурсия

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

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

Задание 1 #15226


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

 


При вызове \(F(n\geq9)\) программа выведет \(NOTHING\). Пропишем весь алгоритм, начиная с конца:
\( F(9)\rightarrow NOTHING\\ F(8)\rightarrow F(13)F(10)8 = 8 \\ F(7)\rightarrow F(12) F(9)7= 7 \\ F(6)\rightarrow F(11)F(8)6= 86 \\ F(5)\rightarrow F(10) F(7) 5= 75\\ F(4)\rightarrow F(9)F(6) 4= 864 \\ F(3)\rightarrow F(8)F(5) 3= 8753 \\ F(2)\rightarrow F(7)F(4) 2= 78642 \\ F(1)\rightarrow F(6)F(3) 1= 8687531 \\ \)

\(8+6+8+7+5+3+1=38\) и будет ответом на вопрос задачи.

Ответ: 38

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

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

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

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

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

Задание 7 #15223


Ниже на трёх языках программирования записан рекурсивный алгоритм 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\; <\; 6: & \{ & \quad begin \\ \quad\quad print(n) & \quad if\; (n\; <\; \; 6)\; \{ & \quad if\; n\; <\; 6\; 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\geq6)\) программа выведет \(NOTHING\). Пропишем весь алгоритм, начиная с конца:
\( F(6)\rightarrow NOTHING\\ F(5)\rightarrow 5 F(7)F(7) = 5 \\ F(4)\rightarrow 4 F(6)F(6) = 4 \\ F(3)\rightarrow 3 F(5) F(5) = 355 \\ F(2)\rightarrow 2 F(4) F(4) = 244 \\ F(1)\rightarrow 1 F(3) F(3) = 1355355\\ \)

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

Ответ: 27