|
== Упражнения ==
'''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>.
== Поиск подходящего элемента в массиве ==
|
