Рекурсия python задачи егэ - Помощь в подготовке к экзаменам и поступлению

Шестнадцатое задание из ЕГЭ по информатике 2022 даётся на рекурсию.

Это задание нужно делать с помощью компьютера.

В программировании рекурсией называется процесс, когда функция вызывает сама себя или, когда две функции попарно вызывают друг друга.

Мы будем писать все программы на языке программирования Python.

Что такое Функция в языке программирования Python ?

Функция – это подпрограмма, результатом работы которой может является определенное значение.

Рассмотрим пример функции, которая суммирует два числа!

def F(x, y):
    s = x + y
    return s

a = int(input())
b = int(input())

r = F(a, b)

print(r)

Здесь функция F, которая суммирует два числа.

В главной части программы запрашиваются два числа с клавиатуры: a и b! Эти два числа передаются в функцию F. В функции эти числа кладутся в локальные переменные x и y. Сумма переменных x и y записывается в переменную s. Переменная s возвращается, как результат работы функции F.

Результат работы функции будет помещён в переменную r (в строке r = F(a, b)) в основной части программы.

Таким образом, в переменной r будет сумма двух переменных a и b.

Функции позволяют сократить программный код для однотипных расчётов.

Тренировочные задачи 16 задания из ЕГЭ по информатике 2023

Задача (Стандартная)

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

F(n) = 1 при n = 1;
F(n) = n + F(n − 1), если n – чётно,
F(n) = 3 × F(n − 2), если n > 1 и при этом n – нечётно.

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

Решение:

Напишем программу для решения данной задачи. В начале опишем все правила, которые даны в условии задачи для функции. В основной части программы запустим эту функцию.

# Сама функция
def F(n):
    if n==1: return 1
    if n%2==0: return n+F(n-1)
    if n>1 and n%2!=0: return 3*F(n-2)
    
# Основная часть программы
print(F(25))

После запуска рекурсивной функции программа выведет ответ 531441.

Выражение n%2 != 0 (остаток от деления на «2» не равен нулю) обозначает нечётное число. Выражение n%2==0 обозначает чётное число.

Ответ: 531441

Продолжаем тренировку по подготовке к 16 заданию ЕГЭ по информатике 2022.

Задача (Продолжаем подготовку)

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

F(1) = 1
F(2) = 3
F(n) = F(n–1) * n + F(n–2) * (n – 1) , при n > 2

Чему равно значение функции F(8)? В ответе запишите только натуральное число.

Решение:

# Сама функция
def F(n):
    if n==1: return 1
    if n==2: return 3
    if n>2: return F(n-1)*n + F(n-2)*(n-1)
    
# Основная часть программы
print(F(8))

Ответ получается 148329.

Ответ: 148329

Закрепляющий пример на рекурсию 16 задания из ЕГЭ по информатике 2022.

Задача(Две функции)

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

F(n) = 0, если n <= 2,
F(n) = G(n — 2), если n > 2

G(n) = 0, n <= 1,
G(n) = F(n — 1) + n, если n > 1

Чему равно значение функции F(8)? В ответе запишите только натуральное число.

Решение:

# Сами функции
def F(n):
    if n<=2: return 0
    if n>2: return G(n-2)

def G(n):
    if n<=1: return 0
    if n>1: return F(n-1)+n

# Основная часть программы
print(F(8))

Получается ответ 9.

Ответ: 9

Задача (Количество значений)

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

F(n) = 2*n*n*n + 1, при n > 25
F(n) = F(n+2) + 2*F(n+3), при n ≤ 25

Определите количество натуральных значений n из отрезка [1; 1000], для которых значение F(n) кратно 11.

Решение:

# Сама функция
def F(n):
    if n>25: return 2*n*n*n + 1
    if n<=25: return F(n+2) + 2*F(n+3)

k=0

# Перебираем диапазон
for i in range(1, 1001):
    if F(i)%11==0:
        k=k+1

print(k)

В начале формируем функцию F. Затем перебираем числа из диапазона от 1 до 1000. Каждое число подставляем в функцию F. Если значение функции F делится на 11, то мы зачитываем такое значение i.

