- Илья, где ты пропадаешь две недели?
- В глубоком-глубоком роуминге :)
Но я вернулся, почти всем ответил на почту и комментарии, а теперь, извините, поделюсь неприятным впечатлением от Питерского Пулково-1. Несколько лет я не был в этом дивном месте, поэтому успел подзабыть его бардак и грязь. Если бы номер гейта на билете соответствовал реальному номеру двери, от которой автобус повезёт к самолёту, если бы табло над гейтом правильно указывало номер рейса, то сотрудницы аэропорта не были бы вынуждены кричать: «Рейс ###, подходите сюда, а рейс ### отойдите, сейчас мы не вас сажаем. Да, мы знаем, что на табло сейчас указан ваш город, поэтому не читайте табло». Зачем я это пишу? Пару лет назад помогло же :) А пока, если меня спросят европейцы, через какую из столиц лучше влетать в Россию, то я однозначно назову Москву. Как минимум, в Москве работают лифты, хорошо светят лампочки и моют туалеты, а в Пулково-1 в тёмных коридорах неподвижно стоят грязные эскалаторы, о которых сразу забываешь, посетив уборную. Злые языки утверждают, что ремонта там не было со времён блокады Ленинграда.
Ладно, забыли и проехали. Давайте лучше вспомним важный жанр задачек на поиск оптимального решения (в данном случае, минимального количества действий для достижения результата):
1. Много лет назад у нас была задачка о хрупких шариках: Есть стакан с очень дорогими одинаковыми хрупкими шариками из очень прочного материала. И есть лестница с сотней ступенек. Какой минимум шариков придётся разбить, чтобы выяснить предельную высоту (число от 1 до 100 — бросаем со ступенек), с которой можно ронять шарики целыми (т.е. чтобы они не разбились)?
2. Старинная детская задачка о готовке звучит так: На одной сковороде может поместиться не более 2 котлет. Одна сторона котлеты жарится 1 минуту. За какое минимальное время можно пожарить три котлеты с 2-х строн.
3а. Два маляра столкнулись на дороге с другими двумя малярами. Этикет обязывает каждого из первой пары поздороваться с каждым из второй пары, но руки у каждого маляра испачканы в краске своего цвета. А так как маляры не хотят пачкать руки в краске другого цвета, то у них есть несколько чистых перчаток. Какое минимальное количество перчаток они будут вынуждены испачкать, чтобы поприветствовать друг друга?
3б. Три маляра столкнулись на дороге с одним маляром. Соответственно, каждый из них должен с ним поздороваться. Остальное как в задаче (3а): их руки испачканы четырьмя цветами, есть несколько чистых перчаток. Сколько перчаток им придётся испачкать?
(последние две задачки своевременно напомнил Антон, а я чуть-чуть поменял формулировки)
Пожалуйста, напишите в комментариях статус по этим задачкам примерно в таком виде:
1. Помню, ответ x,
2. Давно знаю, ответ y,
3. а) тоже слышал, ответ z1, б) первый раз слышу, ответ z2.
Хороших выходных!
14 окт. 2011 г.
Маляры и котлеты
Темы:
математика
Подписаться на:
Комментарии к сообщению (Atom)
Понравилась заметка? Подпишитесь на
RSS-feed или email-рассылку.
Хотите поделиться ссылкой с другими? Добавьте в закладки:
Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.
С уважением,
Илья Весенний
RSS-feed или email-рассылку.Хотите поделиться ссылкой с другими? Добавьте в закладки:
Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.
С уважением,
Илья Весенний
1. Помню, ответ 1;
ОтветитьУдалить2. Первый раз слышу, ответ 3 минуты;
3. а) первый раз слышу, ответ 2; б) тоже впервые слышу, ответ 2.
Григорий
По 1.
ОтветитьУдалитьЕсть более интересная вариация задачи: пусть мы кидаем объекты с этажей; не разбившиеся объекты можно подобрать с земли. Но мы ленивые (старые) и хотим минимизировать число подъемов вверх по лестнице(вниз спускаемся без проблем), чтобы определить с какого этажа объекты бьются.
Если классика решается двумерной динамикой, то тут (авторское и то, до которого мы дошли) требует пятимера.
Можно еще вариации генерить...
к комментарию 67108864: кажется, что ответ тот же, что и в классике. Два шарика, не более 19 подъёмов вверх по лестнице. Если считать вариант "поднялся на 10-й этаж - шарик не разбился, дошел до 20-го, кинул второй шарик" за один подъём, а не за два - тогда задачка резко усложняется.
ОтветитьУдалить3а, 3б — это вариант задачи про три презерватива. ;) Хотя, кажется, есть разница, поскольку у перчатки есть левизна, а у презерватива — нет
ОтветитьУдалить1,2 — помню ответы.
в задаче 3б должно быть три, в остальном согласен с первым комментарием. Первую задачу помню. У второй есть аналог с автомобилем и запаской (не по формулировке, но по виду решения), поэтому как бы знаю. Третьи первый раз слышу.
ОтветитьУдалитьАнтон
1. Первый раз, 1
ОтветитьУдалить2. Помню, 3
3. Первый раз, а-2, б-3
2 Про котлеты - самая лучшая, 4 минуты.
ОтветитьУдалить2.был не прав 3 имнуты
ОтветитьУдалить1. Помню, ответ 1,
ОтветитьУдалить2. Первый раз, 1 мин
3. Первый раз, а-1, б-3.
1. помню, ответ 1
ОтветитьУдалить2. первый раз вижу, ответ 2
3а. видел у антона, две перчатки
3б. тоже там видел, но ответ у меня три. если не прав, объясните как можно с двумя обойтись
1. давно знаю. ответ - 1
ОтветитьУдалить2. помню. ответ - 3
3а. помню про презервативы. ответ - 2
3б. не видел. ответ - 2.
P.S. Через ЖЖ не авторизовало, аккаунту gmail Сказало account do not have access. Фигня какая-то
1. Не видел, ответ 1
ОтветитьУдалить2. Давно знаю, ответ 3
3а. Не видел, ответ 2
3б. Не видел, ответ 2
1) Давно знаю, 1
ОтветитьУдалить2) Помню, 3
3а) Не видел, 2
3б) не видел, 2
1. первый раз слышу, ответ 1
ОтветитьУдалить2. давно знаю, ответ 3
3а. давно знаю (в варианте про презервативы), ответ 2
3б. впервые слышу, ответ 2
1) Помню задачу, тогда не решил, теперь заморочился - оказалось неправильно.
ОтветитьУдалить2) Знаю, где-то в детстве далеком точно решал. ответ: 3.
3а) Не знал, решил, но ответ 3. Что я делаю не так?
3б) Тоже не знал, тоже три. Странно. Опять же: можно выворачивать перчатки?Это может быть важно.
Азат, конечно перчатки выворачивать нужно. Иначе совсем неинтересно :-)
ОтветитьУдалитьгм, я тут опечатался, во второй задаче ответ конечно же 3 минуты.
ОтветитьУдалитьнасчет третей - можно снимать перчатки и передавать другому?
Несколько недель назад я тоже был проездом в аэропорту Пулково-1, и хотел бы поделиться некоторыми впечатлениями.
ОтветитьУдалить1. Трансфер Пулково-2 -> Пулково-1
Я прилетел в терминал Пулково-2, и мне надо было попасть на внутренний авиарейс, в терминал Пулково-1. Между этими двумя терминалами достаточно большое расстояние, пешком идти минут 40 (и самое главное, непонятно как). Вполне логично предположить, что между терминалами должен ходить автобус - "шаттл" аэропорта или хотя бы городской транспорт. На самом деле "шаттла" нет (как мне сказали, над его запуском руководство аэропорта еще только размышляет), а на городском транспорте придется ехать до метро Московская и обратно. Пассажир, у которого следующий рейс вылетает из Пулково-1, должен получить багаж и подойти к окошку "Трансфер" на первом этаже аэропорта, показать билет и объяснить ситуацию. Любезная женщина, которая сидит за этим окошком, собирает пассажиров, которым нужно попасть в другой терминал. Когда набирается достаточно большая группа, женщина выводит их на улицу и усаживает в специальный микроавтобус, который едет до Пулково-1. Мне такая организация трансфера показалась очень милой, но наверное регулярный автобус был бы более практичным решением.
Автоматического перевоза багажа между терминалами нет. То есть нужно получить весь багаж в Пулково-2 и сдать в Пулково-1.
2. Вход в аэровокзал
Для того, чтобы попасть в аэровокзал, необходимо пройти через входной пункт контроля, "просветить" сумки и пройти через металлоискатель. Поскольку на входе стоит только одна установка для проверки багажа и одна или две рамки металлоискателя, очередь двигается очень медленно. Вход, в котором я стоял в очереди, почему-то был еще и выходом. Большая часть очереди стояла на улице и в длинном тамбуре, в котором постоянно дул холодный ветер. Пассажиры спешили, ругались и обещали жаловаться руководству. Сотрудники аэропорта тоже ругались и говорили, что их руководство уже давно не слушает, поэтому жалуйтесь на здоровье. К слову, в предыдущий раз я был в этом терминале три года назад, и основное воспоминание о нем - холодный вход с очередью.
На мой взгляд, гораздо более удобный вход можно сделать за счет небольшого дополнительного помещения снаружи, либо за счет переноса пункта контроля глубже внутрь аэровокзала.
3. Организация пространства
Внутри здания очень тесно, всюду очереди, переходы между этажами очень узкие и извилистые. Указатели есть, но мне приходилось задумываться о том, как попасть в то или иное место. Если я правильно понял, для того, чтобы пройти от входа к выходу, нужно один раз подняться, и один раз спуститься по лестнице.
4. Контроль перед залом вылета
Очень тесное помещение с длинной, но относительно быстро двигающейся очередью. Сотрудников мало, места, где можно было бы раздеться / сложить вещи тоже очень мало.
Вообще, на мой взгляд, конкретно эта процедура максимально адекватно устроена в европейских аэропортах. Типичная схема примерно такая: есть "лента", вдоль которой двигается очередь (примерно как в столовой). По мере приближения к сканирующему оборудованию, люди в очереди снимают верхнюю одежду и выкладывают вещи в коробки, которые стоят на ленте. Ключевой момент - с другой стороны ленты стоят сотрудники аэропорта, которые помогают пассажирам (если надо - подержат сумку, помогут сложить вещи в коробку, при необходимости перенесут сумку назад, чтобы пропустить еще раз через сканирующий аппарат).
5. Зал вылета
В зале на первом этаже почти в самом центре стоит курилка, рядом с которой сильно пахнет табачным дымом. В туалете старая сантехника, грязно. В женский туалет была очередь. Неужели для одного из крупнейших аэровокзалов России нормальные туалеты - нерешаемая проблема?
Конечно большая часть неприятных моментов объясняется тем, что зданию аэровокзала около 40 лет, и со времен проектирования и постройки значительно вырос пассажиропоток и изменились требования безопасности. Но ведь все эти проблемы вполне решабельны, и стоимость решения совсем не фантастическая!
1. Такой вариант первый раз слышу, ответ 1.
ОтветитьУдалитьБолее сложный вариант, на мой взгляд:
Есть всего два шарика и сто ступенек. За какое минимальное количество попыток можно узнать с какой высоты шарики разбиваются. Или лучше сказать какая оптимальная стратегия для получения ответа.
2. Не видел, ответ 3.
3а. Не видел, ответ 4.
3б. Не видел, ответ 3.
Тут вот говорят что можно переворачивать перчатку, но разве перчатка не будет уже испачкана краской внутри?
1. не понимаю условие задачи :(
ОтветитьУдалить2. 4 минуты. Народ, а почему три все пишут, объясните плиз!
3а. 4
3б. 4
fibon-ache,
ОтветитьУдалить> можно снимать перчатки и передавать другому?
Правилами не запрещено.
Дима, спасибо за детальное описание проблем этого аэропорта.
Voland
> Тут вот говорят что можно переворачивать перчатку, но разве перчатка не будет уже испачкана краской внутри?
Будет, конечно. Но иногда это не мешает.
la_sotte,
детали условия задачи и сама задача были давно разобраны (ссылка в заметке есть).
Что касается ответов на вторую и третью задачки, то складывается впечатление, что Вы стараетесь найти не оптимальное, а хоть какое-то решение.
1. Первый раз. Ответил 1, но решил, что сильно просто, начал рыть условие и искать, где ошибся (так и не понял, для чего в условии указана очень высокая прочность шариков?). Прошел по ссылке и понял, что в том месте, где я искал подвох скрупулезнее всего, его не оказалось, а связан он с неверным чтением условия и поиском алгоритма оптимального по времени, а не по экономии шариков. Действительно, здесь "программистский" подход может завести не в ту степь =)
ОтветитьУдалить2. Первый раз, ответ 3 мин.
3. Смутно помнил подобную задачу в формулировке с презервативом, но т.к. забыл и условие, и решение, пришлось решать повторно. В условии есть некоторая неоднозначность: у маляров перчатки парами или нет? Если парами, то можно ли правой рукой пожимать левую руку? Если не парами, то можно ли совершать рукопожатие левыми руками? Поскольку в условии эти моменты не оговорены, я решил, что подразумевается: перчатки не обязательно парные и можно совершать рукопожатие левыми руками. Тогда ответы:
3а. 2 перчатки
3б. 2 перчатки
3б после 3а решается быстро, т.к. принцип обмена перчатками достаточно похож.
Я сравнительно недавно познакомился с вашим блогом и сейчас активно читаю его прошлые статьи. Спасибо вам большое за такой замечательный интернет-дневник и такое вежливое отношение к посетителям, за внимательное чтение комментариев, помощь и постоянное желание слегка подтолкнуть к решению, не раскрывая его. Все это – большая редкость в современном рунете! Постараюсь в ближайшее время прокомментировать потрясающую задачу про туземцев острова беззеркалья, которая не решалась и не выходила у меня из головы два полных вечера подряд.
Почему-то не могу подписаться ни через LiveJournal, ни через Google: "Input error: Cookie value is null for FormRestoration"
Дмитрий,
ОтветитьУдалитья понимаю условие третьей задачи так:
- левые и правые перчатки не отличаются друг от друга,
- поэтому у маляров они не парами, а по одной.
Спасибо за тёплые слова!
Досадно, что авторизация иногда неправильно работает. Здорово, что Вы смогли пробиться через это препятствие.
1. Совсем недавно читал блог с конца.
ОтветитьУдалить2. Решил быстро. Ответ 3 минуты.
3. Задачу не видел. Честно не понял до конца условия задачи. Получается перчатка изнутри не пачкается? Тогда: 3а - 2 перчатки, 3б - 1 перчатка.
Допустим пачкается, тогда всё равно 3а - 2 перчатки. Правда с одним условием. 3б - 3 перчатки.
ОтветитьУдалить«
ОтветитьУдалить- левые и правые перчатки не отличаются друг от друга,
- поэтому у маляров они не парами, а по одной.
»
Тогда задача точно не отличается от задачи про два презерватива (я почему-то в прошлом комментарии почему-то написал три вместо двух).
Если же левизна всё-таки есть, то ответ в 3а будет отличаться — три перчатки вместо двух (правда, строго доказать пока не вижу как), а в 3б ответ такой же — две. Здесь под левизной подразумевается такая особенность, что у каждой перчатки есть две стороны — левая и правая, но если перчатку вывернули, то надеть на ту же руку уже нельзя.
Хм, сейчас заметил, что фраза «левые и правые перчатки не отличаются друг от друга» оставляет некоторую неопределенность. Если есть левизна в том виде, как я определил, то перчатки изначально все одинаковы в том смысле, что путем выворачивания можно их все привести к каноническому виду — чтобы надевались на правую руку. Что оставляет два варианта толкования этой фразы, приводящих к разным ответам для 3а.
Ой, я в предыдущем комментарии везде перепутал 3а и 3б.
ОтветитьУдалитьИлья, вторая задача мне понравилась - интересная и жизненная и комуто может быть полезная на практике, остальные imho высосаны, не из мира сего, поэтому и не даются легко некоторым здесь присутствующим.
ОтветитьУдалитьВот Вы лучше Илья объясните на пальцах чем разновидность дихотомии, основанная на числах Фибоначчи, лучше половинного деления. А то у меня из закоулков памяти неожиданно всплыла фраза лектора, что якобы лучше, а вот чем и при каких обстоятельствах не могу понять. Какое бы число элементов упорядоченного массива я ни пытался взять для эксперимента, у меня всегда получалось, что поиск подходящего элемента методом половинного деления в худшем случае был быстрее либо таким же по скорости по сравнению с методом деления в пропорции Фибоначчи в худшем случае. Или речь должна идти о статистическом преимуществе? Помогите пожалуйста.
Раз уж тут затронута тема дихотомии.
Уважаемый аноним, спасибо за интересный вопрос. Он немножко не по адресу, потому что я не специализируюсь на этих методах. Поэтому я могу только поделиться своей версией ответа на вопрос.
ОтветитьУдалить> Какое бы число элементов упорядоченного массива я ни пытался взять для эксперимента, у меня всегда получалось...
В этом и дело. Вы проверяете эти два метода на одной задаче, а заточены они под различные постановки.
Если задача звучит так: «Есть монотонная функция f(x), определённая на интервале [a, b], найти x из [a, b], для которого f(x) отличается от заданного y не больше чем на d», то метод деления пополам, конечно, должен показывать максимальную эффективность, потому что исследуемый интервал на каждой итерации сокращается в два раза (если мы ничего не знаем о функции f(x), то более эффективного решения не может быть).
Если же наша задача состоит в поиске такого x из [a, b], для которого f(x) является минимальным значением этой функции на этом интервале, то начинаются интересные эффекты:
1. В методе деления пополам для принятия решения о сужении интервала мы опираемся на значения в трёх точках (двух крайних и одной средней). А метод золотого сечения опирается на значения в четырёх точках, что должно увеличивать вероятность выбора правильного интервала (содержащего глобальный минимум).
2. В методе деления пополам отрезок всякий раз сокращается в два раза, а в методе золотого сечения ~1.7, что опять же уменьшает вероятность упустить интервал, содержащий искомое значение.
Вообще тут всё зависит от того, что мы знаем о функции f(x). Но даже если достоверно известно, что на данном интервале функция имеет только один локальный минимум (даже если известно, что она сначала строго убывает, а потом строго возрастает), то легко придумать примеры, когда значения в одной центрально точке не хватит для выбора правильного интервала.
Более того, для таких функций доказано, что достаточно иметь значения в двух точках внутри интервала (см. ternary search). Таким образом, методы Фибоначчи и золотого сечения можно считать, например, разновидностью тернарного поиска. Отличие в том, что эти методы оптимизированы по количеству вычислений f(x) (классический тернарный поиск предполагает в два раза больше вычислений, чем эти методы).
Как я понимаю, в статье 1966 года Avriel, Mordecai; Wilde, Douglass J. , "Optimality proof for the symmetric Fibonacci search technique" как раз поясняется, в каком смысле эти методы являются оптимальными. Если я правильно понял, речь об "удельном сокращении интервала" (т.е. о доле сокращения на каждое обращение к функции).
Занятно, я слышал вторую задачу в варианте про двух мужчин, двух женщин и, извините за выражение, венерические заболевания и презервативы :) В любом случае, ответ 2.
ОтветитьУдалитьИзвиняюсь, я имел в виду не вторую, а третью, о малярах.
ОтветитьУдалитьGrigory Javadyan, да, это известная формулировка, её выше уже пару раз вспоминали. Я стараюсь предлагать задачки в терминах "не из начальной школы" (даже пятиклассники уже не хихикают, услышав слово "презерватив" :).
ОтветитьУдалитьИлья, а вы будете разбирать представленные задачи? А то я, честно говоря, никак не могу понять как управиться с двумя перчатками.
ОтветитьУдалитьVoland, хорошо, мы разберём их в одной из следующих заметок.
ОтветитьУдалитьВот и разбор поспел.
ОтветитьУдалить