Задача:
На столе лежат 12 совершенно одинаковых по виду шаров, но один из них — фальшивый. Он отличается от остальных шаров по весу (мы не знаем, легче он или тяжелее). В вашем распоряжении имеются чашечные весы без гирь. Нужно найти аномальный шар за минимальное количество взвешиваний (подсказка — решение можно найти за 3 взвешивания).Перед тем, как решить задачу за 5 минут, внимательно прочтите условие.
У меня на всё ушло 6 часов (долго, не претендую на гениальность).
public class Balls {
private static final int A = 10;
private static final int B = 11;
private static final int LEFT_BIGGER = 1;
private static final int RIGHT_BIGGER = 2;
private static final int SAME = 4;
public static void printTest() {
System.out.println(Balls.test(true));
System.out.println(Balls.test(false));
}
public static String test(boolean weight) {
int[] array = new int[12];
StringBuilder builder = new StringBuilder();
for (int i = 0; i < array.length; ++i) {
for (int w = 0; w < array.length; ++w) {
array[w] = 5;
}
array[i] += weight ? 2 : -2;
Balls balls = new Balls(array);
builder.append("pos = 0123456789AB\n");
builder.append("array = ");
for (int w : array) {
builder.append(w);
}
builder.append('\n');
builder.append("res = ");
balls.calculateNumber();
int number = balls.getResultPosition();
for (int w = 0; w < array.length; ++w) {
builder.append(w == number ? '*' : ' ');
}
builder.append(" // number = ");
builder.append(number);
builder.append("; steps = ");
builder.append(balls.getStepsCount());
builder.append('\n');
}
return builder.toString();
}
private int[] in;
private int steps;
private int number = -1;
public Balls(int[] in) {
this.in = in;
}
public void calculateNumber() {
this.steps = 0;
int step1 = compare(sum(0, 1, 2, 3), sum(4, 5, 6, 7));
switch (step1) {
case SAME: {
int step2 = compare(sum(0, 1), sum(8, 9));
switch (step2) {
case SAME: {
number = compare(in[0], in[B]) == SAME ? A : B;
break;
}
default: {
number = compare(in[0], in[9]) == SAME ? 8 : 9;
break;
}
}
break;
}
case LEFT_BIGGER: {
int step2 = compare(sum(0, 1, 4), sum(2, 3, 5));
switch (step2) {
case LEFT_BIGGER: {
int tempState = compare(in[0], in[1]);
number = tempState == SAME ? 5 : tempState == LEFT_BIGGER ? 0 : 1;
break;
}
case RIGHT_BIGGER: {
int tempState = compare(in[2], in[3]);
number = tempState == SAME ? 4 : tempState == LEFT_BIGGER ? 2 : 3;
break;
}
case SAME: {
number = compare(in[6], in[7]) == LEFT_BIGGER ? 7 : 6;
break;
}
}
break;
}
case RIGHT_BIGGER: {
int step2 = compare(sum(0, 1, 4), sum(2, 3, 5));
switch (step2) {
case LEFT_BIGGER: {
int newState = compare(in[2], in[3]);
number = newState == SAME ? 4 : newState == LEFT_BIGGER ? 3 : 2;
break;
}
case RIGHT_BIGGER: {
int tempState = compare(in[0], in[1]);
number = tempState == SAME ? 5 : tempState == LEFT_BIGGER ? 1 : 0;
break;
}
case SAME: {
number = compare(in[6], in[7]) == LEFT_BIGGER ? 6 : 7;
break;
}
}
break;
}
}
}
public int getResultPosition() {
return number;
}
public int getStepsCount() {
return steps;
}
private int compare(int l, int r) {
++steps;
return l > r ? LEFT_BIGGER : l < r ? RIGHT_BIGGER : SAME;
}
private int sum(int... array) {
int result = 0;
for (int i : array) {
result += in[i];
}
return result;
}
}Комментарии (59)
Lopar
07.04.2015 13:47-3Какая хорошая задача! Начал писать возмущённый пост «что за бред, решается за минуту» и завис на последнем взвешивании. Подумал. Начал писать «что за бред, три взвешивания невозможны» и завис. Вишу до сих пор. Думаю.
withoutuniverse Автор
07.04.2015 13:58+1Задача мне тоже показалась очень простой на первый взгляд. Решить ее удалось только спустя 6 часов.
toxicdream
07.04.2015 14:00Боянище. Автор, юзай поиск.
Раз = habrahabr.ru/post/230881/
Два = habrahabr.ru/post/243461/withoutuniverse Автор
07.04.2015 14:44Читайте свои же результаты поиска.
1 пункт содержит лишь перечень задач, 2 пункт рассматривает другой алгоритм.
Таким же образом можно было написать «Автор, в твоем посте есть слова! Боянище».
В данном же посте рассматривается другой алгоритм решения задачи из 12 шаров, его математическое обоснование, а также решение задачи на языке программирования.
toxicdream
08.04.2015 06:58В пункте 1 — ответ есть в комментариях (нескольких)
В пункте 2 — доказательство максимального количества требуемых взвешивании.
Кроме того, пункт 2 содержит ссылку на habrahabr.ru/post/169771/ где приведен сам алгоритм.withoutuniverse Автор
08.04.2015 11:40Вы снова не прочли ничего по ссылке, и предоставили любезно её мне.
Там алгоритм приведен для ситуации, когда известно, тяжелее шар или легче.
Перечитайте снова мой предыдущий комментарий, попытайтесь понять его.
SBKarr
07.04.2015 14:53По моему субъективному мнению весь класс подобных задач на взвешивание редуцируется к случаю одного взвешивания и трёх шаров. Каждое отношение неравенства позволяет выделить лишний элемент из трёх, а не из двух групп. Другие случаи тривиальны.
Это как с дихотомией, если не знаешь ключевого момента — долго думаешь над такой задачей. Если знаешь — решаешь на автомате.withoutuniverse Автор
07.04.2015 15:04+1Такое решение о взвешивании среди 3 шаров очевидно, когда знаешь, легче или тяжелее аномальный шар. Если вес аномального шара неизвестен, решение становится сложным при увеличивании общего количества шаров. Т.е. даже зная алгоритм решения, мне было бы весьма трудно найти аномальный шар за минимальное количество взвешиваний (скажем, для 36 шаров). Даже в данной задаче конечное взвешивание происходит между 2 шарами с учетом предыдущих двух взвешиваний и выводом о третьем шаре, основанном на этих результатах.
SBKarr
07.04.2015 15:12-1То есть, проблема задачи не в алгоритме, который понять просто, а в процессе применения алгоритма. То есть в том, что в наш век обычно перекладывается на плечи машины, она ведь не ошибается, не путает шары, и вапще ей не надо всё записывать на бумажке. Я это о том, что сейчас важно знать принцип и основу алгоритма, а не иметь настойчивость и всё верно записывать/запоминать. Я и вовсе бы не влез в эту тему, если бы не остался осадок после школы в стиле «Ты прыгаешь через шаги решения! Ты невнимателен! Ты цифры перепутал! Записывай всё тщательнее!».
bay73
07.04.2015 15:22Ну тут и сам алгоритм не так уж тривиален. Если вам кажется, что всё совсем просто, то опишите алгоритм для 4 взвешиваний и, скажем, 30 шаров.
withoutuniverse Автор
07.04.2015 15:22Понимание алгоритмов должно стоять на первом месте — тогда и применить его труда не составит. Даже в рамках программирования есть нечто подобное и было описано пользователем rboots в статье Не учите фреймворки, учите архитектуру
Основная причина, почему при решении задачи я также пользовался ПК в том, чтобы проверить работоспособность алгоритма для всех вариантов расположения аномального шара (12 для случаев с легким шаром, и 12 для случая с тяжелым шаром).
VenomBlood
08.04.2015 00:03Решается для любого числа шаров по индукции. Доказать надо только для тривиальных случаев чтобы на их основе строить индукцию.
По сути взвешивание дает нам три варианта ответа (<, ==, >), всего возможных исходов при 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 ТЛ+Референс, на выходе имеем или ТТЛ или ТЛ или ЛЛЛ (если равны), все задачи базисные.
Аналогичное рассуждение для любого числа шаров, с тем исключением что возможно когда-нибудь можно наткнуться что варианты не делятся кратно, тогда возможно придется добавить взвешивание.
mbait
07.04.2015 16:01+1Хаб «спортивное программирование»? Are you fucking serious? Я так никогда не настрою свою ленту правильно.
withoutuniverse Автор
07.04.2015 16:17+1Потратив время на возмущенный комментарий, но даже не попросив убрать пост из хаба «спортивное программирование» и не объяснив, почему пост к данному хабу отношения не имеет.
Если бы в начале поста я написал «Я участвовал в конкурсе среди девелоперов, и среди всех задач выделю одну, на мой взгляд, интересную» всё было бы в норме?mbait
07.04.2015 16:33Насчет пустого коментария вы подметили верно, просто я давно уже понял, что бороться за чистоту хабов — бессмысленно. Остается только изредка возмущаться.
Конкурс по программированию не обязательно будет относиться к спортивному программированию. У вас — простая логическая задача, которые, как уже подметили, задают в школе и на собеседованиях. Я бы добавил такую задачу только в хаб «математика». Но полагаю, что именно эта статья и там бы вызвала возмущения, потому что, как опять же уже подметили, она давно известна.withoutuniverse Автор
07.04.2015 16:49+1Я так и не изменил свое мнение насчет того, что может относиться к спортивному программированию, а что не может. Я не против убрать из хаба пост, но при нормальном обосновании.
Также одним из способов борьбы с «неправильным» контентом в хабах будет размещение туда «правильных», но у вас таких постов не имеется, потому я даже в пример не могу взять ничего, и так как в хабе вижу статьи подобные моей, смело туда размещаю ее.
И причем тут хаб математика, если тут алгоритмы и решение на java?
officeMouse
07.04.2015 17:26на самом деле, не понятно как можно было потратить 6 часов?
может автор с сортировками совсем не знаком?withoutuniverse Автор
07.04.2015 17:42+2Не очень понимаю, чем тут сортировки помогли бы.
Я решал задачу, не зная алгоритма и постоянно упирался в то, что решение приходило на 4 шагу. Чтобы решить эту задачу за 3 шага, пришлось потрудиться? неоднократно переписав алгоритм поиска аномального шара.
Если, на ваш взгляд, решение подобной задачи — пустяковое дело, решите её же, но для 39 шаров и за 4 шага. К тому же, формула ведь совсем простая, даже детскаяm <= (3^n – 3)/2
Alexey86
07.04.2015 23:01Как насчет 13 шаров и трех взвешиваний? ;)
withoutuniverse Автор
08.04.2015 11:42Задача не имеет решения при таком условии. от 13 до 39 включительно минимум за 4 взвешивания
Alexey86
08.04.2015 23:05-1Не согласен. Кажется, что решение есть.
withoutuniverse Автор
09.04.2015 13:33прочтите мат. обоснование, там имеется формула, а также объясняется, почему 3 взвешивания максимум для 12 шаров.
Alexey86
09.04.2015 14:13-2Ваша задача:
«На столе лежат 12 совершенно одинаковых по виду шаров, но один из них — фальшивый. Он отличается от остальных шаров по весу (мы не знаем, легче он или тяжелее). В вашем распоряжении имеются чашечные весы без гирь. Нужно найти аномальный шар за минимальное количество взвешиваний (подсказка — решение можно найти за 3 взвешивания).»
Задача по ссылке, которую вы приводите, и где дается мат. обоснование:
«Представьте себе, что на стол высыпана кучка совершенно одинаковых по виду монет, но вам сказали, что одна из этих монет — фальшивая. Она отличается от остальных монет по весу, но вам не сообщили, легче она или тяжелее. В вашем распоряжении имеются чашечные весы без гирь. Как нужно действовать, чтобы выделить эту монету и выяснить её тип (то есть узнать, легче она или тяжелее) за минимальное число взвешиваний?»
Разницу видите? Для вашей задачи, как мне кажется, есть решение с 3 взвешиваниями и 13 монетами.withoutuniverse Автор
09.04.2015 14:33Разницу не вижу. Объясните мне, пожалуйста. Только не говорите мне — «Как же! Там монеты, а тут шары!».
По ссылке с мат. обоснованием не важно, сколько будет шаров, есть формула, которая может указать на минимальное количество взвешиваний.m <= (3^n – 3)/2
12 <= (3^3 — 3) / 2, тут условие верно.
13 <= (3^3 — 3) / 2, тут неверно, и чтобы было верно, нужно минимум 4 взвешивания.
Не вижу смысла в споре ради спора. Если хотите что-то обсудить без доводов с абстрактными фразами «разницу видите?» — это не ко мне. Прочтите, пожалуйста, мат. обоснование, вникните в него, а затем продолжим диалог.Alexey86
09.04.2015 16:46+2Я не спорю ради спора. :) Просто написал, что для вашей задачи можно найти решение (как мне кажется) с 13 шарами/монетами (как хотите) за 3 взвешивания. Вы же прикрываетесь мат. обоснованием, которое относится к другой задаче. При этом, я вполне допускаю, что вы даже не подумали о поиске возможного решения для вашей задачи с 13 шарами/монетами.
Про разницу, формулировка задачи по ссылке, для которой приводится мат. обоснование звучит следующим образом:
«Представьте себе, что на стол высыпана кучка совершенно одинаковых по виду монет, но вам сказали, что одна из этих монет — фальшивая. Она отличается от остальных монет по весу, но вам не сообщили, легче она или тяжелее. В вашем распоряжении имеются чашечные весы без гирь. Как нужно действовать, чтобы выделить эту монету и выяснить её тип (то есть узнать, легче она или тяжелее) за минимальное число взвешиваний?»
Обратите внимание на жирный текст. Его в вашей формулировке нет. Теперь, пожалуйста, подумайте над решением задачи в вашей формулировке. Есть решения для случая с 13 монетами/шарами?withoutuniverse Автор
12.04.2015 19:02Написали бы сразу, о чем говорите :). К сожалению, вес шара для 12 единиц будет лишь бонусом при сложном алгоритме, т.е. когда на первом этапе 4 vs 4 показало, что какой-то из них больше/меньше. Т.е. без определения веса задача решения не имеет.
В данном КОММЕНТАРИИ я расписал, почему так и почему для 13 шаров решения нету (как минимум это правдиво для меня, так как я пытался найти универсальный алгоритм, который будет решать задачу для любого количества шаров).
withoutuniverse Автор
12.04.2015 19:04Надеюсь, я понял правильно и мы говорим о гарантированном решении?
Alexey86
12.04.2015 20:12Да, конечно.
withoutuniverse Автор
12.04.2015 21:15Спасибо за конструктивный диалог.
Я вас в начале совсем не понял, но после разъяснений полностью согласен с решением в 3 шага и 13 шарами.
bay73
09.04.2015 16:58+1Да, без необходимости определать тип аномалии решение для 13 монет есть.
Alexey86
09.04.2015 17:02Спасибо! :) Хоть кто-то внимательно посмотрел!
bay73
09.04.2015 17:51Алгоритм для (3^n-1)/2 монет тривиально строится из того же алгоритма Дайсона — откладываем одну монету, а к остальным применяем алгоритм. Маркер из одних единиц там не используется, а значит любая из (3^к-3)/2 монет участвует хотя бы в одном взвешивании. Следовательно, если по итогам разборок во всех взвешиваниях — равенсто, то отложенная монета — фальшивка.
withoutuniverse Автор
12.04.2015 18:57К сожалению, не могу принять такое решение. Как минимум для того же самого алгоритма (а вы про него и написали). В нем вес монеты это скорее бонус, так как без признаков предыдущих взвешиваний монету не найти.
А так как других я не знаю и вы ссылаетесь на него же, рассмотрю лишь одну ветвь, которая приведет к неопределенности (т.е. решения при данном алгоритме для 13 шаров нету).
Мы начали взвешивания так, как вы описали. т.е. (4 vs 4… 4 )… и 1 в сторонке.
Допустим, мы уже на третем взвешивании и в самом левом нижнем углу на картинке КАРТИНКА
При равенстве шаров возникает неопределенность, какой из шаров искомый (под номером 6 или все же шар, который мы отложили)?
bay73
12.04.2015 19:27Во-первых, вы невнимательно читаете. Я явно указал алгоритм Дайсона. Он по вашей ссылке описан и к картинке отношения не имеет. Там даже явно указаны монеты, которые участвуют в каждом взвешивании:
(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-ая монета фальшивой быть не может (ведь фальшивая монета ровно одна). А случай, когда все три взвешивания дают равенство на вашей картинке остается неиспользованным.withoutuniverse Автор
12.04.2015 20:08// подумаю, и отвечу после взвешивания, не хочу поспешных выводов делать.
withoutuniverse Автор
12.04.2015 21:13+1Да, действительно, я ошибался.
Дело в том, что при решении мною данной задачи я пришел к результату из картинки, но я как-то не задумывался, что другой алгоритм будет даже проще и изящнее, и за тоже количество шагов сможет найти решение для 13 шаров.
Проще говоря — я нашел статью, которая объясняет мое решение.
Надеюсь, это меня хотя бы немного оправдает.
Спасибо за конструктивный диалог.
afiskon
Простите, мне не хотелось бы вас расстраивать, но по-моему эту задачку все со школы еще знают.
withoutuniverse Автор
Возможно и так, но у меня есть подозрение, что решалась похожая задача, в которой известно, больший или меньший вес у аномального шара.
DOC_tr
В стандартной задаче минимальное количество взвешиваний для определения фальшивого шара — 3, а в данной вариации — 4
Задача не сильно усложнилась.
withoutuniverse Автор
В данной вариации минимальное количество взвешиваний = 3
DOC_tr
Поясните алгоритм для людей не сильно разбирающихся в java (меня)
withoutuniverse Автор
Я не хотел присваивать чужой труд, потому вставил ссылку на мат. обоснование.
Алгоритм интересен тем, что выбор шаров для очередного взвешивания зависит от результата предыдущего.
Разьбьем шары на 3 группы и сравним первые 2 -> (ЛЛЛЛ? ПППП)
Если шары равны, то ответ в 3 группе, за 2 шага мы наверняка сможем найти ответ.
Сложности возникают, если шары не равны, так как мы все еще не знаем, тяжелее искомый шар, или легче.
Шаги лучше рассмотреть на этой картинке (она есть по ссылке)
КАРТИНКА
DOC_tr
Каюсь, недопонял сразу.
Спасибо.
kriptomen
А если при первом взвешивании группы не равны? Как мы узнаем в какой группе фальшивый, если неизвестно, больше фальшивый весит или меньше?
withoutuniverse Автор
Как видно на картинке, там всё много интереснее.
Нужно запомнить, при первом взвешивании был результат < или >
Затем нужно хитрым образом сравнить шары, перемешав их.
В результате сравнение будет например ЛЛП? ЛЛП.
Если взвешивание показало, что шары слева и справа равны, искомый шар в оставшихся ПП, найти его будет просто.
Если нет, появляются сложности и нужно учитывать сравнения больше/меньше.
К примеру ЛЛЛЛ < ПППП
затем ЛЛП < ЛЛП
сравниваем левые Л? Л
если они равны, искомый шар — правый П.
если Л < Л — искомый шар правый Л.
если Л > Л — искомый шар левый Л.
Похожим образом действуем для нахождения шара во всех других ситуациях.
kriptomen
Ох, я не обратил внимание на картинке на перемешивание, спасибо вам.
grich
Оба варианта очень известны. Понятно, что второй — он «со звездочкой», встречается чуть реже. Но все равно — дается даже школьникам
withoutuniverse Автор
Очень сомневаюсь, что школьники за урок смогут за 3 взвешивания решить данную задачу.
grich
Это кружковская математика. Кажется, класс 9
withoutuniverse Автор
Буду благодарен за пруфы
grich
www.problems.ru/view_problem_details_new.php?id=60922
Она даже есть в (широко известном в узких кругах) задачнике Спивака: math.ru/lib/files/pdf/mmmf/posev.pdf, стр. 55, №305
Lopar
АФАИК в школьной программе явно указано в какую сторону отличается вес монеты, нет?
grich
У меня в комментарии всего шесть слов, но Вы упустили самое главное из них: «кружковская» =)
withoutuniverse Автор
Я тоже упустил это слово, и не понимал, зачем давать на уроке такую задачу, ведь образовательного смысла она мало несет в себе (3 человека решают из класса, а остальные 20 непонимают о чем речь и скучают).
Спасибо за пруф.
bay73
Образовательного смысла в задаче более чем достаточно. Причем как в построении оценки на число взвашиваний, так и в конкретной реализации алгоритма.
Например, весьма интересно построить зависимость максимального числа монет от числа взвешиваний.
withoutuniverse Автор
В кружке или для заинтересованного школьника очевидно, что вы правы. На уроке я бы такую задачу детям не давал, так как бОльшая часть учеников скучала бы.
bay73
Школы разные бывают. Согласен, что большинству школьников это будет неинтересно, но тут стоит отметить, что и стандартная школьная программа большинству не интересна. А вот в школах с углублённым изучением математики такие уроки вполне бывают.