Есть старая игра: один человек загадывает число, например от 1 до 100, а другой пытается его угадать. После каждой попытки ему говорят только «больше» или «меньше». Как угадывать, чтобы потратить как можно меньше попыток?
Если называть числа подряд — 1, 2, 3, 4… — то на число 98 уйдёт 98 попыток. Это очень долго. А ведь компьютер в играх, телефон в списке контактов и даже обычный бумажный словарь как-то находят нужное среди тысяч и миллионов вариантов почти мгновенно. Значит, есть способ искать умнее.
Я решила разобраться, какой способ угадывания самый быстрый, и доказать это не на словах, а с помощью программы, которая сама сыграет тысячи партий и всё посчитает.
1.2. Гипотеза, цель и задачи
Гипотеза. Если каждый раз называть число из середины того, что ещё осталось, и так отбрасывать сразу половину вариантов, то угадать можно очень быстро: даже для миллиона чисел хватит примерно двадцати вопросов.
Цель работы — наглядно показать и измерить, почему способ «деление пополам» угадывает число намного быстрее, чем перебор чисел подряд.
Чтобы достичь цели, я поставила задачи:
узнать, какие бывают способы угадывать число, и описать их простыми словами;
понять, почему деление пополам отбрасывает половину вариантов за один вопрос;
сделать программу, которая играет в угадывание и считает число вопросов;
провести эксперимент: для разных диапазонов — от 10 до миллиона — сравнить два способа;
сравнить результаты опыта с расчётом и сделать вывод о гипотезе.
1.3. Методы исследования
изучение темы по книгам и интернет-источникам для школьников;
создание компьютерной программы-эмулятора;
компьютерный эксперимент — многократная игра и сбор данных;
сравнение полученных чисел с теоретическим расчётом.
2. Теоретическая часть
2.1. Две стратегии поиска числа
Представим, что загадано число от 1 до N (например, N = 100). Угадывать можно по-разному. Я сравнивала две стратегии.
Перебор подряд. Называем 1, потом 2, потом 3 и так далее, пока не угадаем. Это простой, но медленный способ. Если загадана единица — повезёт, хватит одного вопроса. Если загадано самое большое число — вопросов понадобится ровно N. В среднем — около половины диапазона.
Деление пополам. Называем число из середины диапазона. Нам отвечают «больше» или «меньше» — и одна половина чисел сразу отпадает, она больше не нужна. В оставшейся половине снова берём середину. И так каждый раз отбрасываем половину.
2.2. Почему деление пополам такое быстрое
Главная мысль всей работы: важен не сам размер диапазона, а то, сколько раз его можно разделить пополам, пока не останется одно число.
Возьмём 1000 чисел. Назвали 500 — осталось 500. Потом 250, 125, 63, 32, 16, 8, 4, 2 и, наконец, 1. Получилось всего около десяти шагов. Каждый вопрос уменьшает число «подозреваемых» вдвое:
Сколько раз число N можно поделить пополам — это математическое действие называется логарифм по основанию 2 и записывается log₂N. Нам достаточно знать: это и есть количество нужных вопросов (округлённое вверх).
Удивительное свойство: чтобы диапазон стал в 1000 раз больше, нужно всего около 10 дополнительных вопросов. Поэтому с ростом диапазона число вопросов растёт очень медленно.
2.3. Фокус с карточками и двоичные числа
Тот же секрет лежит в основе фокуса, который умеет моя программа. Берутся 6 карточек с числами. Если я знаю, на каких карточках есть загаданное число, я могу его назвать, просто сложив первые числа этих карточек: 1, 2, 4, 8, 16 и 32.
Эти числа — степени двойки. Любое число от 1 до 63 складывается из них единственным способом. Например, 53 = 32 + 16 + 4 + 1. Получается, что ответы «да/нет» на 6 карточек — это и есть 6 вопросов, а 2 в шестой степени равно 64. Значит, шестью вопросами «да/нет» можно различить 64 разных числа. Это ещё одно подтверждение: каждый вопрос удваивает количество чисел, которые мы умеем различать.
3. Практическая часть
3.1. Программа-эмулятор
Для исследования была сделана программа — страница, которая открывается в браузере и работает без интернета. В ней три части.
«Угадай моё число». Я загадываю число, а компьютер угадывает его делением пополам и показывает на линейке, как исчезает половина вариантов после каждого ответа.
«Карточки-телепаты». Фокус с 6 карточками: я отмечаю, где есть моё число, а программа его называет и объясняет, как сложила степени двойки.
«Эксперимент». Главная часть. Компьютер сам загадывает случайные числа много раз и считает, сколько вопросов нужно каждой из двух стратегий.
3.2. Как проводился эксперимент
Я выбирала диапазоны 1…10, 1…100, 1…1000, 1…10 000, 1…100 000 и 1…1 000 000. Для каждого диапазона компьютер загадывал 5000 случайных чисел и для каждого считал, сколько вопросов задаст перебор подряд и сколько — деление пополам. Потом программа находила среднее и самый худший (самый долгий) случай и сравнивала их с расчётом log₂N. Все числа можно сохранить в файл (кнопка «Сохранить данные»).
Такой опыт честнее, чем сыграть несколько раз руками: 5000 случайных чисел на каждый диапазон убирают влияние везения и показывают настоящую картину.
4. Результаты и их анализ
Результаты эксперимента собраны в таблице 1. Для каждого диапазона показано среднее и худшее число вопросов у обеих стратегий, а в последнем столбце — расчётное значение log₂N.
Таблица 1. Сколько вопросов нужно каждой стратегии (5000 случайных чисел на диапазон).
Видно главное. У перебора подряд среднее число вопросов равно примерно половине диапазона, а худший случай — почти весь диапазон. Для миллиона чисел это в среднем около 500 000 вопросов. А делению пополам даже в худшем случае хватает 20 вопросов.
Ещё одно важное наблюдение: столбец «деление пополам, худший» точно совпал со столбцом log₂N (4, 7, 10, 14, 17, 20). Это значит, что расчёт и опыт дают одинаковый ответ — модель верна.
Рисунок 1. Слева — число вопросов делением пополам почти не растёт. Справа — сравнение двух стратегий (шкала особая: каждое деление по высоте означает рост в 10 раз).
На левом графике хорошо видно: когда диапазон увеличивается в 10 раз, столбик подрастает всего на 3–4 вопроса. На правом графике синяя линия (деление пополам) почти ровная и низкая, а красная (перебор подряд) резко уходит вверх.
Главный итог опыта. Диапазон вырос в 100 000 раз — с 10 до миллиона чисел. При этом делением пополам число вопросов выросло всего в 5 раз: с 4 до 20. А перебор подряд вырос в те же 100 000 раз. Гипотеза подтвердилась.
5. Заключение
В ходе работы я:
разобрала два способа угадывать число — перебор подряд и деление пополам;
поняла, почему деление пополам отбрасывает половину вариантов за один вопрос, и что число вопросов — это log₂N;
сделала программу-эмулятор и провела эксперимент на диапазонах от 10 до миллиона;
сравнила результаты опыта с расчётом.
Гипотеза подтвердилась. Деление пополам действительно угадывает число очень быстро: для миллиона чисел хватает не больше 20 вопросов, тогда как перебор подряд требует в среднем около полумиллиона. Опыт и расчёт дали одинаковый ответ.
Эта работа научила меня важному: иногда правильный способ действовать во много раз быстрее привычного. Деление пополам используют и в жизни — так ищут слово в словаре, так компьютеры находят нужное среди миллионов записей.
Что можно изучить дальше: как компьютер хранит числа в двоичном виде; где ещё применяется поиск делением пополам; можно ли угадывать ещё быстрее, если задавать сразу несколько вопросов.
Список использованных источников
Деление пополам (двоичный поиск) — материалы для школьников, Википедия. URL: https://ru.wikipedia.org/wiki/Двоичный_поиск
Логарифм — статья для школьников, Википедия. URL: https://ru.wikipedia.org/wiki/Логарифм
Двоичная система счисления — статья, Википедия. URL: https://ru.wikipedia.org/wiki/Двоичная_система_счисления
Образовательный портал «Фоксфорд.Учебник» — материалы по степеням и логарифмам. URL: https://foxford.ru/wiki/matematika
Занимательная математика: игры и фокусы с числами — детские научно-популярные издания.
