Представьте в виде построчной записи алгоритм решения следующей задачи: «Имеются четыре арбуза различной массы. Как, пользуясь чашечными весами без гирь, путём не более пяти взвешиваний расположить арбузы по возрастанию веса?»
Так как массы различны, при сравнении на чашечных весах одна чаша обязательно опустится ниже. Арбуз на поднявшейся чаше легче. Будем записывать арбузы слева направо от самого лёгкого к самому тяжёлому.
- Обозначить арбузы
, , , . - Сравнить
и (первое взвешивание). Более лёгкий назвать , более тяжёлый — . Теперь . - Сравнить
с (второе взвешивание). Если , записать тройку . - Если
, сравнить с (третье взвешивание). При записать , иначе — . В любом случае получена упорядоченная тройка; назовём её , где . - Сравнить
со средним арбузом (следующее взвешивание). - Если
, сравнить с (последнее взвешивание). При записать , иначе — . - Если
, сравнить с (последнее взвешивание). При записать , иначе — .
Первые три арбуза упорядочены не более чем за три взвешивания. Для помещения четвёртого на нужное место требуются ровно два сравнения. Итого не более
Сначала упорядочить три арбуза не более чем за три взвешивания, затем сравнить четвёртый со средним и с одним из крайних. Всего не более пяти взвешиваний.
