ГДЗ по информатике, 11 класс, Босова, номер 9.11: Структурное программирование

План решения

Для упорядочивания n элементов (банок) по возрастанию веса с помощью чашечных весов без гирь необходимо использовать алгоритм сортировки сравнением. Наиболее простым и наглядным для школьного курса является метод пузырьковой сортировки или сортировка выбором. В данном решении опишем алгоритм сортировки выбором , так как он требует минимального количества перемещений банок, что удобно при физическом взвешивании.

Пошаговый алгоритм

1. Разместим все n банок в ряд на столе. Обозначим их как B_1,B_2,…,B_n. Изначально они стоят в произвольном порядке.
2. Будем последовательно находить самую легкую банку среди еще не отсортированных и ставить её на нужное место слева направо.
3. Пусть текущий индекс начала неотсортированной части равен i=1.
4. Считаем, что банка B_i — самая легкая среди оставшихся. Запоминаем её как «кандидат».
5. Сравниваем «кандидата» с каждой следующей банкой B_j, где j меняется от i+1 до n.
   • Кладем «кандидата» на одну чашу весов, а банку B_j — на другую.
   • Если чаша с банкой B_j легче, то новая «самая легкая» — это B_j. Обновляем «кандидата».
   • Если чаши уравновешены или чаша с «кандидатом» легче, оставляем «кандидата» прежним.
6. После завершения внутреннего цикла (j достигло n), мы нашли самую легкую банку из диапазона [i,n]. Меняем местами эту найденную банку и банку B_i.
7. Увеличиваем i на 1 (i=i+1). Если i≤n-1, возвращаемся к пункту 4. Если i>n-1, алгоритм завершён.

Проверка и оценка сложности

На каждом шаге i мы делаем ровно (n-i) сравнений. Всего количество сравнений составит сумму арифметической прогрессии: ∑n-1i=1(n-i)=n(n-1)/2. После выполнения всех итераций банки будут стоять в порядке возрастания веса, так как на позицию 1 поставлена самая легкая из всех, на позицию 2 — самая легкая из оставшихся и т.д. Алгоритм корректен и полностью соответствует условию задачи.