TwiddleLab / Код / Алгоритмы в движении

Жадный выбор

Урок 10 из 11 · 7 мин · Бесплатно, без аккаунта

Что ты узнаешь

• Жадный алгоритм на каждом шаге берёт выбор, который выглядит лучшим, и никогда не оглядывается.
• С монетами 1, 5, 10, 25 жадная сдача всегда лучшая. С 1, 3, 4 нет: 6 = 3 + 3, а не 4 + 1 + 1.
• Одного контрпримера достаточно, чтобы доказать, что «всегда» неверно.

Начать урок

Как идёт урок

1. Всегда сначала хватай самую крупную монету. Это всегда даёт меньше всего монет?

   Заплати 30 как можно меньшим числом монет.

2. Робот следует этому правилу. Монеты 1, 3 и 4. Ему нужно заплатить 6.

   Пройди по его выборам.

3. Обыграй робота.

   Заплати 6 монетами 1, 3, 4, используя меньше 3 монет.

4. Жадность и контрпример.

   Жадный алгоритм берёт выбор, который выглядит лучшим прямо сейчас, и никогда его не отменяет. Это быстро и просто.

   Иногда жадность всегда права (монеты 1, 5, 10, 25). Иногда нет (монеты 1, 3, 4).

   Контрпример это один случай, где утверждение не выполняется. Заплатить 6 монетами 1, 3, 4 достаточно, чтобы доказать ложность «жадность всегда даёт меньше всего монет».

5. Напиши робота.

   Для каждой монеты, начиная с крупной: пока влезает, бери.

6. Какие наборы монет могут обмануть робота?

   Робот пробует каждую сумму от 1 до 40. Разложи наборы.

7. Охотник за контрпримерами.

   Монеты 1, 7, 10. Найди 3 суммы, где робот берёт больше монет, чем нужно.

8. Жадность на карте: всегда едь в ближайший город.

   Какой маршрут по всем городам короче? Нажми на него, потом «Проверить».

   «Ближайший следующий» выбирает C, D, потом E, потому что они близко, а потом вынужден ехать к далёкому B и обратно. Если заехать в B до E, длинного возвращения не будет.

9. Побудь роботом: заплати 63 монетами 25, 10, 5 и 1.

   Нажимай на монеты в том порядке, в каком он их берёт.

10. Придумай свою жадную ловушку.

    Монета 1 плюс две монеты на выбор. Сделай так, чтобы робот где-то от 1 до 30 проиграл.

    Жадность ошибается, когда крупная монета оставляет остаток, который можно заплатить только многими мелкими, а если её пропустить, получается более аккуратное разбиение.

Предыдущий урок: Сортирующие сети · Следующий урок: Гонка алгоритмов · Часть курса: Алгоритмы в движении

Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.