В ответе получается 91.

Ответ: 91

Задача (Используем глобальную переменную)

Решение:

При решении этой задачи можно применить глобальную переменную.

def F(n):
    global s
    s=s+1
    if n>=1:
        s=s+1
        F(n-1)
        F(n-2)
        s=s+1

s=0
F(35)
print(s)

Здесь внутри функции заводим глобальную переменную s, которая будет подсчитывать количество напечатанных звёздочек. Теперь эту переменную видно при любом вызове функции, и при каждом вызове функции она будет одна и та же переменная. Вместо печати звёздочек пишем конструкцию s=s+1.

В основной части программы перед первым запуском функции переменной s присваиваем 0.

Программа может немного медленно работать из-за большой глубины рекурсии, но через минуту выведет число 96631265.

Ответ: 96631265

Новые тенденции

В последнее время мы видим тенденцию в 16 задании из ЕГЭ по информатике 2023, что теперь мало переписать функцию и её запустить. Необходимо подумать, как можно преобразовать то рекурсивное выражение, которое нужно вычислить.

Задача (Новое веяние)

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

F(n) = 2, если n = 1,
F(n) = 2 · F(n – 1), если n > 1.

Чему равно значение выражения F(1900)/2¹⁸⁹⁰ ?

Решение:

1 Способ (Аналитическое решение)

Если мы просто перепишем функцию и попытаемся вычислить выражение F(1900)/2¹⁸⁹⁰, то получим ошибку RecursionError: maximum recursion depth exceeded. Возникает она из-за слишком большой цепочки вызовов функции.

В подобных задачах нужно попытаться самому упростить выражение, которое пытаемся вычислить. Посмотрим, что из себя представляет функция.

F(1900) = 2*F(1899) = 2*2*F(1898) = … 2¹⁹⁰⁰

Тогда

F(1900)/2¹⁸⁹⁰ = 2¹⁹⁰⁰/2¹⁸⁹⁰ = 2¹⁰ = 1024

Получается 1024.

2 Способ (Через lru_cache)

Чтобы уменьшить цепочку вызовов функции, можно использовать инструмент lru_cache.

from functools import lru_cache

@lru_cache(None)
def F(n):
    if n==1: return 2
    if n>1: return 2*F(n-1)

for i in range(2, 1900):
    F(i)

print(F(1900)/2**1890)

В задаче функция опирается на значение функции от n-1 и т.д. За счёт этого происходят длинные вычисления для каждого числа n.

Использовав инструмент lru_cache, мы пробегаемся в цикле по значениям n в возрастающем порядке, и для каждого значения сохраняем результаты функции. Таким образом, вычисляя очередное значение, программа опирается на уже готовый результат, тем самым цепочка вызовов функции будет маленькой.

Ответ: 1024

Задача(Новое веяние, закрепление)

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

F(n) = 1 при n ≤ 2;
F(n) = n * F(n-2), если n > 2.

Чему равно значение выражение F(3000)/F(2996) ?

Решение:

1 Способ (Аналитическое решение)

Начнём расписывать F(3000).

F(3000) = 3000*F(2998) = 3000*2998*F(2996)

Получается:

F(3000)/F(2996) = 3000*2998*F(2996)/F(2996) = 3000*2998 = 8994000

2 Способ (Через lru_cache)

from functools import lru_cache

@lru_cache(None)
def F(n):
    if n<=2: return 1
    if n>2: return n*F(n-2)

for i in range(2, 3000):
    F(i)

print(F(3000)/F(2996))

Ответ: 8994000

Задача (Вперёд к победе!)

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

F(n) = 1 при n=1;
F(n) = 2 при n=2;
F(n) = n*(n-1) + F(n-1) + F(n-2), если n > 2.

Чему равно значение функции F(2023) — F(2021) — 2*F(2020) — F(2019)?

Решение:

1 Способ (Аналитическое решение)

