На просторах интернета часто можно встретить те или иные задачи, которые задают на собеседовании в крупнейшие компании. Вот одна из задач, которую задают при поступлении в GOOGLE.
Для того, чтобы узнать, как решить задачу, ведь мы с вами не на собеседовании, и для решения - верного, и не верного, предлагаем два варианта алгоритма решения. Ответы для интереса предложим в виде теста. А сам ответ будет дан в конце статьи, посмотрите и сравните со своим решением. А ведь задача пусть и не сложная, но интересная, недаром же её в GOOGLE предлагают.
У вас имеется 8 шариков одинакового вида и размера.
Вопрос: Как найти более тяжелый шарик, используя весы (чашечные, без гирек), и всего два взвешивания?
Выберем алгоритм решения. для рассмотрения нужно каким-то образом разделить 8 шариков на кучки по: 2 + 3 + 3, или 4 + 3 + 1, или на другое количество шаров. Но учитывая, что разрешено путём двух взвешиваний выявить, где же этот тяжёлый шарик. Можно, конечно, рассмотреть все возможные варианты алгоритма. Но учитывая ситуацию прохождения теста, там наверно не будет много времени для решения, значит, нужно быстро решать, или знать, как решать такие задачи.
Вот и выберем для начала верный ответ. Обратимся к форме теста.
В форме теста выбран единственно верный алгоритм для варианта двух взвешиваний . Но не факт, что именно этот алгоритм единственно верный. в ответах на тест не даны те решения, которые принимают принимающие на работу в GOOGLE.
Варианты, которые предлагает форма теста.
Вариант 1. Шаг1. Делим шары на 2 и 2 шара. Если вес равный переходим к шагу 2.
Шаг 2. Взвешиваем 2 и 2 шара. Находим 2 шара, которые перевешивают.
Вариант 2. Делим шары на 3 и 3 и 2 шара.
Шаг 1. взвешиваем 3 и 3. Если вес равные, переходим к шагу 2.
Шаг 2. взвешиваем 2 шара, 1 и 1 , и находим тяжёлый шар.
Можно посмотреть видео, написанное для пояснения решения задачи.
Вариант видео в Яндекс Дзене, в формате видео с этим же материалом приведён здесь.
Вам может быть также интересны статьи: