Рекурсивные алгоритмы при подготовке к олимпиадам по программированию и ЕГЭ по информатике
Чтобы успешно выступать на олимпиадах по программированию необходимо не только быстро и логически мыслить, но и владеть специальными методами программирования, которые позволяют создавать оптимальные и эффективные программы.
При подготовке учащихся к олимпиадам по программированию, а также при сдаче ЕГЭ по информатике одной из важных тем является «Рекурсия. Рекурсивные алгоритмы».
В математике рекурсией называется способ описания функций или процессов через самих себя. Многие олимпиадные задачи бывает намного проще решить с использованием рекурсии, а не итерационных методов. При объяснении темы «Рекурсия» сначала дается определение, свойства рекурсивных алгоритмов. В качестве примеров рассматриваются игра «Ханойские башни», нахождение наибольшего общего делителя, возведение числа в степень.
Помимо того, что рекурсия применяется в программировании, свое распространение она получила и в едином государственном экзамене по информатике.
В задачах B6 ЕГЭ по информатике в 2013-2014 годах используются рекурсивные алгоритмы.
В 2013 году задавалась рекурсивная формула, и необходимо было вычислить значение функции, например F(5).
Пример:
Алгоритм вычисления значения функции F(n), где n– натуральное число, задан следующими соотношениями [1]:
F(1)=1,
F(n)=F(n-1)*n, при n>1.
Чему равно значение функции F(5)?
Решение:
Заполним таблицу
|
n |
1 |
2 |
3 |
4 |
5 |
|
F(n) |
1 |
2 |
6 |
24 |
120 |
Ответ: F(5)=120.
В 2014 году формулировка задания B6 получила еще один вариант, что нередко учащихся ставит в тупиковую ситуацию, хотя речь идет о той же самой рекурсии.
Например, определите, сколько звездочек будет напечатано в результате вызова F(5) приведенной подпрограммы [3]:
procedure F(n:integer);
begin
if n>1 then
begin
F(n div 2);
F(n-1);
end;
write(‘*’);
end;
Решение:
Способ 1: Определим рекуррентную формулу, обозначим Q(n) количество звездочек, которые будут выведены на экран при вызове F(n).
Из программы видно, что
Q(n)=1, для всех n<=1,
Q(n)=1+Q(n div 2)+Q(n-1) при n>0.
Составим таблицу для нахождения количества выведенных на экран звездочек.
|
n |
1 |
2 |
3 |
4 |
5 |
|
Q(n) |
1 |
3 |
5 |
9 |
13 |
Q(1) = 1
Q(2) = 1 + Q(1) + Q(1) = 1 + 1 + 1 = 3
Q(3) = 1 + Q(1) + Q(2) = 1 + 1 + 3 = 5
Q(4) = 1 + Q(2) + Q(3) = 1 + 3 + 5 = 9
Q(5) = 1 + Q(2) + Q(4) = 1 + 3 + 9 = 13
Ответ: 13.
Способ 2:
- Меньшиков Ф.В. Олимпиадные задачи по программированию. – СПб.: Питер, 2006. – 315 с.
- Демонстрационный вариант ЕГЭ 2013 г. Информатика и ИКТ. 11 класс.
- Ушаков Д.М., Якушкин А.П. ЕГЭ-2014: Информатика: самое полное издание типовых вариантов заданий. – М.: Астрель, 2014. – 316 c.
| Тип выступления | Стендовый доклад |
| Ключевые слова | Рекурсия Олимпиада по программированию Единый государственный экзамен по информатике |
