В. Дан словарь английских слов. Найдите все наборы анаграмм. Например, pots, stop и tops являются анаграммами по отношению друг к другу, так как каждое слово может быть образовано из другого перестановкой букв.
2.2. ВЕЗДЕСУЩИЙ ДВОИЧНЫЙ ПОИСК
Я задумываю целое число от 1 до 100, а вы его угадываете. 50? Слишком мало. 75? Слишком много. И так игра продолжается до тех пор, пока вы не угадаете мое число. Если мое число было задумано в диапазоне от 1 до N, тогда вы угадаете его 3alog„N попыток. Если N = 1000, будет сделано 10 попыток, а если N= 1 000 000, вам потребуется не более 20 попыток.
Этот пример иллюстрирует метод, который позволяет решить множество задач программирования, он называется двоичный поиск. В начальный момент мы знаем, что объект находится в заданной области, а операция выбора и проверки значения "сообщает" нам, где находится объект - в заданной позиции, ниже или выше ее. При двоичном поиске местоположение объекта обнаруживается с помошью повторяющегося выбора элемента из середины текущей области. Если выбранный элемент не тот, который мы ищем, делим текущую область пополам и продолжаем. Мы остановимся, если найдем то, что искали, или область станет пуста.
Наиболее простым примером применения двоичного поиска в программировании является поиск элемента в упорядоченном массиве. При поиске числа 50 алгоритм делает следующие попытки:
