7 дек. 2012 г.

Бегство от перебора

Добрый день.

Решение задачи может осуществляться как минимум с двумя целями:
- узнать ответ (речь о решении проблем на работе или сдаче экзаменов),
- развить себя, решая задачу.

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

Когда я говорю о важности избегания переборных решений, то, конечно, не отказываю этому способу в эффективности. Более того, иногда быстрая реализация решения перебором тоже полезна (например, чтобы с интересом изучать язык программирования). Но исходный смысл задачки «одним росчерком превратить 5+5+5+5=555 в верное равенство» был всё же в развитии воображения и интуиции (что никак не отменяет полезности переборного решения).

В прошлой заметке «Игры в цифры» я предложил решить простые ребусы, посетовав, что далеко не всегда видно, как справляться с ними без перебора. В то же время, мы прекрасно понимаем, что перебрать все возможные перестановки десяти цифр можно очень быстро (даже ученикам начальной школы уже вредно задавать реализацию этой программы, потому что им всегда чего-нибудь интересненького хочется).

Поэтому давайте решим ту вторую систему, не используя грубую силу. Итак, задачка состояла в следующем — решить систему:
     Г*О+Д=21,
     В*Е+К=21,
     Э*Р+А=21.

Заметим, что у нас в ней использовано девять разных букв, а разных цифр бывает всего десять. Другими словами, почти все цифры придётся применить.

Интуиция подсказывает, что полезно проанализировать цифры, являющиеся делителями числа справа (21). Легко почувствовать, что с тройкой бывает много разных решений, поэтому сконцентрируемся на семёрке. Вопрос: где она может стоять в равенстве A*B+C=21?

Если вдруг C=7, то A*B=14, из чего следует, что или A, или B должно быть равно 7, чего не может быть (так как разным цифрам соответствуют разные буквы, а C=7 по предположению). Тогда рассмотрим случай A=7. Легко увидеть, что это возможно только при C=0. Это значит, что если семёрка входит в ответ, то одно из равенств выглядит так: 7*3+0=21.

Как мы ранее уже говорили, с тройкой трудно ждать чего-то интересного, поэтому рассмотрим цифру 0. Вопрос: где 0 может стоять в равенстве A*B+C=21? Легко понять, что ни A, ни B не могут быть равны 0. Это значит, что C=0. Другими словами, если в ответ входит 7, то в него входит и 0. А если в ответ входит 0, то в него входит 7. Поскольку у нас на 9 букв претендуют 10 цифр, то не может быть, что 7 и 0 одновременно не входят в ответ. А это значит, что они обе входят. И это очень хорошо, так как они с собой забрали ещё и цифру 3.

Теперь наша задача звучит так:
     3*7+0=21,
     В*Е+К=21,
     Э*Р+А=21.

Давайте подумаем, какие самые маленькие множители могут быть в произведениях В*Е и Э*Р. Свободные цифры у нас такие: 1, 2, 4, 5, ... Но разве может быть меньшим множителем 5? Нет, так как 5*6 уже больше 21. А может ли быть наименьшим множителем 1? Тоже нет, так как 1*A+B=21 не имеет решения в цифрах. Это означает, что на две позиции у нас ровно два кандидата, поэтому можно считать, что В=2, а Э=4.

Теперь наша задача звучит так:
     3*7+0=21,
     2*Е+К=21 (2<Е),
     4*Р+А=21 (4<Р).

Из Э=4 сразу следует единственная возможность не превысить 21: 4*5+1=21. А с В=2 получаем уже небольшой перебор — свободные цифры у нас такие: 6, 8, 9. Но тут уже трудно не найти 2*6+9=21. Получается, что цифра 8 у нас не может участвовать в решении. Первая задача (где вместо 21 стоит 15) решается совершенно аналогично.

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

Повторюсь: полностью от перебора уйти почти невозможно. Сильные шахматисты не только имеют хорошее шахматное чутьё, но и быстро-быстро перебирают варианты. Но поскольку человек не может рассмотреть все варианты развития шахматной партии, он вынужден тренировать своё «чувство поля». Стоит привыкать стараться сокращать перебор, чтобы взявшись за настоящую и сложную задачу в зрелом возрасте, не опускать руки со словами «всех компьютеров планеты не хватит, чтобы решить эту задачу за век», а бодро проинтуитить, как отбросить огромные объёмы бессмысленных вычислений. Впрочем, нельзя забывать, что хоть ощущения и могут хорошо направить, но им никогда нельзя верить (т.е. обязательно надо за ними проверять).

