🗊Презентация Динамическое программирование

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Динамическое программирование, слайд №1Динамическое программирование, слайд №2Динамическое программирование, слайд №3Динамическое программирование, слайд №4Динамическое программирование, слайд №5Динамическое программирование, слайд №6Динамическое программирование, слайд №7Динамическое программирование, слайд №8Динамическое программирование, слайд №9Динамическое программирование, слайд №10Динамическое программирование, слайд №11Динамическое программирование, слайд №12Динамическое программирование, слайд №13Динамическое программирование, слайд №14Динамическое программирование, слайд №15Динамическое программирование, слайд №16Динамическое программирование, слайд №17Динамическое программирование, слайд №18Динамическое программирование, слайд №19Динамическое программирование, слайд №20Динамическое программирование, слайд №21Динамическое программирование, слайд №22Динамическое программирование, слайд №23Динамическое программирование, слайд №24
Скачать
Вы можете ознакомиться и скачать презентацию на тему Динамическое программирование. Доклад-сообщение содержит 24 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Динамическое программирование
Описание слайда:
Динамическое программирование

Слайд 2


Динамическое программирование, слайд №2
Описание слайда:

Слайд 3


Динамическое программирование, слайд №3
Описание слайда:

Слайд 4


Динамическое программирование, слайд №4
Описание слайда:

Слайд 5


Динамическое программирование, слайд №5
Описание слайда:

Слайд 6


Динамическое программирование, слайд №6
Описание слайда:

Слайд 7


Числа Фибоначчи Решение методом «динамического программирования» предполагает запоминание каждого числа в массиве. Тогда N-е число Фибоначчи легко можно найти по следующей формуле: F[N] = F[N-1] + F[N-2], при N > 2.
Описание слайда:
Числа Фибоначчи Решение методом «динамического программирования» предполагает запоминание каждого числа в массиве. Тогда N-е число Фибоначчи легко можно найти по следующей формуле: F[N] = F[N-1] + F[N-2], при N > 2.

Слайд 8


Задача об n – битных двоичных числах Найти количество F всех n – битных двоичных чисел, у которых в двоичной записи нет подряд идущих двух единиц. (N≤30).
Описание слайда:
Задача об n – битных двоичных числах Найти количество F всех n – битных двоичных чисел, у которых в двоичной записи нет подряд идущих двух единиц. (N≤30).

Слайд 9


Динамическое программирование, слайд №9
Описание слайда:

Слайд 10


Зайчик на лесенке На вершине лесенки, содержащей N ступенек, находится зайчик, который начинает прыгать по ним вниз, к основанию. Зайчик может прыгнуть на следующую ступеньку, на ступеньку через 1 или 2. Определить число всевозможных “маршрутов” зайчика с вершины на землю.
Описание слайда:
Зайчик на лесенке На вершине лесенки, содержащей N ступенек, находится зайчик, который начинает прыгать по ним вниз, к основанию. Зайчик может прыгнуть на следующую ступеньку, на ступеньку через 1 или 2. Определить число всевозможных “маршрутов” зайчика с вершины на землю.

Слайд 11


Зайчик на лесенке Пусть зайчик находится на ступеньке с номером X. По условию он может спрыгнуть на ступеньки с номерами X - 1, X - 2 и X - 3. Пусть F(X) - число маршрутов со ступеньки X до земли F[X] = F[X – 1] + F[X – 2] + F[X – 3]
Описание слайда:
Зайчик на лесенке Пусть зайчик находится на ступеньке с номером X. По условию он может спрыгнуть на ступеньки с номерами X - 1, X - 2 и X - 3. Пусть F(X) - число маршрутов со ступеньки X до земли F[X] = F[X – 1] + F[X – 2] + F[X – 3]

Слайд 12


Программа на С++ #include <iostream> using namespace std; int main() { int N; long long F[31]; cin>>N; F[1]=1;F[2]=2;F[3]=4; for(int i=4; i <= N; i++) F[i]=F[i-1]+F[i-2]+F[i-3]; cout<<F[N]; return 0; }
Описание слайда:
Программа на С++ #include <iostream> using namespace std; int main() { int N; long long F[31]; cin>>N; F[1]=1;F[2]=2;F[3]=4; for(int i=4; i <= N; i++) F[i]=F[i-1]+F[i-2]+F[i-3]; cout<<F[N]; return 0; }

Слайд 13


