Решение логических задач перебором
💻 Информатика · 6 класс
Что такое перебор вариантов
Перебор — это способ решения задачи, при котором проверяют по очереди все возможные варианты и оставляют тот, что подходит под условие. Перебор особенно удобен в логических задачах, где нужно расставить объекты по местам или определить, кто что выбрал. Если вариантов немного, перебор всегда приводит к верному ответу, потому что ни один случай не пропускается.
Когда применяют перебор
Перебор подходит не всегда, а только при определённых условиях.
- когда вариантов конечное и небольшое число;
- когда условие позволяет проверить каждый вариант;
- когда нет более короткого способа рассуждения.
Пример задачи
Аня, Боря и Вера заняли первое, второе и третье места. Известно: Аня не первая, Вера не третья. Кто какое место занял? Запишем все варианты расстановки в таблицу и вычеркнем те, что нарушают условие.
| Вариант | 1 место | 2 место | 3 место | Подходит? |
|---|---|---|---|---|
| 1 | Аня | Боря | Вера | нет |
| 2 | Аня | Вера | Боря | нет |
| 3 | Боря | Аня | Вера | нет |
| 4 | Боря | Вера | Аня | да |
| 5 | Вера | Аня | Боря | да |
| 6 | Вера | Боря | Аня | да |
Применяем условия по очереди. Сначала отбрасываем строки, где Аня на первом месте. Затем отбрасываем строки, где Вера на третьем месте.
Аня не первая → вычеркнуть варианты 1 и 2
Вера не третья → вычеркнуть варианты 3Если по задаче ответ должен быть единственным, добавляют ещё условия, пока не останется ровно одна строка. Так перебор постепенно сужает число возможных ответов.
Сколько бывает вариантов
Число всех расстановок быстро растёт. Для трёх человек по трём местам вариантов шесть, а для четырёх человек их уже двадцать четыре. Поэтому перебором удобно решать только небольшие задачи. Когда вариантов очень много, перебор становится слишком долгим, и ищут более короткие способы рассуждения.
- мало вариантов — перебор быстрый и надёжный;
- много вариантов — перебор отнимает слишком много времени;
- чем раньше отбросить лишнее, тем меньше строк придётся проверить.
Перебор и компьютер
Перебор удобен и для исполнителя-компьютера: ему можно поручить перебрать все варианты и оставить подходящие. Компьютер делает это очень быстро и не устаёт, поэтому он осилит даже такие наборы вариантов, которые человеку перебрать вручную было бы слишком долго. Но и для компьютера число вариантов не должно расти безгранично, иначе времени не хватит даже у быстрой машины.
Правило: при переборе важно не пропустить ни одного варианта. Поэтому их выписывают по строгому порядку, например по алфавиту, и проверяют каждый. Тогда верный ответ точно не будет потерян.
Кратко о главном
- Перебор — это проверка всех возможных вариантов по очереди.
- Способ годится, когда вариантов немного и каждый можно проверить.
- Удобно выписывать варианты в таблицу и вычёркивать неподходящие.
- Варианты перечисляют по порядку, чтобы ни один не пропустить.