Вы здесь

Металлические кубики

Undefined

Имеется 20 металлических кубиков, одинаковых по размерам и внешнему виду. Некоторые из них алюминиевые, остальные - дюралевые (более тяжелые). Как при помощи не более чем 11 взвешиваний на чашечных весах без гирь определить число дюралевых кубиков? (Предполагается, что все кубики могут быть алюминиевыми, но не могут быть все дюралевыми.)

 

Решение. Важная особенность этой задачи на взвешивание состоит в том, что нужно определить всего лишь количество дюралевых кубиков а не установить какие именно из кубиков дюралевые.

Алгоритм решения. Берем любых два кубика и ставим на разные чаши весов. Получим оди из двух вариантов:

1. Если чаши не уравновешены то получается, что мы наугад нашли один алюминиевый (тот который в чашкее выше) и один дюралевый кубик (тяжелее – чашка ниже). Далее достаточно положить оба эти кубика на одну чашу весов и сравнить с оставшимися 9-ю парами кубиков. Если новая пара кубиков на противоположной чаше весов тяжелее, значи в ней два дюралевых кубика, легче – два алюминиевых, а если чаши уравновешены, то в этой паре тоже один кубик дюралевый, а один алюминиевый. В этом случае мы подсчитаем нужное количество за 10 взвешиваний.

2. Если чаши весов при взвешивании первых двух кубиков оказались уравновешенными, то мы нашли два одинаковых кубика. Но они могут оказаться как алюминиевыми так и дюралевыим. И в том и в другом случае следует поступить так же как и в пункте 1 – поставить оба кубика на одну чашу весов и сравнить их с оставшимися 9-ю парами кубиков. При этом могут возникнуть следующие ситуации:

2а. Все девять взвешиваний будут показывать одинаковый вес пар кубиков, т.е. все 20 кубиков одинакового веса и все они, согласно условию, алюминиевые. В этом случае тоже 10 взвешиваний.

2б. При некотором (n-ном) из 9-ти взвешиваний первой пары одинаковых кубиков с остальными парами найдется пара полегче. Значит первая пара состояла из дюралевых кубиков и все кубики, взвешенные до этого момента тоже оказались дюралевыми. Кубики из наденной парой полегче следует сравнить между собой, если они окажуться одинаковыми, то они оба алюминиевые, если нет, то алюминиевый тот, который полегче. Далее для проверки остальных кубиков следует составить пару из одного дюралевого и одного алюминиевого кубика и подсчитать количество дюралевых кубиков среди оставшихся способом, описанным в пункте 1. В этом случае получим 1 + n +1 + 9-n = 11 взвешиваний.

2в. При некотором (n-ном) из 9-ти взвешиваний первой пары одинаковых кубиков с остальными парами найдется пара потяжеле. Значит все кубики, взвешенные до этого момента оказались алюминиевыми. С кубиками из наденной пары и остальными кубиками следует поступить аналогично к пункту 2б. В этом случае получим тоже 11 взвешиваний.

Задачи на взвешивание и сравнение удачно подходят для подготовки будущих программистов, так как хорошо развивают алгоритмическое мышление. Решение таких задач даже сложно назвать решением в узком смысле - это, скорее, общий алгоритм решения, как и в случае нашей задачи. Современные программы, конечно же, не сводятся к простому описанию алгоритма на языке программирования. Но алгоритмизация по прежнему остается важной частью подготовки программиста.
author: 
admin
Просмотров: 
776
Раздел: