Все знают, что подбор — это решение так себе. Чаще всего его даже не засчитывают за решение. И правильно делают. Куда лучше другой похожий метод — перебор. В чём же отличие? Если подбор — это попытка ткнуть пальцем в небо и угадать число, которое удовлетворяет условию, то перебор — это осмысленное последовательное рассмотрение всех возможных значений. Здесь очень важно слово «всех». Исчерпывающее решение большинства задач заключается в том, чтобы найти все решения и показать, что других решений нет. Подбор нам этого не обещает, перебор — гарантирует.
Пример 1. Вы имеете 3 конверта, один нужно немедленно съесть. В каждом конверте содержится листок с двумя утверждениями. В одном конверте оба утверждения истинны, в другом оба ложны, а в третьем одно ложно и одно истинно. Вот эти утверждения:
Конверт 1:
1. Этот конверт есть не надо
2. Обязательно нужно съесть второй конверт
Конверт 2:
1. Не нужно есть первый конверт
2. Ешьте третий конверт
Конверт 3.
1. Не стоит есть этот конверт
2. Смело съедайте первый конверт
Так какой конверт нужно съесть?
Здесь всего три варианта. Съесть надо либо первый конверт, либо второй, либо третий. Допустим, что есть надо первый. Тогда утверждения будут: ЛЛ, ЛЛ, ПП (Л – ложь, П – правда). Не подходит. Допустим, съесть надо второй конверт. Тогда получается: ПП, ПЛ, ПЛ. Не походит. Допустим, съесть надо третий конверт. Тогда получается: ПЛ, ПП, ЛЛ. Подходит. Мы перебрали все случаи и нашли единственный, который удовлетворяет условию.
Здесь стоит отметить, что удалось удачно выбрать объект перебора. Решение сильно усложнилось бы, если бы мы, например, пытались перебирать и искать противоречия в всех комбинациях лжи и правды на каждом из конвертов: ЛЛ ПП ПЛ, ЛЛ ПП ЛП, ПП ЛЛ ПЛ, ПП ЛЛ ЛП, и т.д. (12 вариантов).
Пример 2. В корзине меньше 100 яблок. Известно, что их можно разделить поровну между 2, 3, 5 и 6 детьми, но нельзя разделить между 4 детьми. Сколько яблок в корзине?
Перебирать 100 вариантов (от 0 до 99) достаточно утомительно, поэтому процесс стоит немного оптимизировать. Если число яблок делится на 5, то оно оканчивается на 5 или на 0 (уже 20 вариантов). Если оно делится на 2, то 5 не подходит, и последняя цифра может быть только 0. Число вариантов уменьшилось до десяти: 0, 10, 20, 30, 40, 50, 60, 70, 80, 90. Учитывая, что число должно делиться на 3, оставляем числа: 0, 30, 60, 90. Из них не делятся на 4 только 30 и 90. Итог: в корзине 30 или 90 яблок.
Этот пример прекрасен не только тем, что мы удачно оптимизировали перебор, но тем, что в нём два ответа. Решая подбором или чуть более осмысленно, человек скорей всего найдёт только одно решение.
Какие выводы?
1. Подбор — это плохо. Перебор — это хорошо. Перебор гарантирует нахождение всех возможных решений.
2. Надо думать, что именно в задаче удобней всего перебирать.
3. По возможности перебор надо упрощать и оптимизировать.
Вступайте в группу ВКонтакте: http://vk.com/matolimp
Добавляйтесь в друзья или подписывайтесь в Facebook: https://www.facebook.com/matolimp
Приходите на занятия!