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. struct pracownik {
2.   public int id;
3.   public int kierownik;
4. };
6. static pracownik utworzPracownika(int id, int kierownik) {
7.   pracownik p;
8.   p.id = id;
9.   p.kierownik = kierownik;
10.   return p;
11. }

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. static int[] szukajPodwladnych(pracownik[] pracownicy, int n) {
2.   List<List<int>> lista = new List<List<int>>(n);
3.   for (int i = 0; i < n; i++)
4.     lista.Add(new List<int>());
5.   int glowny = -1;
6.   for (int i = 0; i < n; i++) {
7.     if (pracownicy[i].id == pracownicy[i].kierownik) {
8.       glowny = i;
9.     } else {
10.       lista[pracownicy[i].kierownik].Add(i);
11.     }
12.   }
13.   int[] dane = new int[n];
14.   dane[glowny] = policzPodwladnych(ref lista, ref dane, glowny);
15.   return dane;
16. }

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. static int policzPodwladnych(ref List<List<int>> lista, ref int[] dane, int teraz) {
2.   int suma = 0;
3.   for (int i = 0; i < lista[teraz].Count; i++)
4.     suma += policzPodwladnych(ref lista, ref dane, lista[teraz][i]) + 1;
5.   dane[teraz] = suma;
6.   return suma;
7. }

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. static void Main(string[] args) {
2.   Console.Write("Ilu jest pracowników?\n n = ");
3.   int n = Convert.ToInt32(Console.ReadLine());
4.   Console.WriteLine("Podaj pracowników i ich kierunków:");
5.   pracownik[] pracownicy = new pracownik[n];
6.   for (int i = 0; i < n; i++) {
7.     string[] data = Console.ReadLine().Split(' ');
8.     pracownicy[i] = utworzPracownika(Convert.ToInt32(data[0]), Convert.ToInt32(data[1]));
9.   }
10.   int[] dane = szukajPodwladnych(pracownicy, n);
11.   for(int i = 0; i < n; i++)
12.     Console.WriteLine("{0}\t{1}", i, dane[i]);
13.   Console.ReadKey();
14. }

• Kod źródłowy Implementacja