Парад решений2
раскрыть ветку (26)
Да, если по нормальному решать, даже если мы не знаем, фальшивка легче или нет.
Делим на 3 кучки по 4, взвешивам 2 кучкиА так по условию нужно найти, минимальное количество взвешиваний = 2 (а не универсальный алгоритм для худшего случая ):
1. Допустим они равны, знчит фальшивая в оставшейся кучке, рассмотрим ее, взвесим 2 монеты
1.1 Допустим они равны, значит фальшивая среди 2 оставшихся, а одна из уже взвешанных настоящая.
Взвесим 1 из оставшихся и 1 настоящую
1.1.1 они равны, значит 1 осиавшаяся - фальшивая. Конец
1.1.2 они не равны, значит мы взяли фальшивую на шаге 1.1. Конец
1.2 Они различны, значит из 2 взвешанных 1 фальшивая, а остальные настоящие. Возьмем 1 настоящую и 1, взвешанную на шаге 1
1.2.1 Они равны, значит вторая, взвешанная на шаге 1 фальшивая. Конец
1.2.2 Они различны, значит на шаге 1.2 взяли фальшивую. Конец
2. Горстки по 4 оказались различны. Тогда обозначим их так Л1Л2Л3Л4 < Т1Т2Т3Т4. Кроме того есть горстка из настоящих НННН. Взвесим Л1Л2Т1 и Л3Л4Т2.
2.1 Допустим они равны, значит фальшивка либо Т3, либо Т4, в таком случае мы точно знаем, что фальшивка тяжелее настоящей монеты (исходя из самого первого взвешивания). Просто сравним их.
2.1.1 Т3 < Т4, значит фальшивка Т4. Конец.
2.1.2 Т3 > Т4, значит фальшивка Т3. Конец.
2.2 Допустим Л1Л2Т1 < Л3Л4Т2. Тогда либо фальшивка тяжелее и ею является Т2, либо легче и ею может являтся Л1 или Л2. Взвесим Л1 и Л2.
2.2.1 Л1 = Л2, значит фальшивка Т2. Конец
2.2.2 Л1 < Л2, значит фальшивка среди легких, значит она легче, значит это Л1. Конец
2.2.3 Л1 > Л2, значит это Л2 (аналогично 2.2.2). Конец.
2.3 Допустим Л1Л2Т1 > Л3Л4Т2, тогда фальшивка может быть тяжелее - Т1, либо легче - Л3/Л4. Аналогично 2.2 (ситуации симметричны) мы можем выяснить фальшивку следующим взвешиванием. Конец
Итого за 3 взвешивания БЕЗ ДОДУМЫВАНИЯ ИНФЫ, КОТОРОЙ НЕ ДАНО ПО УСЛОВИЮ, мы нашли фальшивку
- Взвешиваем две монеты случайно
* Нам везёт и они разные
- Одну монету оставляем, берем оставшиеся из 10, взвешиваем
* Если в равновесии, то оставленная монета в стороне - фальшивка
* Если в неравновесии, то фальшивка - та монета, которую мы взвесили 2 раза.
раскрыть ветку (22)
1. по условию как раз надо найти минимальное количество взвешиваний, работающее для любых условий.
2. Если точно знать, что монета легче (тяжелее) то таких взвешиваний 3 (но не по описанной вами системе). Если неизвестно, легче или тяжелее, то 4.
2. Если точно знать, что монета легче (тяжелее) то таких взвешиваний 3 (но не по описанной вами системе). Если неизвестно, легче или тяжелее, то 4.
раскрыть ветку (10)
"Условие" можно по разному трактовать. Тут как с итальянской забастовкой. Все понимают, что в условиях невозможно прописать всё, и делают не как написано, а так как подразумевалось, но алгоритм на 2 решения -- хоть и полушуточный, но всё же формально не нарушает условие).
Во-вторых, то, что по вашей, более очевидной схеме требуется 4 взвешивания, никак не говорит, что моя схема - неверна, это просто говорит, что у вас просто менее оптимальное решение, хотя тоже верный.
раскрыть ветку (2)
Как руководитель разработчиков скажу, что для реализации я бы выбрал алгоритм с 4 взвешиваниями - максимально сбалансированный с точки зрения очевидность/производительность между тупым вариантом (простой перебор) и хитрым поиском решения (оптимальный).
Оптимальный алгоритм гораздо менее очевидный, потребует больших усилий и времени на реализацию, отладку и документирование + отложенная затрата времени на то, что каждый новый сотрудник начнет в первую очередь копаться в этой неочевидной части при поиске ошибки, даже если ошибка в другом месте, да и в целом дополнительные сложности в легаси для новых разработчиков.
Выберу оптимальный вариант только если заранее известно, что совсем критично по изначальным условиям, либо, наоборот, выявятся проблемы с производительностью после реализации (риск).
В других случаях поиск оптимального решения оставлю на откуп разработчикам на перспективу, когда появится свободное время - найти решение, реализовать, проверить, положить на полочку до возможности внедрения.
До сих пор такая стратегия всегда работала как часы)
Т.е. ТС тебе объяснил как определить за 3 взвешивания, привёл алгоритм, а ты говоришь что всё равно нужно 4 ?)
Ты случайно не с Украины с такими навыками отрицания очевидного ?)
раскрыть ветку (5)
в отличие от ТСа, который "объяснил", у меня ученая степень по математике. Хотя она тут и не требуется.
а вам не стоит грубить незнакомым людям.
раскрыть ветку (4)
Не переживайте, ничего страшного, людям свойственно ошибаться, даже людям с ученой степенью)
Если напишете где тс не прав - извинюсь и заберу свои слова обратно. Я не увидел у него ошибки, и если вдруг я что-то просмотрел, хотелось бы этот момент обнаружить для себя, т.к. я в парочке шагов от ученой степени технических наук))
раскрыть ветку (3)
ну тогда начинайте:
перед вами 12 монет, одна из них фальшивая: она отличается по весу. Легче или тяжелее - неизвестно.
Начинайте взвешивать, я буду писать вам результат. Посмотрим, за сколько вы найдете фальшивую монету.
раскрыть ветку (2)
Что так сложно. (С делением на 3 кучки)
1. Берём произвольные 6 монет. Взвешиваем 3 на 3. не равны значит фальшивая среди них, иначе в оставшихся.
2. Берём из тех в которых фальшивка 3 и взвешиваем с 3 из тех в которых нет. Итог определили 3 монеты среди которых фальшивка.
3. Дальше берём любые 2 из этих 3. Если равны то 3я фальшивка. Если нет то
4. любую из оставшихся 2 взвешиваем с не фальшивой
раскрыть ветку (10)
раскрыть ветку (9)
раскрыть ветку (8)
раскрыть ветку (7)
раскрыть ветку (6)
Три интеграции в лоб. Взвешивание группами, дальнейшее взвешивание с более лёгкой группой
1. 6-6
2. 3-3
3. 1-1 и одна монета в запасе. Если на весах одинаковые монеты, значит фальшивая в запасе.
1. 6-6
2. 3-3
3. 1-1 и одна монета в запасе. Если на весах одинаковые монеты, значит фальшивая в запасе.
раскрыть ветку (3)
Я тоже так подумал, работает только если известно легче фальшивка или тяжелей)
Если неизвестно, то есть риск пойти не по тому пути после первого шага.
Если неизвестно, то есть риск пойти не по тому пути после первого шага.
раскрыть ветку (2)
Тогда 4. После первой интеграции берём любую группу (тяжёлую или лёгкую) и взвешиваем 3-3. Если вес равный, то работаем с другой группой.
Скриншоты комментов
62.7K поста41.4K подписчиков
Правила сообщества
В сообществе можно размещать ЛЮБЫЕ скрины (комментов) с любого сайта!!
ПРИКРЕПИТЬ ССЫЛКУ НА КОМЕНТ ЕСЛИ ОН С Пикабу желательно, но не обязательно!!!
Если скрин не с пикабу, а со стороннего сайта( Твиттер,. Вк, Одноклассники и т.д.) то ссылка не обязательна.
Для сообщества подходит любой скрин, набранный на клавиатуре, даже если это не диалог (под вид Твита) Так же подходит скрин с картинкой и хотя бы одним комментарием под ним, с любого источника.