Презентация к уроку информатики на тему: "Рекурсивные алгоритмы" (11 класс)

Слайд #1

Рекурсивные алгоритмы
http://aida.ucoz.ru
решение заданий ЕГЭ по информатике
Автор: учитель информатики Агишева Светлана Александровна

Слайд #2

Что такое рекурсия?
Рекурсивная функция это функция, которая вызывает сама себя напрямую или через другие процедуры и функции
например, функция A вызывает функцию B, а функция B — функцию A,
при каждом вызове функции решается идентичная, но меньшая задача
одна из подзадач решается иначе, чем другие, первая является базовой
проверка базисных условий позволяет остановить процесс рекурсии

Слайд #3

задание ЕГЭ по информатике
Дан рекурсивный алгоритм F. Запишите подряд без пробелов и разделителей все числа, которые будут показаны на экране при выполнении вызова F(7). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.
def F(n):
if n > 3:
F(n - 1)
F(n // 2)
print(n, end='')

Слайд #4

Ответ: 324253637
def F(n):
if n > 3:
F(n - 1)
F(n // 2)
print(n, end='')

Рекурсивный алгоритм
при n>3: F(n) = F(n-1)+F(n//2)+n
при n<=3: F(n) = n
Вызов F(7)-?
F(7) = F(6)+F(3)+7
F(3) = 3
F(6) = F(5) + F(3) +6
F(5) = F(4) + F(2) + 5
F(4) = F(3) + F(2) + 4
F(2) = 2
2
3 2 4
3 2 4 2 5
3 2 4 2 5 3 6
3
3 2 4 2 5 3 6
3
7

Слайд #5

задание ЕГЭ по информатике
def F(n):
print(n)
if n < 6:
F(n+2)
F(n*3)

Ответ: 79
Функция F(n), где n – натуральное число, задана следующим образом:
Найдите сумму чисел, которые будут выведены при вызове F(1).

при n<6: F(n) = n + F(n+2) +F(n*3)
при n>=6: F(n) = n
Сумма при вызове F(1) - ?
F(1) = 1 + F(3) +F(3)
F(3) = 3 +F(5) +F(9)
F(5) = 5 +F(7) +F(15)
F(7) = 7
F(15) = 15
F(9) = 9
9
15
7
5+7+15=27
3+27+9=39
1+39+39=79

Слайд #6

задание ЕГЭ по информатике
def F(n):
if n > 0:
G(n - 1)
def G(n):
print("*")
if n > 1:
F(n - 3)

Ответ: 3
Ниже записаны две рекурсивные функции (процедуры): F и G.
Сколько звездочек напечатает эта процедура при вызове F(11)?

для F(n):
n>0: F(n) =G(n-1)
n<=0: F(n) = не выполняется
для G(n):
n>1: G(n) =* +F(n-3)
n<=1: G(n) =*
Вызов F(11)- количество * ?
F(11) = G(10)
G(10) = * + F(7)
F(7) = G(6)
G(6) = * + F(3)
F(3) = G(2)
G(2) = * + F(-1)
*
*
* *
* *
* * *