§ 4-5. Поиск решения, удовлетворяющего заданным ограничениям

Определения и обозначения

Ограничение — условие, которому должны удовлетворять искомые значения или объект. Например, для числа это может быть требование быть больше 10 или делиться на 3. Ограничения помогают понять, какие варианты подходят, а какие сразу можно исключить.

Кандидат на решение — возможный вариант, который проверяют на соответствие ограничениям. Если ищем число от 1 до 20, каждое число из этого диапазона можно считать кандидатом. Этот термин нужен, чтобы отличать ещё не проверенный вариант от уже найденного ответа.

Допустимое решение — кандидат, удовлетворяющий всем заданным ограничениям. Если условие требует, чтобы число было больше 10 и делилось на 3, недостаточно выполнить только одно требование. Понятие помогает точно определить, какие варианты можно записать в ответ.

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

Как это устроено

Поиск начинают с точного определения того, что требуется найти, и перечня всех условий задачи. Иначе можно выбрать не тот объект или забыть проверить важное требование. Например, если ищут числа, нужно понять, требуется одно число или все подходящие числа, целое оно или может быть дробным. Записанные заранее условия служат планом проверки каждого кандидата.

Ограничения сужают множество возможных вариантов, потому что отсекают тех кандидатов, которые не соответствуют условию. Чем точнее сформулированы ограничения, тем легче заметить неподходящий вариант и не тратить на него дальнейшие проверки. Если требуется число больше 10, числа от 1 до 10 можно исключить ещё до проверки делимости. При этом кандидат должен пройти проверку по всем условиям, а не только по самому заметному.

Область поиска — множество значений или объектов, среди которых рассматривают кандидатов. Её важно определить, потому что без границ перебор может оказаться бесконечным или неполным: непонятно, когда остановиться и что именно проверить. В задаче «найти целое число от 1 до 20» область задана явно, а значит, можно составить полный список кандидатов. Если границы не даны, их нужно определить из текста задачи или уточнить, какие значения допустимы.

Перебор организуют в понятном порядке: например, проверяют числа от меньшего к большему или рассматривают пары сначала по первому, затем по второму значению. Такой порядок облегчает контроль и помогает не перескочить через вариант. При переборе пар следует определить, считаются ли пары (2, 5) и (5, 2) разными: это зависит от условия. Полный перебор означает, что проверен каждый кандидат из заданной области.

Ограничения удобно записывать как логические условия — высказывания, для которых можно определить, истинны они или ложны. Например, для числа x можно записать: x > 10 и x делится на 3. Союз «и» означает, что должны выполняться оба условия одновременно; если хотя бы одно ложно, кандидат не подходит. Для сложной задачи проверяйте каждое условие отдельно, а затем принимайте решение о кандидате в целом.

Этапы поиска решения с ограничениями

Пользуйся таблицей как планом: переходи к следующему этапу, когда выполнил предыдущий. Если на проверке кандидат не проходит хотя бы одно ограничение, исключи его; если проходит все — запиши как допустимое решение. В конце сверь ответ с вопросом задачи и проверь, что перебор завершён.

Разбор задач

Задача 1. Найти целое число от 1 до 20, которое делится на 3 и больше 10. Здесь область поиска конечная: целые числа от 1 до 20. Оба ограничения должны выполняться одновременно, поэтому одного только деления на 3 недостаточно.

1. Перебираем числа от 1 до 20 и сначала отбрасываем те, которые не больше 10.
2. Среди оставшихся чисел проверяем делимость на 3: подходят 12, 15 и 18.
3. Проверяем эти числа по исходным условиям: каждое больше 10 и делится на 3.

Ответ: 12, 15, 18. Перебор завершён, потому что проверена вся область, а не только первые подходящие значения.

Задача 2. Подобрать двузначные числа, сумма цифр которых равна 9, а число делится на 4. Чтобы не проверять все числа от 10 до 99 одинаковым способом, сначала используем ограничение на сумму цифр. Затем проверим делимость оставшихся вариантов на 4.

