Задание 258 ГДЗ Семенов Рудченко 6 класс (Информатика)

Задача

Имеется 68 алмазов, все алмазы разные по весу. Как за 100 взвешиваний на чашечных весах найти самый легкий и самый тяжелый алмаз?
Делим алмазы на две кучи по 34 алмаза. Взвешиваем на весах по одному алмазу из каждой кучи. Более легкий в одну сторону кладем (куча 1), более тяжелый в другую (куча 2). Сделали 34 взвешивания. Самый тяжелый находится в куче 2, самый легкий в куче 1. В кучах по 34 алмаза.
Теперь сортируем кучу 1 (легкие) по весу, взвешивая каждый с каждым и переставляя из от меньшего к большему. В конце 33 взвешиваний у нас на первом месте будет самый легкий.
Также сортируем кучу 2, после 33 взвешиваний самый тяжелый будет на последнем месте.
Алмазы найдены. Взвешиваний было 34 +2*33 = 100
Можно, конечно, по-другому. Каждый раз делить кучи пополам, затем перебирать на больший и меньший. В конце у нас выдут больший и меньший по весу алмазы.

Подробный ответ

Разделим 68 алмазов на две кучки по 34 алмаза. Затем сравним алмазы попарно: по одному из первой кучки и по одному из второй. Более лёгкий будем относить в кучку лёгких, более тяжёлый — в кучку тяжёлых.

Так как пар 34, потребуется 34 взвешивания. После этого в кучке лёгких окажутся все 34 более лёгких алмаза, а в кучке тяжёлых — все 34 более тяжёлых.

Теперь найдём самый лёгкий алмаз в кучке лёгких. Для этого достаточно упорядочить 34 алмаза по весу. При последовательном сравнении соседних элементов нужно $$34-1=33$$ взвешивания.

Аналогично найдём самый тяжёлый алмаз в кучке тяжёлых: ещё $$34-1=33$$ взвешивания.

Итого:

$$34+33+33=100$$

Значит, за 100 взвешиваний можно найти и самый лёгкий, и самый тяжёлый алмаз.