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

16. Рекурсия

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


Алгоритм вычисления значения функции \(F(n)\), где \(n\) — натуральное число, задан следующими соотношениями:

\(F(1) = 1\), \(F(2) = 2\), \(F(3) = 4\);
\(F(n) = 5\cdot F(n - 1) + 3\cdot F(n -3)\), при \(n > 3\).

Чему равно значение функции \(F(5)\)?

 


Данная в условии формула \(F(n) = 5\cdot F(n - 1) + 3\cdot F(n -3)\) называется рекурретной. Это означает, что значение функции от некоторого аргумента зависит от значения функций от других аргументов. Так, чтобы найти значение \(F(n)\), нужно найти значение \(F(n-1)\) и \(F(n-3)\), а чтобы найти найти значение \(F(n-1)\), нужно найти значение \(F(n-1-1)\) и \(F(n-1-3)\) (аналогично для \(F(n-3)\)) и так далее (до момента, пока аргумент функции не станет меньше или равен 3, так как для таких аргументов значение функции известно из условия).

Нам даны значения функции для \(n = 1, \; 2, \; 3\), найдем значение функции \(F(5)\):

\(F(5) = 5\cdot F(4) + 3\cdot F(2)\);

Значение \(F(4)\) нам неизвестно, найдем его:

\(F(4) = 5\cdot F(3) + 3\cdot F(1) = 20 + 3 = 23\);

Подставим найденное значение в \(F(5)\):

\(F(5) = 5\cdot 23 + 3\cdot 2 = 115 + 6 = 121\).

Ответ: 121

Задание 2 #11996


Алгоритм вычисления значения функции \(F(n)\), где \(n\) — целое неотрицательное число, задан следующими соотношениями:

\(F(n) = n\), при \(n <3\);
\(F(n) = F(n - 1)\cdot F(n - 2) - F(n - 3)\), при \(n > 2\).

Чему равно значение функции \(F(4)\)?

 


Данная в условии формула \(F(n) = F(n - 1)\cdot F(n - 2) - F(n - 3)\) называется рекурретной. Это означает, что значение функции от некоторого аргумента зависит от значения функций от других аргументов. Так, чтобы найти значение \(F(n)\) при \(n > 2\), нужно найти значение \(F(n-1)\), \(F(n-2)\) и \(F(n-3)\), а чтобы найти найти значение \(F(n-1)\), нужно найти значение \(F(n-1-1)\), \(F(n-2-1)\) и \(F(n-3-1)\) (аналогично с поиском значения \(F(n-2)\) и \(F(n-3)\)) и так далее (до момента, пока аргумент функции не станет меньше или равен 2, так как для таких аргументов значение функции известно из формулы из условия).

Найдем значение функции \(F(4)\):

\(F(4) = F(3)\cdot F(2) - F(1)\);

Нам известны значения \(F(2)\), \(F(1)\) и \(F(0)\) (2, 1, 0), но неизвестно значение \(F(3)\). Найдем его:

\(F(3) = F(2)\cdot F(1) - F(0) = 2\cdot 1 - 0 = 2\);

Подставим найденные значения в \(F(4)\):

\(F(4) = 2\cdot 2 - 1 = 3\).

Ответ: 3

Задание 3 #11997


Алгоритм вычисления значения функции \(F(n)\), где \(n\) — натуральное число, задан следующими соотношениями:

\(F(1) = 1\), \(F(2) = 2\);
\(F(n)= F(n - 1) + 3\cdot F(n - 2)\), при \(n > 2\).

Чему равно значение функции \(F(6)\)?

 


Данная в условии формула \(F(n)= F(n - 1) + 3\cdot F(n - 2)\) называется рекурретной. Это означает, что значение функции от некоторого аргумента зависит от значения функций от других аргументов. Так, чтобы найти значение \(F(n)\) при \(n > 2\), нужно найти значение \(F(n-1)\) и \(F(n-2)\), а чтобы найти найти значение \(F(n-1)\), нужно найти значение \(F(n-1-1)\) и \(F(n-2-1)\) (аналогично с поиском значения \(F(n-2)\)) и так далее (до момента, пока аргумент функции не станет меньше или равен 2, так как для таких аргументов значение функции известно из условия).

