Презентация "Динамическое программирование: вычисление рекурсивных функций" (11 класс углубленный уровень)

Динамическое программирование (вычисление рекурсивных функций)

Болгова Н.А.

МБОУ СОШ с УИОП с.Тербуны

Тербунского муниципального района Липецкой области

Определение:

Динамическое программирование – это способ решения сложных задач путем сведения их к более простым задачам того же типа.

Рекурсия — это функция, которая вызывает саму себя.

Процедура(подпрограмма) в Python

def имя(переменные):

локальные переменные

(внутри процедуры)

return

основная программа:

глобальные переменные

(основная + процедура)

1 Составьте рекурсию для вычисления функции F(7) и найдите ее значение. 1- алгоритм или дерево 2- программа в Python " width="640"

Задача № 16 (ЕГЭ, П, 5 мин)

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

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

Составьте рекурсию для вычисления функции F(7) и найдите ее значение.

1- алгоритм или дерево

2- программа в Python

1 F(7) = 7 + 1 + F(6) F(6) = 6 + 1 + F(5) F(5) = 5 + 1 + F(4) F(4) = 4 + 1 + F(3) F(3) = 3 + 1 + F(2) F(2) = 2 + 1 + F(1) F(7) = 8 + 26 = 34 F(6) = 7 + 19 = 26 F(5) = 6 + 13 = 19 F(4) = 5 + 8 = 13 F(3) = 4 + 4 = 8 F(2) = 3 + 1 = 4 Ответ: 34 " width="640"

Алгоритм работы рекурсии: F ( n ) = n + 1 + F ( n– 1), при n 1

F(7) = 7 + 1 + F(6)

F(6) = 6 + 1 + F(5)

F(5) = 5 + 1 + F(4)

F(4) = 4 + 1 + F(3)

F(3) = 3 + 1 + F(2)

F(2) = 2 + 1 + F(1)

F(7) = 8 + 26 = 34

F(6) = 7 + 19 = 26

F(5) = 6 + 13 = 19

F(4) = 5 + 8 = 13

F(3) = 4 + 4 = 8

F(2) = 3 + 1 = 4

Ответ: 34

Программа:

увеличивается время обработки " width="640"

Библиотеки Python:

import sys sys.setrecursionlimit(1000000)

from functools import lru_cache

@lru_cache(число) – в памяти хранятся числа, но не в рекурсии- увеличивается время обработки

1: return x * f(x - 1) print(f(2023) / f(2020)) " width="640"

№ 16-1

def f(x): if x == 1: return 1 if x 1: return x * f(x - 1) print(f(2023) / f(2020))

1: return x * f(x - 1) for x in range(20,2020): f(x) print(f(2023) / f(2020)) " width="640"

from functools import lru_cache @lru_cache(1000) def f(x): if x == 1: return 1 if x 1: return x * f(x - 1)

for x in range(20,2020): f(x) print(f(2023) / f(2020))

import sys sys.setrecursionlimit(1000000) def f(x): return 2 * (g(x - 3) + 8) def g(x): if x return 2 * x else : return g(x - 2) + 1 print(f(15548))

№ 67

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

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

F ( n ) = n + 2* F ( n + 2), когда n ≥ 3 и четно,

F ( n ) = F ( n – 2) + n – 2, когда n ≥ 3 и нечетно.

Сколько существует чисел n , для которых значение F ( n ) определено и будет трехзначным?

1 вариант

2 вариант

Ручное решение

3: break print(k) " width="640"

k = 0 for n in range(1, 10001, 2): a_n = str(f(n)) if len(a_n) == 3: k += 1 if len(a_n) 3: break print(k)

1 Найти  (F(2024) + 2 × F(2023)) / F(2022) 2) F(n)=n при n 2024; F(n)=n × F(n+1), если n ≤ 2024. Найти  F(2022) / F(2024) " width="640"

Практика ( файлы 16-1фипи, 16-2фипи

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

F(n)=(n−1) × F(n−1), если n 1

Найти  (F(2024) + 2 × F(2023)) / F(2022)

2) F(n)=n при n 2024; F(n)=n × F(n+1), если n ≤ 2024.

Найти  F(2022) / F(2024)

файл 16-3джобс

Литература:

• Поляков К.Ю., Еремин Е.А. «Информатика 10 класс (базовый и углубленный уровни)»- Москва, Бином, 2018)
• informatics.mccme.ru
• Питон тьютор
• Python 3.7