Форум: "Начинающим";
Текущий архив: 2007.05.13;
Скачать: [xml.tar.bz2];
ВнизНеобычная задача на поиск числа. Найти похожие ветки
← →
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]> Причем чем больше аргумент функции, тем больше необходимо времени на выполнение.
Если конкретизирован закон, по которому это время растет в зависимости от роста аргумента, тогда обретает смысл и задача "как за наименьшее время найти число".
← →
TUser © (2007-04-23 10:09) [4]Тут, вроде, не просто бинарный поиск нужен. Там время вычисления всегда одно. А в задаче - зависит от аргумента по некоторой возрастающей функции F(x). Предлагаю эвристику - на каждом шаге поиска выбирать среднее значение аргумента так, чтобы интеграл F(x)dx справа и слева был одинаковым (предполагается, что вычисления такого значения аргумента - за O(1)). Обоснование - мы тогда оставляем в среднем равное время на поиск справа и слева. Точно доказать, что это будет минимум в среднем - не могу.
Страницы: 1 вся ветка
Форум: "Начинающим";
Текущий архив: 2007.05.13;
Скачать: [xml.tar.bz2];
Память: 0.45 MB
Время: 0.04 c