F(2023) = 2023*2022 + F(2022) + F(2021) =
= 2023*2022 + 2022*2021 + F(2021) + F(2020) + F(2021) =
=2023*2022 + 2022*2021 + 2021*2020 + F(2020) + F(2019) + F(2020) + F(2021) =
2023*2022 + 2022*2021 + 2021*2020 + 2*F(2020) + F(2019) + F(2021) =
2023*2022 + 2022*2021 + 2021*2020 + F(2021) + 2*F(2020) + F(2019)

Если подставим полученный результат в выражение, которое нужно найти, то получим:

2023*2022 + 2022*2021 + 2021*2020 = 12259388

2 Способ (Через lru_cache)

from functools import lru_cache

@lru_cache(None)
def F(n):
    if n==1: return 1
    if n==2: return 2
    if n>2: return n*(n-1) + F(n-1) + F(n-2)

for i in range(2, 2023):
    F(i)

print(F(2023) - F(2021) -2*F(2020) - F(2019))

Ответ: 12259388

Удачи при решении 16 задания из ЕГЭ по информатике 2022.

А если промежуток намного больше будет? например не [1, 1000], а [1,500 000 000]? пк зависнет просто.. можно кроме как разбивать промежуток много на разных программ решить такую задачу?

Ниже на пяти языках программирования записан рекурсивный алгоритм F.
def F(n):
  print(n)
  if n > 0:
  F(n — 1)
  F(n — 3)
Чему равна сумма всех чисел, напечатанных на экране при выполнении вызова F(5)?
А можете показать как это через python решать ?

Источник

В программировании рекурсия, или же рекурсивная функция — это такая функция, которая вызывает саму себя.

Рекурсивные функции с возвращаемыми значениями

Задание 6 (ИНФ-11 ЕГЭ 2023_ДЕМО)

Алгоритм вычисления значения функции F(n), где n – натуральное число,
задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = n × F(n − 1), если n > 1.
Чему равно значение выражения F(2023) / F(2020)?

Вариант программы 1

Лимит рекурсии по умолчанию в Python является 1000, вы получите ошибку « RecursionError: максимальная глубина рекурсии превышена в сравнении »
Это может быть исправлено, увеличивая предел рекурсиона в Python, ниже – фрагмент о том, как вы можете увеличить предел рекурсии.

import sys
sys.setrecursionlimit(2030)

Вариант программы 2

Алгоритмы, опирающиеся на несколько предыдущих значений

Задание 6 (Решу ЕГЭ)

Последовательность чисел Падована задается рекуррентным соотношением:

F(1) = 1

F(2) = 1

F(3) = 1

F(n) = F(n–3) + F(n–2), при n >3, где n – натуральное число.

Чему равно двенадцатое число в последовательности Падована?

В ответе запишите только натуральное число.

Задание 6 (Решу ЕГЭ)

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

F(1) = 1;

F(n) = n + F(n − 2), если n — нечётно, и n > 1;

F(n) = n × F(n − 1), если n — чётно.

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

Алгоритмы, опирающиеся на несколько предыдущих значений

Задание 6 (Решу ЕГЭ)

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

F(1) = 0

F(n) = F(n–1) + n, при n >1

G(1) = 1

G(n) = G(n–1) * n, при n >1

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

В ответе запишите только натуральное число.

Сложные задачи

Задание 6 (Поляков ЕГЭ)

(№ 5604) (А. Куканова) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = sqrt(n), если sqrt(n) – натуральное число,
F(n) = F(n + 1) + 1, если sqrt(n) – дробное число.
Чему равно значение выражения F(4850) + F(5000)?

При делении натурального числа на 2 мы получаем в остатке (%) или 0 или 1 (чётные и нечётные числа), таким образом проверяем, если корень дает четное или нечётное целое число, то выводим корень этого числа во всех остальных случаях применяет функцию F(n+1)+1
sqrt(n) запишем как n**0.5, что бы не подключать дополнительный математический модуль из библиотеки

Задание 6 (Поляков ЕГЭ)

Определите, сколько символов * выведет эта процедура при вызове F(140):

Алгоритмы, опирающиеся на несколько предыдущих значений

Задание 6 (Поляков ЕГЭ)

