Вот загадывают допустим число от $% n \in [0;\infty) $%, получается ли(во всех случаях) число двоичным поиском найти это число не получится?

задан 18 Июн '17 1:24

Просто у алгоритма же всегда два конца, который всегда выполняется и который всегда не выполняется, а потом дихотомия, а в случае с бесконечностью... Не понятно и если двоичным поиском не удастся, то как отгадывать произвольные числа из этого диапазона?

(18 Июн '17 1:26) Williams Wol...

@Williams Wol...: старайтесь по возможности грамотно писать по-русски. Ведь тут само строение фраз просто ужасающее. Перечитайте, и послушайте, как этот текст звучит.

Из общих соображений понятно, что найти загаданное число всегда можно -- на худой конец, спрашивая про все числа подряд. Тогда число будет угадано за n шагов (или n+1, но это не важно). Можно также спрашивать про двоичные разряды числа, что аналогично принципу двоичного поиска. После того, как мы узнали последние несколько разрядов, можно спросить, не оно ли загадано. Здесь будет нужно примерно 2log n вопросов.

(18 Июн '17 1:56) falcao

@Williams Wol... Кстати, равновероятно загадать число на $%[0,\infty)$% - невозможно. Вроде есть какой-то такой парадокс, если не ошибаюсь.

(18 Июн '17 3:40) abc

@abc, да? А мне кажется это вроде просто, есть генераторы аля [0;pi/2] и передать аргумент $%tan(x)$% и вот равномерное бесконечное число, ну может не совсем понятно как до иррационального числа брать, тогда что-то рациональное придумать.

(18 Июн '17 4:51) Williams Wol...

@abc: равномерного распределения на счётном множестве в самом деле не существует, но оно здесь и не нужно.

@Williams Wol...: для того генератора с тангенсом, который Вы предлагаете, получится заведомо не равномерное распределение. Появление "очень больших" чисел будет крайне маловероятно -- как и нахождение равномерно брошенной на отрезок точки сильно вблизи одного из его концов.

(18 Июн '17 6:09) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,709

задан
18 Июн '17 1:24

показан
253 раза

обновлен
18 Июн '17 6:09

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru