tag:blogger.com,1999:blog-6846929136376245264.post7054220471088615224..comments2024-01-03T12:54:39.457+03:00Comments on Привычка не думать: Маляры и котлетыИлья Весеннийhttp://www.blogger.com/profile/12075968879288943233noreply@blogger.comBlogger35125tag:blogger.com,1999:blog-6846929136376245264.post-16845864544509640352011-11-14T13:50:47.786+04:002011-11-14T13:50:47.786+04:00Вот и разбор поспел.Вот и <a href="http://my-tribune.blogspot.com/2011/11/blog-post_14.html" rel="nofollow">разбор</a> поспел.Илья Весеннийhttps://www.blogger.com/profile/12075968879288943233noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-84720976345940237042011-11-10T19:57:25.919+04:002011-11-10T19:57:25.919+04:00Voland, хорошо, мы разберём их в одной из следующи...<b>Voland</b>, хорошо, мы разберём их в одной из следующих заметок.Илья Весеннийhttps://www.blogger.com/profile/12075968879288943233noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-26189124111593117072011-11-10T18:21:29.615+04:002011-11-10T18:21:29.615+04:00Илья, а вы будете разбирать представленные задачи?...Илья, а вы будете разбирать представленные задачи? А то я, честно говоря, никак не могу понять как управиться с двумя перчатками.Volandhttps://www.blogger.com/profile/10198475558902401305noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-78374443696300791632011-10-28T16:20:25.630+04:002011-10-28T16:20:25.630+04:00Grigory Javadyan, да, это известная формулировка, ...<b>Grigory Javadyan</b>, да, это известная формулировка, её выше уже пару раз вспоминали. Я стараюсь предлагать задачки в терминах "не из начальной школы" (даже пятиклассники уже не хихикают, услышав слово "презерватив" :).Илья Весеннийhttps://www.blogger.com/profile/12075968879288943233noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-42839976863848329792011-10-28T14:48:52.754+04:002011-10-28T14:48:52.754+04:00Извиняюсь, я имел в виду не вторую, а третью, о ма...Извиняюсь, я имел в виду не вторую, а третью, о малярах.Grigory Javadyanhttp://onlinehut.orgnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-255621801091010442011-10-28T14:47:55.013+04:002011-10-28T14:47:55.013+04:00Занятно, я слышал вторую задачу в варианте про дву...Занятно, я слышал вторую задачу в варианте про двух мужчин, двух женщин и, извините за выражение, венерические заболевания и презервативы :) В любом случае, ответ 2.Grigory Javadyanhttp://onlinehut.orgnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-66056238398816239882011-10-23T16:27:35.812+04:002011-10-23T16:27:35.812+04:00Уважаемый аноним, спасибо за интересный вопрос. Он...Уважаемый аноним, спасибо за интересный вопрос. Он немножко не по адресу, потому что я не специализируюсь на этих методах. Поэтому я могу только поделиться своей версией ответа на вопрос.<br /><br />> <i>Какое бы число элементов упорядоченного массива я ни пытался взять для эксперимента, у меня всегда получалось...</i><br />В этом и дело. Вы проверяете эти два метода на одной задаче, а заточены они под различные постановки.<br /><br />Если задача звучит так: «Есть монотонная функция f(x), определённая на интервале [a, b], найти x из [a, b], для которого f(x) отличается от заданного y не больше чем на d», то метод деления пополам, конечно, должен показывать максимальную эффективность, потому что исследуемый интервал на каждой итерации сокращается в два раза (если мы ничего не знаем о функции f(x), то более эффективного решения не может быть).<br /><br />Если же наша задача состоит в поиске такого x из [a, b], для которого f(x) является минимальным значением этой функции на этом интервале, то начинаются интересные эффекты:<br /><br />1. В методе деления пополам для принятия решения о сужении интервала мы опираемся на значения в трёх точках (двух крайних и одной средней). А метод золотого сечения опирается на значения в четырёх точках, что должно увеличивать вероятность выбора правильного интервала (содержащего глобальный минимум).<br /><br />2. В методе деления пополам отрезок всякий раз сокращается в два раза, а в методе золотого сечения ~1.7, что опять же уменьшает вероятность упустить интервал, содержащий искомое значение.<br /><br />Вообще тут всё зависит от того, что мы знаем о функции f(x). Но даже если достоверно известно, что на данном интервале функция имеет только один локальный минимум (даже если известно, что она сначала строго убывает, а потом строго возрастает), то легко придумать примеры, когда значения в одной центрально точке не хватит для выбора правильного интервала.<br /><br />Более того, для таких функций доказано, что достаточно иметь значения в двух точках внутри интервала (см. <a href="http://en.wikipedia.org/wiki/Ternary_search" rel="nofollow">ternary search</a>). Таким образом, методы Фибоначчи и золотого сечения можно считать, например, разновидностью тернарного поиска. Отличие в том, что эти методы оптимизированы по количеству вычислений f(x) (классический тернарный поиск предполагает в два раза больше вычислений, чем эти методы).<br /><br />Как я понимаю, в статье 1966 года Avriel, Mordecai; Wilde, Douglass J. , "Optimality proof for the symmetric Fibonacci search technique" как раз поясняется, в каком смысле эти методы являются оптимальными. Если я правильно понял, речь об "удельном сокращении интервала" (т.е. о доле сокращения на каждое обращение к функции).Илья Весеннийhttps://www.blogger.com/profile/12075968879288943233noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-14349447418690764452011-10-20T07:12:33.334+04:002011-10-20T07:12:33.334+04:00Илья, вторая задача мне понравилась - интересная и...Илья, вторая задача мне понравилась - интересная и жизненная и комуто может быть полезная на практике, остальные imho высосаны, не из мира сего, поэтому и не даются легко некоторым здесь присутствующим. <br /><br />Вот Вы лучше Илья объясните на пальцах чем разновидность дихотомии, основанная на числах Фибоначчи, лучше половинного деления. А то у меня из закоулков памяти неожиданно всплыла фраза лектора, что якобы лучше, а вот чем и при каких обстоятельствах не могу понять. Какое бы число элементов упорядоченного массива я ни пытался взять для эксперимента, у меня всегда получалось, что поиск подходящего элемента методом половинного деления в худшем случае был быстрее либо таким же по скорости по сравнению с методом деления в пропорции Фибоначчи в худшем случае. Или речь должна идти о статистическом преимуществе? Помогите пожалуйста.<br /><br />Раз уж тут затронута тема дихотомии.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-80122603771816599152011-10-18T11:57:32.849+04:002011-10-18T11:57:32.849+04:00Ой, я в предыдущем комментарии везде перепутал 3а ...Ой, я в предыдущем комментарии везде перепутал 3а и 3б.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-53699328786870630672011-10-18T11:55:36.988+04:002011-10-18T11:55:36.988+04:00«
- левые и правые перчатки не отличаются друг от ...«<br />- левые и правые перчатки не отличаются друг от друга,<br />- поэтому у маляров они не парами, а по одной.<br />»<br /><br />Тогда задача точно не отличается от задачи про два презерватива (я почему-то в прошлом комментарии почему-то написал три вместо двух).<br /><br />Если же левизна всё-таки есть, то ответ в 3а будет отличаться — три перчатки вместо двух (правда, строго доказать пока не вижу как), а в 3б ответ такой же — две. Здесь под левизной подразумевается такая особенность, что у каждой перчатки есть две стороны — левая и правая, но если перчатку вывернули, то надеть на ту же руку уже нельзя.<br /><br />Хм, сейчас заметил, что фраза «левые и правые перчатки не отличаются друг от друга» оставляет некоторую неопределенность. Если есть левизна в том виде, как я определил, то перчатки изначально все одинаковы в том смысле, что путем выворачивания можно их все привести к каноническому виду — чтобы надевались на правую руку. Что оставляет два варианта толкования этой фразы, приводящих к разным ответам для 3а.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-53179486475947676562011-10-18T10:16:20.123+04:002011-10-18T10:16:20.123+04:00Допустим пачкается, тогда всё равно 3а - 2 перчатк...Допустим пачкается, тогда всё равно 3а - 2 перчатки. Правда с одним условием. 3б - 3 перчатки.Олегnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-90615845408194348232011-10-18T10:08:57.519+04:002011-10-18T10:08:57.519+04:001. Совсем недавно читал блог с конца.
2. Решил быс...1. Совсем недавно читал блог с конца.<br />2. Решил быстро. Ответ 3 минуты. <br />3. Задачу не видел. Честно не понял до конца условия задачи. Получается перчатка изнутри не пачкается? Тогда: 3а - 2 перчатки, 3б - 1 перчатка.Олегnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-20850704893953304052011-10-17T16:27:22.252+04:002011-10-17T16:27:22.252+04:00Дмитрий,
я понимаю условие третьей задачи так:
- л...<b>Дмитрий</b>,<br />я понимаю условие третьей задачи так:<br />- левые и правые перчатки не отличаются друг от друга,<br />- поэтому у маляров они не парами, а по одной.<br /><br />Спасибо за тёплые слова!<br />Досадно, что авторизация иногда неправильно работает. Здорово, что Вы смогли пробиться через это препятствие.Илья Весеннийhttps://www.blogger.com/profile/12075968879288943233noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-35321591920120223792011-10-17T16:09:57.978+04:002011-10-17T16:09:57.978+04:001. Первый раз. Ответил 1, но решил, что сильно про...1. Первый раз. Ответил 1, но решил, что сильно просто, начал рыть условие и искать, где ошибся (так и не понял, для чего в условии указана очень высокая прочность шариков?). Прошел по ссылке и понял, что в том месте, где я искал подвох скрупулезнее всего, его не оказалось, а связан он с неверным чтением условия и поиском алгоритма оптимального по времени, а не по экономии шариков. Действительно, здесь "программистский" подход может завести не в ту степь =)<br />2. Первый раз, ответ 3 мин.<br />3. Смутно помнил подобную задачу в формулировке с презервативом, но т.к. забыл и условие, и решение, пришлось решать повторно. В условии есть некоторая неоднозначность: у маляров перчатки парами или нет? Если парами, то можно ли правой рукой пожимать левую руку? Если не парами, то можно ли совершать рукопожатие левыми руками? Поскольку в условии эти моменты не оговорены, я решил, что подразумевается: перчатки не обязательно парные и можно совершать рукопожатие левыми руками. Тогда ответы:<br />3а. 2 перчатки<br />3б. 2 перчатки<br />3б после 3а решается быстро, т.к. принцип обмена перчатками достаточно похож.<br /><br />Я сравнительно недавно познакомился с вашим блогом и сейчас активно читаю его прошлые статьи. Спасибо вам большое за такой замечательный интернет-дневник и такое вежливое отношение к посетителям, за внимательное чтение комментариев, помощь и постоянное желание слегка подтолкнуть к решению, не раскрывая его. Все это – большая редкость в современном рунете! Постараюсь в ближайшее время прокомментировать потрясающую задачу про туземцев острова беззеркалья, которая не решалась и не выходила у меня из головы два полных вечера подряд.<br /><br />Почему-то не могу подписаться ни через LiveJournal, ни через Google: "Input error: Cookie value is null for FormRestoration"Дмитрийhttp://oxigeny.livejournal.com/noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-84409535760814885942011-10-17T13:54:27.839+04:002011-10-17T13:54:27.839+04:00fibon-ache,
> можно снимать перчатки и передава...<b>fibon-ache</b>,<br />> <i>можно снимать перчатки и передавать другому?</i><br />Правилами не запрещено.<br /><br /><b>Дима</b>, спасибо за детальное описание проблем этого аэропорта.<br /><br /><b>Voland</b><br />> <i>Тут вот говорят что можно переворачивать перчатку, но разве перчатка не будет уже испачкана краской внутри?</i><br />Будет, конечно. Но иногда это не мешает.<br /><br /><b>la_sotte</b>,<br />детали условия задачи и сама задача были давно разобраны (ссылка в заметке есть).<br />Что касается ответов на вторую и третью задачки, то складывается впечатление, что Вы стараетесь найти не оптимальное, а хоть какое-то решение.Илья Весеннийhttps://www.blogger.com/profile/12075968879288943233noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-76903783718167791482011-10-17T13:03:01.794+04:002011-10-17T13:03:01.794+04:001. не понимаю условие задачи :(
2. 4 минуты. Народ...1. не понимаю условие задачи :(<br />2. 4 минуты. Народ, а почему три все пишут, объясните плиз!<br />3а. 4<br />3б. 4m077hahttps://www.blogger.com/profile/17867310392307911323noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-25453920180296482822011-10-17T12:10:16.947+04:002011-10-17T12:10:16.947+04:001. Такой вариант первый раз слышу, ответ 1.
Более ...1. Такой вариант первый раз слышу, ответ 1.<br />Более сложный вариант, на мой взгляд:<br />Есть всего два шарика и сто ступенек. За какое минимальное количество попыток можно узнать с какой высоты шарики разбиваются. Или лучше сказать какая оптимальная стратегия для получения ответа.<br />2. Не видел, ответ 3.<br />3а. Не видел, ответ 4.<br />3б. Не видел, ответ 3.<br />Тут вот говорят что можно переворачивать перчатку, но разве перчатка не будет уже испачкана краской внутри?Volandhttps://www.blogger.com/profile/10198475558902401305noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-81901683930172181792011-10-15T15:51:07.236+04:002011-10-15T15:51:07.236+04:00Несколько недель назад я тоже был проездом в аэроп...Несколько недель назад я тоже был проездом в аэропорту Пулково-1, и хотел бы поделиться некоторыми впечатлениями.<br /><br />1. Трансфер Пулково-2 -> Пулково-1<br /><br />Я прилетел в терминал Пулково-2, и мне надо было попасть на внутренний авиарейс, в терминал Пулково-1. Между этими двумя терминалами достаточно большое расстояние, пешком идти минут 40 (и самое главное, непонятно как). Вполне логично предположить, что между терминалами должен ходить автобус - "шаттл" аэропорта или хотя бы городской транспорт. На самом деле "шаттла" нет (как мне сказали, над его запуском руководство аэропорта еще только размышляет), а на городском транспорте придется ехать до метро Московская и обратно. Пассажир, у которого следующий рейс вылетает из Пулково-1, должен получить багаж и подойти к окошку "Трансфер" на первом этаже аэропорта, показать билет и объяснить ситуацию. Любезная женщина, которая сидит за этим окошком, собирает пассажиров, которым нужно попасть в другой терминал. Когда набирается достаточно большая группа, женщина выводит их на улицу и усаживает в специальный микроавтобус, который едет до Пулково-1. Мне такая организация трансфера показалась очень милой, но наверное регулярный автобус был бы более практичным решением.<br />Автоматического перевоза багажа между терминалами нет. То есть нужно получить весь багаж в Пулково-2 и сдать в Пулково-1.<br /><br />2. Вход в аэровокзал<br /><br />Для того, чтобы попасть в аэровокзал, необходимо пройти через входной пункт контроля, "просветить" сумки и пройти через металлоискатель. Поскольку на входе стоит только одна установка для проверки багажа и одна или две рамки металлоискателя, очередь двигается очень медленно. Вход, в котором я стоял в очереди, почему-то был еще и выходом. Большая часть очереди стояла на улице и в длинном тамбуре, в котором постоянно дул холодный ветер. Пассажиры спешили, ругались и обещали жаловаться руководству. Сотрудники аэропорта тоже ругались и говорили, что их руководство уже давно не слушает, поэтому жалуйтесь на здоровье. К слову, в предыдущий раз я был в этом терминале три года назад, и основное воспоминание о нем - холодный вход с очередью.<br />На мой взгляд, гораздо более удобный вход можно сделать за счет небольшого дополнительного помещения снаружи, либо за счет переноса пункта контроля глубже внутрь аэровокзала.<br /><br />3. Организация пространства<br /><br />Внутри здания очень тесно, всюду очереди, переходы между этажами очень узкие и извилистые. Указатели есть, но мне приходилось задумываться о том, как попасть в то или иное место. Если я правильно понял, для того, чтобы пройти от входа к выходу, нужно один раз подняться, и один раз спуститься по лестнице.<br /><br />4. Контроль перед залом вылета<br /><br />Очень тесное помещение с длинной, но относительно быстро двигающейся очередью. Сотрудников мало, места, где можно было бы раздеться / сложить вещи тоже очень мало.<br /><br />Вообще, на мой взгляд, конкретно эта процедура максимально адекватно устроена в европейских аэропортах. Типичная схема примерно такая: есть "лента", вдоль которой двигается очередь (примерно как в столовой). По мере приближения к сканирующему оборудованию, люди в очереди снимают верхнюю одежду и выкладывают вещи в коробки, которые стоят на ленте. Ключевой момент - с другой стороны ленты стоят сотрудники аэропорта, которые помогают пассажирам (если надо - подержат сумку, помогут сложить вещи в коробку, при необходимости перенесут сумку назад, чтобы пропустить еще раз через сканирующий аппарат).<br /><br />5. Зал вылета<br /><br />В зале на первом этаже почти в самом центре стоит курилка, рядом с которой сильно пахнет табачным дымом. В туалете старая сантехника, грязно. В женский туалет была очередь. Неужели для одного из крупнейших аэровокзалов России нормальные туалеты - нерешаемая проблема?<br /><br />Конечно большая часть неприятных моментов объясняется тем, что зданию аэровокзала около 40 лет, и со времен проектирования и постройки значительно вырос пассажиропоток и изменились требования безопасности. Но ведь все эти проблемы вполне решабельны, и стоимость решения совсем не фантастическая!Димаnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-5182798813246067452011-10-15T12:01:40.959+04:002011-10-15T12:01:40.959+04:00гм, я тут опечатался, во второй задаче ответ конеч...гм, я тут опечатался, во второй задаче ответ конечно же 3 минуты.<br />насчет третей - можно снимать перчатки и передавать другому?fibon-achehttps://www.blogger.com/profile/16810016675238501128noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-75773049147268935872011-10-15T06:05:26.118+04:002011-10-15T06:05:26.118+04:00Азат, конечно перчатки выворачивать нужно. Иначе с...Азат, конечно перчатки выворачивать нужно. Иначе совсем неинтересно :-)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-55462598033951754762011-10-14T21:21:43.655+04:002011-10-14T21:21:43.655+04:001) Помню задачу, тогда не решил, теперь заморочилс...1) Помню задачу, тогда не решил, теперь заморочился - оказалось неправильно.<br />2) Знаю, где-то в детстве далеком точно решал. ответ: 3.<br />3а) Не знал, решил, но ответ 3. Что я делаю не так?<br />3б) Тоже не знал, тоже три. Странно. Опять же: можно выворачивать перчатки?Это может быть важно.Азатhttps://www.blogger.com/profile/06470535313501711469noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-24631932378072611042011-10-14T20:18:42.480+04:002011-10-14T20:18:42.480+04:001. первый раз слышу, ответ 1
2. давно знаю, ответ ...1. первый раз слышу, ответ 1<br />2. давно знаю, ответ 3<br />3а. давно знаю (в варианте про презервативы), ответ 2<br />3б. впервые слышу, ответ 2Vitaliihttps://www.blogger.com/profile/12720364210713708106noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-30097279539134173662011-10-14T16:56:41.268+04:002011-10-14T16:56:41.268+04:001) Давно знаю, 1
2) Помню, 3
3а) Не видел, 2
3б) н...1) Давно знаю, 1<br />2) Помню, 3<br />3а) Не видел, 2<br />3б) не видел, 2Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-25078903306039356962011-10-14T15:55:17.127+04:002011-10-14T15:55:17.127+04:001. Не видел, ответ 1
2. Давно знаю, ответ 3
3а. Н...1. Не видел, ответ 1 <br />2. Давно знаю, ответ 3<br />3а. Не видел, ответ 2<br />3б. Не видел, ответ 2Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-60244507786818990282011-10-14T15:12:06.016+04:002011-10-14T15:12:06.016+04:001. давно знаю. ответ - 1
2. помню. ответ - 3
3а. п...1. давно знаю. ответ - 1<br />2. помню. ответ - 3<br />3а. помню про презервативы. ответ - 2<br />3б. не видел. ответ - 2.<br />P.S. Через ЖЖ не авторизовало, аккаунту gmail Сказало account do not have access. Фигня какая-тоAnonymousnoreply@blogger.com