Практика 1.
Базовую теорию МПО, думаю, я зафиксировал. Немножко попрактикуемся на разных задачках.
"Из Лондона в Хогвартц и из Хогвартца в Лондон на рассвете (одновременно) вышли навстречу друг другу (по одной дороге) Гарри Поттер и Хагрид. Они встретились в полдень, но не остановились, а каждый продолжала идти с той же скоростью, и Гарри Поттер пришел (в Хогвартц) в 4 часа дня, а Хагрид (в Лондон) в 9 часов вечера. В котором часу был в этот день рассвет?"
В качестве пробы здесь можно выбирать час рассвета. Всего будут такие варианты 0,1,2,3,...12. Можно бы и уменьшить число вариантов (3,4,5,6,7,8), но для этого нужно чуть-чуть подумать. Чтобы понять как определять ошибку, возьмем одну пробу и посмотрим, что получается. Пусть рассвет был в 0 часов. Тогда путь, который прошел Гарри Поттер за 12 часов, Хагрид прпошел за 9. Значит скорость Хагрида должна быть больше, т.е. скорость Гарри Поттера составляет 9/12 от скорости Хагрида (v1=9/12 v2). Но с другой стороны, путь, который прошел Хагрид за 12 часов, Гарри Поттер одолел за 4 часа. И скорость мальчика, который выжил, должна быть больше скорости Хагрида, т.е. v1=12/4 v2 . Получается противоречие. Т.е. ошибка, это когда при подстановке предполагаемого времени рассвета в условия задачи, не сходятся результаты вычислений пропорции между скоростями. Если все сошлось, то и час рассвета определен правильно. Можно было бы подбирать часы по очереди 0,1 и т.д. Но мы пойдем другим путем и заодно познакомимся с одним из вариантов математического алгоритма - дихотомией (деление пополам). 0 часов не подходит, но и 12 часов тоже не подходит, а это два крайних значения рассматриваемого диапазона. Следующим шагом возьмем середину диапазона - 6 часов утра. Тогда скорость Гарри Поттера 9/6=3/2 от скорости Хагрида v1=3/2 v2, а скорость Хагрида 4/6=2/3 от скорости Гарри, v2=2/3 v1! Все сходится! Ура, рассвет был в 6 часов, что мы обнаружили с третьей попытки. Вот она сила математических алгоритмов.
Да ладно, нам просто повезло. Или не повезло, ведь не получилось показать важный принцип в методе дихотомии - какой из двух новых интервалов делить пополам (если бы 6 утра не подошло, то рассвет был от 0 до 6, либо от 6 до 12, а значение ошибки при выборе 6 утра однозначно бы показало какую половину оставить). Чтобы с этим разобраться посмотрим на пробу рассвет в 3 утра, что дает расхождение в скоростях v1=9/9 v2=a v2 или v1=9/4 v2=b v2. А при попытке в 10 утра, v1=9/2 v2=a v2 или v1=2/4 v2=b v2. Здесь я вижу, что нужно ввести два обозначения a,b для отношения скоростей старушек определенных по первому и по второму условиям, a(t)=9/(12-t), b(t)=(12-t)/4. Ошибка тогда это разница между a и b. Вообще, а и b это функции от времени рассвета. Посмотрим на знак ошибки для разных вариантов рассвета
a(0)-b(0)<0,
a(3)-b(3)<0,
a(6)-b(6)=0 ,
a(10)-b(10)>0,
a(12)-b(12)=+Infinity-0>0.
То есть, если выберем рассвет чуть раньше - ошибка будет отрицательной, а чуть позже - ошибка будет положительной. Значит при разбиении интервала пополам, если ошибка в середине получилась положительной, то рассвет нужно искать в ранней половине, а если ошибка отрицательная, то искать нужно в поздней половине. В этой задаче, в отличии от задачи про кирпич, гарантии, что мы достигнем нулевой ошибки нет. Хотя, с практической точки зрения, знать время рассвета с точностью большей чем секунды и не нужно.