(№ 5604) (А. Куканова) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n!, если n ≥ 5000,
F(n) = 2 · F(n + 1) / (n + 1), если 1 ≤ n < 5000.
Чему равно значение выражения 1000 · F(7) / F(4)?
Примечание.
Факториал числа n, который обозначается как n!, вычисляется по формуле n!=1·2·…·n.

Модуль math – один из наиважнейших в Python. Этот модуль предоставляет обширный функционал для проведения вычислений с вещественными числами (числами с плавающей точкой).

Для использования этих функций в начале программы необходимо подключить модуль, что делается командой import:
# программный код
import math
num1 = math.sqrt(2) # вычисление корня квадратного из двух
Как можно заметить из примера выше, для вызова функции мы вынуждены указывать название модуля и символ точки. С другой стороны, если функции используются достаточно часто, то такой вызов (постоянное указание названия модуля и символа точки) может усложнить программу и сделать её менее читабельной. Для того, чтобы не указывать название модуля и символ точки при вызове функций, мы пишем следующий код:

# программный код
from math import *
Если нужно использовать только некоторые функции модуля, то мы можем импортировать только их следующим образом:
from math import sqrt, ceil, factorial

ещё не решила)

Источник

Характеристика задания

1. Тип ответа: запись числового значения.

2. Структура содержания задания: дана рекурсивная функция.

3. Уровень сложности задания: повышенный.

4. Примерное время выполнения: (5) минут.

5. Количество баллов: (1).

6. Требуется специальное программное обеспечение: да.

7. Задание проверяет умение работать с рекурсивными алгоритмами, осуществлять вычисления с помощью языка программирования.

Пример задания (демоверсия (2022))

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

(F(n)) (=) (1) при (n=1);

(F(n) = n + F(n-1)), если (n) чётно,

(F(n)) (= 2 × F(n-2)), если (n>1) и при этом (n) нечётно.

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

Как решать задание?

Задание можно решить «ручным» методом, т. е. самостоятельно посчитать функцию. Это займёт слишком много времени, поэтому лучше написать программу.

Что такое функция, можно вспомнить тут.

Что такое рекурсивный алгоритм, можно вспомнить тут.

Напишем программу

	Объявим функцию
	Опишем первое условие: если (n=1), то…
	Оператор return прекращает вычисление функции. При (n=1) функция закончит своё вычисление и будет равна (1)
	В следующем условии будет определять чётность (n). % — это получение остатка от деления
	Если (n) будет чётным, то выполним следующее действие: (n+f(n-1))
	Если (n) больше единицы и при этом нечётное… Напомним, знак (!=) обозначает «не равно»
	Выполним действие: (2*f(n-2))
	Организуем вывод данных, в скобках укажем необходимое нам значение (n). Запустим программу

Ответ: (4122).

Источник

Вычисление значений рекурсивной
функции

Разбор заданий № 16 КЕГЭ-2021

(соответствует за да нию № 11 ЕГЭ 2020)

Проверяемые элементы содержания: Вычисление рекуррентных выражений. Индуктивное определение
объектов. Умение записать и исполнить ре курсивный вычислительный алгоритм,
заданный в виде рекуррентных соотношений.

Проверяемые умения или способы действий: Строить информационные модели объектов, систем и процессов в
виде алгоритмов.

(повышенный уровень, время – 9 мин)

Что нужно знать:

