Решение задания 112: Алгоритм взвешивания 4 арбузов на чашечных весах (Информатика 8 класс, Босова)

Задание 112. Представьте в виде построчной записи алгоритм решения следующей задачи.
Имеются четыре арбуза различного веса. Как, пользуясь чашечными весами без гирь, путём не более пяти взвешиваний расположить их по возрастанию веса?

Алгоритм для задачи:

1. Обозначим арбузы A, B, C, D. Взвешиваем A vs B: если A > B, продолжаем; иначе B > A (меняем местами).
2. Взвешиваем C vs D: если C > D, продолжаем; иначе D > C (меняем местами).
3. Взвешиваем A vs C: если A > C, A — самый тяжёлый; иначе C — самый тяжёлый.
4. Если A > C: взвешиваем B vs C. Если B > C, порядок: D < C < B < A.
5. Если в 4 B < C, порядок: D < B < C < A.
6. Если в 3 C > A: взвешиваем A vs B. Если A > B, порядок: D < B < A < C.
7. Если в 6 A < B, порядок: D < A < B < C.
8. Конец. Если равновесие, повторить взвешивание.

Подробное решение задания:

Обозначим арбузы как A, B, C, D. Алгоритм использует не более 5 взвешиваний на чашечных весах (две чаши, без гирь). На каждом шаге помещаем по одному арбузу на каждую чашу и фиксируем результат сравнения. В худшем случае потребуется 5 взвешиваний для полного упорядочения по весу (от самого лёгкого к самому тяжёлому). Алгоритм адаптирован для определения порядка на основе попарных сравнений.

Шаг 1: Поместить арбуз A на левую чашу, арбуз B на правую чашу.

• Если левая чаша тяжелее, то A > B (A тяжелее B).
• Если правая чаша тяжелее, то B > A (B тяжелее A).
• Если чаши уравновешены (что невозможно, так как веса различны), повторить взвешивание.
  (Предположим для продолжения, что A > B. Если наоборот, скорректируйте обозначения A и B местами.)

Шаг 2: Поместить арбуз C на левую чашу, арбуз D на правую чашу.

• Если левая чаша тяжелее, то C > D (C тяжелее D).
• Если правая чаша тяжелее, то D > C (D тяжелее C).
  (Предположим для продолжения, что C > D. Если наоборот, скорректируйте обозначения C и D местами.)

Шаг 3: Поместить арбуз A на левую чашу, арбуз C на правую чашу.

• Если левая чаша тяжелее, то A > C (A — самый тяжёлый из A, B, C, D). Перейти к шагу 4.
• Если правая чаша тяжелее, то C > A (C — самый тяжёлый). Перейти к шагу 5.
• Если чаши уравновешены, повторить (невозможно).

Шаг 4 (если A > C): Поместить арбуз B на левую чашу, арбуз C на правую чашу.

• Если левая чаша тяжелее, то B > C (порядок: D < C < B < A).
• Если правая чаша тяжелее, то C > B (порядок: D < B < C < A).
• Конец алгоритма.

Шаг 5 (если C > A): Поместить арбуз A на левую чашу, арбуз B на правую чашу.

• Если левая чаша тяжелее, то A > B (порядок: D < B < A < C).
• Если правая чаша тяжелее, то B > A (порядок: D < A < B < C).
• Конец алгоритма.

Результат: После выполнения шагов арбузы упорядочены по возрастанию веса. Если на каком-то шаге результат неоднозначен (например, из-за погрешности весов), повторите взвешивание. В худшем случае (когда самый тяжёлый определяется на шаге 3) требуется 5 взвешиваний, но часто меньше.