Вниз
Скачать: 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.029 c
2-1176958517
san655
2007-04-19 08:55
2007.05.13
Не изменяется свойство Count у компонента Listbox


15-1176752457
Raderd
2007-04-16 23:40
2007.05.13
Как на форме перемещать объекты?


6-1162213016
arefart
2006-10-30 15:56
2007.05.13
Перехват пакетов


15-1176232304
ArtemESC
2007-04-10 23:11
2007.05.13
Как выципить мелодию которая подоется на колонки?


15-1176128895
default
2007-04-09 18:28
2007.05.13
Фень Юань "Программирование графики для windows"




   Наверх