Применение графов при построении алгоритма решения задач

Рассмотрим следующую задачу. «Среди 6 монет находится одна фальшивая, но неизвестно, легче она настоящих или тяжелее. Среди этих монет известная также настоящая монета. Необходимо с помощью двух взвешиваний на чашечных весах определить фальшивую монету». Занумеруем монеты, и пусть монета 6 – настоящая. Обозначим через F(А) вес монет, принадлежащих множеству А. Процесс определения фальшивой монеты с помощью двух взвешиваний изображен на рис.3. Из рисунка видно, что в любом случае можно найти фальшивую монету за 2 действия (взвешивания), т.е. сложность алгоритма будет равна двум.

Построение алгоритмов в младших классах является подготовительным этапом к их изучению в старших. Ученик подойдет к началу изучения информатики с интуитивным пониманием, что алгоритм должен удовлетворять требованиям детерминированности, массовости, конечности.

Рис.3