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

Принцип “разделяй и влавствуй” при построении алгоритмов

• Разделение задачи на несколько подзадач, которые представляют собой меньшие экземпляры той же задачи.
• Властвование над подзадачами путем их рекурсивного решения. Если размеры подзадач достаточно малы, такие подзадачи могут решаться непосредственно.
• Комбинирование решений подзадач в решение исходной задачи.

Если подзадачи достаточно велики для рекурсивного решения, мы называем эту ситуацию рекурсивным случаем. Если подзадачи становятся достаточно малы для того, чтобы не прибегать к рекурсии, мы говорим, что рекурсия “достигает дна” и опускается до базового случая. Иногда, в дополнение к подзадачам, которые представляют собой меньшие экземпляры той же задачи, приходится решать под­задачи, несколько отличающиеся от исходной задачи. Мы рассматриваем решение таких подзадач как часть шага комбинирования.

Задача поиска максимального подмассива

Задача поиска максимального подмассива

Предположим, что у вас появилась возможность вложить деньги в корпорацию по производству неустойчивых химических соединений Volatile Chemical Corpo­ration. Подобно производимой продукции цена акций Volatile Chemical Corpora­tion тоже очень неустойчива. Вы можете купить только один комплект акций и продать его в какой-то другой день, осуществляя покупки и продажи после за­крытия торгов. Ваши неудобства компенсируются тем, что вы владеете информа­цией о будущих ценах на акции. Ваша цель — получить максимальную прибыль. На рис. 4.1 показана цена акций за 17-дневный период. Вы можете покупать ак­ции в любой день, начиная с нулевого дня, когда цена равна $100. Конечно, вы захотите купить подешевле, а продать подороже, но — увы! — так может и не по­лучиться. На рис. 4.1 наименьшая цена достигается после седьмого дня, т.е. после того, как

Цена
Изменение
100 113 110 85 105 102 86 63 81 101 94 106 101 79 94 90 97