Инструменты сайта


Навигация




Яндекс.Метрика

Рейтинг@Mail.ru


Индекс цитирования

Сколько дней блогу

Цена nozdr.ru

Траст nozdr.ru

Настоящий ПР nozdr.ru

nozdr.ru Alexa/PR

nozdr.ru Tic/PR

Метод перебора

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

Рассмотрим пару примеров применения метода перебора в решении различных задач.

Перебор последовательности

Допустим, нам встретилась последовательность цифр 141526418, и мы знаем, что в ней зашифровано латинскими буквами некое слово. Какой самый простой способ зашифровать слово? Конечно же, использовать шифр замены A1Z26! Число цифр нечётное, значит хотя бы одна буква закодирована всего одной цифрой. Но как отделить буквы первой десятки от последующих, кодируемых двумя цифрами? 14 - это AD или N? Вот тут-то нам и пригодится метод перебора. Переберём все комбинации из одной-двух цифр из диапазона [1-26].

В последовательности 141526418 можно выделить следующие удовлетворяющие нашим условиям комбинации: 1,2,4,5,6,8,14,15,18,26. Эти числа соответствуют буквам A,B,D,E,F,H,N,O,R,Z. Комбинации 41, 52 и 64 нам не подходят, так как в латинице всего 26 букв.

Перебирать будем так: сначала возьмём самую развёрнутую последовательность, где все буквы из первого десятка, а затем будем по очереди увеличивать используемые числа, то есть заменять последовательности 1-4 на 14, 1-5 на 15, 1-8 на 18, 2-6 на 26, перебирая все возможные комбинации.

  1. 1-4-1-5-2-6-4-1-8 = ADAEBFDAH
  2. 1-4-1-5-2-6-4-18 = ADAEBFDR
  3. 1-4-1-5-26-4-1-8 = ADAEZDAH
  4. 1-4-1-5-26-4-18 = ADAEZDR
  5. 1-4-15-2-6-4-1-8 = ADOBFDAH
  6. 1-4-15-2-6-4-18 = ADOBFDR
  7. 1-4-15-26-4-1-8 = ADOZDAH
  8. 1-4-15-26-4-18 = ADOZDR
  9. 14-1-5-2-6-4-1-8 = NAEBFDAH
  10. 14-1-5-2-6-4-18 = NAEBFDR
  11. 14-1-5-26-4-1-8 = NAEZDAH
  12. 14-1-5-26-4-18 = NAEZDR
  13. 14-15-2-6-4-1-8 = NOBFDAH
  14. 14-15-2-6-4-18 = NOBFDR
  15. 14-15-26-4-1-8 = NOZDAH
  16. 14-15-26-4-18 = NOZDR

Итого получили 16 вариантов. Единственное читаемое слово NOZDR (кому читаемое, а кому и нет :-)), получилось в самом конце. Оно и будет ответом. Вот если бы в самом начале была подсказка, что из последовательности 141526418 должно получиться 5 букв, то тогда задача решится однозначно. И перебор будет не нужен, потому что разбить на 5 букв последовательность 141526418 можно только одним единственным способом. Но такой подсказки не было, и метод перебора пригодился.

Перебор решений при недостатке условий

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

Учитель на уроке математики задал ученикам такую задачу: «У матери три дочери. Произведение возрастов дочерей = 40, сумма возрастов равна числу учеников в классе. Каков возраст каждой из дочерей?» Ну, ученики по-быстрому посчитали, сколько их всего в классе, и стали решать задачу. Решали-решали… Не решается. Попросили у учителя подсказку. Учитель подумал и говорит: «А, точно! У младшенькой голубенькие глазки!». Ученики обрадовались, и решили задачу. А теперь вопрос вам: сколько же лет каждой из дочерей?

Если решать задачу в лоб (AxBxC=40, A+B+C=D, голубенькие глазки), то сразу наталкиваешься на кучу неизвестных и недостаток условий. 4 неизвестных, два уравнения и ещё голубенькие глазки!!! Как известно, сколько неизвестных, столько должно быть и независимых условий. У нас в задаче два нормальных условия и одно непонятное. Как же её решать?

А методом перебора! Во-первых, такие задачи по умолчанию решаются целочисленно. Найдём все комбинации из трёх целых чисел, произведение которых даёт 40. Заодно посчитаем сумму этих чисел. Оказывается, таких комбинаций не так уж и много - всего шесть.

  1. 1x1x40=40, 1+1+40=42
  2. 1x2x20=40, 1+2+20=23
  3. 1x4x10=40, 1+4+10=15
  4. 1x5x8=40, 1+5+8=14
  5. 2x2x10=40, 2+2+10=14
  6. 2x4x5=40, 2+4+5=11

Если бы учеников в классе было 42, 23, 15 или 11, то они бы сразу решили задачу. Но у них возникло затруднение - их было 14, и они никак не могли выбрать, какой же из вариантов 1-5-8 или 2-2-10 подходит. Но когда учитель сказал про голубые глазки, им это помогло определиться. Голубые глазки были у младшенькой, то есть была самая младшая дочь, а в варианте 2-2-10 младшеньких две. Значит, нам подходит только четвёртый вариант 1-5-8.

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

games/quest/math/methods.txt · Последние изменения: 2017/11/21 11:00 — NoZDR

Инструменты страницы




Инструменты пользователя