Question

Как записать алгоритм решения задачи про арбузы см.?

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

Answer 1

Попробуем решить эту задачу:

Ну проще всего сделать так: Обозначим арбузы буквами АБВГ

1) Будем взвешивать потихонечку. А с Б взвесим. Если А тяжелее, то А взвесим С В, если опять тяжелее А, то А взвесим с В, если опять а тяжелее, то а на последнем месте и у нас уже было три взвешивания. Теперь берем арбуз б взвешиваем его с в, если б тяжелее, то он на предпоследнем месте, теперь остается взвесить в с г, если в тяжелее в, то он второй по счету, а г самый легкий. Получилось как раз пять взвешиваний, меньше не получается. Ну, а в зависимости от того какие ситуации получаются будем идти по разным путям.

А с Б взвесим. Если Б тяжелее, то Б взвесим С В, если опять тяжелее Б, то Б взвесим с В, если опять Б тяжелее, то Б на последнем месте и у нас уже было три взвешивания. Теперь берем арбуз А взвешиваем его с в, если А тяжелее, то он на предпоследнем месте, теперь остается взвесить В с Г, если в тяжелее В, то он второй по счету, а Г самый легкий. Получилось как раз пять взвешиваний, меньше не получается. Ну и так далее рассуждая всегда за пять взвешиваний можно определить самый легкий арбуз и так далее.

Answer 2

Идём по самому долгому пути.

1) Взвешиваем арбуз А с арбузом Б (пусть А>Б).

2) Взвешиваем арбуз А с арбузом В (пусть А>В)

3) Взвешиваем арбуз В с арбузом Б (тут уже соотношение неважно, пусть будет для красоты А>Б>В)

4) Взвешиваем арбуз Г с арбузом Б (тут возможны два варианта: или Г>Б, или Б>Г)

5.1) Если Г>Б, то взвешиваем арбуз Г с арбузом А

5.2) Если Б>Г, то взвешиваем арбуз Г с арбузом В

таким образом получаем варианты ранжира по убыванию веса:

ГАБВ, АГБВ, АБГВ, АБВГ