Читать «Вычислительное мышление: Метод решения сложных задач» онлайн - страница 14

Насколько это эффективно?

Задавать вопросы, которые оставляют половину возможных ответов, — лучше, чем называть конкретное имя, но насколько? Давайте предположим, что я изначально задумал кого-то одного из миллиона. Если после каждого вопроса отметать половину людей, сколько вопросов понадобится? После первого останется 500 000 человек, после второго — 250 000... После десяти вопросов от исходного миллиона останется примерно 1000 человек (рис. 1). Продолжаем... После следующего вопроса осталось 500, потом 250, 125... и на двадцатом вопросе остается один возможный человек. Если вам удастся каждый раз точно задавать вопрос, после которого останется половина ответов, то вы гарантированно выиграете. И всегда это будет 20 вопросов.

Все это, конечно, Мы пытались разработать алгоритм для игры «20 вопросов». Однако до конца решить задачу не удалось — было непонятно, как определить нужные вопросы. Это остается вашей задачей во время игры. Здесь используется еще один трюк вычислительного мышления — (разложение на части) Надо разделить проблему на части, чтобы сосредоточиться на каждой отдельно. Пока у нас получилось найти общую стратегию. Подобрать конкретные вопросы, которые оставят половину вариантов, — отдельная проблема.

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

полагается на — сокрытие деталей. Здесь мы абстрагируемся от конкретных вопросов и думаем только о том, какого типа вопросы надо задавать. Мы также использовали , когда размышляли, насколько эффективным был наш изначальный алгоритм. Чтобы выяснить, каким образом можно написать книгу, мы разложили одну задачу на две: выяснить, как передавать отдельные буквы, и провести всю необходимую работу с помощью полученного решения.

Новый алгоритм

Итак, если правильно задавать вопросы, то в худшем случае понадобится только 20 вопросов, чтобы угадать задуманного человека из миллиона возможных вариантов. Вспомним теперь, что хватит 13 вопросов (в худшем случае — 26), чтобы определить одну из 26 букв алфавита. «Да/нет» не отличается от «моргнуть / не моргать». А спрашивать «Это A? Это В?» — примерно то же самое, что спрашивать «Вы Микки-Маус?» или «Вы Нельсон Мандела?». Вы точно так же пытаетесь выяснить, о какой из многих вещей я думаю. Это опять-таки та же самая задача, что и предиктивная система набора текста в телефонных сообщениях!