Рекурсия^{^[1]}— определение, описание, изображение какого-либо объекта или
процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект
является частью самого себя.
Рекурсия – способ определения множества объектов через это же множество на
основе заданных базовых случаев.
Рекурсивная функция^{^[2]}(от лат. recursio — возвращение) — это числовая функция
*f(n)* числового аргумента, которая в своей записи содержит себя же. Такая запись
позволяет вычислять значения *f(n)* на основе значений *f(n-1), f(n-2)*, …, подобно
рассуждению по индукции. Чтобы вычисление завершалось для любого n, необходимо,
чтобы для некоторых n функция была определена нерекурсивно
(например, для n = 0, 1).
Рекурсивно заданная функция определяет своё значение через обращение к себе
самой с другими аргументами. При этом возможно два варианта:
● Конечная рекурсивная функция. Она задаётся таким образом, чтобы для любого
конечного аргумента за конечное число рекурсивных обращений привести к одному из
отдельно определённых частных случаев, вычисляемых без рекурсии. Классический
пример: рекурсивно-определённый факториал целого неотрицательного числа:
● Бесконечная рекурсивная функция. Она задаётся в виде обращения к самой себе
во всех случаях (по крайней мере, для некоторых из аргументов). Подобным образом
могут задаваться бесконечные ряды, бесконечные непрерывные дроби и так далее.
Примером рекурсии в математике является числовая последовательность, заданная
рекуррентной формулой, когда каждый следующий член последовательности
вычисляется как результат функции от n предыдущих членов (например, числа
Фибоначчи).
	Рекурсивные алгоритмы – это вспомогательные алгоритмы, которые напрямую
	или через другие вспомогательные алгоритмы вызывают сами себя.
В программировании рекурсия^{^[3]}— вызов функции (процедуры) из неё же самой,
непосредственно (простая рекурсия) или через другие функции (сложная или
косвенная рекурсия), например, функция A вызывает функцию B, а функция B —
функцию A. Рекурсивная программа позволяет описать повторяющееся или даже
потенциально бесконечное вычисление, причём без явных повторений частей
программы и использования циклов.
Структурно рекурсивная функция на верхнем уровне всегда представляет собой
команду ветвления (выбор одной из двух или более альтернатив в зависимости от
условия (условий), которое в данном случае уместно назвать «условием прекращения
рекурсии»), имеющую две или более альтернативные ветви, из которых хотя бы одна
является рекурсивной и хотя бы одна — терминальной. Рекурсивная ветвь
выполняется, когда условие прекращения рекурсии ложно, и содержит хотя бы один
рекурсивный вызов — прямой или опосредованный вызов функцией самой себя.
Терминальная ветвь выполняется, когда условие прекращения рекурсии истинно; она
возвращает некоторое значение, не выполняя рекурсивного вызова. Правильно
написанная рекурсивная функция должна гарантировать, что через конечное число
рекурсивных вызовов будет достигнуто выполнение условия прекращения рекурсии, в
результате чего цепочка последовательных рекурсивных вызовов прервётся и
выполнится возврат.
Помимо функций, выполняющих один рекурсивный вызов в каждой рекурсивной
ветви, бывают случаи «параллельной рекурсии», когда на одной рекурсивной ветви
делается два или более рекурсивных вызова. Параллельная рекурсия типична при
обработке сложных структур данных, таких как деревья.
Основной недостаток рекурсии — повторные вычисления одних и тех же значений.
*Рекурсивным* называется алгоритм, вызывающий в процессе исполнения сам себя.	Рекуррентное соотношение – это запись, позволяющая вычислить следующее значение последовательности через значения предыдущих.
Для того, чтобы рекурсивный алго ритм имел завершение, требуется, чтобы его параметр изменялся в процессе исполне ния и чтобы было явно написано условие завершения рекурсии.	В рекуррентном соот ношении обязательным является указание значения для первого (начального) элемента последовательности.

Рекомендации:

Задание
выполняется на компьютере либо посредством написа ния рекурсивного

алгоритма в одной из систем программирования, либо организацией цепочки

вычислений в электронных
таблицах.

Информационные ресурсы:

1.
Теория:
Интерактивный плакат «Фракталы» http://elementy.ru/posters/fractals;

Запись вспомогательных алгоритмов на языке Паскаль;
Функции;

Рекурсия в
Python; Программирование на python: Теоретический материал (Рекурсия)

2. Задания
для тренировки: ЕГЭ−2021, Информатика: задания, ответы, решения. Обучающая
система Дмитрия Гущина

3. Онлайн-тест
Константина Полякова для подготовки к ЕГЭ:

16 —
Рекурсивные алгоритмы (Паскаль).

16 — Рекурсивные алгоритмы (Python).

16 — Рекурсивные алгоритмы (C++).

За да ние № 16 (ДЕМО ФИПИ КЕГЭ-2021)

