51

Как быстро найти загаданное число

Я загадал случайное число от 1 до 10. Как быстро вы сможете отгадать его? Кому-то повезёт с первой попытки. Кто угодно уж точно отгадает с десятой. В среднем у людей будет получаться за 5 попыток. А как можно точно сделать это быстрее всего? Чтобы это было проще, после неправильного ответа я буду говорить вам, большее или меньшее число я загадал

Как быстро найти загаданное число Научпоп, Математика, Программирование, Алгоритм, Шахматы, Логарифм, График, Человек наук, Длиннопост

Правильный ответ — за 4 попытки. Не очень впечатляет: лишь на 1 меньше 50%. Но что если я скажу вам, что я отгадаю 1 число из 100 всего за 7 попыток? И одно из тысячи всего за 10

Знание о том, больше или меньше загаданное число нашей попытки очень сильно облегчает задачу. Например, мы можем предположить число 9. Вероятность попасть в любое число одинакова, поэтому девятка ничем не хуже других. Если она и была ответом, мы победили, а если нет, услышав «меньше» мы будем знать, что и 10 не является загаданным числом! Так можно пройти в 2 раза меньше чисел и мы уже улучшим средний результат

Но есть ещё более эффективный способ. Мы можем взять число из середины последовательности. Если не угадаем, у нас тогда останется ещё половина вариантов, это верно. Но мы избавимся и от целой другой половины! В случае 10 это не так важно, но если нам загадали число от 1 до 100, мы даже неправильным предположением убираем 50 вариантов!

С оставшейся половиной можно проделать то же самое. Давайте посмотрим, как это работает на примере. В начале я загадал число 8. Оно отгадывается всего за 2 шага — это неинтересно. Давайте разберём на примере от 1 до 100. На этот раз я сразу скажу ответ, чтобы вы следили за его поиском: это число 43

–Это число 50?
–Меньше
–Это число 25?
–Больше
–Это число 37?
–Больше
–Это число 43?
–Верно!

Мы управились всего за 4 шага! При случайном угадывании нам потребовалось бы 50. Попробуйте сами так «отгадать» любое число из 1000 — вам скорее всего понадобится даже меньше 10 шагов

4, 7, 10 — почему именно эти числа? Вы могли бы подумать, что я просто прибавляю 3, но это неверно: 1 из 10000 точно отгадывается уже за 14 шагов

В нашем алгоритме мы каждый раз делим оставшийся интервал на 2. Давайте попробуем решить обратную задачу: через сколько умножений на 2 мы достигнем определённой длины? 2*2*2 = 8 — это всё ещё не равно 10. Но умножив 2 на себя 4 раза — другими словами, возведя 2 в 4 степень, мы получим 16, что явно больше 10. Значит, можно гарантированно угадать число за 4 шага! Математическая операция, которая позволит это посчитать — обратная к возведению в степень: логарифм по основанию 2. Его функция возрастает очень медленно:

Как быстро найти загаданное число Научпоп, Математика, Программирование, Алгоритм, Шахматы, Логарифм, График, Человек наук, Длиннопост

Степень двойки растёт очень быстро. С этим связаны известные факты: например, почти невозможно сложить лист бумаги пополам больше 7 раз, что неудивительно — в нём будет уже 128 слоёв! Рвать листы бумаги пополам также с определённого момента становится очень сложно

Как быстро найти загаданное число Научпоп, Математика, Программирование, Алгоритм, Шахматы, Логарифм, График, Человек наук, Длиннопост

По легенде древнеиндийский математик создал шахматы и показал их правителю страны. Тому игра настолько понравилась, что он позволил изобретателю самому выбрать себе награду. Математик попросил одно зёрнышко пшеницы за первую клетку, 2 за вторую и так далее до конца доски. Правитель обиделся, что мудрец просит так мало, но повелел выплатить награду. Однако, оказалось, что сделать это невозможно. Количество зерна превышает урожай пшеницы за всю историю человечества, а его масса бы равнялась 1200 миллиардов тонн

Как быстро найти загаданное число Научпоп, Математика, Программирование, Алгоритм, Шахматы, Логарифм, График, Человек наук, Длиннопост

Если пронумеровать каждый атом на нашей планете и попросить найти один определённый, это можно сделать всего лишь за 167 раз! У числа атомов на нашей планете, к слову, 50 нулей

