Думайте сразу над общим случаем
Очень часто наблюдаю, как многие школьники, да и не только школьники, начиная решать какую-то задачу, начинают сначала думать с разные мелких частных случаев, которые на самом деле никак не помогают в общем решении.
Например, опять задача «Отрезок»: на клетчатой плоскости заданы две точки (x1, y1) и (x2, y2),
надо посчитать, сколько клеток пересекает отрезок, соединяющий эти две точки. Прочитав эту задачу, вы можете начать думать примерно так: ага, если отрезок горизонтален или вертикален (x1==x2 или y1==y2), то ответ понятен.
Или задача задача «Точки и отрезки»: на прямой задано N отрезков и M точек, требуется для
каждой точки посчитать, сколько отрезков ее накрывают. Тоже первая мысль, которая может у вас возникнуть: ну хорошо, давайте для начала
разберемся с точками, которые идут раньше всех отрезков. А именно, найдем минимальную из всех координат начал отрезков, пусть это координата X — тогда левее X отрезков нет. Тогда мы можем пройтись по всем точкам, и, если координата точки меньше чем X, то ответ для этой точки — ноль.
Или, например, задача поиска кратчайшего пути в графе: дан граф и две вершины, надо найти кратчайший путь между ними (вот она, например, на алгопроге). Вы тоже можете начать думать: вот если начальная и конечная вершины совпадают, то ответ 0. Дальше давайте проверим, а вдруг они соседние — тогда можно вывести 1…
Но на самом деле учет таких частных случаев ни на шаг вас не приблизит к правильному решению. У вас всегда может быть тест, в котором отрезок не горизонтален и не вертикален, и понятно, что именно такие тесты составляют наиболее общий случай. Аналогично, во второй задаче, даже если вы выкинете все точки, лежащие левее X, это не сделает ситуацию сильно проще; и в третьей задаче учет соседних вершин не сильно вам поможет.
Даже более того: ясно, что вам все равно придется придумывать какой-нибудь алгоритм для общего случая. И несложно в принципе понять, что скорее всего алгоритм для общего случая будет корректно обрабатывать и эти частные случаи. Точнее ладно, в первой задаче это еще не так очевидно, но во второй задаче совершенно понятно, что сложно написать алгоритм, который будет работать правильно всегда, кроме как для тех точек, которые лежат левее X, и то же самое в третьей.
Поэтому не надо тратить свое время и свои умственные усилия на то, чтобы решить задачу в таком частном случае. Думайте сразу над общим случаем.
Конечно, потом может оказаться, что общий алгоритм не работает в каких-то частных случаях. Во всех приведенных выше примерах правильно
написанное правильное решение учтет и эти особые случаи, но, конечно, бывает и так, что общий алгоритм в каком-то крайнем случае не
работает. Поэтому полезно запомнить такие частные случаи и, после того как вы придумали общий алгоритм, посмотреть, работает ли он
в этих случаях и, если нет, то уже думать дальше. Но даже тут «думать дальше» обозначает не просто написать if на этот частный случай,
а сначала подумать, может быть, можно просто чуть-чуть поправить общий алгоритм. (Но вообще это отдельная тема — как исправлять
программу, не работающую в каком-то частном случае.)
При этом надо отличать приведенные выше примеры, когда частный случай вам никак не помогал продвинуться в общем решении, от ситуаций, когда учет какого-то частного случая вам сильно упрощает оставшуюся задачу. Например, если вы смогли свести общий случай к более частному, то дальше, конечно, думайте над этим частным случаем. Или если вы понимаете, что в задаче действительно есть несколько существенно разных случаев, то можно подумать над каждым случаем по отдельности. Еще немного похожая ситуация — когда вы понимаете, что вам не надо рассматривать всё вообще множество возможных решений, а достаточно рассмотреть только решения определенного вида — конечно, это зачастую тоже имеет смысл.
Также бывают частные случаи, которые имеют в определенном смысле довольно общий вид. Грубо говоря, это такие частные случаи, которые могли бы быть полноправной задачей (в частности, как во многих олимпиадах сейчас принято выделять подзадачи). Например, это может быть задача с меньшими ограничениями (т.е. решаемая алгоритмом с худшей сложностью). Или, например, если в оригинальной задаче есть какие-то стоимости, то можно подумать над задачей «а что, если все стоимости одинаковы», если такая задача нетривиальна и имеет смысл. Вот такие «частные» случаи тоже может иметь смысл продумывать, т.к. они вам могут подсказать решение в общем случае.
И еще одно замечание на эту же тему. Если вы просто думаете над задачей и подумали о таких частных случаях, которые не упрощают общее
решение — это еще ладно. Но когда вы все-таки придумаете общее решение, то и пишите сразу общее решение, не надо в коде выделять какие-то частные случаи, если и общее решение для них работает. Т.е. когда вы будете писать решение той же задачи «Отрезок», не надо в коде
писать явный if x1==x2 or y1==y2, если ваше общее решение работает в таком случае. Добавляя такой if, вы не делаете программу более правильной, вы только ее усложняете и повышаете риск допустить ошибку. Более того, такой if еще плох тем, что может маскировать ошибку в основном алгоритме. Пусть, например, ваш основной алгоритм не работает в случае, если x2 делится на x1 (это плохой пример, т.к. в этой задаче очень сложно написать основной алгоритм так, чтобы он работал всегда, кроме такого частного случая, но для примера сойдет). Если вы не выделите случай x1==x2 or y1==y2 особо, то вы легко заметите эту ошибку, проверив тест с x1==x2. А вот если вы изначально написали явный if x1==x2 or y1==y2, то вы можете эту ошибку пропустить, т.к. на тесте с x1==x2 сработает ваш особый if и программа выведет правильный ответ, хотя основной алгоритм работает в этом случае неправильно; а других случаев, когда x2 делится на x1, вы не тестировали. В итоге в вашей программе осталась ошибка, но вы ее не заметили, т.к. в самом простом случае эта ошибка замаскирована вашим ifом.
Мой курс по алгоритмическому программированию (и подготовке к олимпиадам) для школьников, студентов и всех желающих — algoprog.ru