Найдем значение функции \(F(6)\):

\(F(6)= F(5) + 3\cdot F(4)\);

\(F(5)= F(4) + 3\cdot F(3)\) ;

\(F(4)= F(3) + 3\cdot F(2)\) ;

\(F(3)= F(2) + 3\cdot F(1) = 2 + 3 = 5\);

\(F(4)= F(3) + 3\cdot F(2)= 5 + 6 = 11\);

\(F(5)= F(4) + 3\cdot F(3) = 11 + 15 = 26\);

\(F(6)= F(5) + 3\cdot F(4) = 26 + 33 = 59\).

Ответ: 59

Задание 4 #11998


Алгоритм вычисления значения функции \(F(n)\), где \(n\) — целое неотрицательное число, задан следующими соотношениями:

\(F(0)= 0\), \(F(1)=2\), \(F(2)=3\);
\(F(n)= F(n - 2) + 2\cdot F(n -3)\), при \(n > 2.\)

Чему равно значение функции \(F(7)\)?

 


Данная в условии формула \(F(n) = F(n - 2) + 2\cdot F(n -3)\) называется рекурретной. Это означает, что значение функции от некоторого аргумента зависит от значения функций от других аргументов. Так, чтобы найти значение \(F(n)\) при \(n > 2\), нужно найти значение \(F(n-2)\) и \(F(n-3)\), а чтобы найти найти значение \(F(n-2)\), нужно найти значение \(F(n-2-2)\) и \(F(n-3-2)\) (аналогично с поиском значения \(F(n-3)\)) и так далее (до момента, пока аргумент функции не станет меньше или равен 2, так как для таких аргументов значение функции известно из условия).

Нам даны значения \(F(0)\), \(F(1)\) и \(F(2)\). Найдем значение функции \(F(7)\):

\(F(7) = F(5) + 2\cdot F(4)\);

\(F(5) = F(3) + 2\cdot F(2)\);

\(F(4) = F(2) + 2\cdot F(1) = 3 + 2\cdot 2 = 7\);

\(F(3) = F(1) + 2\cdot F(0) = 2 + 0 = 2\);

\(F(5) = 2 + 2\cdot 3 = 2 + 6 = 8\);

\(F(7) = 8 + 2\cdot 7 = 8 + 14 = 22\).

Ответ: 22

Задание 5 #11999


Алгоритм вычисления значения функции \(F(n)\), где \(n\) — натуральное число, задан следующими соотношениями:

\(F(1) = 1\), \(F(2) = 3\), \(F(3) = 6\);
\(F(n) = F(n - 2) \cdot F(n - 3)\), при \(n > 3\).

Чему равно значение функции \(F(8)\)?

 


Данная в условии формула \(F(n) = F(n - 2) \cdot F(n - 3)\) называется рекурретной. Это означает, что значение функции от некоторого аргумента зависит от значения функций от других аргументов. Так, чтобы найти значение \(F(n)\) при \(n > 2\), нужно найти значение \(F(n-2)\) и \(F(n-3)\), а чтобы найти найти значение \(F(n-2)\), нужно найти значение \(F(n-2-2)\) и \(F(n-2-3)\) (аналогично с поиском значения \(F(n-3)\)) и так далее (до момента, пока аргумент функции не станет меньше или равен 3, так как для таких аргументов значение функции известно из условия).

Нам даны значения \(F(1)\), \(F(2)\) и \(F(3)\). Найдем значение функции \(F(8)\).

\(F(8) = F(6) \cdot F(5)\);

\(F(6) = F(4) \cdot F(3)\);

\(F(5) = F(3) \cdot F(2)\);

\(F(4) = F(2) \cdot F(1) = 3\cdot 1 = 3\);

\(F(5) = 6 \cdot 3 = 18\);

\(F(6) = 3 \cdot 6 = 18\);

