Необычная задача на поиск числа.

← →
Ezorcist (2007-04-23 08:15) [0]

Необходимо найти число Z (такое, что оно лежит на оси абсцисс левее некоторого Z0 на расстоянии не больше заданного D) при помощи функции F(X):Boolean; Если функция вернет истину, то X лежит правее заданного числа Z0, если ложь - левее. Причем чем больше аргумент функции, тем больше необходимо времени на выполнение. Вопрос: как за наименьшее время найти число?

← →
MBo © (2007-04-23 08:37) [1]

>Если функция вернет истину, то X лежит правее заданного числа Z0, если ложь - левее
А если равно, то всей планете кирдык ? ;)

Доопределяешь задачу с учетом замечания, открываешь любую книжку по численным методам и читаешь о методе половинного деления. Собственно говоря, из его названия все понятно.
Или в книжках по алгоритмам - Бинарный поиск.

← →
Думкин © (2007-04-23 08:51) [2]

> Ezorcist (23.04.07 08:15)

Потом реши сложнее:
Есть функция F(x,y): boolean оторая возвращает истину если внутри фигуры или на границе, и ложь если вне. Найти площадь фигуры. Причем известно, что фигура образует компактное множество, которое можно триангулировать на выпуклые множества в количиестве не больше N.

← →
palva © (2007-04-23 09:48) [3]

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

Тут, вроде, не просто бинарный поиск нужен. Там время вычисления всегда одно. А в задаче - зависит от аргумента по некоторой возрастающей функции F(x). Предлагаю эвристику - на каждом шаге поиска выбирать среднее значение аргумента так, чтобы интеграл F(x)dx справа и слева был одинаковым (предполагается, что вычисления такого значения аргумента - за O(1)). Обоснование - мы тогда оставляем в среднем равное время на поиск справа и слева. Точно доказать, что это будет минимум в среднем - не могу.

Необычная задача на поиск числа. Найти похожие ветки