Макинтош и образование:Информатика и ИТ:

Методами перебора можно решать задачи на поиск экстремума, оптимизационные и т. п

1.1  Метод случайного перебора с фиксированными границами

Генерируются псевдослучайные значения переменной величины. Как только относительная погрешность оказывается меньше заданной процесс прекращается

1.2  Метод прямого упорядоченного перебора с постоянным шагом (метод равномерного поиска)

Значение переменной величины изменяется с постоянным шагом (равным, например, допустимой ошибке ответа по этой величине). Процесс прекращается при получении нужного значения целевой функции

1.3  Метод упорядоченного перебора с переменным шагом (метод поразрядного приближения)

Значение переменной величины изменяется с некоторым достаточно большим шагом. Как только целевая функция перейдет искомое значение, отходим на шаг¹ назад и начинаем движение с уменьшенным в R раз шагом (при R = 10 метод называется методом подекадного приближения). Процесс повторяется до достижения требуемой точности

1.4  Метод поразрядного приближения с изменением направления поиска (<<затухающего маятника>>)

Аналогично предыдущему, но вместо отступления на шаг изменяется направление движения по числовой оси

1.5  Метод Монте-Карло

На числовой отрезок <<бросаются>> случайные точки. Подсчитывается, какая часть из них оказалась в части отрезка, где значение целевой функции превосходит заданное. Затем отрезок делится пропорционально этому числу

1.6  Метод половинного деления (дихотомии)

Числовой отрезок делится на две равные части. По значению целевой функции в средней точке определяется, на какой половине отрезка располагается искомое значение. Затем процедура деления повторяется до достижения требуемой точности

1.7  Метод <<золотого сечения>>

Аналогично методу дихотомии, но отрезок делится на части в соответствии с пропорцией <<золотого сечения>>: D = (sqrt(5)-1)/2

1.8  Метод случайного перебора с переменными границами

Метод подобен методу дихотомии, но отрезок делится случайным образом

Задача 1 Снаряд зенитного орудия вылетает вертикально вверх с начальной скоростью v₀ = 1000 м/с и взрывается на некоторой высоте. Звук взрыва был услышан в месте расположения орудия через 7 секунд после выстрела. На какой высоте взорвался снаряд? Скорость звука равна 330 м/с.

Литература

[1]

В. Г. Петросян, Т. В. Петросян. Методы перебора в решении физических задач//Информатика и образование. 1996. 3 с. 73-83.

Примечания:

¹ при поиске экстремума может потребоваться <<отступление>> назад на 2 шага