Главная / Моделирование, тестирование и диагностика цифровых устройств / Жадный алгоритм поиска масок, описанный в лекции 31,базируется на применении конструкции дерева решений. Проиллюстрируйте конструкцию классического дерева решений для решения следующей задачи: имеется 8 одинаковых монет, среди которых одна фальшивая (она

Жадный алгоритм поиска масок, описанный в лекции 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 и т.д. Алгоритм определения фальшивой монеты при таком взвешивании очевиден

Сложность вопроса

Сложность курса: Моделирование, тестирование и диагностика цифровых устройств

Оценить вопрос

Очень сложно

Сложно

Средне

Легко

Очень легко

Комментарии:

Аноним

Гранд мерси за подсказками по intiut'у.

16 авг 2016

Другие ответы на вопросы из темы аппаратное обеспечение интуит.