\(F(8) = 18 \cdot 18 = 324\).

Ответ: 324

Задание 6 #12000


Алгоритм вычисления значения функции \(F(n)\), где \(n\) — целое неотрицательное число, задан следующими соотношениями:

\(F(n)= n\), при \(n < 3\);
\(F(n) = F(n - 1)\cdot F(n - 3) + 2\cdot F(n - 2)\), при \(n > 2\).

Чему равно значение функции \(F(6)\)?

 


Данная в условии формула \(F(n) = F(n - 1)\cdot F(n - 3) + 2\cdot F(n - 2)\) называется рекурретной. Это означает, что значение функции от некоторого аргумента зависит от значения функций от других аргументов. Так, чтобы найти значение \(F(n)\) при \(n > 2\), нужно найти значение \(F(n-1)\), \(F(n-3)\) и \(F(n-2)\), а чтобы найти найти значение \(F(n-1)\), нужно найти значение \(F(n-1-1)\), \(F(n-3-1)\) и \(F(n-2-1)\) (аналогично с поиском значения \(F(n-3)\)) и так далее (до момента, пока аргумент функции не станет меньше или равен 2, так как для таких аргументов значение функции известно из формулы из условия).

Найдем значение функции \(F(6)\):

\(F(6) = F(5)\cdot F(3) + 2\cdot F(4)\);

\(F(5) = F(4)\cdot F(2) + 2\cdot F(3)\);

\(F(4) = F(3)\cdot F(1) + 2\cdot F(2)\);

\(F(3) = F(2)\cdot F(0) + 2\cdot F(1) = 2\cdot 0 + 2\cdot 1 = 2\) ;

\(F(4) = 2\cdot 1 + 2\cdot 2 = 2 + 4 = 6\);

\(F(5) = 6\cdot 2 + 2\cdot 2 =12 + 4 = 16\);

\(F(6) = 16\cdot 2 + 2\cdot 6 = 32 + 12 = 44\).

Ответ: 44

Задание 7 #12001


Алгоритм вычисления значения функции \(F(n)\), где \(n\) — натуральное число, задан следующими соотношениями:

\(F(n) = n\), при \(n < 4\);
\(F(n) = 4\cdot F(n - 1) - 2\cdot F(n - 2)\cdot F(n - 3)\), при \(n > 2\).

Чему равно значение функции \(F(6)\)?

 


Данная в условии формула \(F(n) = 4\cdot F(n - 1) - 2\cdot F(n - 2)\cdot F(n - 3)\) называется рекурретной. Это означает, что значение функции от некоторого аргумента зависит от значения функций от других аргументов. Так, чтобы найти значение \(F(n)\) при \(n > 2\), нужно найти значение \(F(n-1)\), \(F(n-2)\) и \(F(n-3)\), а чтобы найти найти значение \(F(n-1)\), нужно найти значение \(F(n-1-1)\), \(F(n-2-1)\) и \(F(n-3-1)\) (аналогично с поиском значения \(F(n-2)\), \(F(n-2)\) и \(F(n-3)\)) и так далее (до момента, пока аргумент функции не станет меньше или равен 3, так как для таких аргументов значение функции известно из формулы из условия).

Найдем значение функции \(F(6)\):

\(F(8) = 4\cdot F(7) - 2\cdot F(6)\cdot F(5)\);

\(F(7) = 4\cdot F(6) - 2\cdot F(5)\cdot F(4)\);

\(F(6) = 4\cdot F(5) - 2\cdot F(4)\cdot F(3)\);

\(F(5) = 4\cdot F(4) - 2\cdot F(3)\cdot F(2)\);

\(F(4) = 4\cdot F(3) - 2\cdot F(2)\cdot F(1) = 4\cdot 3 - 2\cdot 2\cdot 1 = 12 - 4 = 8\);

\(F(5) = 4\cdot 8 - 2\cdot 3\cdot 2 = 32 - 12 = 20\);

\(F(6) = 4\cdot 20 - 2\cdot 8\cdot 3 = 80 - 48 = 32\).

Ответ: 32