Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Метод динамического программирования


Var

Begin

Var

Тип Variant

Else

If4 inB then

Else

writeln('4 Is Not inC');

 

writeln(' 4 Is inB')

writeln('4 Is Not inB');

 

ShowElementsOfSet('A', A);

ShowElementsOfSet('B', B);

 

P := A + B;

ShowElementsOfSet('A+B', P);

 

P := A - B;

ShowElementsOfSet('A-B', P);

 

ShowElementsOfSet('A*B', A * B + [0]);

 

readln;

end.

 

 


V1, V2, V3, V4: Variant;

I: Integer; D: Double; S: string;

V1 := 1; // integer value, integer type

V2 := 1234.5678; // real value, real type

V3 := ‘1000’; // stringvalue, string type

V4 := V1 + V2 + V3; // double value 2235.5678, double type

I := V1;

D := V2;

S := V3; // S=’1000’

I := V4; // I = 2236

end;

 

Delphi: Help, “Variant type conversions

 

 

VB6, VBA-MS/Office: Тип Variant разрешен.

 

VBScript: Все переменные есть переменные типа Variant.

 

VB.Net: Тип Variant запрещен.

 

 


Тип «Денежный»

 

x: Currency;

 

Диапазон изменения: –922337203685477.5808 . . 922337203685477.5807

Объем памяти: 8 байт.

 


 

Пример. Найти наиболее «дешевый» путь от элемента матрицы размера до элемента . Второй способ решения задачи.

Проект ProjectBoth прилагается. В нём реализованы оба подхода к решению задачи.

 

Идея метода динамического программирования состоит в следующем. Для каждого элемента строится оптимальный путь от него до конца пути. Сначала это делается для всех элементов, которые в одном шаге от конца пути. Затем для всех элементов, которые в двух шагах от конца пути. Затем для всех элементов, которые в трёх шагах от конца пути. И так далее.

 

Пусть матрица цен имеет размер и выглядит так:


Пусть есть цена оптимального пути от элемента до конца пути.

Множество предпоследних элементов (1-я волна):

, двигаться можно только вниз;

, двигаться можно только вправо.

Множество «предпредпоследних» элементов (2-я волна):

, двигаться можно только вниз;

, двигаться лучше вправо;

, двигаться можно только вправо.

 

 

Множество «предпредпредпоследних» элементов (3-я волна):

, двигаться можно только вниз;

, двигаться лучше вниз;

, двигаться лучше вправо;

, двигаться можно только вправо.
Таким образом, можно найти цены и начальное направления оптимального пути для всех «волн», а значит, и для всех элементов матрицы, заканчивая элементом . Результат поиска показан в виде постановки при каждом элементе матрицы двух индексов: цена оптимального пути от этого элемента до конца (нижний индекс), направление оптимального пути от этого элемента (верхний индекс).



 

<== предыдущая лекция | следующая лекция ==>
If 4 in C then | Условная компиляция

Дата добавления: 2014-01-04; Просмотров: 151; Нарушение авторских прав?


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2020) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.004 сек.