Алгоритм вычисления значения функции F(n), где n – натуральное число, задан
следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = n + F(n − 1), если n – чётно,
F(n) = 2 × F(n − 2), если n > 1 и при этом n – нечётно.
Чему равно значение функции *F(26)*?
Решение:

I вариант – решение в
электронных таблицах:

1.
Составим таблицу для n = 1÷26. Введем в ячейки B2,
C2
и D2
формулы
соответствующие заданным рекуррентным соотношениям:

2. С
помощью автозаполнения копируем формулы из диапазона C2:D2 в E2:AA2

II вариант – решение на
Python:

Ответ:
4122

За да ние № 16 (ЕГЭ−2021. Досрочная волна)

Алгоритм вычисления значения функции F(n), где n – натуральное число, задан
следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = n + F(n − 1), если n – чётно,
F(n) = 2 × F(n − 2), если n > 1 и при этом n – нечётно.
Чему равно значение функции *F(24)*?
Решение:

I
вариант – решение в электронных таблицах:

1. Составим таблицу для n
= 1÷24. Введем в ячейки B2, C2
и D2
формулы
соответствующие заданным рекуррентным соотношениям:

2. С
помощью автозаполнения копируем формулы из диапазона C2:D2 в
E2:Y2

II
вариант – решение на Python:

Ответ: 2072

Разбор заданий №16. Готовимся к
итоговой аттестации 2021. Лещинер, В.Р.^{^[4]}Вариант № 1

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан
следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = 2×n + F(n — 1), если n — чётно,
F(n) = 3 × F(n — 2), если n > 1 и при этом n — нечётно.
Чему равно значение функции *F(18)*?
Решение:

I
вариант – решение в электронных таблицах:

1. Составим таблицу для n
= 1÷18. Введем в ячейки B2, C2
и D2
формулы
соответствующие заданным рекуррентным соотношениям:

2. С
помощью автозаполнения копируем формулы из диапазона C2:D2 в
E2:S2

II
вариант – решение на Python:

Ответ:
6597

Вариант № 2

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан
следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = 3×n + F(n — 1), если n — чётно,
F(n) = 3 × F(n — 2), если n > 1 и при этом n — нечётно.
Чему равно значение функции F(20)?
Решение:

I
вариант – решение в электронных таблицах:

1. Составим таблицу для n
= 1÷20. Введем в ячейки B2, C2
и D2
формулы
соответствующие заданным рекуррентным соотношениям:

2. С
помощью автозаполнения копируем формулы из диапазона C2:D2 в
E2:U2

II
вариант – решение на Python:

Ответ:
19743

Задание № 16.1

Алгоритм вычисления значения функции *F(n)*, где n — натуральное число, задан
следующими соотношениями:
F(n) = 1 при n ≤ 2;
F(n) = F(n — 1) + 2 × F(n — 2) при n > 2.
Чему равно значение функций F(7), F(12), F(17)?
В ответе запишите только натуральное число.
Решение:

I вариант – решение в
электронных таблицах:

1.
Составим таблицу для n = 1÷17. Введем в ячейки
B2,
C2
и D2
формулы
соответствующие заданным рекуррентным соотношениям:

2. С помощью автозаполнения
копируем формулы из ячейки D2 в диапазон E2:R2

II вариант – решение на
Python:

Ответ:
43, 1365, 43691

Задание № 16.2

Алгоритм вычисления значения функции *F(n), где n — натуральное* число, задан
следующими соотношениями:
F(n) = 2 при п ≤ 2;
F(n) = F(n — 1) + 3 × F(n — 2) при п > 2.
Чему равно значение функции F(5), F(10), F( 15)?
В ответе запишите только натуральное число.
Решение:

I вариант – решение в
электронных таблицах:

1.
Составим таблицу для n = 1÷15. Введем в ячейки
B2,
C2
и D2
формулы
соответствующие заданным рекуррентным соотношениям:

2. С помощью автозаполнения
копируем формулы из ячейки D2 в диапазон E2:P2

II вариант – решение на
Python:

Ответ: 38, 2318, 150632

