Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Начинающим";
Текущий архив: 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
2-1176908127
stud
2007-04-18 18:55
2007.05.13
недоступность формы


2-1177493618
I-New
2007-04-25 13:33
2007.05.13
Цифровая подпись


2-1177432489
dzhagr
2007-04-24 20:34
2007.05.13
Проблема с SQL-запросом.


2-1177341918
I-New
2007-04-23 19:25
2007.05.13
иконка в длл


15-1176378501
CCili
2007-04-12 15:48
2007.05.13
Как определить что за видеоадаптер?





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский