Page 192 - Bkhargava_-_Grokaem_algoritmy

Задача о покрытии множества 191

Также понадобится список станций, из которого будет выбираться покры­
тие. Я решил воспользоваться хешем:

stations = {}
stations["kone"] set(["id", "nv", "ut"])
stations["ktwo"] set(["wa", "id", "mt"])
stations["kthree"] = set(["or", "nv", "са"])
stations["kfour"] set(["nv", "ut"])
stations["kfive"] = set(["ca", "az"])

Ключи - названия станций, а значения - сокращенные обозначения шта­
тов, входящих в зону охвата. Таким образом, в данном примере станция kone
вещает в штатах Айдахо (id), Невада (nv) и Юта (ut). Все значения являют­
ся множествами. Как вы вскоре увидите, хранение данных во множествах
упрощает работу.
Наконец, нам понадобится структура данных для хранения итогового на­
бора станций:

final_stations set()

Вычисление ответа

Теперь необходимо вычислить набор используемых станций. Взгляните на
диаграмму и попробуйте предсказать, какие станции следует использовать.

www.trk.kg