Что такое инвариант: определение термина
Его часто изучают преобразования: перенос, поворот, отражение, масштабирование, а также разные операции и шаги алгоритма. Инвариантом называют то, что при таких действиях сохраняется. Например, при переносе и повороте фигуры ее форма не меняется, а расстояния между точками остаются прежними, значит расстояние может быть инвариантом для таких преобразований.
В задачах на процессы инвариант — это то, что сохраняется после каждого шага. Именно поэтому инварианты полезны: если вы нашли, что какая-то величина всегда остается постоянной, вы можете делать выводы о результате, не перебирая все варианты.
Как использовать инвариант при решении задач
Сначала нужно понять, какие действия разрешены в задаче и что именно меняется. Затем попробуйте найти то, что сохраняется: сумму, разность, четность, остаток при делении, количество объектов определенного типа, площадь, расстояние или другой показатель. После этого проверяйте: действительно ли выбранная величина не меняется после каждого допустимого шага.
Если инвариант найден, он помогает доказать невозможность какого-то результата или, наоборот, показать, что результат обязателен. Например, если в задаче каждый шаг сохраняет четность суммы, то из четного состояния нельзя получить нечетное.