Такой алгоритм поиска широко используется в программировании — там, где количество шагов и время критически важно. Его также можно несколько улучшить. Наша последовательность расположена по возрастанию и в центре находится число 5 (если округлять середину вниз). Но если число загадывает человек, он с большей вероятностью загадает 7. Если расположить его в середине, часто мы будем попадать с первого раза! Также удобно расположив другие числа, можно ещё больше улучшить алгоритм

Как быстро найти загаданное число Научпоп, Математика, Программирование, Алгоритм, Шахматы, Логарифм, График, Человек наук, Длиннопост

Если интересны посты про образование и науку, заглядывайте ко мне в группу ВК и телеграм-канал

Лига образования

1.9K постов16.5K подписчиков

Добавить пост

Правила сообщества

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


ДЛЯ АВТОРОВ:


Приветствуются:

-уважение к читателю и открытость

-желание учиться

Не рекомендуются:

-публикация недостоверной информации


ДЛЯ ЧИТАТЕЛЕЙ:


Приветствуются:

-конструктивные дискуссии на тему постов

Не рекомендуются:

-личные оскорбления и провокации

-неподкрепленные фактами утверждения


В этом сообществе мы все союзники - мы все хотим учиться! :)

Подробнее
Лучшие посты за сегодня
8124

Один

5662

Занятой

5289

Ох уж эти встречи выпускников

Ох уж эти встречи выпускников Понты, Владивосток, Встреча выпускников, Барахолка, Farpost
4612

Правильно что не дали права?

4321

Аферы в Г**ноМобиль

Аферы в Г**ноМобиль Москва, Такси, Длиннопост, Ситимобил, Негатив
Аферы в Г**ноМобиль Москва, Такси, Длиннопост, Ситимобил, Негатив
Аферы в Г**ноМобиль Москва, Такси, Длиннопост, Ситимобил, Негатив
Аферы в Г**ноМобиль Москва, Такси, Длиннопост, Ситимобил, Негатив
Аферы в Г**ноМобиль Москва, Такси, Длиннопост, Ситимобил, Негатив
Аферы в Г**ноМобиль Москва, Такси, Длиннопост, Ситимобил, Негатив
Аферы в Г**ноМобиль Москва, Такси, Длиннопост, Ситимобил, Негатив
Аферы в Г**ноМобиль Москва, Такси, Длиннопост, Ситимобил, Негатив
Показать полностью 8
4240

Нужно быстрее

3845

В ответ на пост

3617

Беляш дело говорит

Беляш дело говорит Twitter, Скриншот, Мужчины
3345

Ответ на пост «Ютуб, иди на х*й! Со своей рекламой где орут, плачут, ноют и лезут с прочим скамом! Вонючие мошенники!» 

