Выбор ответа Middle Жадные спрашивают часто обновлено
Жадная сдача
Вопрос
Монеты номиналом 1, 3, 4. Жадный алгоритм берёт самую крупную подходящую монету. Сколько монет он выдаст для суммы 6 и сколько минимум?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Жадный 3 (4+1+1), минимум 2 (3+3). Жадный возьмёт 4, затем 1 и 1: три монеты.
Варианты ответа
- Жадный 3 (4+1+1), минимум 2 (3+3)правильный ответ
- Жадный 2, минимум 2: 6 делится на 3
- Жадный 3 (4+1+1), минимум 3 (4+1+1)
- Жадный 2 (3+3), минимум 2 (3+3)
Разбор
Жадный возьмёт 4, затем 1 и 1: три монеты. Оптимум 3 + 3: две. Значит, для произвольных номиналов жадность неверна, нужна динамика. Для «канонических» систем вроде 1, 2, 5, 10 жадность работает.
- Жадный не берёт 3 первой: 4 крупнее.
- Минимум не 3: есть 3 + 3.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.