Если вы согласны, что важно тренировать интуицию в раннем возрасте, то, пожалуйста, поделитесь ссылкой на заметку в Twitter, Google+, Facebook, Вконтакте или добавьте её в свой блог/ЖЖ: <a href="http://my-tribune.blogspot.com/2012/12/brute-force.html">Бегство от перебора</a>. Спасибо!

Хороших выходных!

7 комментариев:

  1. Не сразу заметил Ваше решение. Я так рассуждал.
    Допустим цифра 1 – это второе слагаемое в одном из уравнений. Для порядка, пусть это будет первое уравнение. Если 1 – второе слагаемое, то произведение первых двух цифр в уравнении должно быть 20 (21-1=20). Только цифры 4 и 5 могут дать такое произведение. Значит, считаем, что цифры 1, 4 и 5 уже заняты. Идем дальше. В произведении во втором уравнении не могут быть большие цифры, иначе общее выражение будет больше 21. Поэтому там должны присутствовать 2 и/или 3. 2 * 3 не подходит, так как второе слагаемое должно быть 15, а это уже не цифра, а число. Поэтому возьмем отдельно, например, 3. В этом случае только 3*7+0=21. Остаются цифры, 2, 6, 8, 9. В них легко рассмотреть 2*6+9=21.
    Только оставшиеся цифры для последнего уравнения я записал на бумажку, чтобы ничего не забыть. Будь у меня лучше память, можно было бы обойтись без бумажки.

    ОтветитьУдалить
    Ответы
    1. Анонимный07.12.2012, 19:04

      Это метод "подбора". Он позволяет найти хоть какое-нибудь решение, но не даёт доказательства, что других нет. Было вполне возможно, что цифра 1 вообще не входит в ответ, поэтому мало разбирать только случай "1 – это второе слагаемое в одном из уравнений", надо ещё рассмотреть остальные случаи.

      Удалить
  2. В таких достаточно простых задачках человек интуитивно считает, что метод перебора (подбора) быстрее приведёт его к решению, чем логические рассуждения. И, как видите, это так. Чего париться думать, если первая же проба даёт решение. Поэтому, если вы хотите заставить человека именно думать, то сложность должна быть повыше, чтобы интуиция с предложением "подобрать в лоб" даже не просыпалась.
    Я тут на днях объяснял детям значение фразы "НАУКА УМЕЕТ МНОГО ГИТИК". Кто по каким-то причинам не знает эту фразу, может посмотреть википедию: http://ru.wikipedia.org/wiki/%CD%E0%F3%EA%E0_%F3%EC%E5%E5%F2_%EC%ED%EE%E3%EE_%E3%E8%F2%E8%EA .
    Чем замечательна эта фраза? В ней использовано 10 букв, каждая буква встречается ровно два раза, а взяв любые две строчки (в т.ч. и дважды одну строку) мы получим ровно одну букву, встречающуюся в обеих строках. Собственно, ради этих свойств эта фраза и была придумана.
    Так и хочется по этой фразе сварганить задачку по теме.
    Программка с прошлой задачи у меня осталась, я её чуть подправил и погонял на этой фразе. Самый простой и эстетичный вид получился такой:
    Н*А+У+К*А=35
    У*М+Е+Е*Т=35
    М*Н+О+Г*О=35
    Г*И+Т+И*К=35
    Есть и второй возможный вариант, когда справа вместо "35" стоит "40". Но способа решить эту задачу аналитически с разумным числом переборов, увы, я не нашёл.

    А вот другой вариант я достаточно несложно решил "руками" на пол-листе бумаги. Самое то, чтобы заставить человека думать. Предлагаю попробовать решить и вам:
    НА+У*К*А=86
    УМ+Е*Е*Т=86
    МН+О*Г*О=86
    ГИ+Т*И*К=86
    Здесь, как всегда, разным буквам соответствуют разные цифры. Две буквы, стоящие рядом в начале каждого уравнения - это двузначные числа.

    ОтветитьУдалить
    Ответы
    1. Замечание: в "двузначном числе" первая цифра может быть и нулём.

      Удалить
    2. Спасибо за задачки и идеи!

      > человек интуитивно считает, что метод перебора (подбора) быстрее приведёт его к решению, чем логические рассуждения. И, как видите, это так. Чего париться думать, если первая же проба даёт решение.
      Если надо найти только одно решение, то может сработать. Но нам же надо найти все, доказав, что других нет.

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

      Удалить
  3. Я написал пост в стиле Три чего-нибудь, Три задачи по программированию "Решение", я вынес в отдельный пост, при чём это скорее детальное руководство или подсказки. Думаю, многим будет интересно.

    ОтветитьУдалить

Понравилась заметка? Подпишитесь на RSS-feed или email-рассылку.

Хотите поделиться ссылкой с другими? Добавьте в закладки:



Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.

С уважением,
      Илья Весенний