Метод дихотомии: различия между версиями
Содержимое удалено Содержимое добавлено
Gribozavr (обсуждение | вклад) rvv |
|||
Строка 6:
== Биты и количество информации ==
Отвлечёмся и вспомним более простую задачу. Вы, конечно, помните, что такое ''один бит информации''? Бит — это количество информации, уменьшающее степень неопределённости в два раза.
Классический пример — представим себе, что Вася не готовился к контрольной работе по математике, и может получить любую из оценок от двойки до пятерки. И вот, запыхавшийся Вася на пороге, и на вопрос «Как контрольная?» следует ответ: «Четыре!» Сколько бит информации сообщил вам Вася?
Для того, чтобы ответить на этот вопрос, разобьём наш вопрос «Как контрольная?» на этапы, причём таким образом, чтобы на каждом этапе неопределённость уменьшалась ровно в два раза. С точки зрения нормального человека это довольно необычный способ узнать ответ на вопрос. Но, тем не менее, приступим.
Первым этапом может быть, например, вопрос: «Оценка выше тройки?» Всего различных оценок четыре, этот вопрос разделяет их на две группы — «больше трёх» и «меньше либо равно трём». Очень важно, что эти группы одинаковы по количеству элементов — в каждой ровно по две возможных оценки. В первой группе находятся «отлично» и «хорошо», во второй — «удовлетворительно» и «плохо». Теперь нам предстоит определить одну оставшуюся оценку из двух, то есть уменьшить неопределённость ещё в два раза и получить ещё один бит информации. Отсюда следует, что искомое число бит в ответе Васи «Четвёрка!» равно двум — первый бит из четырёх возможных вариантов выбирает два, второй — выбирает из двух один.
Необходимо отметить, что разбиение потенциальных оценок на «группы» — исключительно дело вкуса, нужно лишь чтобы эти группы состояли из одинакового числа элементов. Вопрос первого этапа мог бы звучать, например, так: «Твоя оценка — двойка или пятерка?»
== Пополам не делится ==
Строка 28 ⟶ 38 :
== Упражнения ==
'''1'''
Сколько потребуется вопросов для того, чтобы отгадать:
* Число от одного до ста?
* В чью пользу и с каким счётом окончился матч в шахматы, который вёлся до трех побед и завершился победой одной из сторон?
* Определённую перестановку из четырёх различных элементов, например, порядок [карандаш, фломастер, ластик, калькулятор] из всех возможных способов выкладывания этих четырёх предметов в ряд.
* Какие вопросы следует задавать в предыдущем задании? Пусть для простоты элементы (предметы) называются <math>A</math>, <math>B</math>, <math>C</math> и <math>D</math>.
'''2'''
Петя… нет, пусть будет, скажем, Андрей. Андрей предложил другой способ задавать вопросы. Первый вопрос: «Является ли твое число ''чётным''?» Второй вопрос (если он нужен): «Является ли частное от деления твоего числа на два чётным?» В третьем вопросе изучается чётность частного от деления числа на четыре, в четвертом — на восемь, и вообще, в <math>n</math>-м вопросе изучается чётность частного от деления задуманного числа на <math>2^{n - 1}</math> (не забывайте, что <math>2^0 = 1</math>). Допустим, на пять вопросов Андрей получил ответы «Да, да, нет, да, нет» именно в таком порядке, и положим, что задуманное число лежит в диапазоне от <math>1</math> до <math>32</math>. Какое число было задумано? Придумайте общий способ называть задуманное число по набору ответов «Да»/«Нет» при условии задавания вопросов по данному принципу.
'''3'''
Докажите, что «варьирование» числа вопросов, которое мы наблюдали в примере с «не всегда обязательным» четвёртым вопросом, возможно тогда и только тогда, когда число возможных вариантов не является степенью двойки<ref>Подсказка: докажите вначале, что тот факт, что число возможных вариантов не является степенью двойки, является необходимым и достаточным условием появления на некотором шаге нечётного числа элементов, из которых нужно выбирать.</ref>.
== Поиск подходящего элемента в массиве ==
| |||