Задача о фишке Фишка может двигаться по полю длины N только вперед. Длина хода фишки не более K (N, K ≤10). Найти количество различных путей, по которым фишка может пройти поле от позиции 1 до позиции N.
Описание слайда:
Задача о фишке Фишка может двигаться по полю длины N только вперед. Длина хода фишки не более K (N, K ≤10). Найти количество различных путей, по которым фишка может пройти поле от позиции 1 до позиции N.

Слайд 14


Задача о фишке Пусть S[i] - количество различных путей, по которым фишка может пройти поле от начала до позиции с номером i. Предположим, что для любого j от 1 до i известны значения величин S[j]. Задача состоит в определении правила вычисления значения S[i+1], используя значения известных величин. Заметим, что в позицию с номером i+1 фишка может попасть из позиций i, i-1,...,i-k. S[i+1]=S[i]+S[i-1]+...+S[i-k] Вычисляя последовательно значения величин S[1], S[2],..., S[N] по правилу, получаем значение S[N] – решение задачи
Описание слайда:
Задача о фишке Пусть S[i] - количество различных путей, по которым фишка может пройти поле от начала до позиции с номером i. Предположим, что для любого j от 1 до i известны значения величин S[j]. Задача состоит в определении правила вычисления значения S[i+1], используя значения известных величин. Заметим, что в позицию с номером i+1 фишка может попасть из позиций i, i-1,...,i-k. S[i+1]=S[i]+S[i-1]+...+S[i-k] Вычисляя последовательно значения величин S[1], S[2],..., S[N] по правилу, получаем значение S[N] – решение задачи

Слайд 15


Динамическое программирование, слайд №15
Описание слайда:

Слайд 16


Задача о черепашке
Описание слайда:
Задача о черепашке

Слайд 17


Формулировка задачи динамического программирования Дано: множество состояний в том числе начальное и конечное множество возможных переходов из одного состояния в другое с каждым переходом связывается числовой параметр интерпретируется как затраты, выгода, расстояние, время и т.п. Найти: оптимальную последовательность переходов (путь) из начального состояния в конечное максимум или минимум суммы числовых параметров предполагается, что хотя бы один путь из начального состояния в конечное существует
Описание слайда:
Формулировка задачи динамического программирования Дано: множество состояний в том числе начальное и конечное множество возможных переходов из одного состояния в другое с каждым переходом связывается числовой параметр интерпретируется как затраты, выгода, расстояние, время и т.п. Найти: оптимальную последовательность переходов (путь) из начального состояния в конечное максимум или минимум суммы числовых параметров предполагается, что хотя бы один путь из начального состояния в конечное существует

Слайд 18


Пример
Описание слайда:
Пример

Слайд 19


Математическая запись
Описание слайда:
Математическая запись

Слайд 20


Принцип оптимальности Беллмана Если вершины A и B лежат на оптимальном пути между вершинами 0 и X, то часть оптимального пути от 0 до X между вершинами A и B непременно является оптимальным путём от A до B. Следствие Чтобы найти оптимальный путь от 0 до A, достаточно исследовать продолжения к A всех оптимальных путей до вершин, предшествующих A Продолжения неоптимальных путей к предшествующим вершинам можно не просчитывать: они никогда не дадут оптимального пути к A Принцип Беллмана позволяет построить простую и эффективную вычислительную процедуру для решения задач динамического программирования
Описание слайда:
Принцип оптимальности Беллмана Если вершины A и B лежат на оптимальном пути между вершинами 0 и X, то часть оптимального пути от 0 до X между вершинами A и B непременно является оптимальным путём от A до B. Следствие Чтобы найти оптимальный путь от 0 до A, достаточно исследовать продолжения к A всех оптимальных путей до вершин, предшествующих A Продолжения неоптимальных путей к предшествующим вершинам можно не просчитывать: они никогда не дадут оптимального пути к A Принцип Беллмана позволяет построить простую и эффективную вычислительную процедуру для решения задач динамического программирования

Слайд 21


Алгоритм решения задач динамического программирования
Описание слайда:
Алгоритм решения задач динамического программирования

Слайд 22


Алгоритм решения задач динамического программирования
Описание слайда:
Алгоритм решения задач динамического программирования

Слайд 23


Экономические приложения
Описание слайда:
Экономические приложения

Слайд 24


Динамическое программирование, слайд №24
Описание слайда:

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию