|
Занятие 18. Жадный алгоритм
|
1. |
У продавца имеется набор n гирек весом a1, a2, ..., an.
Известно, что вес первой гирьки равен 1, а вес каждой следующей не превосходит суммарного веса предыдущих. Докажите, что с
помощью своих гирек продавец может взвесить любой вес от 1 до a1 + a2 + ... + an.
| |
2. | Два игрока по очереди проводят диагонали в правильном 111-угольнике. После каждого своего хода игрок платит противнику число рублей равное количеству
пересечённых диагоналей. Кто из игроков может заведомо не остаться в проигрыше?
| |
3. |
В компьютерном классе имеется 50 компьютеров, которые нужно
объединить в локальную сеть, затратив при этом как можно меньше провода (по суммарной длине). Системный администратор прелагает действовать следующим образом. Сначала соединит каждые два компьютера проводом, а затем будет перебирать все провода по длине — от самого длинного к самому короткому — и удалять очередной провод, если это не приводит к распаду сети.
а) Докажите, что получится сеть с минимальной суммарной длиной проводов.
б) Завхоз заявил, что после такой процедуры останется много обрезков, и что нужно действовать по-другому: выбирать на каждом шаге два самых близких компьютера и соединять их проводом, если между ними еще нет связи; затем следующие два, и так далее. Верно ли, что и в этом случае получится сеть с минимальной длиной проводов?
| |
4. | Есть набор гирек 1, 2, 3, ... , N г и чашечные весы. Двое играющих по очереди кладут на весы по одной гирьке из набора, каждый на свою чашу. Выигрывает тот, после чьего хода установится равновесие. Может ли кто-нибудь из игроков всегда выигрывать независимо от игры противника?
| |
5. | На плоскости дан набор из 200 векторов. Двое по очереди берут себе по одному вектору, пока они не кончатся. Выигрывает тот, у кого длина суммы векторов окажется больше. Кто выигрывает при правильной игре?
| |
6. | Имеется аудитория и список заявок на занятия в этой аудитории (в заявке содержится время начала и окончания предполагаемого занятия, эти интервалы времени вообще говоря перекрываются). Требуется составить расписание занятий так, чтобы было
удовлетворено наибольшее число заявок. Как это проще всего сделать?
| |
7. | Дано n точек на координатной прямой. Нужно покрыть их наименьшим возможным количеством отрезков длины 1. |
Пусть есть какая-то монетная система (например, в России используется система, состоящая из 1, 5, 10, 50 копеек) и требуется выплатить некую сумму этими монетами, выдав при этом наименьшее количество монет.
Жадный алгоритм выплаты определим так: чтобы выплатить N копеек, выдадим монету самого большого достоинства, не превосходящего N, а затем остаток (если он ненулевой) выплатим, применив для него жадный алгоритм.
Монетную систему назовём удобной, если выплата согласно жадному алгоритму является оптимальной по количеству выданных монет.
|
8. | а) Докажите, что система монет 1, p,
p2,..., pn
является удобной для натурального p, большего 1.
б) Докажите, что российская монетная система является удобной.
в) Приведите пример неудобной монетной системы.
|
|
