14 нояб. 2011 г.

Пробуй!

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

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

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

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

Предупреждаю, ниже будет краткий разбор задачек, поэтому остановитесь сейчас, если не хотите случайно его прочитать.

Сначала разберёмся с тремя котлетами, которые надо приготовить на двухместной сковородке за минимальное время. Первую минуту мы можем жарить любые две котлеты (т.е. первый ход можно зафиксировать). Но вот если на вторую минуту ничего не поменять (лишь перевернуть котлеты), то к началу третьей минуты у нас останется одна сырая с двух сторон котлета, которая потребует ещё двух минут времени (и половина сковородки будет зря простаивать, что намекает на неоптимальность данного решения). Это значит, что уже на второй итерации надо что-то менять. А поменять-то мы можем только одно — набор котлет на сковороде (одну придётся оставить, конечно). Сделав этот шаг, мы сразу понимаем, что именно надо делать на третьей минуте. А так как сковорода каждую минуту была заполнена на 100%, то быстрее приготовить три котлеты невозможно.

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

Теперь разберёмся с малярами и перчатками. Опять же, надо пробовать, а не бояться неведомого. У одной перчатки две стороны, а маляры испачканы четырьмя разными цветами, поэтому одной перчатки заведомо не хватит (надо как минимум две). А что можно сделать с двумя перчатками? Есть следующие варианты первого действия:

1) Надеть перчатки на руки маляров, идущих навстречу друг другу,
2) Обе перчатки надеть на руки маляров, идущих в одну сторону.

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

Если же мы пойдём по второму пути, то опять есть два варианта:

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

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

Опять же, мы просто рассмотрели все возможные варианты, пытаясь не потратить больше двух перчаток. Мы попробовали, мы честно расписали возможности. Часто этого достаточно. Безусловно, настоящие сложные задачи не позволят одолеть себя так легко. Но это не значит, что не надо развивать в себе способность справляться с простыми. Когда средние задачи покажутся вам простыми, тогда сложные покажутся средними :)

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

Ещё раз повторюсь, что далеко не всё решается перебором. Например, задачка о покрытии г-образными триминошками поля 128х128 клеток без одной клеточки предполагает очень большое количество действий и вариантов, поэтому здесь лучше применить какую-то другую технику. Но для освоения таких техник сначала необходимо научиться решать простые проблемы «руками». Во всяком случае, почему бы не попробовать делать заведомо безопасные действия?

