Code that belongs in a problem
If you want proof, Harry, that you belong in Gryffindor, I suggest you look more closely at this.
Harry Potter and the Chamber of Secrets, by J.K. Rowling
Часто, когда я вижу чье-то решение по какой-нибудь задаче, я сразу понимаю, что оно не может быть правильным. И не потому, что я сразу вижу в нем ошибку, или могу предъявить тест, на котором программа не работает — а потому, что я вижу в решении код, которого там точно не должно быть.
В каждой задаче есть код, который естественным образом должен быть в ней, и есть код (на самом деле бесконечно много вариантов кода), которого точно в правильном решении этой задачи быть не должно. И если я вижу код, которого там быть не должно, то совершенно понятно, что это решение не может быть правильным.
Например, задача «Отрезок»: на клетчатой плоскости заданы две точки (x1, y1) и (x2, y2),
надо посчитать, сколько клеток
пересекает отрезок, соединяющий эти две точки. В этой задаче на алгопроге указана тема — НОД, — и поэтому школьники,
начиная решать эту задачу, сразу начинают вычислять НОД каких-нибудь величин. Но, например, вычисление НОД(x1, y1)
— это очевидно неверное действие. Ни в каком правильном решении вам не может понадобиться НОД(x1, y1).
Поэтому, если я вижу в решении вычисление этого НОДа, я даже не буду искать контр-тест — сразу понятно, что решение неверно.
Более того, этому решению даже контр-тесты не особо помогут, его бессмысленно отлаживать на каких-то тестах
— в нем принципиальная ошибка сразу в начале решения.
С другой стороны, в этой задаче надо в первую очередь вычислить x1-x2 и y1-y2 (а еще лучше сразу взять по модулю),
т.к. ответ зависит только от этих величин. Вычисление этих разностей должно быть в любом правильном решении,
поэтому, если в решении этого нет, то тоже сразу понятно, что решение неправильное и смотреть его дальше не имеет смысла.
Или еще задача (простая): на шахматной доске даны две клетки, надо проверить, бьет ли вторую клетку слон, стоящий в первой клетке. Я видел в этой задаче решения, которые зачем-то считают остатки от деления на 2 каких-то чисел. Это явно неправильно, тут никакой периодичности с периодом 2 нет, и потому совершенно непонятно, зачем в этой задаче брать остаток от деления на 2. (Вот если бы стоял вопрос «может ли слон добраться с одной клетки до другой за несколько ходов», то да, остаток от деления на 2 был бы очень в тему — если кто и не знает, что слоны бывают белопольными и чернопольными, то достаточно нарисовать картинку на бумажке и вы сразу увидите, что доступные и недоступные клетки чередуются.)
Поэтому не удивляйтесь, когда вы меня просите найти ошибку в программе, а я вам вместо этого говорю, что у вас в коде какая-то очень странная конструкция, которой явно тут не должно быть. Это обозначает, что в вашей программе конкретную ошибку искать довольно бессмысленно, у вас, видимо, сам подход неправильный. В таком случае надо подумать, почему вы вобще решили, что этот код нужен, и понять, что тут явно надо что-то другое.
…В английском языке есть прекрасное выражение «belong in». Merriam-Webster дает ему следующее определение: «to be suitable, appropriate, or advantageous; to be in a proper situation». Я не знаю адекватного перевода этой фразы на русский, но примерный смысл — быть на своем месте. «A dictionary belongs in every home» (примеры из той же статьи) — это значит даже не то, что в каждом доме есть словарь, или что словарь обычно находится дома, а то, что словарю самое место в каждом доме. Или «a man of his ability belongs in teaching» — человек может и не быть учителем вообще, но тем не менее по его способностям он очень подходит для учительствования.
В цитате в эпиграфе к этому посту Дамблдор говорит вовсе не про то, что Гарри уже гриффиндорец, а про то, что Гарри в Гриффиндоре самое место, что Гарри — настоящий гриффиндорец, не по ошибке, а по глубоким причинам.
Так же и код. Есть код, который belong in решение задачи, а есть код, который does not belong in. И если вы пишете в задаче код, который не belong in, то неудивительно, что ваше решение не работает, и сколько if’ов не добавляйте, ваше решение не заработает.
Мой курс по алгоритмическому программированию (и подготовке к олимпиадам) для школьников, студентов и всех желающих — algoprog.ru