1. Обозначим цифру десятков через a, а цифру единиц через b. Условие суммы записывается как a + b = 9; при этом a — от 1 до 9, b — от 0 до 9.
2. Составляем пары цифр с суммой 9: 1 и 8, 2 и 7, 3 и 6, 4 и 5, 5 и 4, 6 и 3, 7 и 2, 8 и 1, 9 и 0. Получаются числа 18, 27, 36, 45, 54, 63, 72, 81, 90.
3. Проверяем каждое полученное число на делимость на 4. Делятся 36 и 72; у остальных при делении на 4 остаётся остаток.
4. Проверяем ответы по двум условиям: у 36 и 72 сумма цифр равна 9, и оба числа делятся на 4.

Ответ: 36 и 72. Сначала мы сократили область перебора условием о цифрах, а затем проверили оставшиеся кандидаты по второму ограничению.

Задача 3. Найти все пары натуральных чисел от 1 до 10, сумма которых не превышает 12, а произведение равно 20. Перебираем упорядоченные пары: здесь порядок имеет значение, поэтому (2, 10) и (10, 2) — разные пары. Оба ограничения проверяем для каждой пары одновременно.

1. Для произведения 20 рассматриваем делители, которые могут быть числами пары: 1 и 20, 2 и 10, 4 и 5. Число 20 не входит в диапазон от 1 до 10, поэтому пару 1 и 20 исключаем.
2. Проверяем остальные пары по сумме: 2 + 10 = 12, а 4 + 5 = 9. Обе суммы не превышают 12.
3. Так как порядок учитывается, записываем также обратные пары: (10, 2) и (5, 4). Для них произведение и сумма остаются такими же.
4. Проверяем, что в каждой паре оба числа натуральные, не больше 10, сумма не превышает 12, а произведение равно 20.

Ответ: (2, 10), (10, 2), (4, 5), (5, 4). Если в конкретной задаче пары считаются неупорядоченными, обратные варианты не записывают отдельно.

Типичные ошибки

Проверяют только одно из условий и принимают вариант, который подходит лишь частично. Так происходит, когда ограничения рассматривают отдельно и забывают соединить их логическим «и». Проверь себя: для каждого ответа поставь отметку напротив каждого условия; если хотя бы одной отметки нет, кандидат недопустим.

Начинают перебор, не задав границы области поиска. Тогда легко пропустить варианты или перебирать их без конца, потому что непонятно, где остановиться. Перед поиском запиши, какие именно значения входят в область и каков её крайний элемент; если границ в условии нет, выясни их из требований задачи.

Считают первый подходящий вариант единственным решением. Первый найденный кандидат действительно может подойти, но за ним могут быть другие допустимые варианты. Если задача просит найти все решения, продолжай перебор до конца области и только после этого подводи итог.

Не проверяют найденный ответ по исходному условию. Ошибка в вычислении или переборе может остаться незамеченной, даже если решение казалось правильным. Подставь каждый ответ обратно в условия и проверь все требования; дополнительно убедись, что не пропущены кандидаты, которые стояли между найденными.

Связь с другими темами

Для поиска решений нужно уметь задавать диапазон значений и перебирать элементы конечного множества. Эти навыки позволяют установить границы проверки и организовать её по порядку. Тема также опирается на логические операции и проверку истинности условий: кандидат подходит, только если все ограничения выполнены. В программировании такой поиск превращается в алгоритм перебора, который проверяет варианты и сохраняет допустимые. Поэтому метод используют при составлении программ и решении задач на программирование.

Что запомнить

• Сначала точно сформулируй, что требуется найти.
• Задай область поиска и перечисли все ограничения.
• Кандидат становится решением, только если выполняет все условия.
• При поиске всех решений проверь каждого кандидата.
• Перебор должен быть организован так, чтобы не пропустить варианты.
• После поиска проверь результат по исходному условию.