Хорошего дня!

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

  1. Одинцов Михаил14.11.2011, 14:24

    Хм... странно, чего-то я не понял. Всю жизнь решал задачу про маляров другим способом :)

    Может объясните почему нельзя так?
    Пусть маляры А1 А2 и Б1 Б2
    Надевают перчатки А1 и Б1 - жмут руки
    А1 передает перчатку А2 - так как краска внутри того же цвета, руки А2 не пачкаются, А2 жмет руки Б1.
    Дальше Б1 передает Б2 - жмут руки А2 и Б2.
    А2 возвращает А1 - жмет руки А1 и Б2 - готово.

    Каждый использовал перчатку только испачканную с внутренней стороны в краску своего цвета, потому в чужую не пачкался, все рукопожатия сделаны. Если ставится вопрос - как можно стянуть перчатку не запачкав в краску - легко, с помощью того, кто сейчас носит вторую перчатку.

    ОтветитьУдалить
  2. Одинцов Михаил14.11.2011, 14:28

    хотя, наверное я просто не так понимал условие :) я думал что краска разная попарно - у первой пары одна, у второй другая. А если краски четыре, тогда да, только так.

    ОтветитьУдалить
  3. Одинцов Михаил,
    я не понимаю строчку «А1 передает перчатку А2 - так как краска внутри того же цвета, руки А2 не пачкаются». Цвета и А1 и А2 разные, поэтому такое действие не пройдёт. Или я Вас не понял?

    Но вообще Вы правы в том смысле, что решение возможно и без надевания двух перчаток на одну руку. Разница только в том, что если изначально две перчатки надеты на руки идущих навстречу друг другу маляров, то решающие обычно пробуют сразу совершить максимум рукопожатий, не двигая перчатки. И как раз три рукопожатия удаются, но дальше после этого не сдвинуться не получается.

    ОтветитьУдалить
  4. А1 и А2 надевают перчатки,
    А1 жмёт руку Б1, А2 жмёт руку Б2
    перчатки переворачивают другой стороной
    А1 жмёт руку Б2, А2 жмёт руку Б1.
    Разве так нельзя?

    ОтветитьУдалить
  5. Анонимный14.11.2011, 17:06

    Air, что значит "перчатки переворачивают другой стороной"? Выворачивают и надевавют на руки А1 и А2? Если да, то это не получится, так как изнутри они уже испачканы цветами А1 и А2, а снаружи испачканы цветами Б1 и Б2.

    ОтветитьУдалить
  6. Я имел в виду тыльной стороной.
    А если этого делать нельзя, то как тогда выглядит решение при обоих перчатках надетых на одну и ту же руку?

    ОтветитьУдалить
  7. гм, Илья, смотрите. есть четыре маляра, назовем 1, 2 и 3, 4. нам нужно получить комбинации
    1-3
    1-4,

    и комбинации
    2-3
    2-4.

    1. маляр 1 одевает две перчатки, одну на другую, здоровается с 3 и снимает ее.
    статус: внешняя перчатка чистая внутри, снаружи она цвета 3.
    решено 1-3

    2. маляр 2 одевает чистую перчатку и он здоровается с номером 3.
    статус:внешняя перчатка внутри цвета 2, снаружи цвета 3
    решено 2-3

    3. маляр 1 здоровается с маляром 4
    статус: перчатка вторая внутри цвета 1, снаружи цвета 4.
    решено 1-4.

    4. как поздороваться маляру 2 и маляру 4, то есть получить комбинацию 2-4, если остались две перчатки цветов 2-3 и 1-4…
    хотел было я задать вопрос, но теперь сам вижу решение. перчатка 2-3 одевается на перчатку 1-4 и мы получаем перчатку 2-4.
    может кому интересно.

    ОтветитьУдалить
  8. В задачках с монетами вы говорите: "А вот в первой минимальность количества действий не очевидна, поэтому трудно убедиться в верности своего решения."

    Почему не очевидна? Однозначно не может быть 1 действие. Мы не можем переместить монеты №№ 1 и 4, ибо не будет соседей.

    Значит если будет найдено решение в 2 перемещения можно сказать, что 2 это минимально, неважно сколько будет различных решений с 2 перемещениями. Минимум всё равно будет 2.

    ОтветитьУдалить
  9. Air,
    я так и не понял Вашего решения. Но ниже greatbigsled уже на всё ответил (кстати, спасибо!).

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

    ОтветитьУдалить
  10. Анонимный15.11.2011, 17:38

    Олег, почему вы пишете что мы не можем переместить монеты 1 и 4 ибо не будет соседей. После перемещения у 4 соседней будет №2, а у 1-й - №№ 3 и 5. Или условие не совсем корректно?

    ОтветитьУдалить
  11. "Если мы пошли по первому пути, то произойдёт три рукопожатия (сначала поприветствуют друг друга маляры в перчатках, что сохранит чистоту внешних сторон перчаток). Проблема в том, что после этих трёх рукопожатий ничего больше нельзя сделать [без добавления чистых перчаток], а нам нужно ещё четвёртое приветствие."

    А1 - Красный
    А2 - Зелёный
    Б1 - Жёлтый
    Б2 - Синий

    Одевают перчатки А1 и Б1 и здороваются между собой. Потом они здороваются так: А1 с Б2 и Б1 с А2.
    После чего перчатки такого цвета: одна внутри красная, снаружи синяя, вторая внутри жёлтая, снаружи зелёная.
    А1 берёт вторую перчатку и выворачивает её наизнанку и одевает, Б2 берёт первую перчатку и выворачивает её наизнанку и надевает. И они здороваются так, руки не испачканы, но перчатки в итоге будут одна внутри красно-зелёная снаружи синяя, вторая внутри жёлто-синяя, снаружи зелёная (ну если их обратно вывернуть).

    Т.е. практически как и предложил greatbigsled только не одевая. Мне вначале казался этот способ неподходящим, ибо мне казалось что это нарушает условия о каком-либо смешивании цветов. Прочитав условие внимательнее, я увидел, что только руки не должны поменять цвет, а перчаткам можно. Или я добавляю условий?

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

    Например меняем местами монеты 1 и 2.
    У монеты под №1 один сосед - монета 2, у монеты 2 - соседи 1 и 3. После того как мы поменяли местами у монеты 2 остался сосед - монета 1, а у монеты 1 соседями монета 2 и монета 3. Т.е. и у первой монеты и у второй монеты остался сосед, которого они имели до этого, только он теперь с другой стороны.

    Если поменять монеты 1 и 4, то:
    у монеты 1 только 1 сосед - монета 2. У монеты 4 соседи монеты 3 и 5. После обмена у монеты 4 будет сосед монета 2, у монеты 1 будут соседи монеты 3 и 5. Т.е. ни одна из них не касается тех соседей, что они имели до этого.

    Получается что менять мы можем либо соседние, либо через одну. Соседние остаются соседями сами себе, просто меняются местами. АБ - БА Через одну - через неподвижную: АБВ - ВБА. У А был сосед Б, после смены у А есть сосед Б и наоборот.

    ОтветитьУдалить
  13. То: Илья Весенний
    То: Анноним

    Там изменили трактовку условия задачи. Я понимал её неправильно. Решение получается интереснее, не так банально.

    ОтветитьУдалить
  14. Олег,
    Вы совершенно правы со своим замечанием о перчатках, об этом я и написал в третьем комментарии к этой заметке (с пояснением).

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

    И по-русски будет "надевают перчатки", а не "одевают" (одевать можно ребёнка, например).

    ОтветитьУдалить
  15. Илья,
    Вопрос не по теме. Есть возможность писать в приват что-то? Например, не хочется мусорить комментариями напрямую не относящимися к теме, но являющимися неким продолжением диалога, но что вовсе необязательно для прочтения всеми остальными читателями. С одной стороны нечего сказать - не мусорь, с другой хочется на какую-то заметку сказать спасибо или ещё как-то отреагировать ради что ли человеческого общения.
    Как быть? Или форум - это форум. Блог - это блог? И надо учиться общению в различных условиях?

    ОтветитьУдалить
  16. Анонимный16.11.2011, 19:22

    Олег, по моему опыту Илья всегда отвечает на мэйлы.

    ОтветитьУдалить
  17. Олег,
    этот движок не позволяет многого делать с комментариями. В частности, приватных комментариев тут не бывает. Поэтому личная переписка смещается в почту (что логично). Мой адрес указан на каждой странице - mytribune АТ yandex.ru.

    ОтветитьУдалить
  18. Спасибо, Илья, за разъяснения. Точней мне помогла запись greatbigsled (за что ему тоже спасибо) :)
    Ход моих рассуждений был аналогичен, но вот последний шаг я упустил. Наверное стоило расписать в таком же виде, а не рисовать диаграмму.

    ОтветитьУдалить
  19. Анонимный18.12.2011, 10:23

    Про перчатки.
    Есть две перчатки М и Н.
    Навстречу малярам А1 и А2 идут маляры Б1 и Б2.
    Обозначения цветов соответствуют малярам, "чистый" цвет обозначается "0".
    Вариант без надевания двух перчаток.
    ===========================
    1) А1 и Б1 надевают соответственно перчатки М и Н; жмут друг другу руки.
    --------------------
    М(А1)+Б1 = А1-0; Н(Б1)+А1 = Б1-0.
    ===========================
    2) А1 жмет руку Б2, Б1 - А2.
    --------------------
    М(А1)+Б2 = А1-Б2; Н(Б1)+А2 = Б1-А2.
    ===========================
    3) А1 передает перчатку Б2, Б1 - А2; А2 и Б2 надевают вывернутые перчатки и жмут друг другу руки.
    --------------------
    М(Б2)+А2 = Б2-А1*А2; Н(А2)+Б2 = А2-Б1*Б2.

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

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

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



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

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