Статьиcегодня статей - 280

© Волков Игорь, Лапо Анжелика, 2002

Отличие нестандартной задачи по информатике от стандартной состоит, преимущественно, в том, что для нее не существует общих подходов к решению. Успех или неуспех решения задачи часто объясняется слепой интуиции и удачей. Поэтому желательно систематизировать поиск решения, выделить какие-то полезные методики и следовать им. Давайте рассмотрим один из полезных подходов при поиске решения, который условно назовем "сделай хоть что-нибудь".

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

Определим сначала, что надо найти в этой задаче — координату некой точки z на прямой. Из условия задачи не ясно, где она должна находиться, поэтому для начала зададим какой-нибудь набор из нескольких точек на прямой и попытаемся выбрать координату z произвольным образом (рис. 1).

Из рисунка не очевидно, хорошо мы эту точку задали или нет. Поэтому попытаемся поставить точку z настолько плохо, чтобы она, без сомнения, не являлась решением задачи (рис. 2).

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

Пусть координаты точек x 1, ..., x n не убывают (если это не так, то просто их предварительно отсортируем). Если n четное, n=2k, то точка z может быть любой из точек отрезка [x k, x k+1 ], если же n=2k+1, то точка z=x k+1 .

Итак, пройдемся еще раз по решению задачи. Для начала мы положили искомое значение равным какой-то, достаточно произвольной, величине. Получили, что она не является решением задачи, и определили для себя, почему это не искомое решение. Это дало нам возможность определить, чем отличается "хорошее", правильное решение от неправильного, и способ преобразования "плохого" решения в "хорошее". Основная идея — мы положили неизвестную искомую величину равной какому-то значению и проанализировали, почему полученный результат нас не устраивает и как его изменить.

Покажем, как можно воспользоваться этим подходом при решении других задач.

Искомая величина — количество страниц V в самом толстом томе. Положим это количество страниц равным какой-то величине L. Попытаемся распределить главы по томам так, чтобы объем каждого тома не превосходил L. Будем заносить в очередной том главы до тех пор, пока добавление следующей главы не приводит к превышению L. После этого перейдем к формированию следующего тома. После того, как все главы будут распределены по томам, мы можем проанализировать то, что у нас получилось.

Если нам удалось распределить все главы по K или менее томам, то L — это оценка для V сверху.
Если же мы сформировали последний том, и после этого осталась еще хотя бы одна глава, то c максимальным объемом тома не более L страниц главы рас-пределить нельзя. В этом случае L — это оценка для V снизу.

Таким образом, мы можем получить для искомого количества страниц оценки сверху и снизу, а далее действовать методом половинного деления (или, по другому, дихотомии) — мы взяли решение "в вилку", а теперь будем анализиро-вать середину возможного промежутка значений L: если середина дает большее количество томов, чем надо, то она становится новым нижним концом промежутка, иначе — верхним. И в этом случае мы нашли подход к решению задачи, каким-то образом полагая значение искомой величины. Анализ получившегося количества томов показывает, что нужно делать со значением L: уменьшать или увеличивать.

И еще несколько задач, решаемых аналогичным способом

Неизвестен радиус окружности R. Положим его равным некоторой величине L. Начнем вписывать ломаную с длинами последовательных сторон 1, 2, ..., N в получившуюся окружность. Если ломаная не замкнулась, то значение L чересчур велико, и его надо уменьшить. Если же ломаная пошла "внахлест", то L мало, и его надо увеличить. Методом дихотомии найдем неизвестную величину R.

Мы знаем массу m 1. Если бы мы знали массу m 2, то могли бы вычислить m 3, ..., m N . Следовательно, m N зависит от m 2. Как и раньше, возьмем несколько различных значений m 2 и проанализируем получившиеся значения m N. Оказывается, что в зависимости от параметров m 1, N, и d возможны два варианта:

 1) или большему значению m 2 соответствует большее значение m N.
  2) или меньшему значению m 2 соответствует большее значение m N.

Определяем, какой у нас случай. Затем значение m 2 находим методом половинного деления.

Надо определить, будет ли вращаться система шестерен. Так возьмем и повернем шестерню 1 и посмотрим, что будет с остальными шестернями. Будем обозначать вращение по часовой стрелке нулем, против — единицей. Сначала припишем шестерне с номером 1 число нуль. На следующем шаге всем шестерням, сцепленным с первой, будут приписаны числа 1 (они будут вращаться в противоположную шестерне 1 стoрону). Далее всем шестерням, находящимся в зацеплении с занумерованными на предыдущем шаге, припишем значения 0 и и.т.д. Процесс будем повторять до тех пор, пока

• либо на очередном шаге ни одной шестерне не будет приписано новое значение (и тогда шестерню с номером 1 удастся повернуть),
• либо на каком-то шаге пометка шестерни изменяется с 1 на 0 или с 0 на 1 (и тогда система в движение не придет — шестерня "заклинила" всю систему).

В задаче не известен начальный порядок карточек в стопке, который дает искомый расклад. Давайте начнем с какой-нибудь простой начальной комбинации. Пусть карточки в колоде лежат в порядке возрастания их номеров, от 1 до n. Возьмем и выложим карточки на стол. Полученный порядок карточек, естественно, не совпадает с искомым, в котором карточки должны лежать от 1 до n. Однако карточка с номером 1 лежит на своем месте, это значит, что она в колоде должна быть первой. Карточка с номером 2, вообще говоря, не лежит второй. Пусть на втором месте лежит карточка с номером k. Значит, в исходной стопке вместо карточки с номером k мы должны положить карточку с номером 2. Рассуждая аналогично, разложим все остальные карточки.

* * *

Данный метод, понятно, не является универсальным. Цель его — показать, как можно сделать первый шаг к решению задачи исходя из ее постановки.

Все приведенные выше задачи предлагались на олимпиадах по информатике.