Задание № 16.3
Алгоритм вычисления значения функции *F(n), где n — натуральное* число, задан
следующими соотношениями:
F(n) = n при п ≤ 2;
F(n) = F(n — 1) + 3 × F(n — 2) при п > 2.
Чему равно значение функции F(6), F(12), F( 18)?
В ответе запишите только натуральное число.
Решение:

I вариант – решение в
электронных таблицах:

1.
Составим таблицу для n = 1÷18. Введем в ячейки
B2,
C2
и D2
формулы
соответствующие заданным рекуррентным соотношениям:

2. С помощью автозаполнения копируем формулы из
ячейки D2 в диапазон E2:S2

II вариант – решение на
Python:

Ответ: 59, 8843, 1318811

Задание № 16.4
Алгоритм вычисления значения функции *F(n), где n — натуральное* число, задан
следующими соотношениями:
F(n) = n + 1 при п ≤ 2;
F(n) = F(n — 1) + 2 × F(n — 2) при п > 2.
Чему равно значение функции F(4), F(9), F( 14)?
В ответе запишите только натуральное число.
Решение:

I вариант – решение в
электронных таблицах:

1.
Составим таблицу для n = 1÷14. Введем в ячейки
B2,
C2
и D2
формулы
соответствующие заданным рекуррентным соотношениям:

2. С помощью автозаполнения копируем формулы из
ячейки D2 в диапазон E2:O2

II вариант – решение на
Python:

Ответ: 13, 427, 13653

За да ние № 11 (ДЕМО ЕГЭ-2020 ФИПИ)

