Метод перебора: рассмотреть все случаи

  • 5 мин чтения
  • Послушать — 2 мин
  • 7 карточек

Математика, 5 класс · Г. В. Дорофеев, Л. Г. Петерсон

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

Задача про автобусы. Модель: xy = 240 и (x + 1)(y - 8) = 240, где x — число больших автобусов, y — сколько детей в одном. Из первого равенства x и y — парные делители числа 240, а из второго y > 8. Составим таблицу:

xy = 240 : x(x + 1)(y - 8)
1240464
2120336
380288
460260
548240
640224
830198
1024176
1220156
1516128
1615119
201284
241050

Подходит только x = 5, y = 48: надо заказать 5 больших автобусов.

Задача про число и цифры. Двузначное число на 46 больше произведения своих цифр: 10x + y = xy + 46, где x — цифра десятков, y — цифра единиц. Правая часть не меньше 46, значит, число не меньше 46, и x не меньше 4; при x = 4 получаем 40 + y = 4y + 46 — так не бывает. Остаётся проверить x от 5 до 9: при x = 5 выходит y = 1 (число 51), при x = 7 — y = 4 (число 74), при x = 6, 8, 9 цифры y нет. Ответ: 51 или 74 — условие не позволяет выбрать одно.

Найдя одно число, перебор не останавливают: среди непроверенных случаев могут быть ещё решения.

Определение

1 / 7

Метод полного перебора

Подобрав одно решение пробами, нельзя быть уверенным, что найдены все.

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

Перебор бывает долгим, но анализ условия часто подсказывает, как перебирать короче.

Разбор

2 / 7

Ряды в зале

«24 ученика сидят в x рядах по y человек. Если рядов на один больше, в каждом на 2 ученика меньше». Модель:

xy = 24 и (x + 1)(y - 2) = 24

  1. Сужаем

    x и y — парные делители 24, причём y > 2.

  2. Таблица
    xy(x + 1)(y - 2)
    12444
    21230
    3824
    4620
    6414
    839
  3. Ответ

    Подходит только x = 3, y = 8: 3 ряда по 8 учеников.

Проверь себя

3 / 7

Почему нет x = 5?

Из xy = 24: x и y — парные делители.

Почему в таблице нет строки x = 5?

24 на 5 нацело не делится5 — нечётное числопри x = 5 слишком много
Ответ и объяснение

При x = 5 получилось бы y = 24 : 5 — не натуральное число. Поэтому x берём только среди делителей 24.

Разбор

4 / 7

Число и его цифры

«Двузначное число на 52 больше произведения своих цифр». Цифра десятков x, единиц y:

10x + y = xy + 52

  1. Сужаем

    Число не меньше 52, значит, x не меньше 5.

  2. Пять и шесть

    x = 5: 50 + y = 5y + 52 — так не бывает. x = 6: 60 + y = 6y + 52 — ни одна цифра y не подходит.

  3. Семь — девять

    x = 7: y = 3, ведь 73 = 21 + 52. x = 8: y = 4, ведь 84 = 32 + 52. x = 9: цифры нет.

  4. Ответ

    73 или 84 — условие не позволяет выбрать одно.

Частая ошибка

5 / 7

Нашли одно — и остановились

Ошибка: найти 73 и закончить перебор.

Но при x = 8 тоже подходит: 84 = 8 · 4 + 52.

Найдя одно решение, перебор не останавливают: среди непроверенных случаев могут быть ещё.

Проверь себя

6 / 7

Что дальше?

Перебор полный — все случаи.

При переборе x от 5 до 9 решение нашлось при x = 7. Что делать с x = 8 и x = 9?

проверить их тожене проверять: ответ найденпроверить только x = 8
Ответ и объяснение

В полном переборе проверяют все случаи: так нашлось второе число 84.

Главное

7 / 7

Главное

  • Полный перебор — рассмотреть все случаи.
  • Условие помогает перебирать короче: парные делители, границы для цифр.
  • Нашёл решение — продолжай: может быть ещё.
  • Ответ может состоять из нескольких чисел: 73 или 84.

Проверь себя: тест по теме

Несколько заданий по этой теме из того же учебника. Каждый ответ проверяется сразу, а начать можно без регистрации.

  • Задания из этого учебника
  • Ответ проверяется сразу
  • Без регистрации
Начать тест