Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2007.05.13;
Скачать: 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 вся ветка

Текущий архив: 2007.05.13;
Скачать: CL | DM;

Наверх




Память: 0.48 MB
Время: 0.054 c
3-1172500836
avsam
2007-02-26 17:40
2007.05.13
ADO-версия. Как узнать?


15-1176400346
Kostafey
2007-04-12 21:52
2007.05.13
Надежность программного обеспечения


1-1173946566
shreck
2007-03-15 11:16
2007.05.13
Как в делфях сделать то, что на С выглядит следующим образом:


15-1176289781
ArtemESC
2007-04-11 15:09
2007.05.13
Файловый обменник....


15-1176473077
Desdechado
2007-04-13 18:04
2007.05.13
Куда подевались остальные страницы форума?