Ответ на пост «Ютуб, иди на х*й! Со своей рекламой где орут, плачут, ноют и лезут с прочим скамом! Вонючие мошенники!» YouTube, Блокировка Рекламы, Windows, Android, Youtube Vanced, Повтор, Adblock, Adguard, Ответ на пост, Длиннопост
Ответ на пост «Ютуб, иди на х*й! Со своей рекламой где орут, плачут, ноют и лезут с прочим скамом! Вонючие мошенники!» YouTube, Блокировка Рекламы, Windows, Android, Youtube Vanced, Повтор, Adblock, Adguard, Ответ на пост, Длиннопост
Ответ на пост «Ютуб, иди на х*й! Со своей рекламой где орут, плачут, ноют и лезут с прочим скамом! Вонючие мошенники!» YouTube, Блокировка Рекламы, Windows, Android, Youtube Vanced, Повтор, Adblock, Adguard, Ответ на пост, Длиннопост
Ответ на пост «Ютуб, иди на х*й! Со своей рекламой где орут, плачут, ноют и лезут с прочим скамом! Вонючие мошенники!» YouTube, Блокировка Рекламы, Windows, Android, Youtube Vanced, Повтор, Adblock, Adguard, Ответ на пост, Длиннопост
Ответ на пост «Ютуб, иди на х*й! Со своей рекламой где орут, плачут, ноют и лезут с прочим скамом! Вонючие мошенники!» YouTube, Блокировка Рекламы, Windows, Android, Youtube Vanced, Повтор, Adblock, Adguard, Ответ на пост, Длиннопост
Ответ на пост «Ютуб, иди на х*й! Со своей рекламой где орут, плачут, ноют и лезут с прочим скамом! Вонючие мошенники!» YouTube, Блокировка Рекламы, Windows, Android, Youtube Vanced, Повтор, Adblock, Adguard, Ответ на пост, Длиннопост
Ответ на пост «Ютуб, иди на х*й! Со своей рекламой где орут, плачут, ноют и лезут с прочим скамом! Вонючие мошенники!» YouTube, Блокировка Рекламы, Windows, Android, Youtube Vanced, Повтор, Adblock, Adguard, Ответ на пост, Длиннопост
Ответ на пост «Ютуб, иди на х*й! Со своей рекламой где орут, плачут, ноют и лезут с прочим скамом! Вонючие мошенники!» YouTube, Блокировка Рекламы, Windows, Android, Youtube Vanced, Повтор, Adblock, Adguard, Ответ на пост, Длиннопост
Ответ на пост «Ютуб, иди на х*й! Со своей рекламой где орут, плачут, ноют и лезут с прочим скамом! Вонючие мошенники!» YouTube, Блокировка Рекламы, Windows, Android, Youtube Vanced, Повтор, Adblock, Adguard, Ответ на пост, Длиннопост
Ответ на пост «Ютуб, иди на х*й! Со своей рекламой где орут, плачут, ноют и лезут с прочим скамом! Вонючие мошенники!» YouTube, Блокировка Рекламы, Windows, Android, Youtube Vanced, Повтор, Adblock, Adguard, Ответ на пост, Длиннопост
Ответ на пост «Ютуб, иди на х*й! Со своей рекламой где орут, плачут, ноют и лезут с прочим скамом! Вонючие мошенники!» YouTube, Блокировка Рекламы, Windows, Android, Youtube Vanced, Повтор, Adblock, Adguard, Ответ на пост, Длиннопост
Ответ на пост «Ютуб, иди на х*й! Со своей рекламой где орут, плачут, ноют и лезут с прочим скамом! Вонючие мошенники!» YouTube, Блокировка Рекламы, Windows, Android, Youtube Vanced, Повтор, Adblock, Adguard, Ответ на пост, Длиннопост
Показать полностью 11
3221

Колесо Сансары

Колесо Сансары
3195

По-моему лучшее объяснение массовой вакцинации

По-моему лучшее объяснение массовой вакцинации Коронавирус, Вакцинация, Комментарии, Комментарии на Пикабу, Скриншот
3074

Тайна яжматерей раскрыта!

3052

Один из раздеов FAQ у организаторов горнолыжного тура

Один из раздеов FAQ у организаторов горнолыжного тура Тур, Горнолыжный курорт, Мат, Вакцинация, QR-код, Коронавирус
Показать полностью 1
2987

Ответ на пост «Интриган» 

2984

Ответ на пост «Сила Пикабу, помоги, очень нужна работа» 

Ответ на пост «Сила Пикабу, помоги, очень нужна работа» Поиск работы, Сила Пикабу, IT, Сисадмин, Информационная безопасность, Работа, Вакансии, Без рейтинга, Ответ на пост, Длиннопост
Ответ на пост «Сила Пикабу, помоги, очень нужна работа» Поиск работы, Сила Пикабу, IT, Сисадмин, Информационная безопасность, Работа, Вакансии, Без рейтинга, Ответ на пост, Длиннопост
Ответ на пост «Сила Пикабу, помоги, очень нужна работа» Поиск работы, Сила Пикабу, IT, Сисадмин, Информационная безопасность, Работа, Вакансии, Без рейтинга, Ответ на пост, Длиннопост
Ответ на пост «Сила Пикабу, помоги, очень нужна работа» Поиск работы, Сила Пикабу, IT, Сисадмин, Информационная безопасность, Работа, Вакансии, Без рейтинга, Ответ на пост, Длиннопост
Показать полностью 2
2734

Распечатанные голые женщины

2711

Переводчик

2688

Всё для пользы

Всё для пользы Увлажнитель воздуха, Осушитель воздуха, Польза, Девушки
2559

Кто же съел все пирожные?

2520

Маленькая победа Джонни

Маленькая победа Джонни Джонни Депп, Актеры и актрисы, Знаменитости, Фильмы, Показ, Великий, Картинка с текстом, Из сети, Фотография, Длиннопост
Маленькая победа Джонни Джонни Депп, Актеры и актрисы, Знаменитости, Фильмы, Показ, Великий, Картинка с текстом, Из сети, Фотография, Длиннопост
Показать полностью 2
Похожие посты закончились. Возможно, вас заинтересуют другие посты по тегам: