Интересна задача от интервю за работа

msmilkoff 338 Точки

Интересна задача от интервю за работа

Наскоро се мъчих със следната логическа задача - идеи?
В парламента има 15 депутати, всеки от които има най-много трима врагове измежду останалите. Как ще разделите депутатите в две групи, така че всеки депутат да има най-много двама врагове в собствената си група?

Тагове:

11/06/2016 23:48:31 Общи приказки 11/06/2016 23:49:36

RFilipov 136 Точки

Поставяш един в група 1 и ForEach на враговете => поставяш един враг в група 2 и следващия в група 1 и така докато се изчерпат след това рекурсивно за враговете същата функция като проверяваш колко врагове има всеки един в групата вече съществуващи. Това е greedy алгоритъм, които може да не сработи само ако условието е зададено, така че да няма възможно разпределение. Започваш от тези с най-много врагове тъй като те са проблемните.

12/06/2016 01:03:52

Filkolev 4482 Точки

Не виждам обаче в условието да е казано, че е известно кой на кого е враг, така че трябва да се подходи с ограничена информация, което прави задачата доста по интересна.

12/06/2016 10:49:13

msmilkoff 338 Точки

Измислих го само за едната група
Първо всеки един го слагам в група А и ако след добавянето някой от групата вече е станал с повече от 2-ма врагове, местя текущия (т.е. този, който е нарушил баланса) в група Б:

currentDep = deps.First
while deps.count > 0
    Push currentDep -> to group A
    forech dep in group A
        if dep.enemies.count > 2:
            group A->Pop(currentDep)
            push currentDep -> group B
currentDep = deps.Next

Обаче никой не знае в гупа Б какъв мазаляк е :)

12/06/2016 11:30:29

Alex_29 5 Точки

Намерих подобна задача в книгата Програмиране = ++Алгоритми в глава 5.7.2. Независими множества, страница 340.Ето и сорс кода от книгата на C#.Надявам се да помогне.

12/06/2016 20:28:49