Ilu Podwładnych?

Zadanie

W firmie każdy pracownik podlega kierownikowi prócz najwyższego kierownika (podlegającego sobie). Mając daną listę pracowników i ich kierowników określ ile każdy pracownik ma podwładnych. Zakładamy, że pracownicy mają przypisane id będące kolejnymi liczbami nieujemnymi.

Przykład

Przypuśćmy, że firma składa się z 7 osób i hierarchia pracowników przedstawia się następująco:

Hierarchia w firmie

Pomiędzy dwoma połączonymi pracownikami kierownikiem jest ten, który znajduje się wyżej na przedstawionym rysunku. Oznacza to, że (główny) kierownik 2 jest bezśporednim zwierzchnikiem 1, 3 oraz 4, ale właśsciwie podlegają mu wszyscy pracownicy (zgodnie z zadaniem nawet on sam). Do programu taka hierarchia zostałaby wprowadzona jako następujący zestaw danych:

1. 0 3
2. 1 2
3. 2 2
4. 3 2
5. 4 2
6. 5 1
7. 6 3

Na podstawie tych danych należy określić, że pracownik 3 jest kierownikiem dwóch pracowników, ale, że pracownik 2 jest kierownikiem, aż 6 osób!

Algorytm

Istnieje wiele sposobów na rozwiązywani tego typu zadań. Najprostszy z nich polega najpierw na pogrupowaniu informacji, którzy pracownicy komu podlegają. Na koniec tej operacji powinniśmy otrzymać listę o takiej długości ilu jest pracowników i po i-tą pozycją znajdą się wszyscy podlegli bezpośrednio kierownikowi i.

Następnie potrzebna jest pusta tablica o n pozycjach, gdzie n oznacza ilość pracowników. Na początku wybieramy kierownika głównego, którego można poznać po tym, że jego id pokrywa się z id kierownika. Następnie dla każdego z jego bezpośrednio wywołujemy sprawdzenie ile oni mają podwładnych. Warunkiem stopu jest sytuacja, gdy dany pracownik nie jest czyimś zwierzchnikiem. Wtedy taka osoba jest liczona jako 1 dla kierownika. Z kolei taka osoba ma wpisane 0, że nikt jej nie podlega. Po zakończeniu rekurencji w tablicy zapisane są informacje ile każdy z pracowników ma podwładnych.

Implementacja

Przechowywanie danych

Na początku deklarowany jest obiekt pracownik, który może przechowywać zarówno id pracownika jak również id jego kierownika. W celu uproszczenia wczytywania dodatkowo zostało napisana funkcja tworząca instancję pracownika z zadanami danymi.

1. class pracownik:
2.   def __init__(self, id, kierownik):
3.     self.id = id
4.     self.kierownik = kierownik

Liczenie Podwładnych

Funkcja szukajPodwladnych() przeprowadza najpierw grupowanie osób. Podczas grupowania zostaje znaleziony kierownik i jego id zostaje przechowane jako punkt startowy do dalszych obliczeń. Po przygotowaniu listy można policzyć ilu jest podwładnych.

1. def szukajPodwladnych(pracownicy, n):
2.   lista = [[] for i in range(n)]
3.   glowny = -1
4.   for i in range(n):
5.     if (pracownicy[i].id == pracownicy[i].kierownik):
6.       glowny = i
7.     else:
8.       lista[pracownicy[i].kierownik].append(i)
9.   dane = [0]*n
10.   dane, dane[glowny] = policzPodwladnych(lista, dane, glowny)
11.   return dane

Liczenie podwładnych przeprowadz funkcja policzPodwladnych(), która rekurencyjnie wyznacza ile osób ma podwładnych ma każda kolejna osoba. W każdym wywołaniu funkcja oblicza sumę podwładnych każdej osoby, której jest bezpośrednim kierownikiem. Oczywiście należy pamiętać, że każda osoba podwładna liczy się do sumy jako jej liczba podwładnych powiększona o 1 (o nią samą).

1. def policzPodwladnych(lista, dane, teraz):
2.   suma = 0;
3.   for i in range(len(lista[teraz])):
4.     dane, w = policzPodwladnych(lista, dane, lista[teraz][i])
5.     suma += w + 1
6.   dane[teraz] = suma
7.   return dane, suma

Testowanie funkcji

Przedstawiony fragment kodu wczytuje od użytkownika szukane informacje, a następnie wyświetla w rosnącym porządku id pracownika w pierwszej kolumnie, a w drugiej liczbę mu podległych.

1. n = int(input("Ilu jest pracowników?\n n = "))
2. print("Podaj pracowników i ich kierowników:")
3. pracownicy = []
4. for i in range(n):
5.   data = [int(x) for x in input().split()]
6.   pracownicy.append(pracownik(data[0], data[1]))
7. dane = szukajPodwladnych(pracownicy, n);
8. for i in range(n):
9.   print(str(i) + "\t" + str(dane[i]))

• Kod źródłowy Implementacja