Comments 59
Простите, мне не хотелось бы вас расстраивать, но по-моему эту задачку все со школы еще знают.
Возможно и так, но у меня есть подозрение, что решалась похожая задача, в которой известно, больший или меньший вес у аномального шара.
В стандартной задаче минимальное количество взвешиваний для определения фальшивого шара — 3, а в данной вариации — 4
Задача не сильно усложнилась.
Задача не сильно усложнилась.
В данной вариации минимальное количество взвешиваний = 3
Поясните алгоритм для людей не сильно разбирающихся в java (меня)
Я не хотел присваивать чужой труд, потому вставил ссылку на мат. обоснование.
Алгоритм интересен тем, что выбор шаров для очередного взвешивания зависит от результата предыдущего.
Разьбьем шары на 3 группы и сравним первые 2 -> (ЛЛЛЛ? ПППП)
Если шары равны, то ответ в 3 группе, за 2 шага мы наверняка сможем найти ответ.
Сложности возникают, если шары не равны, так как мы все еще не знаем, тяжелее искомый шар, или легче.
Шаги лучше рассмотреть на этой картинке (она есть по ссылке)
КАРТИНКА
Алгоритм интересен тем, что выбор шаров для очередного взвешивания зависит от результата предыдущего.
Разьбьем шары на 3 группы и сравним первые 2 -> (ЛЛЛЛ? ПППП)
Если шары равны, то ответ в 3 группе, за 2 шага мы наверняка сможем найти ответ.
Сложности возникают, если шары не равны, так как мы все еще не знаем, тяжелее искомый шар, или легче.
Шаги лучше рассмотреть на этой картинке (она есть по ссылке)
КАРТИНКА
Каюсь, недопонял сразу.
Спасибо.
Спасибо.
А если при первом взвешивании группы не равны? Как мы узнаем в какой группе фальшивый, если неизвестно, больше фальшивый весит или меньше?
Как видно на картинке, там всё много интереснее.
Нужно запомнить, при первом взвешивании был результат < или >
Затем нужно хитрым образом сравнить шары, перемешав их.
В результате сравнение будет например ЛЛП? ЛЛП.
Если взвешивание показало, что шары слева и справа равны, искомый шар в оставшихся ПП, найти его будет просто.
Если нет, появляются сложности и нужно учитывать сравнения больше/меньше.
К примеру ЛЛЛЛ < ПППП
затем ЛЛП < ЛЛП
сравниваем левые Л? Л
если они равны, искомый шар — правый П.
если Л < Л — искомый шар правый Л.
если Л > Л — искомый шар левый Л.
Похожим образом действуем для нахождения шара во всех других ситуациях.
Нужно запомнить, при первом взвешивании был результат < или >
Затем нужно хитрым образом сравнить шары, перемешав их.
В результате сравнение будет например ЛЛП? ЛЛП.
Если взвешивание показало, что шары слева и справа равны, искомый шар в оставшихся ПП, найти его будет просто.
Если нет, появляются сложности и нужно учитывать сравнения больше/меньше.
К примеру ЛЛЛЛ < ПППП
затем ЛЛП < ЛЛП
сравниваем левые Л? Л
если они равны, искомый шар — правый П.
если Л < Л — искомый шар правый Л.
если Л > Л — искомый шар левый Л.
Похожим образом действуем для нахождения шара во всех других ситуациях.
Оба варианта очень известны. Понятно, что второй — он «со звездочкой», встречается чуть реже. Но все равно — дается даже школьникам
Очень сомневаюсь, что школьники за урок смогут за 3 взвешивания решить данную задачу.
Это кружковская математика. Кажется, класс 9
Буду благодарен за пруфы
www.problems.ru/view_problem_details_new.php?id=60922
Она даже есть в (широко известном в узких кругах) задачнике Спивака: math.ru/lib/files/pdf/mmmf/posev.pdf, стр. 55, №305
Она даже есть в (широко известном в узких кругах) задачнике Спивака: math.ru/lib/files/pdf/mmmf/posev.pdf, стр. 55, №305
АФАИК в школьной программе явно указано в какую сторону отличается вес монеты, нет?
У меня в комментарии всего шесть слов, но Вы упустили самое главное из них: «кружковская» =)
Я тоже упустил это слово, и не понимал, зачем давать на уроке такую задачу, ведь образовательного смысла она мало несет в себе (3 человека решают из класса, а остальные 20 непонимают о чем речь и скучают).
Спасибо за пруф.
Спасибо за пруф.
Образовательного смысла в задаче более чем достаточно. Причем как в построении оценки на число взвашиваний, так и в конкретной реализации алгоритма.
Например, весьма интересно построить зависимость максимального числа монет от числа взвешиваний.
Например, весьма интересно построить зависимость максимального числа монет от числа взвешиваний.
Есть похожая игра только с монетами
www.mathplayground.com/coinweighing.html
www.mathplayground.com/coinweighing.html
Какая хорошая задача! Начал писать возмущённый пост «что за бред, решается за минуту» и завис на последнем взвешивании. Подумал. Начал писать «что за бред, три взвешивания невозможны» и завис. Вишу до сих пор. Думаю.
Боянище. Автор, юзай поиск.
Раз = habrahabr.ru/post/230881/
Два = habrahabr.ru/post/243461/
Раз = habrahabr.ru/post/230881/
Два = habrahabr.ru/post/243461/
Читайте свои же результаты поиска.
1 пункт содержит лишь перечень задач, 2 пункт рассматривает другой алгоритм.
Таким же образом можно было написать «Автор, в твоем посте есть слова! Боянище».
В данном же посте рассматривается другой алгоритм решения задачи из 12 шаров, его математическое обоснование, а также решение задачи на языке программирования.
1 пункт содержит лишь перечень задач, 2 пункт рассматривает другой алгоритм.
Таким же образом можно было написать «Автор, в твоем посте есть слова! Боянище».
В данном же посте рассматривается другой алгоритм решения задачи из 12 шаров, его математическое обоснование, а также решение задачи на языке программирования.
По моему субъективному мнению весь класс подобных задач на взвешивание редуцируется к случаю одного взвешивания и трёх шаров. Каждое отношение неравенства позволяет выделить лишний элемент из трёх, а не из двух групп. Другие случаи тривиальны.
Это как с дихотомией, если не знаешь ключевого момента — долго думаешь над такой задачей. Если знаешь — решаешь на автомате.
Это как с дихотомией, если не знаешь ключевого момента — долго думаешь над такой задачей. Если знаешь — решаешь на автомате.
Такое решение о взвешивании среди 3 шаров очевидно, когда знаешь, легче или тяжелее аномальный шар. Если вес аномального шара неизвестен, решение становится сложным при увеличивании общего количества шаров. Т.е. даже зная алгоритм решения, мне было бы весьма трудно найти аномальный шар за минимальное количество взвешиваний (скажем, для 36 шаров). Даже в данной задаче конечное взвешивание происходит между 2 шарами с учетом предыдущих двух взвешиваний и выводом о третьем шаре, основанном на этих результатах.
То есть, проблема задачи не в алгоритме, который понять просто, а в процессе применения алгоритма. То есть в том, что в наш век обычно перекладывается на плечи машины, она ведь не ошибается, не путает шары, и вапще ей не надо всё записывать на бумажке. Я это о том, что сейчас важно знать принцип и основу алгоритма, а не иметь настойчивость и всё верно записывать/запоминать. Я и вовсе бы не влез в эту тему, если бы не остался осадок после школы в стиле «Ты прыгаешь через шаги решения! Ты невнимателен! Ты цифры перепутал! Записывай всё тщательнее!».
Ну тут и сам алгоритм не так уж тривиален. Если вам кажется, что всё совсем просто, то опишите алгоритм для 4 взвешиваний и, скажем, 30 шаров.
Понимание алгоритмов должно стоять на первом месте — тогда и применить его труда не составит. Даже в рамках программирования есть нечто подобное и было описано пользователем rboots в статье Не учите фреймворки, учите архитектуру
Основная причина, почему при решении задачи я также пользовался ПК в том, чтобы проверить работоспособность алгоритма для всех вариантов расположения аномального шара (12 для случаев с легким шаром, и 12 для случая с тяжелым шаром).
Основная причина, почему при решении задачи я также пользовался ПК в том, чтобы проверить работоспособность алгоритма для всех вариантов расположения аномального шара (12 для случаев с легким шаром, и 12 для случая с тяжелым шаром).
Решается для любого числа шаров по индукции. Доказать надо только для тривиальных случаев чтобы на их основе строить индукцию.
По сути взвешивание дает нам три варианта ответа (<, ==, >), всего возможных исходов при N взвешиваниях — 3^N. Возможное количество входных данных = число шаров*2 (т.е. или один из шаров легче или один из шаров тяжелее). Тогда более полная формулировка задачи (найти шар и сказать тяжелее он или легче) — не может быть решена если 3^N < число шаров*2. В нашей задаче единственный случай когда мы можем сказать что шар отличается по весу — но не знаем в какую сторону — если мы его никогда не взвешивали, анализируя дерево решений можно прийти к выводу что это возможно только на одном пути — когда все взвешивания дали результат "==", т.е. мы можем разделить 3^N+1 набора входных данных. Дальше основная сложность в том что K*2 при разбиении на 3 части не всегда даст множители, которые являются степенями тройки. По базису индукции мы можем решить задачу для 2 неизвестных шаров за 1 взвешивание (2*2 = 3^1+1), или для 4 шаров для которых известны ожидания (легче-тяжелее), при наличии одного референс-шара и гарантированно верным весом (такой шар очевидно будет, при правильной стратегии, т.к. чтобы получить ожидания нужно провести предварительно взвешивание) (3 < 3^1+1). Далее мы просто добавляем шары и ищем взвешивание наиболее равномерно разделяющее возможности по трем исходам основываясь на том что мы можем решить исходя из базиса.
Для 36 шаров:
Количество вариантов входных данных 36*2=72, 4 взвешивания покрывает 82 исхода, 3 взвешивания покрывают только 28, поэтому цель — 4 взвешивания.
Для начала определим сколько шаров взвешивать, для этого посмотрим сколько исходов покрывают 3 осташихся взвешивания (28), этого хватит чтобы разделить 14 шаров при наличии референса (а он будет, т.к. последующие взвешивания не первые).
Для 14 шаров (если первый результат "==") — взвешиваем 4 на одной чаше, 3 + референс на другой, в случае если они равны по весу, надо разделить 5 шаров за два взвешивания, взвешиваем 2 vs 1+референс, сводим задачу к базису. Если не равны — имеем 5 тяжелых и 4 легких (или наоборот) — 9 вариантов и 2 взвешивания. Взвешиваем 4предположительно тяжелых vs 2 предположительно легких как ТТЛ vs ТТЛ. (ТЛЛ остаются невзешены), все три исхода сводят задачу к базису. Таким образом первое взвешивание разделяет исходы как 22+22+28.
Если вначале получили < или > — то имеем 11 предположительно тяжелых, 11 предположительно легких, убираем 5Т + 4Л (чтобы при равенстве свести задачу к уже решенной). Оставшиеся 6Т+7Л вешаем как ТТТЛЛЛ vs ТТТЛЛЛЛ, при равенстве задача сводится к решенной, при неравенстве имеем или ТТТЛЛЛЛ или ТТТЛЛЛ и 2 взвешивания в запасе. Для ТТТЛЛЛ просто вешаем Т vs Т и Л vs Л, для ТТТЛЛЛЛ вешаем ТТЛ vs ТЛ+Референс, на выходе имеем или ТТЛ или ТЛ или ЛЛЛ (если равны), все задачи базисные.
Аналогичное рассуждение для любого числа шаров, с тем исключением что возможно когда-нибудь можно наткнуться что варианты не делятся кратно, тогда возможно придется добавить взвешивание.
По сути взвешивание дает нам три варианта ответа (<, ==, >), всего возможных исходов при N взвешиваниях — 3^N. Возможное количество входных данных = число шаров*2 (т.е. или один из шаров легче или один из шаров тяжелее). Тогда более полная формулировка задачи (найти шар и сказать тяжелее он или легче) — не может быть решена если 3^N < число шаров*2. В нашей задаче единственный случай когда мы можем сказать что шар отличается по весу — но не знаем в какую сторону — если мы его никогда не взвешивали, анализируя дерево решений можно прийти к выводу что это возможно только на одном пути — когда все взвешивания дали результат "==", т.е. мы можем разделить 3^N+1 набора входных данных. Дальше основная сложность в том что K*2 при разбиении на 3 части не всегда даст множители, которые являются степенями тройки. По базису индукции мы можем решить задачу для 2 неизвестных шаров за 1 взвешивание (2*2 = 3^1+1), или для 4 шаров для которых известны ожидания (легче-тяжелее), при наличии одного референс-шара и гарантированно верным весом (такой шар очевидно будет, при правильной стратегии, т.к. чтобы получить ожидания нужно провести предварительно взвешивание) (3 < 3^1+1). Далее мы просто добавляем шары и ищем взвешивание наиболее равномерно разделяющее возможности по трем исходам основываясь на том что мы можем решить исходя из базиса.
Для 36 шаров:
Количество вариантов входных данных 36*2=72, 4 взвешивания покрывает 82 исхода, 3 взвешивания покрывают только 28, поэтому цель — 4 взвешивания.
Для начала определим сколько шаров взвешивать, для этого посмотрим сколько исходов покрывают 3 осташихся взвешивания (28), этого хватит чтобы разделить 14 шаров при наличии референса (а он будет, т.к. последующие взвешивания не первые).
Для 14 шаров (если первый результат "==") — взвешиваем 4 на одной чаше, 3 + референс на другой, в случае если они равны по весу, надо разделить 5 шаров за два взвешивания, взвешиваем 2 vs 1+референс, сводим задачу к базису. Если не равны — имеем 5 тяжелых и 4 легких (или наоборот) — 9 вариантов и 2 взвешивания. Взвешиваем 4предположительно тяжелых vs 2 предположительно легких как ТТЛ vs ТТЛ. (ТЛЛ остаются невзешены), все три исхода сводят задачу к базису. Таким образом первое взвешивание разделяет исходы как 22+22+28.
Если вначале получили < или > — то имеем 11 предположительно тяжелых, 11 предположительно легких, убираем 5Т + 4Л (чтобы при равенстве свести задачу к уже решенной). Оставшиеся 6Т+7Л вешаем как ТТТЛЛЛ vs ТТТЛЛЛЛ, при равенстве задача сводится к решенной, при неравенстве имеем или ТТТЛЛЛЛ или ТТТЛЛЛ и 2 взвешивания в запасе. Для ТТТЛЛЛ просто вешаем Т vs Т и Л vs Л, для ТТТЛЛЛЛ вешаем ТТЛ vs ТЛ+Референс, на выходе имеем или ТТЛ или ТЛ или ЛЛЛ (если равны), все задачи базисные.
Аналогичное рассуждение для любого числа шаров, с тем исключением что возможно когда-нибудь можно наткнуться что варианты не делятся кратно, тогда возможно придется добавить взвешивание.
Хаб «спортивное программирование»? Are you fucking serious? Я так никогда не настрою свою ленту правильно.
Потратив время на возмущенный комментарий, но даже не попросив убрать пост из хаба «спортивное программирование» и не объяснив, почему пост к данному хабу отношения не имеет.
Если бы в начале поста я написал «Я участвовал в конкурсе среди девелоперов, и среди всех задач выделю одну, на мой взгляд, интересную» всё было бы в норме?
Если бы в начале поста я написал «Я участвовал в конкурсе среди девелоперов, и среди всех задач выделю одну, на мой взгляд, интересную» всё было бы в норме?
Насчет пустого коментария вы подметили верно, просто я давно уже понял, что бороться за чистоту хабов — бессмысленно. Остается только изредка возмущаться.
Конкурс по программированию не обязательно будет относиться к спортивному программированию. У вас — простая логическая задача, которые, как уже подметили, задают в школе и на собеседованиях. Я бы добавил такую задачу только в хаб «математика». Но полагаю, что именно эта статья и там бы вызвала возмущения, потому что, как опять же уже подметили, она давно известна.
Конкурс по программированию не обязательно будет относиться к спортивному программированию. У вас — простая логическая задача, которые, как уже подметили, задают в школе и на собеседованиях. Я бы добавил такую задачу только в хаб «математика». Но полагаю, что именно эта статья и там бы вызвала возмущения, потому что, как опять же уже подметили, она давно известна.
Я так и не изменил свое мнение насчет того, что может относиться к спортивному программированию, а что не может. Я не против убрать из хаба пост, но при нормальном обосновании.
Также одним из способов борьбы с «неправильным» контентом в хабах будет размещение туда «правильных», но у вас таких постов не имеется, потому я даже в пример не могу взять ничего, и так как в хабе вижу статьи подобные моей, смело туда размещаю ее.
И причем тут хаб математика, если тут алгоритмы и решение на java?
Также одним из способов борьбы с «неправильным» контентом в хабах будет размещение туда «правильных», но у вас таких постов не имеется, потому я даже в пример не могу взять ничего, и так как в хабе вижу статьи подобные моей, смело туда размещаю ее.
И причем тут хаб математика, если тут алгоритмы и решение на java?
на самом деле, не понятно как можно было потратить 6 часов?
может автор с сортировками совсем не знаком?
может автор с сортировками совсем не знаком?
Не очень понимаю, чем тут сортировки помогли бы.
Я решал задачу, не зная алгоритма и постоянно упирался в то, что решение приходило на 4 шагу. Чтобы решить эту задачу за 3 шага, пришлось потрудиться? неоднократно переписав алгоритм поиска аномального шара.
Если, на ваш взгляд, решение подобной задачи — пустяковое дело, решите её же, но для 39 шаров и за 4 шага. К тому же, формула ведь совсем простая, даже детская
Я решал задачу, не зная алгоритма и постоянно упирался в то, что решение приходило на 4 шагу. Чтобы решить эту задачу за 3 шага, пришлось потрудиться? неоднократно переписав алгоритм поиска аномального шара.
Если, на ваш взгляд, решение подобной задачи — пустяковое дело, решите её же, но для 39 шаров и за 4 шага. К тому же, формула ведь совсем простая, даже детская
m <= (3^n – 3)/2
Как насчет 13 шаров и трех взвешиваний? ;)
Задача не имеет решения при таком условии. от 13 до 39 включительно минимум за 4 взвешивания
Не согласен. Кажется, что решение есть.
прочтите мат. обоснование, там имеется формула, а также объясняется, почему 3 взвешивания максимум для 12 шаров.
Ваша задача:
«На столе лежат 12 совершенно одинаковых по виду шаров, но один из них — фальшивый. Он отличается от остальных шаров по весу (мы не знаем, легче он или тяжелее). В вашем распоряжении имеются чашечные весы без гирь. Нужно найти аномальный шар за минимальное количество взвешиваний (подсказка — решение можно найти за 3 взвешивания).»
Задача по ссылке, которую вы приводите, и где дается мат. обоснование:
«Представьте себе, что на стол высыпана кучка совершенно одинаковых по виду монет, но вам сказали, что одна из этих монет — фальшивая. Она отличается от остальных монет по весу, но вам не сообщили, легче она или тяжелее. В вашем распоряжении имеются чашечные весы без гирь. Как нужно действовать, чтобы выделить эту монету и выяснить её тип (то есть узнать, легче она или тяжелее) за минимальное число взвешиваний?»
Разницу видите? Для вашей задачи, как мне кажется, есть решение с 3 взвешиваниями и 13 монетами.
«На столе лежат 12 совершенно одинаковых по виду шаров, но один из них — фальшивый. Он отличается от остальных шаров по весу (мы не знаем, легче он или тяжелее). В вашем распоряжении имеются чашечные весы без гирь. Нужно найти аномальный шар за минимальное количество взвешиваний (подсказка — решение можно найти за 3 взвешивания).»
Задача по ссылке, которую вы приводите, и где дается мат. обоснование:
«Представьте себе, что на стол высыпана кучка совершенно одинаковых по виду монет, но вам сказали, что одна из этих монет — фальшивая. Она отличается от остальных монет по весу, но вам не сообщили, легче она или тяжелее. В вашем распоряжении имеются чашечные весы без гирь. Как нужно действовать, чтобы выделить эту монету и выяснить её тип (то есть узнать, легче она или тяжелее) за минимальное число взвешиваний?»
Разницу видите? Для вашей задачи, как мне кажется, есть решение с 3 взвешиваниями и 13 монетами.
Разницу не вижу. Объясните мне, пожалуйста. Только не говорите мне — «Как же! Там монеты, а тут шары!».
По ссылке с мат. обоснованием не важно, сколько будет шаров, есть формула, которая может указать на минимальное количество взвешиваний.
12 <= (3^3 — 3) / 2, тут условие верно.
13 <= (3^3 — 3) / 2, тут неверно, и чтобы было верно, нужно минимум 4 взвешивания.
Не вижу смысла в споре ради спора. Если хотите что-то обсудить без доводов с абстрактными фразами «разницу видите?» — это не ко мне. Прочтите, пожалуйста, мат. обоснование, вникните в него, а затем продолжим диалог.
По ссылке с мат. обоснованием не важно, сколько будет шаров, есть формула, которая может указать на минимальное количество взвешиваний.
m <= (3^n – 3)/2
12 <= (3^3 — 3) / 2, тут условие верно.
13 <= (3^3 — 3) / 2, тут неверно, и чтобы было верно, нужно минимум 4 взвешивания.
Не вижу смысла в споре ради спора. Если хотите что-то обсудить без доводов с абстрактными фразами «разницу видите?» — это не ко мне. Прочтите, пожалуйста, мат. обоснование, вникните в него, а затем продолжим диалог.
Я не спорю ради спора. :) Просто написал, что для вашей задачи можно найти решение (как мне кажется) с 13 шарами/монетами (как хотите) за 3 взвешивания. Вы же прикрываетесь мат. обоснованием, которое относится к другой задаче. При этом, я вполне допускаю, что вы даже не подумали о поиске возможного решения для вашей задачи с 13 шарами/монетами.
Про разницу, формулировка задачи по ссылке, для которой приводится мат. обоснование звучит следующим образом:
«Представьте себе, что на стол высыпана кучка совершенно одинаковых по виду монет, но вам сказали, что одна из этих монет — фальшивая. Она отличается от остальных монет по весу, но вам не сообщили, легче она или тяжелее. В вашем распоряжении имеются чашечные весы без гирь. Как нужно действовать, чтобы выделить эту монету и выяснить её тип (то есть узнать, легче она или тяжелее) за минимальное число взвешиваний?»
Обратите внимание на жирный текст. Его в вашей формулировке нет. Теперь, пожалуйста, подумайте над решением задачи в вашей формулировке. Есть решения для случая с 13 монетами/шарами?
Про разницу, формулировка задачи по ссылке, для которой приводится мат. обоснование звучит следующим образом:
«Представьте себе, что на стол высыпана кучка совершенно одинаковых по виду монет, но вам сказали, что одна из этих монет — фальшивая. Она отличается от остальных монет по весу, но вам не сообщили, легче она или тяжелее. В вашем распоряжении имеются чашечные весы без гирь. Как нужно действовать, чтобы выделить эту монету и выяснить её тип (то есть узнать, легче она или тяжелее) за минимальное число взвешиваний?»
Обратите внимание на жирный текст. Его в вашей формулировке нет. Теперь, пожалуйста, подумайте над решением задачи в вашей формулировке. Есть решения для случая с 13 монетами/шарами?
Написали бы сразу, о чем говорите :). К сожалению, вес шара для 12 единиц будет лишь бонусом при сложном алгоритме, т.е. когда на первом этапе 4 vs 4 показало, что какой-то из них больше/меньше. Т.е. без определения веса задача решения не имеет.
В данном КОММЕНТАРИИ я расписал, почему так и почему для 13 шаров решения нету (как минимум это правдиво для меня, так как я пытался найти универсальный алгоритм, который будет решать задачу для любого количества шаров).
В данном КОММЕНТАРИИ я расписал, почему так и почему для 13 шаров решения нету (как минимум это правдиво для меня, так как я пытался найти универсальный алгоритм, который будет решать задачу для любого количества шаров).
Надеюсь, я понял правильно и мы говорим о гарантированном решении?
Да, без необходимости определать тип аномалии решение для 13 монет есть.
Спасибо! :) Хоть кто-то внимательно посмотрел!
Алгоритм для (3^n-1)/2 монет тривиально строится из того же алгоритма Дайсона — откладываем одну монету, а к остальным применяем алгоритм. Маркер из одних единиц там не используется, а значит любая из (3^к-3)/2 монет участвует хотя бы в одном взвешивании. Следовательно, если по итогам разборок во всех взвешиваниях — равенсто, то отложенная монета — фальшивка.
К сожалению, не могу принять такое решение. Как минимум для того же самого алгоритма (а вы про него и написали). В нем вес монеты это скорее бонус, так как без признаков предыдущих взвешиваний монету не найти.
А так как других я не знаю и вы ссылаетесь на него же, рассмотрю лишь одну ветвь, которая приведет к неопределенности (т.е. решения при данном алгоритме для 13 шаров нету).
Мы начали взвешивания так, как вы описали. т.е. (4 vs 4… 4 )… и 1 в сторонке.
Допустим, мы уже на третем взвешивании и в самом левом нижнем углу на картинке КАРТИНКА
При равенстве шаров возникает неопределенность, какой из шаров искомый (под номером 6 или все же шар, который мы отложили)?
А так как других я не знаю и вы ссылаетесь на него же, рассмотрю лишь одну ветвь, которая приведет к неопределенности (т.е. решения при данном алгоритме для 13 шаров нету).
Мы начали взвешивания так, как вы описали. т.е. (4 vs 4… 4 )… и 1 в сторонке.
Допустим, мы уже на третем взвешивании и в самом левом нижнем углу на картинке КАРТИНКА
При равенстве шаров возникает неопределенность, какой из шаров искомый (под номером 6 или все же шар, который мы отложили)?
Во-первых, вы невнимательно читаете. Я явно указал алгоритм Дайсона. Он по вашей ссылке описан и к картинке отношения не имеет. Там даже явно указаны монеты, которые участвуют в каждом взвешивании:
(1,4,7,10) – (3,6,9,12), (3,6,9,10) – (2,5,8,12), (3,4,8,12) – (2,6,7,11)
Легко заметить, что каждая из 12 монет хотя бы в одном взвешивании участвует, а значит при равенстве во всех трех взвешиваниях — фальшивой будет тринадцатая монета.
Во-вторых, даже для вашей картинки все очевидно. Если хотя бы на одном из нарисованных на картинке взвешиваний было неравенство, то 13-ая монета фальшивой быть не может (ведь фальшивая монета ровно одна). А случай, когда все три взвешивания дают равенство на вашей картинке остается неиспользованным.
(1,4,7,10) – (3,6,9,12), (3,6,9,10) – (2,5,8,12), (3,4,8,12) – (2,6,7,11)
Легко заметить, что каждая из 12 монет хотя бы в одном взвешивании участвует, а значит при равенстве во всех трех взвешиваниях — фальшивой будет тринадцатая монета.
Во-вторых, даже для вашей картинки все очевидно. Если хотя бы на одном из нарисованных на картинке взвешиваний было неравенство, то 13-ая монета фальшивой быть не может (ведь фальшивая монета ровно одна). А случай, когда все три взвешивания дают равенство на вашей картинке остается неиспользованным.
// подумаю, и отвечу после взвешивания, не хочу поспешных выводов делать.
Да, действительно, я ошибался.
Дело в том, что при решении мною данной задачи я пришел к результату из картинки, но я как-то не задумывался, что другой алгоритм будет даже проще и изящнее, и за тоже количество шагов сможет найти решение для 13 шаров.
Проще говоря — я нашел статью, которая объясняет мое решение.
Надеюсь, это меня хотя бы немного оправдает.
Спасибо за конструктивный диалог.
Дело в том, что при решении мною данной задачи я пришел к результату из картинки, но я как-то не задумывался, что другой алгоритм будет даже проще и изящнее, и за тоже количество шагов сможет найти решение для 13 шаров.
Проще говоря — я нашел статью, которая объясняет мое решение.
Надеюсь, это меня хотя бы немного оправдает.
Спасибо за конструктивный диалог.
Sign up to leave a comment.
12 шаров