Ниже на пяти языках программирования записан рекурсивный алгоритм F.
Бейсик	Python	С++
SUB F(n) PRINT n, IF n >= 3 THEN F(n 2) F(n — 1) END IF END SUB	def F(n): print(n, end=») if n >= 3: F(n // 2) F(n — 1)	void F(int n) { std::cout << n; if (n >= 3) { F(n / 2); F(n — 1); } }
Алгоритмический язык	Паскаль
алг F(цел n) нач вывод n если n >= 3 то F(div(n, 2)) F(n — 1) все кон	procedure F(n: integer); begin write(n); if n >= 3 then begin F(n div 2); F(n — 1) end end;
Запишите подряд без пробелов и разделителей все числа, которые будут выведены на
экран при выполнении вызова *F(5)*. Числа должны быть записаны в том же порядке, в
котором они выводятся на экран.

Решение:

f(5)	5	>= 3 – yes
	f(div(5,2))	2	>= 3 – not	∎
	f(5 — 1)	4	>= 3 – yes
		f(div(4,2))	2	>= 3 – not	∎
		f(4-1)	3	>= 3 – yes
				f(div(3,2))	1	>= 3 – not	∎
				f(3-1)	2	>= 3 – not	∎
Ответ:	5		24		23		12

Ответ: 5242312

За да ние № 11 (ДЕМО ЕГЭ-2019 ФИПИ)

Ниже на пяти языках программирования записан рекурсивный алгоритм F.
Бейсик	Python	С++
SUB F(n) IF n > 0 THEN F(n — 1) PRINT n F(n — 2) END IF END SUB	def F(n): if n > 0: F(n — 1) print(n) F(n — 2)	void F(int n) { if (n > 0){ F(n — 1); std::cout << n; F(n — 2); } }
Алгоритмический язык	Паскаль
алг F(цел n) нач если n > 0 то F(n — 1) вывод n F(n — 2) все кон	procedure F(n: integer); begin if n > 0 then begin F(n — 1); write(n); F(n — 2) end end;
Запишите подряд без пробелов и разделителей все числа, которые будут выведены на
экран при выполнении вызова *F(4)*. Числа должны быть записаны в том же порядке, в
котором они выводятся на экран.

Решение:

n=4

f(4)

f(4-2)

f(2-2)

∎

F(n — 1)
PRINT n

F(n — 2)

f(3)

f(3-2)

f(1-2)

∎ ↑

f(1)

∎ ↑

f(2)

f(2-2)

∎ ↑

f(1-1)

∎ ↑

f(0)

∎ ↑

f(1)

f(1-2)

∎ ↑

f(0)

∎ ↑

Ответ:

Ответ: 1231412

За да ние № 11 (ДЕМО ЕГЭ-2018 ФИПИ)

Ниже на пяти языках программирования записан рекурсивный алгоритм F.
Бейсик	Python	С++
SUB F(n) IF n > 0 THEN PRINT n F(n — 3) F(n 3) END IF END SUB	def F(n): if n > 0: print(n) F(n — 3) F(n // 3)	void F(int n) { if (n > 0){ F(n — 1); std::cout << n; F(n — 2); } }
Алгоритмический язык	Паскаль
алг F(цел n) нач если n > 0 то вывод n F(n — 3) F(div(n, 3)) все кон	procedure F(n: integer); begin if n > 0 then begin write(n); F(n — 3); F(n div 3) end end;
Запишите подряд без пробелов и разделителей все числа, которые будут выведены на
экран при выполнении вызова *F(9)*. Числа должны быть записаны в том же порядке, в
котором они выводятся на экран.

Решение:

f(9)	9							f(div(6, 3))	3
⤷	f(9-3)	6				f(div(6, 3))	2	⤴	f(3-3)	∎
	⤷	f(6-3)	3	f(div(3, 3))	1	⤴	f(2-3)	∎	f(div(3,3))	1
		⤷	f(3-3)	⤴	f(1-3)	∎				f(1-3) f(div(1,3))	∎ ∎
Ответ:	9	6	3		1		2		3	1

Ответ: 9631231

Источник

Программный комплекс NetTest

1. Дан рекурсивный алгоритм:

  def F( n ):
    print( '*' )
    if n > 0:
      F(n-2)
      F(n-2)
      F(n // 2)

Сколько символов «звездочка» будет напечатано на экране при выполнении вызова F(6)?

Ответ:

2. Дан рекурсивный алгоритм:

  def F( n ):
    print( '*' )
    if n > 0:
      print( '*' )
      F(n-2)
      F(n // 2)
      F(n // 2)

Сколько символов «звездочка» будет напечатано на экране при выполнении вызова F(7)?

Ответ:

3. Дан рекурсивный алгоритм:

  def F( n ):
    print( '*' )
    if n > 0:
      print( '*' )
      F(n-2)
      F(n-2)
      F(n // 2)

Сколько символов «звездочка» будет напечатано на экране при выполнении вызова F(6)?

Ответ:

4. Дан рекурсивный алгоритм:

  def F( n ):
    if n > 0:
      F(n-2)
      F(n-1)
      F(n-1)     
    print( '*' )

Сколько символов «звездочка» будет напечатано на экране при выполнении вызова F(5)?

Ответ:

5. Дан рекурсивный алгоритм:

  def F( n ):
    print( n )
    if n < 5:
      F(n+2)
      F(n*2)

Найдите сумму чисел, которые будут выведены при вызове F(1).

Ответ:

6. Дан рекурсивный алгоритм:

  def F( n ):
    print( n )
    if n < 6:
      print( n )
      F(n+2)
      F(n+3)

Найдите сумму чисел, которые будут выведены при вызове F(1).

Ответ:

7. Ниже записаны две рекурсивные процедуры, F и G:

  def F( n ):
    print( '*' )
    if n > 0: G(n - 1)      def G( n ):
    print( '*' )
    if n > 1: F(n - 2)

Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(13)?

Ответ:

8. Определите, что выведет на экран программа при вызове F(5).

  def F( n ):
    if n > 0:
      F(n - 1)
      print( n, end="" )
      F(n // 4)

Ответ:

9. Определите, что выведет на экран программа при вызове F(1).

  def F( n ):
    if n < 10:
      F(2*n + 1)
      F(3*n + 1)
      print( n, end="" )

Ответ:

10. Определите, что выведет на экран программа при вызове F(1).

  def F( n ):
    if n < 10:
      print( n+5, end="" )
      F(2*n + 4)
      F(2*n + 1)

Ответ:

kpolyakov.spb.ru

Источник

Пройти тестирование по этим заданиям
Вернуться к каталогу заданий

Версия для печати и копирования в MS Word