Данная тема актуальна в свете того, что ученики часто не понимают, как именно выполняются рекурсивные процедуры, пренебрегают их использованием для решений задач повышенной сложности на ЕГЭ. Поэтому необходимо написать подробный разбор заданий с вариантами решений.
Условно можно все задания, относящиеся к рекурсивным алгоритмам на ЕГЭ, можно разделить на три большие группы:
- Алгоритмы, опирающиеся на несколько предыдущих значений ;
- Вызов рекурсивных процедур;
- Алгоритмы, опирающиеся на одно предыдущее значение.
- Алгоритмы, опирающиеся на несколько предыдущих значений
1.1. Алгоритм вычисления значения функции F ( n ), где n – натуральное число, задан следующими соотношениями:
F(n) = F(n–1) * (n+1) + F(n–2) * (n + 2) , при n >2
Чему равно значение функции F(4)?
В ответе запишите только натуральное число.
Удобнее всего данное задание решать составлением таблицы значений.
Значение аргумента x функции F ( x )
11 Задание ЕГЭ Информатика Рекурсия
Значение функции F(x)
F(3) = F(2)*4 + F(1)*5 = 30
F(4) = F(3)*5 + F(2)*6 = 180
1.2. Последовательность чисел Фибоначчи задается рекуррентным соотношением:
Function(x) = Function(x–2) + Function(x–1), при x >2, где x – натуральное число.
Чему равно шестое число в последовательности Фибоначчи?
В ответе запишите только натуральное число.
Вероятно, проще прописать числа данной последовательности, не обращаясь к значениям функции, т. к. последовательность Фибоначчи – довольно известный числовой ряд.
Кроме того, в разделе «Алгоритмы, опирающиеся на несколько предыдущих значений» (исходя из заданий прошлых лет) могут встретиться: числа Трибоначчи, последовательность Люка, последовательность Падована.
Вызов рекурсивных процедур
Источник: Демонстрационная версия ЕГЭ-2023 по информатике
2.1. Ниже записан рекурсивный алгоритм F.
procedure F(n: integer );
Чему равна сумма всех чисел, напечатанных на экране при выполнении вызова F(1)?
Разберемся, что делает этот алгоритм. Удобно рисовать дерево, и потом подниматься с нижних ветвей вверх, но для статьи будет предложена подробная таблица.
Печатает на экране 1, вызывает F (2)
Печатает на экране 2, вызывает F (3)
Печатает на экране 3, вызывает F (4)
Печатает на экране 4, вызывает F (5)
Печатает на экране 5, передает управление F (4)
Печатает на экране 7, передает управление F (3)
F(3) вызывает F ( 6)
Печатает на экране 6, передает управление F (2)
F(2) вызывает F ( 5)
Печатает на экране 5, передает управление F (1)
F(1) вызывает F ( 4 )
Печатает на экране 4, вызывает F (5)
Печатает на экране 5, передает управление F (4)
Печатает на экране 7, процедура закончена
Анализируем данные и выбираем, какие числа были напечатаны:
Sum = 1 + 2 + 3 + 4 + 5 + 7 + 6 + 5 + 4 + 5 + 7 = 49
Источник: Досрочная волна. ЕГЭ 5.05.2023
Информатика ЕГЭ № 11. Рекурсия: Разбор задачи
2.2. Ниже записаны две рекурсивные функции (процедуры): F и G.
procedure F(n: integer); forward;
procedure G(n: integer); forward;
procedure F(n: integer);
procedure G(n: integer);
Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(11)?
Заметим, что печать происходит лишь при вызове процедуры G ( n ).
F (11) вызывает G (10), печатается звездочка
G(10) вызывает F ( 8 )
F (8) вызывает G (7), печатается звездочка
G( 7 ) вызывает F( 5 )
F(5) вызывает G(4), печатается звездочка
G(4) вызывает F( 2 )
F (2) вызывает G (1), печатается звездочка
После аргумент n перестает отвечать заданному условию.
2.3. Ниже записана рекурсивная функция (процедура) F.
procedure Function(n: integer);
Что выведет программа при вызове F(3)? В ответе запишите последовательность выведенных цифр слитно (без пробелов).
Рассмотрим, как выполняется данный алгоритм:
Печатается 3, F(3) вызывает F(1)
Печатается 1, F (1) передает управление F (2)
Печатается 2, F (2) передает управление F (2)
Печатается 2 , условие перестает выполняться
Источник: Демонстрационная версия ЕГЭ-2023 по информатике
2.4 Ниже на записан рекурсивный алгоритм F .
procedure F(n: integer);
if n > 0 then begin
Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова F (9). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.
Рассмотрим, как выполняется данный алгоритм:
Печатается 9 , F(9) вызывает F(6)
Печатается 6, F(6) вызывает F(3)
Печатается 3, F(3) вызывает F ( 0 )
F(0) передает управление F(1)
Печатается 1, F(1) вызывает F ( — 2)
F ( — 2) передает управление F( 2 )
Печатается 2, F (2) вызывает F (-1) и F (0)
F(0) передает управление F( 3 )
Печатается 3, F (3) вызывает F (0) и F (1)
Довольно любопытное задание можно найти на другом сайте по подготовке к ЕГЭ (ссылка: http://kpolyakov.spb.ru/ ):
2.5 При выполнении вызова F (8) на экран было выведено математическое выражение. Вычислите его значение.
procedure G(n: integer );forward;
procedure F(n: integer );
if n > 0 then begin
procedure G(n: integer );
Рассмотрим, как выполняется данный алгоритм:
Печатается 2, Печатается *, F (8) вызывает G (7)
Печатается 3, G(7) вызывает F(5)
Печатается 2, Печатается *, F (5) вызывает G (4)
Печатается 3, G(4) вызывает F(2)
Печатается 2, Печатается *, F (2) вызывает G (1)
Получившееся выражение: 2*32*32*3 = 6144
Алгоритмы, опирающиеся на одно предыдущее значение
Источник: Демонстрационная версия ЕГЭ-2013 по информатике
3.1. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = F(n–1) * n, при n >1
Чему равно значение функции F(5)?
В ответе запишите только натуральное число.
Очевидно, что требуется найти факториал от 5. Таблицу факториалов до 6 нужно знать.
3.2 Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
Function (1) = 1
F unction(n) = Function(x–1) + 2 n –1 , если x> 1.
Чему равно значение функции Function(9)?
В ответе запишите только натуральное число.
Можно заметить, что F (9) = 2#k8SjZc9Dxk9 – 1 = 511.
3.3. Алгоритм вычисления значения функции Function ( x ), где x — натуральное число, задан следующими соотношениями:
Function (1) = 4;
Function (x) = F(x − 1) + x если x>1
Чему равно значение функции Function(36)? В ответе запишите только натуральное число.
Легко заметить, что данная функция представляет собой сумму арифметической прогрессии Function (x) = Function (1) + d (x -1), где Function (1) = 4, d = 1. Sum Function (x ) = ( Function (1) + Function (x ))/2* x = ( Function (1) + Function (1) + d (x -1))/2*x = 774
3.4. Алгоритм вычисления значения функции Function (x ) и G (x ), где x – натуральное число, задан следующими соотношениями:
Function(x) = 2 * G(x–1) + 5 * x, при x >1
G(x) = F(n–1) + 2 * x, при x >1
Чему равно значение функции F(4) + G(4)?
В ответе запишите только натуральное число.
Составим таблицу значений для F (x ) и для G (x ):
Значение аргумента x функции F ( x )
Значение функции Function(x)
Function(2) = 2*G(1) + 10 = 12
Function(3) = 2*G(2) + 15 = 25
Function(4) = 2* G(3) + 20 = 56
Значение аргумента x функции G ( x )
Значение функции G(x)
G(2) = Function(1) + 4 = 5
G(3) = Function(2) + 6 = 18
G(4) = Function(3) + 8 = 33
Function(4) + G(4) = 56 + 33 = 89
Нет никакой сложности в том, чтобы составить таблицу значений и для двух функций.
Таким образом, для этого типа заданий характерны арифметические, геометрические или произвольные последовательности. Рекомендуется выучить формулы n -члена для арифметической и геометрической последовательностей, формулы суммы n -членов последовательностей.
Вывод
Исходя из всего вышесказанного, можно сделать вывод, что наиболее трудные задачи – из 2 подраздела ( Вызов рекурсивных процедур ), т. к. необходимо очень хорошо понимать, как работает программа, простая математика не поможет. Необходимо делать упор на отработку именно этого типа задач. Рекомендуется составлять программы самостоятельно с использованием рекурсивных функций, проводить отладку со входом в подпрограмму. Можно расписывать дерево решений, составлять таблицы.
Преобразование логических высказываний на ЕГЭ
Предлагаю также рассмотреть преобразование логических высказываний (задание 18), как второе наиболее сложное для учеников в первой части экзамена.
Их также можно условно разделить на 2 группы:
- Числовые отрезки;
Логические высказывания.
1. Числовые отрезки
Перечислим операции в порядке убывания приоритетов (выполнения) :
Символ ¬ обозначает инверсию
Символ 18) или A ∈(26; 39]. В таком случае, наибольшая длина отрезка A = 39-26 = 13.
Все остальные задания аналогичны этому.
2. Логические высказывания
2. 1. Элементами множества А являются натуральные числа. Известно, что выражение
истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наименьшее наименьшее возможное количество элементов во множестве A.
Преобразуем данное логическое выражение в соответствие с законами логики:
(x ∉ ) | (x ∉ ) = 1 при всех значениях x , кроме 13 (оно исключено из обоих множеств). Таким образом, множество A должно содержать как минимум 13. Т.е. один элемент.
Источник: Досрочная волна. ЕГЭ 5.05.2023
2.2. Обозначим через ДЕЛ( n , m ) утверждение «натуральное число n делится без остатка на натуральное число m ».
Для какого наибольшего натурального числа А формула
¬ДЕЛ(x, А) → (ДЕЛ(x, 6) → ¬ДЕЛ(x, 4))
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?
Преобразуем данное логическое выражение в соответствие с законами логики:
¬ДЕЛ(x, А) → (ДЕЛ(x, 6) → ¬ДЕЛ(x, 4)) = 1
ДЕЛ ( x , А ) | ¬(ДЕЛ( x , 6) | ¬ДЕЛ( x , 4) = 1
Рассмотрим логическое выражение (ДЕЛ( x , 6) | ДЕЛ( x , 4) = 1. В соответствие с формулами де Моргана ¬(¬(ДЕЛ( x , 6) | ¬ДЕЛ( x , 4)) = ДЕЛ( x , 6) 12. Они будут давать ложное значение при x кратных 12.
Таким образом, наибольшее A = 12.
Тренировочная работа по информатике, 11 класс 26.11.2023 Вариант ИН10204
2.3. Обозначим через m5 = 1110 2 25 ≠ 0 → (xА ≠ 0)
тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной х)?
Преобразуем данное логическое выражение в соответствие с законами логики:
x19 = 0 → x25 = 0 | xA ≠ 0
Рассмотрим конечное выражение в двоичной записи. Биты считать справа налево с 0:
Источник: open-budget.ru
Что выведет программа при вызове
Оцени ответ
- Алгебра
- Математика
- Русский язык
- Українська мова
- Информатика
- Геометрия
- Химия
- Физика
- Экономика
- Право
- Английский язык
- География
- Биология
- Другие предметы
- Обществознание
- История
- Литература
- Українська література
- Беларуская мова
- Қазақ тiлi
Показать ещё
Источник: www.shkolniku.com
Что выведет программа при вызове
Планируемые образовательные результаты:
предметные – представления о понятиях «рекурсия»,«глубина рекурсии», «прямой и обратный ход рекурсии»; умение анализировать работу готовых рекурсивных алгоритмов;
метапредметные – умение самостоятельно планировать пути достижения целей; умение соотносить свои действия с планируемыми результатами, осуществлять контроль своей деятельности, определять способы действий в рамках предложенных условий, корректировать свои действия в соответствии с изменяющейся ситуацией; умение оценивать правильность выполнения учебной задачи;
личностные – алгоритмическое мышление, необходимое для профессиональной деятельности в современном обществе; представление о программировании как сфере возможной профессиональной деятельности.
1 этап урока: объяснение нового материала:
Слово рекурсия от лат. recursio означает круговорот. Синонимами этого слова являются возвращение, повторение. Классическим примером рекурсивного алгоритма является алгоритм решения задачи «Ханойские башни». Есть три стержня, на одном из которых находятся кольца разного диаметра. Необходимо переложить их с первого стержня на свободный, используя еще один.
Рассмотрим случай с пятью кольцами.
Учащимся предлагается самостоятельно составить алгоритм к этой задаче и устно описать его.
Далее учитель загружает файл Hanoy.exe и демонстрирует учащимся работу алгоритма.
Переместить пятое кольцо самого большого диаметра невозможно до тех пор, пока мы не перенесем четыре верхних. Т.е задача приводит нас к решению подобной задачи, но уже с меньшим количеством колец — четырьмя. Переместив пятое кольцо нам нужно будет положить на него четвертое, освободить которое мы можем только убрав верхние три.
Т.е следующая задача, которую мы будем решать эта задача перекладывания трех колец. Продолжая наши рассуждения мы дойдем до того момента, когда нам нужно будет переложить всего лишь одно кольцо. Рекурсивный алгоритм обязательно должен иметь условие остановки. Если остановки не произойдет, он будет работать бесконечно. В нашем случае это произойдет когда количество колец для перекладывания станет равно 0.
Рекурсия это способ определения объекта , который опирается на само понятие объекта на основе заданных простых базовых случаев. Преимущество такого определения заключается в том, что оно способно описывать бесконечно большое число объектов. Мы разрабатываем алгоритм, сводя исходную задачу к более простым. Рекурсия позволяет сделать решение более понятным, сократить текст программы, упростить ее.
Рекурсивная (процедура) функция вызывает сама себя напрямую или через другие процедуры и функции. Количество таких вызовов называется глубиной рекурсии.
Классическим примером рекурсивного алгоритма является алгоритм нахождения факториала числа n. Факториал может быть введен с помощью рекуррентной формулы, которая связывает факториал числа с факториалом предыдущего числа.
базовые случаи здесь: 0!=1, 1!=1
рекурентная формула:N!=N*(N-1)! при N>=2
На языке Паскаль функция выглядит следующим образом:
function factorial(N: integer) : longint;
if N = 0 then factorial := 1
factorial := factorial(N-1) * N
Что же происходит, если одна функция вызывает другую?
· в памяти размещаются параметры, передаваемые функции
· для внутренних переменных вызываемой функции также отводится новая область памяти (несмотря на совпадение их имен и типов с переменными вызывающей функции);
· запоминается адрес возврата в вызывающую функцию;
· управление передается вызванной функции.
Если функцию или процедуру вызвать повторно из другой функции/процедуры или из нее самой, будет выполняться тот же код, но работать он будет с другими значениями параметров и внутренних переменных.
Действия, выполняемые функцией до входа на следующий уровень рекурсии, выполняются на прямом ходу рекурсии, а действия, выполняемые по возврату с более глубокого уровня к текущему, – выполняются на обратном ходу рекурсии.
2 этап: практическая работа за компьютером
Продемонстрируем ход рекурсии. Учащимся предлагается протестировать программу , пошагово проследить, как она работает.
var glubina: integer := 0;
function factorial(N: integer) : longint;
glubina := glubina + 1;
writeln(‘Прямой ход рекурсии. Глубина = ‘, glubina);
if N > 0 then result := factorial(N-1) * N;
Writeln(‘Обратный ход рекурсии. Глубина = ‘, glubina);
glubina := glubina — 1;
При запуске этой программы, будет выведено:
Прямой ход рекурсии. Глубина = 1
Прямой ход рекурсии. Глубина = 2
Прямой ход рекурсии. Глубина = 3
Прямой ход рекурсии. Глубина = 4
Обратный ход рекурсии. Глубина = 4
Обратный ход рекурсии. Глубина = 3
Обратный ход рекурсии. Глубина = 2
Обратный ход рекурсии. Глубина = 1
3 этап: закрепление нового материала при решении задач.
Рассмотрим задачи ЕГЭ , в которых присутствуют рекурсивные алгоритмы выполнения процедур. В процессе выполнения таких задач будут осуществляться рекурсивные вызовы процедуры. Необходимо правильно проследить порядок вызовов. Это возможно сделать разными способами, один из которых нарисовать дерево вызовов. Дерево может получится достаточно громоздким, поэтому более простым способом решения является анализ выполняемого алгоритма, его связи с вопросом задачи. Внутри алгоритма могут находится следующие операторы:
Writeln(*); в этом случае в задаче возможен вопрос: сколько * выведется на экран после выполнения алгоритма;
Writeln(n); в этом случае может быть задан вопрос :какова сумма всех n, выводимых на экран или потребуется записать последовательность из выводимых n.
Рассмотрим следующую задачу:
procedure F(n: integer);
begin
writeln(n);
Найдите сумму чисел, которые будут выведены при вызове F(2). (Автор задачи: Поляков К.Ю.)
1) сумму чисел, полученных при вызове F(n) обозначим через S(n).
2) аккуратно и последовательно выполним вычисления:
s(2)=2+s(4)+S(6), т.е необходимо найти S(4) и s(6).
Рассмотрим еще один рекурсивный алгоритм:
procedure F(n: integer);
begin
if n > 0 then begin
F(n div 2);
F(n div 2);
Сколько символов «звездочка» будет напечатано на экране при выполнении вызова F(5)?(Автор задачи: Поляков К.Ю.)
1) обозначим через Z(n) количество звездочек, которые выводит программа при вызове F(n)
2) из программы видим, что
Z(n) = 1 при всех n
Z(n) = 1 +Z(n-2) + Z(n div 2) + Z(n div 2) при n > 0
3) n div 2– это частное от деления n на 2
4) попробуем начать с нуля:
Z(1) = 1 + Z(-1) + Z(0) + Z(0) = 1 + 1 +2* 1 =4
Z(2) = 1 + Z(0) + Z(1) + Z(1) = 1 + 1 + 2*4 = 10
Z(3) = 1 + Z(1) + Z(1)+ Z(1) = 1 +3* 4 = 13
Z(4) = 1 + Z(2) + Z(2) + Z(2) = 1 + 3*10 = 31
Z(5) = 1 + Z(3) + Z(2) + Z(2) = 1 + 13 +2*10 = 34
Можно анализировать с конца, так как мы делали в предыдущей задаче, ответ будет таким же.
Определите, что выведет на экран программа при вызове F(9).
procedure F(n: integer);
begin
if n > 0 then begin
F(n div 2)
end;(Автор задачи: Поляков К.Ю.)
1. при вызове F(9) условие n>0 выполняется, распечатывается 9, затем вызывается F(n-4) = F(5), затем вызывается F(n div 2) = F(4); т.е. можно записать, что F(9)= 9 F(5) F(4)
2. аналогично рассматриваем F(5) и F(4)
теперь неизвестны F(2), F(1)
F(4)= 4 F(0) F(2) =4 2 1
F(5)= 5 F(1) F(2)=5 1 2 1
F(9)= 9 F(5) F(4)=9 5 1 2 1 4 2 1
Учащиеся могут проверить данную задачу на компьютере, выполнив следующую программу:
procedure F(n: integer);
if n > 0 then begin
Последовательность будет аналогичной.
4. Домашнее задание:
выполнить следующие задания из открытого банка заданий ЕГЭ
1. Алгоритм вычисления значения функции F(n), где n –натуральное число, задан следующими соотношениями:
F(n) = n + 1 при n ≤ 2;
F(n) = F(n − 1) + 2 × F(n − 2) при n > 2.
Чему равно значение функции F(4)?
В ответе запишите только натуральное число.
2. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = F(n − 1) + 3 × F(n − 2) при n > 2.
Чему равно значение функции F(7)?
В ответе запишите только натуральное число.
3. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = F(n − 1) + 2 × F(n − 2) при n > 2.
Чему равно значение функции F(9)?
В ответе запишите только натуральное число.
4. Дан рекурсивный алгоритм:
procedure F(n: integer);
if n > 0 then begin
Сколько символов «звездочка» будет напечатано на экране при выполнении вызова F(7)? (Автор задачи: Поляков К.Ю.)
5. Дан рекурсивный алгоритм:
procedure F(n: integer);
Найдите сумму чисел, которые будут выведены при вызове F(1). (Автор задачи: Поляков К.Ю.)
6. Что выведет программа при вызове F(8)?
procedure F(n: integer);
if n > 3 then begin
end; (Автор задачи Е. Филина-Поликарпова)
Источник: sites.google.com