Угадывая неограниченное целое число - PullRequest
4 голосов
/ 20 августа 2009

Если я скажу вам:

«Я думаю о числе от 0 до n, и я скажу вам, является ли ваше предположение высоким или низким», тогда вы сразу же доберетесь до бинарного поиска.

Что если я уберу верхнюю границу? то есть я думаю о положительном целом числе, и вам нужно угадать его.

Один из возможных способов - угадать 2, 4, 8, ..., пока вы не угадаете 2 ** k для некоторого k, и я скажу «ниже». Тогда вы можете применить бинарный поиск.

Есть ли более быстрый метод?

EDIT:

Очевидно, что любое решение займет время, пропорциональное размеру целевого числа. Если я проверю число Грэма через функцию Аккермана, мы подождем некоторое время, какую бы стратегию вы ни преследовали.

Я мог бы предложить и этот алгоритм: угадывайте каждое целое число по очереди, начиная с 1.

Это гарантированно закончится за ограниченное количество времени, но все же это явно намного хуже, чем моя стратегия "полномочия 2". Если я найду худший алгоритм (и знаю, что он хуже), то, может быть, я найду лучший?

Например, вместо степеней 2, может быть, я могу использовать степени 10. Затем я нахожу верхнюю границу с шагом log_10(n) вместо log_2(n) шагов. Но я должен искать больше места. Скажите k = ceil(log_10(n)). Затем мне нужно log_2(10**k - 10**(k-1)) шагов для моего бинарного поиска, который, я думаю, составляет около 10+log_2(k). Для степеней 2 у меня есть примерно log_2(log_2(n)) шагов для фазы поиска. Кто победит?

Что если я буду искать вверх, используя n**n? Или какая-то другая последовательность? Получит ли приз тот, кто сможет найти последовательность, которая растет быстрее всего? Это проблема с ответом?

Спасибо за ваши мысли. И мои извинения тем из вас, кто предложил мне начать с MAX_INT или 2 ** 32-1, так как я явно отдаляюсь от границ практичности здесь.

Окончательное редактирование:

Привет всем,

Спасибо за ваши ответы. Я принял ответ Нормана Рэмси (и еще одного комментатора) для того, что я понял следующим аргументом: для целевого числа n любая стратегия должна быть способна различать (по крайней мере) числа от 0..n, что означает вам нужно (как минимум) O (log (n)) сравнений.

Однако некоторые из вас также указали, что проблема не является четко определенной, во-первых, потому что невозможно выбрать «случайное положительное целое число» при равномерном распределении вероятности (или, скорее, равномерное распределение вероятности не может существовать над бесконечным множеством). И как только я дам вам неравномерное распределение, вы можете разделить его пополам и применить бинарный поиск как обычно.

Это проблема, о которой я часто размышлял, когда ходил, поэтому я рад получить два убедительных ответа на нее.

Ответы [ 13 ]

15 голосов
/ 20 августа 2009

Если действительно нет верхней границы, и все числа вплоть до бесконечности одинаково вероятны, то нет оптимального способа сделать это. Для любого конечного предположения G вероятность того, что число меньше, чем G, равна нулю, а вероятность того, что оно выше, равна 1, поэтому не существует конечного предположения, которое имеет ожидание быть больше, чем число.

ОТВЕТ НА РЕДАКТИРОВАНИЕ ДЖОНА :

По тем же соображениям, что ожидается, что степени 10 будут лучше, чем степени 2 (есть только конечное число возможных N, для которых степени 2 лучше, и бесконечное число, где степени 10 лучше), степени 20 может быть лучше, чем 10.

Таким образом, в принципе, да, приз идет к самой быстро растущей последовательности (и для той же самой последовательности, самой высокой начальной точки) - для любой данной последовательности можно показать, что более быстрая растущая последовательность выиграет в бесконечно большем количестве случаев. А поскольку для любой последовательности, которую вы называете, я могу назвать одну, которая растет быстрее, а для любого целого числа, которое вы называете, я могу назвать одну более высокую, нет ответа, который нельзя улучшить. (И каждый алгоритм, который в конечном итоге даст правильный ответ, имеет ожидаемое число догадок, которое в любом случае бесконечно).

5 голосов
/ 20 августа 2009

Люди (которые никогда не изучали вероятность) склонны думать, что «выбрать число от 1 до N» означает «с равной вероятностью каждого», и они действуют согласно своему интуитивному пониманию вероятности.

Затем, когда вы говорите «выберите любое положительное целое число», они все еще думают, что это означает «с равной вероятностью каждого».

Это, конечно, невозможно - не существует дискретного распределения вероятностей с областью положительных целых чисел, где p (n) == p (m) для всех n, m.

Итак, человек, выбирающий номер, должен был использовать другое распределение вероятностей. Если вы вообще что-то знаете об этом распределении, то вы должны основывать свою схему угадывания на этих знаниях, чтобы иметь «самое быстрое» решение.

