Жадный алгоритм поиска масок, описанный в лекции 31,базируется на применении конструкции дерева решений. Проиллюстрируйте конструкцию классического дерева решений для решения следующей задачи: имеется 8 одинаковых монет, среди которых одна фальшивая (она легче, чем стандартная). Монеты пронумерованы числами 1,2,…,8. Требуется найти фальшивую монету, используя равновесные весы с двумя чашками (пусть левая чашка имеет №1, правая - №2).
(Отметьте один правильный вариант ответа.)
Варианты ответа
на чашку №1 кладутся монеты 1-4, на чашку №2 - монеты 5-8 и производится первое взвешивание. Если чашка №1 легче, то на чашку №1 кладутся монеты 1,2, а на чашку №2 -монеты 3,4 и производится второе взвешивание. Если чашка №1 легче, то на чашку №1 кладется монета 1, на чашку №2 - монета 2 и производится третье взвешивание. Если чашка №1 легче, то монета 1-фальшивая, в противном случае монета 2-фальшивая. Аналогичные действия производятся с монетам 5-8 после первого взвешивания, если чашка №2 оказалась легче (Верный ответ)
на чашки весов последовательно кладутся монеты 1 и 2, затем 3 и 4 и т.д. Алгоритм определения фальшивой монеты при таком взвешивании очевиден