4261638923

3

z kim może utworzyć parę. Jeżeli zawodnicy o numerach X i Y mogą utworzyć jedną parę, to fakt ten zapisujemy w następujący sposób: X — Y. Mając dane wyniki ankiety należy dobrać zawodników w pary tak, aby liczba utworzonych par była maksymalna i oczywiście każdy zawodnik był przypisany tylko do jednej pary. Zaproponuj algorytm (zapisz jego pseudokod) umożliwiający rozwiązanie powyższego problemu. Wykonaj algorytm (przedstaw kolejne etapy działania) dla listy podanej poniżej:

1 - 6

2- 7

3- 6

4- 5

5- 2

6- 4

7 -    1

8-3

9 -    1

Zadanie 14

Zaproponuj modyfikację procedury FWUC (rys. 1), która umożliwi wyznaczenie ujemnego cyklu, a nie tylko jego wykrycie. Zapisz treść zmodyfikowanej procedury FWUC.

Zadanie 15

Bankring polega na przełamywaniu prawno-technicznych zabezpieczeń związanych z funkcjonowaniem banków nie naruszając ich regulaminów. Wiele banków za zdeponowanie pieniędzy wypłaca prowizję. Tak więc przelewając pieniądze z banku X do banku Y ponosimy z jednej strony koszty związanie z opłatą za przelew bankowy, z drugiej strony za zdeponowane pieniądze bank przelewa nam prowizję. Cała operacja kosztuje nas kwotę jaką stanowi różnica pomiędzy opłatą za przelew, a prowizją. Zakładając, że mamy założone konta w różnych bankach można wyobrazić sobie sytuację, w której po wprowadzeniu w obieg stałej kwoty, stan kont będzie ciągle wzrastał. Jeśli przelew z banku X do banku Y kosztuje nas K złotych, to fakt ten zapisujemy: X —> Y K, np. zapis: Bank A —* Bank B 10 oznacza, że przelew z Banku A do Banku B będzie nas kosztował 10 złotych (różnica między opłatą, a prowizją). Zaproponuj algorytm (podaj pseudokod), który dla zadanej listy opisującej przelewy i ich koszty wyznaczy ciąg banków, który będzie generował wzrost stanu na koncie. Wykonaj algorytm (przedstaw kolejne etapy działania) dla listy podanej poniżej:

Bank 1		Bank 2	2
Bank 1	—►	Bank 3	4
Bank 1	—*	Bank 5	-3
Bank 2	—►	Bank 1	2
Bank 2	—*	Bank 3	8
Bank 2	—»	Bank 5	1
Bank 3	—►	Bank 1	6
Bank 3	—*	Bank 2	-2
Bank 3	—»	Bank 4	4
Bank 3	—*	Bank 5	3
Bank 4	—*	Bank 1	1
Bank 4	—*	Bank 5	5
Bank 5	-»	Bank 4	1

Zadanie 16

Mrówki postanowiły dokonać zapasów na najbliższą zimę. Mapa mrowiska została przedstawiona na poniższym rysunku.