Единственный способ рассчитать, насколько «быстрой» является данная схема угадывания, - это рассчитать ожидаемое количество догадок, чтобы найти ответ. Вы можете сделать это, только предполагая распределение вероятностей для целевого числа. Например, если они выбрали n с вероятностью (1/2) ^ n, то я думаю, что ваша лучшая схема угадывания - «1», «2», «3», ... (в среднем 2 догадки). Я не доказал это, хотя, может быть, это какая-то другая последовательность догадок. Конечно, догадки должны начинаться с малого и расти медленно. Если они выбрали 4 с вероятностью 1 и все другие числа с вероятностью 0, то ваша лучшая схема угадывания - «4» (в среднем 1 угадывание). Если они выбрали число от 1 до триллиона с равномерным распределением, вам следует выполнить бинарный поиск (в среднем около 40 догадок).

Я говорю, что единственный способ определить «быстрый» - вы могли бы взглянуть на худший случай. Вы должны принять ограничение на цель, чтобы все схемы не имели одинаковую скорость, а именно: «нет ограничения в худшем случае». Но вам не нужно предполагать распределение, и ответ для «самого быстрого» алгоритма в этом определении очевиден - бинарный поиск начинается с выбранной вами границы. Так что я не уверен, что это определение ужасно интересно ...

На практике вы не знаете распределение, но можете сделать несколько образованных предположений, основываясь на том факте, что сборщик - это человек, и сколько людей способны зачать. Как кто-то говорит, если число, которое они выбрали, является функцией Аккермана для числа Грэма, то у вас, вероятно, проблемы. Но если вы знаете, что они способны представлять выбранное число цифрами, то это фактически устанавливает верхний предел числа, которое они могли выбрать. Но это все еще зависит от того, какие методы они могли использовать для генерации и записи числа, и, следовательно, насколько вам известно о вероятности того, что число будет иметь конкретную величину.

4 голосов
/ 20 августа 2009

В худшем случае вы можете найти его во времени логарифмически по размеру ответа, используя именно те методы, которые вы описываете. Вы можете использовать функцию Аккермана, чтобы найти верхнюю границу быстрее, чем логарифмическое время, но тогда двоичный поиск между угаданным числом и предыдущим предположением потребует логарифмического времени в размере интервала, который (если догадки растут очень быстро) близок к логарифмический по размеру ответа.

Было бы интересно попытаться доказать , что более быстрого алгоритма нет (например, O (log log n) ), но я понятия не имею, как это сделать.

3 голосов
/ 20 августа 2009

Математически говоря:

Вы не можете правильно найти это целое число. На самом деле, строго говоря, утверждение «выбрать любое положительное целое число» бессмысленно, так как его невозможно сделать: хотя вы, как человек, можете верить, что можете это сделать, вы фактически выбираете из ограниченного набора - вы просто не осознаёте границ .

В вычислительном отношении:

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

2 голосов
/ 20 августа 2009

Двоичный поиск можно обобщить: каждый раз набор возможных вариантов должен быть разделен на подмножества вероятности 0,5. В этом случае это все еще применимо к бесконечным множествам, но все еще требует знания о распределении (для конечных множеств это требование часто забывают) ...

1 голос
/ 20 августа 2009

Поскольку вы не указываете какое-либо распределение вероятностей чисел (как правильно упоминали другие, не существует равномерного распределения по всем натуральным числам), Теорема о бесплатном обеде дает ответ: Любой метод (который не повторяет одно и то же число дважды) так же хорош, как и любой другой.

Как только вы начинаете делать предположения о распределении (например, это число выбирается человеком или двоичным компьютером и т. Д.), Это, конечно, меняется, но, как указано, проблема любой алгоритм так же хорош как и любой другой при усреднении по всем возможным распределениям.

1 голос
/ 20 августа 2009

Стандартное предположение по умолчанию о равномерном распределении для всех натуральных чисел не приводит к решению, поэтому вам следует начать с определения вероятностного распределения чисел для угадывания.

1 голос
/ 20 августа 2009

Если предположить верхнюю границу числа, генерируемого компьютером, я бы начал с 2 ** [число бит / 2], а затем увеличил или уменьшил на степени два. Это, по крайней мере, дает вам наиболее близкие к возможным значениям в наименьшем количестве прыжков.

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

1 голос
/ 20 августа 2009

Используйте бинарный поиск, начиная с MAX_INT / 2, где MAX_INT - наибольшее число, которое может обработать ваша платформа.

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

ОБНОВЛЕНИЕ: Учитывая, что вы настаиваете на вхождении в бесконечность, я просто проголосую, чтобы закрыть ваш вопрос как не связанный с программированием: -)

1 голос
/ 20 августа 2009

Мое главное уточнение заключается в том, что я бы начал с более высокого первого предположения вместо 2, примерно среднего значения, которое я ожидал от них выбрать. Начиная с 64, можно сэкономить 5 догадок против 2, если число превышает 64, при стоимости 1-5 больше, когда оно меньше. 2 имеет смысл, если вы ожидаете, что ответ будет примерно в 1 или 2 раза меньше. Вы могли бы даже сохранить память о прошлых ответах, чтобы решить, какое первое предположение лучше. Другое улучшение может заключаться в том, чтобы пробовать негативы, когда они говорят «ниже» на 0.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...