10. Egzamin

Egzamin z AA2 ('ZWl-UL-W)

Zadanie l Obszar działania firmy transportowej obejmuje pewną liczbę miast, połączonych drogami (pomiędzy niektórymi miastami nie istnieje bezpośrednie połączenie i droga musi prowadzić przez inne miasta) Nad każdą drogą iuga się znajdować wiadukty, które są przeszkodą dla zbyt wysokich ciężarówek Firiii.i chce ii.sr.iln- niK-il/.y każdą parą miast taką trasę, dla której wysokość najniższego wiaduktu jest jak iiajwię!'~^i. Zaproponuj algorytm, który wyznaczy takie trasy między wszyskinń parami miast, na podstawie wy. sokusci luijniższego wiaduktu na każdej drodze. Podaj złożoność twojego algorytmu. Wskazówka: zastosuj piu!ii'.imowaiiiv dynamiczne.

Zadanie 2 Dali.. jest n.Lstfpująca gra. Dostępny jest stos kart, S, zawierających liczby od l du 9. Dwóch sraczy. .4 i D. i\'\'kuiiuie naprzemiennie ruchy (zaczyna gracz A). Ruchem gracza może być: • zrezygnowanie z wzięcia tej karty. • wzit-cit- kartv znajdującej się na szczycie stosu, ^ ^9S

i •leżeli

obydwaj gracze bezpośrednio po sobie zrezygnują z wzięcia karty, to gra się kończy. Gra kończy się również wtedy. gdy staś się wyczerpie. Po zakończeniu gry, gracze sumują liczby na kartach, które wzięli otrzymując suiny SA oraz S B- Wynikiem gry jest różnica R = SA - S B, która jest wypłatą przekazywaną graczowi A przez gracza B. Jeśli R jest liczbą ujemną, to oczywiście A wypłaca B kwotę \R\. Każdy z graczy dąży do zmaksymalizowania swojej wypłaty, tzn. A stara się, żeby R była jak największa, a B aby R była jak najmniejsza. Przykład l: Początkowa zawartość stosu to S = (2,4, l). Przykładowy przebieg partii: • .4 bierze kartę ze szczytu czyli 2 (zawartość stosu: S = (4, l)), • B bierze kartę ze szczytu czyli 4 (zawartość stosu: S = (l)), • A bierze kartę ze szczytu czyli l (zawartość stosu: 5 = ()), • gra się kończy ze względu na opróżnienie stosu. \\ r", m wypildku 5.4 = 2 + l = 3. SB = 4. R = SĄ - SB = 3 - 4 = -l, a więc gracz A wypłaca graczowi B kwotę l. Przykład 2: Początkowa zawartość stosu to S = (2,4, l). Przykładowy przebieg partii: • .4 bierne kartę ze szczytu czyli 2 (zawartość stosu: S = (4, l)), • B rezygnuje z wzięcia karty (zawartość stosu: S = (4. l)), • .4 rezygnuje z wzięcia karty (zawartość stosu: S = (4. l)), • ara -if kończy ze względu na to. że gracze bezpośrednio po sobie zrezygnowali z wzięcia karty. \V t\ ni wyp.idku SA = 2, SB = 0. R = SA - SB ss 2 - O = 2, a więc gracz B wypłaca graczowi .4 kwotę 2. Dla i .
Dziiii.mif .il^urytliiu ininiinax powinno zostać zilistrowane na drzewach y\'.