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


Навигация




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

Рейтинг@Mail.ru


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

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

Цена nozdr.ru

Траст nozdr.ru

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

nozdr.ru Alexa/PR

nozdr.ru Tic/PR

Группы и комбинации

Квадраты с чёрными дырами

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

Квадрат 9×9 клеток заполнен цифрами от 1 до 9, каждая цифра присутствует в квадрате 9 раз. Требуется разбить квадрат на группы цифр так, чтобы они в каждой такой группе давали число 10. Группы должны быть «цельными», то есть клетка должна соединяться в группу с другими клетками не через углы, а через рёбра. Часть цифр будет невозможно объединить в такие группы, и они «выпадут». Такие клетки называются «чёрными дырами». Правильное решение подобной задачи - не просто сгруппировать клетки в «десятки», но и чтобы количество «чёрных дыр» при этом было минимально.

Рассмотрим алгоритм решения таких задач на примере.

Группируя цифры, будем ограничивать их со всех сторон отрезками, являющимися сторонами клеток. Каждую сторону клетки будем называть «стенкой». Если клетка ограничена со всех сторон стенками, она становится «чёрной дырой» и заштриховывается.

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

Существует метод, который позволяет найти верное решение с минимальным числом «чёрных дыр». Он состоит из трёх этапов.

I этап

Нужно отделить стенкой две соседние цифры, если они в сумме превышают 10.

Поставив таким образом стенки, видим, что часть клеток автоматически стала «чёрными дырами». Переходим ко второму этапу. Продолжаем анализировать клетки, между которыми ещё нет стенок.

II этап

Берём две соседние цифры и смотрим, можно ли их сумму дополнить до 10 соседними примыкающими по вертикали или горизонтали цифрами. Если этого сделать нельзя, то между этими цифрами рисуем стенку.

Например, если взять две соседние цифры 1(c8) и 7(d8), то к этой паре примыкают цифры 9,1,4. Цифры 9 и 4 заведомо не подходят. Далее, если взять во внимание 1(b8), то сумма трёх цифр составит 9(7+1+1). До десятки не хватает единицы, но её вокруг этих трёх цифр нигде нет. Значит, между 1(c8) и 7(d8) рисуем стенку, и клетка d8 с семёркой становится «чёрной дырой».

Далее, к примеру, смотрим на 6(i8) и 3(i9). Примыкающие к ним цифры 7,3 и 4 заведомо дают в сумме больше 10. Значит, и эту пару отделяем стеной. Аналогично поступаем с остальными оставшимися парами. В конце этапа головоломка уже выглядит как настоящий лабиринт с тупиками и переходами.

III этап

Все возможные стенки расставлены на первых двух этапах. Остался третий и самый трудный этап - сгруппировать оставшиеся цифры в «десятки». Это уже не очень очевидно. Теперь придётся думать немного больше, просчитывая на несколько ходов вперёд. Например, кажется очевидным сгруппировать 4(g8)-6(g9) или 3(h8)-7(h9). Но тогда 2(f9), 2(g7) и 1(h7) в дальнейшем не получится использовать, и они превратятся в лишние «чёрные дыры», а нам это не нужно. Поэтому будет правильным только такое расположение групп цифр в этом углу квадрата: 7(h9)-3(i9), 4(i7)-6(i8), 2(f8)-2(f9)-6(g9), 2(g7)-4(g8)-3(h8)-1(h7).

Дальнейший поиск, в ходе которого каждый раз нужно выполнять анализ сложившейся ситуации на шаг вперёд, и выбирать такой вариант решения, который образует меньшее количество «дыр», приводит нас к окончательному решению. Количество «чёрных дыр» получилось при этом минимально и равно 21.

Если «чёрные дыры» вырезать, то получившийся квадрат с окошками можно использовать как аналог решётки Кардано - в качестве шаблона для шифрования текста.

Метод перебора для решения разных задач

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

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

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

Допустим, нам встретилась последовательность цифр 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

Единственное читаемое слово 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/combi.txt · Последние изменения: 2017/05/16 06:18 (внешнее изменение)

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




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