Рассмотрите число 20 вопросов игры. В этой игре игрок 1 думает о числе в диапазоне от 1 до n. Игрок 2 должен выяснить это число, задав наименьшее количество истинных/ложных вопросов. Предположите, что никто не обманывает. i. Что такое оптимальная стратегия, если n известно? ii. Что такое хорошая стратегия, n неизвестно?Используйте алгоритм сортировки
См. Эту вики: binary search for number guessing game.
Если n известно, используйте бинарный алгоритм поиска, чтобы найти его, поэтому заданные вопросы не более floor(log2(n)).
Если n неизвестно, вы можете сначала найти верхнюю границу повторным удвоением, а затем применить двоичный поиск. Понятно, что заданные вопросы не более 2 * floor(log2(k)) + 1, где k - неизвестный выбранный номер.
да! Спасибо за это! но в вопросе, он говорит, что это должно быть сделано в Оптимальной и в хорошей стратегии! :( – ECR
Я обновил свой ответ, чтобы дать сложность времени для обоих случаев. Они оказались оптимальными и, безусловно, хорошими стратегиями. –
Это называется бинарным поиском в терминах CS. –
или [Дихотомический поиск] (http://en.wikipedia.org/wiki/Dichotomic_search) –
Двоичный поиск, если 'n' известен, в противном случае проблема становится более интересной. – IVlad