Скачать: CL | DM;

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

← →
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 вся ветка

Скачать: CL | DM;



Память: 0.46 MB
Время: 0.027 c