И оставался счастлив, как вдруг зрение начало портиться. В 2013 году я стал плохо видеть шайбу, к 2015 — футбольный мяч (я играю в футбол и хоккей 6 раз в неделю) и наконец я перестал встречать некрасивых женщин. В мозгу вырисовывался вопрос — что, опять?
Несмотря на совет местного хабра-доктора, которого мы все знаем и уважаем, я решил сделать повторную операцию по коррекции зрения.
Разумеется, я вновь выбрал ЭКСИМЕР, но не московский, а поближе нижегородский.
Мне сделали операцию в пятницу 13-ого. 350 евро за глаз. Как и 17 лет назад, я стал временно дальнозорким; дело в том что после операции ближнее зрение возвращается в обычный режим не сразу. Отеки и туманы могут исчезнуть за 2 дня, а могут и за месяц — все зависит от индивидуума, которому порезали глаза.
Что же такое дальнозоркость? Когда не можешь читать и писать и образ жизни меняется. В основном слушаешь, щупаешь и размышляешь. В голову лезет всякая чушь, в том числе математические загадки, которые достаточно сложно решить в уме.
Одна из таких головоломок неожиданно надолго застряла в голове. Это ребус про фальшивую монету. Напомню условие задачи —
Дано 12 монет и весы разновесы. Известно, что одна из монет фальшивая, то есть либо легче, либо тяжелее прочих.
Как найти фальшивую монету при помощи трех взвешиваний?
Когда-то я успешно решал эту задачу с карандашом на бумаге, но не в уме. Теперь же мне не хватало терпения перебрать в темноте сознания все варианты.
И я решил написать простое приложение под iOS, моделируя условия задачи. Программировать вслепую — это квест. Как и писать эту статью. Но я справился благодаря двум клавишам CMD и +. В данный момент времени я могу распознать текст на 27- дюймовом мониторе, если на экране вмещается не более 18-20 строк. Нечетко. С клавиатурой также непросто — пальцы помнят, но довольно часто сбиваются с привычных позиций. Сами клавиши я, вообще говоря, не вижу, но Ж от i отличаю.
Было довольно много смешных и трагикомичных моментов, Вы и сами можете догадаться; но важно, что я смог отвлечься от сумеречного состояния души.
Приложение, конечно, совершенно безумное, а пользу оно мне принесло. В том числе в интеллектуальном плане. Задачу про фальшивую монету теперь могу решать с закрытыми глазами, в разных модификациях, с продолжениями, слева направо и сверху вниз. Кстати, её до сих пор задают на собеседованиях при приеме на работу.
Несколько слов про жизненный цикл разработки. Изначально я сделал один оригинальный уровень, повторяющий условия задачи. Вдоволь нарешавшись, добавил уровни с 2-мя, 3-мя, 4-мя и так далее, 11-ти монетами. Даже дошкольники научились решать упрощенные задачи.
Я подумал, что неплохо бы добавить уровни, в которых можно решить задачу с вероятностью не менее 0.5 и добавил еще 5 уровней с 13,14,15,16,17-ю монетами. Быстро пройдя новые рубежи, я добавил бесконечное число уровней в рамках 5 бит и успокоился. Да успокойся ты!
Специально для читателей Хабра игра бесплатна и переведена на русский язык.
Фальшивовомонетчик
Все замечания по ошибкам в статье никуда не присылайте. Помните, я не могу их прочитать.
Разумеется, в статье есть математическая умышленная ошибка, кто её обнаружил — тот настоящий программист, не то что я.
Надеюсь, скоро увидимся!
Комментарии (70)
Ckpyt
17.05.2016 12:45Хм… максимальное число монет для взвешиваний = (3^n)/2, где 3 — система счислений, n — число взвешиваний, 2 — число вероятностей веса монеты. Т.е. игра на 14 монет при 3-х взвешиваний имеет логичное решение, если заранее известно, что монета тяжелее или легче.
GennPen
17.05.2016 13:10«Разумеется, в статье есть математическая умышленная ошибка,»
Ну, это очевидно же, что: «Как и 17 лет назад,» =)
CrazyNiger
17.05.2016 13:11-4Мне вот всегда было интересно, что трудного в этой задачи? Особенно для программистов, если они знакомы с теорией информации.
И кстати, за три взвешивания можно гарантировано вычислить фальшивую монету из пачки до 27 монет.
T-362
17.05.2016 13:11+1Четыре дна после повторной(!) операции — и нагружать зрение работой на компьютере… Не бережете вы себя!
По своему опыту — от фемтоласика отходил неделю стараясь не нагружать зрение вообще.
PapaBubaDiop
17.05.2016 13:28+1Спасибо за правильный комментарий; В самом деле я в основном глазею в окно, все заготовки для игры были сделаны заранее. С операцией все было сложнее, когда восстановится зрение — я опишу квест более подробно в разделе здоровье гика.
Что касается умышленной ошибки - она здесьВариант игры с двумя монетами не имеет решения ни за какое количество взвешиваний.T-362
17.05.2016 15:04+2Буду ждать статью. Особенно хорошо будет упомянуть различия ласика и фемтоласика, а еще добавить полезный совет — не смотреть на ютубе как выглядит операция — со стороны это гораздо страшнее выглядит чем «от первого лица».
Безумная идея — сделать для окулуса игру показывающую как собственно это все видится, со всеми положенным затемнениями, мутностями и спецэффектами.
Sirion
17.05.2016 13:20+420 лет назад я был сильно близорук -7 vs -14
Я дико извиняюсь, но почему «vs»? У вас глаза дрались между собой? Или это общепринятое сокращение при указании зрения на оба глаза?
Bokhan
17.05.2016 14:15-2Крайне просто решается задача. Итак, 12 монет, весом в известную(?) сторону отличается только одна, 3 раза можно взвесить.
1. 6 / 6 — отсекаем сразу половину
2. 3 / 3 — отсекаем половину от оставшегося
3. 1 / 1 — либо одна перевесит, либо фальшивую не взвесили; в любом случае, решение однозначно найдено
Исхожу из предположения, что известно, тяжелее или легче фальшивая монета в сравнении с настоящей. В условиях как-то неоднозначно сказано.
Если неизвестно, то в третьем шаге при перевешивании одной монеты надо угадать.
Shultc
17.05.2016 14:25+2то есть либо легче, либо тяжелее прочих.
Ох уж эта непонятность, да?.. Мне кажется вы просто не старались понять. Как и большинство здесь отписавшихся.
lolhunter
17.05.2016 14:31-1Если известно тяжелее или легче — задача решается минимум 2-3 способами. Если взвешивать по 4 в большинстве решений будет 2 шага. Если принять условия топикстартера "Известно, что одна из монет фальшивая, то есть либо легче, либо тяжелее прочих." — задача однозначно не решается за 3 шага во всех случаях хотя бы потому, что финальным шагом надо будет взвесить фальшивую монету относительно нормальной.
anmipo
17.05.2016 14:38+2Любая сложная задача имеет простое, легкое для понимания неправильное решение. © Артур Блох
В условиях сказано вполне однозначно: «либо легче, либо тяжелее прочих».
Вариант решенияШаг 1. Три монеты на одной чашке, три монеты на другой.
Шаг 2. Оставшиеся шесть монет снова делим на две тройки и взвешиваем их.
В результате первых двух шагов мы узнаём тройку монет, в которой есть фальшивая, а также тяжелее она или легче остальных.
Шаг 3. Из найденной тройки откладываем одну монету в сторонку, оставшиеся две сравниваем на весах. Поскольку мы уже знаем характеристики фальшивой монеты (тяжелее/легче), по весам её легко определить. Если взвешенные монеты весят одинаково, то фальшивая монета — та, что в сторонке.
Shultc
17.05.2016 14:41+2Как вы узнаете, тяжелее фальшивая монета или легче после шага 2?
Вот есть у вас результат первых двух взвешиваний:
- Две чаши весов в равновесии
- Правая чаша весов ниже левой
Как вы из этого сможете сделать вывод, должна ли фальшивая монета быть тяжелее или легче?
xrun2k
17.05.2016 14:39По этому решению если неизвестно то на всех этапах не ясно какую группу оставлять. На первом мы вполне можем отсечь рабочий вариант, где нет фальшивки. Как и на втором.
PapaBubaDiop
17.05.2016 14:55+2Вспомнил, у меня же есть видео!
Shultc
17.05.2016 14:57Ну спрячьте под спойлер! Меня тут уже пару часов ломает, чтобы решение не рассказать, и люди сами решали. А вы взяли и… Эх вы…
PapaBubaDiop
17.05.2016 15:11Прости меня, но все-таки видео само не запустится? Оно не хуже спойлера…
Shultc
17.05.2016 15:15Согласен. Но и текст «сам не читается». Смысл в том, что видя спойлер, ты сначала читаешь его название, к примеру «Осторожно, решение!». Видео же можно запустить и не зная, что там решение (вы, кстати, об этом и не написали). В результате хабравчанен может включить ваше видео лишь для того, чтобы посмотреть на то, как работает ваше приложение, а получит решение, которое возможно и не хотел пока видеть.
xrun2k
17.05.2016 15:18После второго шага вполне может получиться что две эти кучки будут равны и значит что одна из трех отложенных фальшивая. И у нас остается одно взвешивание чтобы из трех монет найти одну верную. Что, не зная легче\тяжелее, невозможно.
PapaBubaDiop
17.05.2016 15:21+1Не торопитесь, у Вас есть информация с первого взвешивания — она и пригодится в этом случае — главное, правильно положить монеты на правую и левую чашки!
xrun2k
17.05.2016 15:32Итого у нас есть три неизвестные монеты и 9 известных. Обозначим как 1-2-3, известные как Х.
Возьмем взвешивание ХХ1 и ХХ2.
1. Если оно равно, то фальшивая монета 3. Но если не равны, то опять таки незнание о весе не даёт нам понимание 1 или 2 фальшивая без дополнительного взвешивания, типа ХХХ и ХХ1.
2. Если не равно, то см. пункт 1.
Мешать монеты по типу Х12 и ХХ3, тоже смысла нет ибо имея худший вариант получим не знание 1 или 2.
Я может заблуждаюсь где-то, просьба прислать в личку решение, если оно всё-таки есть.PapaBubaDiop
17.05.2016 15:52РешениеВ третьем взвешивании положите левую монету на ПРАВУЮ чашку весов и одну из прав монет к ней рядом. На левую — две настоящие; Рассмотрите ТРИ варианта взвешивания — и сравните с ПЕРВЫМ взвешиванием. Если чашки разновесны, но знак поменялся, решение очевидно. Перекинутая монета фальшива. Если не поменялся — ответ еще очевиднее. А если равенство, совсем еще вообще очевиднее.
Denai
17.05.2016 15:52+1Это перевод, реклама ЭКСИМЕР или автор во время написания поста прозрел?
PapaBubaDiop
17.05.2016 15:55Это отзыв, среди нашего брата много очкариков, им важна любая информация. По поводу эксимера — в 1999 году у него не было конкурентов в Москве и результат — 14 лет хорошего зрения после операции я считаю успешным. А вот с нижегородским офисом все гораздо сложнее и мой совет — не пользуйтесь провинцией. Впрочем, возможно я неправ — мое мнение может измениться через месяц.
Прозрею — все расскажу: ух.Denai
17.05.2016 15:56т.е. вы мой комментарий не видите и отвечаете наугад?
PapaBubaDiop
17.05.2016 15:58Комментарий Ваш я хорошо увеличил и вижу (догадываюсь); а вот имя не вижу — другой фонт-шрифт, плохо масштабируется.
Denai
17.05.2016 16:02Хм… тогда строчка про «никуда не присылайте» неуместна. А какое у вас сейчас зрение?
PapaBubaDiop
18.05.2016 10:16Сегодня чуть лучше- я распознал Ваш ник. Мое зрение невозможно опередить количественно — полная анизотропия до схода отеков внутри глаза.
Denai
18.05.2016 13:14А это вообще не вредно напрягать зрение в такой период? Вы не пробовали скринридеры (не уверен в названии) и аналогичые приблуды для браузера, которые зачитывают нужный текст?
PapaBubaDiop
18.05.2016 13:24Доктор наложил единственное ограничение — запрет на сауну в течении 2 недель; Секс, алкоголь, наркотики, пауэрлифтинг — все можно.
gearbox
17.05.2016 18:56+2>Все замечания по ошибкам в статье никуда не присылайте.
Патентовать не будете, это же уже в public domain? Можно использовать?
Grace_Aredel
19.05.2016 09:32Как-то была я в одной фирме на собеседовании на позицию тестировщика. После стандартного вопроса про взвешивание бильярдных что ли шаров за минимальное количество заходов. А потом мне задали такую задачку: «Есть грубо говоря 100 коробок с компьютерными мышками, по 100 мышек в коробке. Но одна коробка содержит в себе бракованные мышки. за одно взвешивание надо обнаружить, какая именно.»
Я с ней самостоятельно не справилась, предложенное собеседующим решение меня не устроило, и вообще все внутри меня бунтовало против этой идиотской задачи.))
rafuck
20.05.2016 11:041) Известно ли, тяжелее или легче?
2) Известно ли, насколько?
3) По-прежнему весы Фемиды или те, которые позволяют узнать вес?
4) Если весы Фемиды, то есть ли в наличии гирьки?
Т.е. примерно понятно, как решать, но хотелось бы полную формулировку.Grace_Aredel
20.05.2016 11:141 и 2 — легче, на 1 грамм, то есть вес бракованных мышек составляет 99 грамм за каждую. Весы не Фемиды, а обычные грузовые с одной платформой.
Shultc
Возникает вопрос: а почему у весов-разновесов только три взвешивания? Что их ограничивает? Возможно, это аркадные весы-разновесы, в которые нужно бросить монету, чтобы они взвешивали? =)
Можно добавить, на весы прорезь для монет, и сделать, что одно взвешивание стоит 4 монеты (копейки?). А первое взвешивание бесплатно. Так мы оправдаем искусственное ограничение задачи, оставив те же три взвешивания!
P.S. Тоже дальнозоркий. Задачу решил в уме, но с трудом. Спасибо!
GarryC
Если Вы вспомните троичную систему счисления (троичную уравновешеную), то решается в уме без малейших затруднений.
Shultc
Я не особо представляю, как троичная симметричная (уравновешенная) система счисления поможет решить эту задачу.
Если у вас есть такое оригинальное решение, не могли бы вы его показать? Разумеется, спрятав под спойлер.
TerraV
совершенно верно. любое число монет. необходимо N взвешиваний для числа монет
TerraV
прошу прощения, не сделал предпросмотр и хабр схавал половину комментария.
Необходимо N взвешиваний для монет 3 в степени N. Т.е. для 9 монет достаточно 2, от 10 до 27 достаточно 3 и т.д.
Shultc
Мне кажется, что это подходит только в случае, если известно, тяжелее или легче фальшивая монета. Не могли бы вы показать своё решение? Разумеется, спрятав его под спойлер.
TerraV
да, я к сожалению проглядел что неизвестно тяжелее или легче монета. В случае неопределенности как писал Ckpyt ниже, максимальное число монет для однозначной идентификации взвешиванием (3^N)/2
vndtta
не правда ваша
в таком случае при N=3 получится 13 монет
покажите способ определения фальшивой монеты за 3 взвешивания для 13 монет
TerraV
Пожалуйста:
Взвешиваем 4 + 4.
Вариант А, весы равновесны: имеем 8 нормальных монет и 1 фальшивую в куче из 5. Взвешиваем 3 нормальные монеты и 3 монеты из кучи с фальшивой. А1 — весы равновесны — имеем 11 нормальных монет и 2 фальшивые. Взвешивание нормальной и любой из оставшихся позволяет определить фальшивую. А2. Весы имеют отклонение. В группе из 3 монет из фальшивой кучи 1 фальшивая и мы знаем тяжелее или легче она. Взвешиваем 1 + 1 из фальшивой кучи, определяем фальшивую однозначно.
Конец варианта А.
Вариант Б, весы показали перевес. Имеем 5 нормальных монет (те которые не взвешивали), 4 Л/Н (легкие или нормальные) и 4 Т/Н (тяжелые или нормальные). Следим за движениями рук: взвешиваем 3 Л/Н + 1 Т/Н на одной чаше весов и 3 Н + 1 Л/Н на другой чаше весов. Т.е. мы поменяли по 1 монете с разных чаш и 3 Т/Н заменили на строго Н. Имеем 3 варианта:
Б1 — чаши имеют тот же перевес что был в предыдущем взвешивании. Значит мы взвешивали 3 Л/Н + Н и 4 Н. выбрать из 3 монет одну фальшивую зная что она легче не представляет труда. взвешиваем любые 2 монеты из тройки, та что легче, та фальшивая. если вес одинаковый, то фальшивая третья.
Б2 — чаши равновесны. Т.к. при взвешивании 3 Т/Н были заменены на Н, фальшивая монета тяжелее и находится по аналогии Б1.
Б3 — чаши имеют другой перевес. значит одна из монет которую мы поменяли на чашах фальшивая. Мы не можем однозначно определить легче она или тяжелее. Взвешиваем одну из двух с любой нормальной и либо весы равны и фальшивая третья, либо весы не равны но мы знаем нормальную монету.
PapaBubaDiop
?
PapaBubaDiop
В самом деле — и 13 монет решается однозначно за 3 взвешивания.
PapaBubaDiop
Это вы погорячились. Пусть 9 монет — какое первое взвешивание?
rafuck
Можно еще проще. Пусть монеты три. Какое взвешивание?
PapaBubaDiop
Еще проще — две монеты. Тут полное фиаско.
wataru
Ограничение чисто математическое. Гораздо логичнее другая постановка той же задачи — найти фальшивую монету за наименьшее количество взвешиваний (в худшем случае). Путем не сложной логической цепочки можно додуматься, что меньше, чем за 3 взвешивания это сделать точно не получится (каждое взвешивание может дать 3 различных исхода. 2 взвешивание даст 9 различных исходов, чего не хватит для определения одной из 12 монет).