Matematyka Dyskretna
Andrzej Szepietowski
25 marca 2004 roku
Rozdział 1
Stosy, kolejki i drzewa
1.1 Listy
Lista to uporządkowany ciąg elementów. Przykładami list są tablice jednowymiarowe. W
tablicach mamy dostęp do dowolnego elementu, poprzez podanie indeksu tego elementu.
Przykład 1.1 W języku Pascal przykładem typu tablicy jednowymiarowej jest
array[1..N] of integer.
Jeżeli mamy zmienną tego typu
a:array[1..N] of integer,
to tablicaazawieraNelementów
a[1], a[2], ... ,a[N].
W programie możemy odwoływać się do całej tablicy, na przykład w instrukcji przypisania
a:=b,
lub do pojedynczych elementów:
a[i]:=a[i+1].
Możemy także używać tablic dwu lub więcej wymiarowych. Przykładem tablicy dwuwy-
miarowej jest typ
array[1..N,1..M] of real.
Zmienna
c:array[1..N,1..M] of real
zawiera N · M elementów. Dla każdej pary liczb i, j speÅ‚niajÄ…cej warunki 1 d" i d" N,
1 d" j d" M, elementc[i,j]zawiera liczbÄ™ typureal.
1.2 Stosy i kolejki
Czasami wygodniej posługiwać się listami bez używania indeksów. Przykładami list, któ-
rych można używać bez konieczności odwoływania się do indeksów poszczególnych ele-
3
4 Rozdział 1. Stosy, kolejki i drzewa
mentów, są kolejki i stosy.
Definicja 1.2 Kolejka jest listÄ… z trzema operacjami:
" dodawania nowego elementu na koniec kolejki,
" zdejmowania pierwszego elementu z poczÄ…tku kolejki,
" sprawdzania, czy kolejka jest pusta.
Taki sposób dodawania i odejmowania elementów jest określany angielskim skrótem
FIFO (first in first out, czyli pierwszy, który wszedł, pierwszy wyjdzie). Przykłady kolejek
spotykamy w sklepach, gdzie klienci czekający na obsłużenie tworzą kolejki.
Definicja 1.3 Stos jest listÄ… z trzema operacjami:
" dodawania elementu na wierzch stosu,
" zdejmowania elementu z wierzchu stosu,
" sprawdzania, czy stos jest pusty.
Na stosie dodajemy i odejmujemy elementy z tego samego końca, podobnie jak w
stosie talerzy spiętrzonym na stole. Talerze dokładane są na wierzch stosu i zdejmowane
z wierzchu stosu. Taka organizacja obsługi listy określana jest angielskim skrótem LIFO
(last in first out, czyli ostatni, który wszedł, pierwszy wyjdzie). Niektórzy w ten sposób
organizują pracę na biurku. Przychodzące listy układają na stosie i jak mają czas, to zdej-
mujÄ… jeden list i odpowiadajÄ… na niego.
Przyjrzyjmy się zastosowaniu kolejki lub stosu do szukania. Przypuśćmy, że szukamy
przez telefon pewnej informacji (na przykład chcielibyśmy się dowiedzieć, kto z naszych
znajomych ma pewną książkę).
Algorytm szukania książki wśród znajomych
tworzymy STOS, który na początku jest pusty,
wkładamy na STOS numery telefonów swoich znajomych,
dopóki na stosie są jakieś numery, powtarzamy:
zdejmujemy z wierzchu STOSU jeden numer telefonu,
dzwonimy pod ten numer,
jeżeli osoba, do której się dodzwoniliśmy, posiada szukaną książkę,
to koniec poszukiwań,
w przeciwnym przypadku
pytamy ją o znajomych, którzy mogą mieć książkę
numery tych znajomych sÄ… dopisywani na STOS.
W powyższym algorytmie zamiast stosu może być użyta kolejka.
1.3. Implementacja stosu 5
1.3 Implementacja stosu
W wielu językach programowania stosy i kolejki nie występują jako standardowe struktu-
ry danych. W tym i następnym podrozdziale pokażemy jak można je utworzyć za pomocą
tablic.
Tworzymy tablicÄ™
ST OS[0..max]
oraz zmienna W ierzchStosu. W tablicy przechowujemy elementy stosu. Element ST OS[0]
leży na dnie stosu, a kolejne elementy nad nim. Zmienna W ierzchStosu wskazuje na
pierwsze wolne miejsce w tablicy ST OS. W pustym stosie W ierzchStosu = 0. Opera-
cja włożenia nowego elementu x na ST OS implementujemy za pomocą instrukcji:
ST OS[W ierzchStosu] := x;
W ierzchStosu := W ierzchStosu + 1;
Tak skonstruowany stos może pomieścić co najwyżej max + 1 elementów. Jeżeli
W ierzchStosu = max + 1, to stos jest pełny i nie można na niego wkładać nowych
elementów. Operacja zdejmowania elementu z wierzchu ST OSU implementujemy za
pomocÄ… instrukcji:
W ierzchStosu := W ierzchStosu - 1;
x := ST OS[W ierzchStosu];
Operację tą można wykonać, jeżeli stos nie jest pusty, to znaczy jeżeli W ierzchStosu >
0.
1.4 Implementacja kolejki
Kolejkę też można utworzyć za pomocą tablicy. W tym celu deklarujemy tablicę
KOLEJKA[0...max]
oraz dwie zmienne P oczatekKolejki, KoniecKolejki. W tablicy przechowujemy ele-
menty kolejki. Zmienna P oczatekKolejki wskazuje na pierwsze element kolejki, a zmien-
na KonieckKolejki na pierwsze wolne miejsce za kolejką. Kolejka jest pusta, jeże-
li P oczatekKolejki = KonieckKolejki. Operacja włożenia nowego elementu x do
KOLEJKI implementujemy za pomocą dwóch instrukcji:
KOLEJKA[KoniecKolejki] := x;
KoniecKolejki := KoniecKolejki + 1;
Operacja zdejmowania elementu z końca KOLEJKI implementujemy za pomocą in-
strukcji:
x := KOLEJKA[P oczatekKolejki];
P oczatekKolejki := P oczatekKolejki + 1;
6 Rozdział 1. Stosy, kolejki i drzewa
Ta operacja może być wykonana, jeżeli kolejka nie jest pusta, to znaczy jeżeli P oczatekKolejki =

KoniecKolejki;
Aby lepiej wykorzystać tablicę KOLEJKA, należy zapełniać ją cyklicznie. To zna-
czy po dojściu do końca (miejsca max - 1) dalsze elementy wstawiamy na początek
(jeżeli zwolniły się tam miejsca po zdjęciu elementów). Trzeba tylko zadbać, żeby za
ostatni elementem w kolejce było przynajmniej jedno wolne miejsce. Operacje na kolejce
przedstawiają się teraz następująco:
" Jeżeli (KoniecKolejki+1) mod (max + 1) = P oczatekKolejki, to KOLEJKA
jest pełna.
" Jeżeli KoniecKolejki = P oczatekKolejki, to KOLEJKA jest pusta.
" Wstawianie nowego elementu x na koniec kolejki implementujemy za pomocÄ… in-
strukcji:
KOLEJKA[KoniecKolejki] := x;
KoniecKolejki := (KoniecKolejki + 1) mod (max + 1);
" Zdejmowanie ostatniego elementu x z poczÄ…tku kolejki implementujemy za pomo-
cÄ… instrukcji:
x := KOLEJKA[P oczatekKolejki];
P oczatekKolejki := (P oczatekKolejki + 1) mod (max + 1);
1.5 Drzewa ukorzenione
Przypomnijmy, że drzewo ukorzenione to drzewo z wyróżnionym jednym wierzchołkiem,
korzeniem. Każdy wierzchołek v różny od korzenia jest z nim połączony dokładnie jedną
drogą prostą. Sąsiad leżący na drodze do korzenia nazywamy ojcem wierzchołka v. Poza-
stali sąsiedzi są synami wierzchołka v. Korzeń drzewa nie ma ojca, wszyscy jego sąsiedzi
są jego synami. Wierzchołek, który nie posiada syna nazywamy liściem.
1.6 Drzewa binarne
Drzewa binarne to takie drzewa ukorzenione, w których każdy wierzchołek ma co naj-
wyżej dwóch synów. Do oznaczania wierzchołków w drzewie binarnym wygodnie jest
używać ciągów zer i jedynek, czyli elementów zbioru {0, 1}". Wierzchołki drzewa ozna-
czamy w następujący sposób:
" korzeń drzewa oznaczamy przez   pusty ciąg,
" jeżeli jakiś wierzchołek jest oznaczony przez x, to jego synowie oznaczeni są przez
x0 i x1.
1.6. Drzewa binarne 7
Rysunek 1.1: Przykład drzewa binarnego

0 1
00 01 10 11
110 111
Przy takim oznaczeniu wierzchołków drzewa binarnego nazwa wierzchołka x mówi
nam, jaka ścieżka prowadzi od korzenia do x. Na przykład, aby dojść od korzenia do
wierzchołka 110 nalezy: pójść w prawo do 1, potem znowu w prawo do 11, a na końcu
w lewo do 110. Jeżeli mamy drzewo binarne T , to z każdym wierzchołkiem x możemy
skojarzyć poddrzewo Tx złożone z wierzchołka x i wszystkich jego potomków. Na przy-
kład w drzewie przedstawionym na rysunku 1.1 wierzchołek x = 1 wyznacza poddrze-
wo Tx przedstawione na rysunku 1.2. Mówimy też, że drzewo Tx składa się z korzenia
Rysunek 1.2: Poddrzewo T1
1
10 11
110 111
(wierzchołka x), z lewego poddrzewa Tx0 i z prawego poddrzewa Tx1. Wysokością drze-
wa nazywamy długość (liczbę krawędzi) najdłuższej ścieżki w drzewie prowadzącej od
korzenia do liścia. Na przykład drzewo z rysunku 1.1 jest wysokości 3.
8 Rozdział 1. Stosy, kolejki i drzewa
1.7 Drzewa wyrażeń arytmetycznych
Przykładem zastosowania drzew binarnych są drzewa wyrażeń arytmetycznych. Najpierw
przykład. Na rysunku 1.3 przedstawiono drzewo wyrażenia 2a+3/d. W drzewie tym każ-
dy wierzchołek ma etykietę. Liście etykietowane są stałymi albo zmiennymi. Wierzchołki
nie będące liśćmi etykietowane są operacjami arytmetyczymi. Każdemu wierzchołkowi
w drzewie możemy przypisać wyrażenie arytmetyczne według następującej zasady:
" dla liści wyrażeniami są etykiety tych liści (stałe lub zmienne),
" jeżeli wierzchołek x ma etykietę op, a jego synom przypisano wyrażenia W (x0) i
W (x1), to wierzchołkowi x przypisujemy wyrażenie W (x) = (W (x0) op W (x1)).
Rysunek 1.3: Drzewo wyrażenia 2a + 3/d
+
· /
2 a 3 d
PrzykÅ‚ad 1.4 W drzewie z rysunku1.3 wierzchoÅ‚kowi z etykietÄ… · odpowiada wyrażenie
2 · a, wierzchoÅ‚kowi z etykietÄ… / wyrażenie 3/d, a korzeniowi wyrażenie
((2 · a) + (3/d)).
Wyrażenie to zawiera więcej nawiasów, niż to się zwykle stosuje. Normalnie to samo wy-
rażenie przedstawiamy bez nawiasów w postaci 2a + 3/d.
Opuszczenie nawiasów może prowadzić do niejednoznaczności lub może zmienić
sens wyrażenia. Na przykład wyrażenie
2(a + 3/d)
po opuszczeniu nawiasów stanie się identyczne z wyrażeniem 2a + 3/d i zmieni sens.
Drzewo, które odpowiada wyrażeniu 2(a + 3/d), przedstawiono na rysunku 1.4.
Drzewo wyrażenia arytmetycznego oddaje logiczną strukturę i sposób obliczania tego
wyrażenia.
1.7. Drzewa wyrażeń arytmetycznych 9
Rysunek 1.4: Drzewo wyrażenia 2(a + 3/d)
·
2 +
a /
3 d
Istnieje sposób przedstawiania wyrażeń arytmetycznych nie wymagający nawiasów.
Jest to tak zwana notacja polska lub A
ukasiewicza. Jest ona też nazywana notacją postfi-
xową, ponieważ znak operacji stoi na końcu wyrażenia, za argumentami, czyli wyrażenie
w notacji postfixowej ma postać:
pierwszy argument  drugi argument  operacja.
Notacja, do jakiej jesteśmy przyzwyczajeni, nazywa się infixowa, ponieważ operacja znaj-
duje się pomiędzy argumentami, czyli wyrażenie w notacji infixowej ma postać:
pierwszy argument  operacja  drugi argument.
Przykład 1.5 Wyrażenie w postaci postfixowej
2, a+
ma w postaci infixowej postać
2 + a,
a wyrażenie
2, a · 3, d/+
jest postfixową postacią wyrażenia
2a + 3/d.
W wyrażeniach w postaci postfixowej nie potrzeba nawiasów. Wartość wyrażenia można
w sposób jednoznaczny odtworzyć z samego wyrażenia za pomocą następującego algo-
rytmu.:
10 Rozdział 1. Stosy, kolejki i drzewa
Algorytm obliczania wartości wyrażenia w postaci postfixowej.
Dla kolejnych elementów zapisu wyrażenia:
jeżeli element jest stałą lub zmienną, to
wkładamy jego wartość na stos,
jeżeli element jest znakiem operacji, to:
zdejmujemy dwie wartości z wierzchu stosu,
wykonujemy operację na tych wartościach,
obliczoną wartość wkładamy na wierzch stosu.
Po przejściu całego wyrażenia jego wartość znajduje się na stosie.
Przykład 1.6 Zademonstrujmy ten algorytm na przykładzie wyrażenia:
abc + · de/+
Załóżmy, że zmienne mają następujące wartości: a = 3, b = 2, c = 1, d = 4, e = 2.
Poniższa tabela przedstawia zawartość stosu po przeczytaniu kolejnych elementów wyra-
żenia.
czytany element stos
a 3,
b 3, 2,
c 3, 2, 1,
+ 3, 3,
· 9,
d 9, 4,
e 9, 4, 2,
/ 9, 2,
+ 11.
1.8 Przeszukiwanie drzew binarnych
Zajmiemy siÄ™ teraz dwoma algorytmami przeszukiwania drzew (binarnych): przeszuki-
wanie w głąb i wszerz. Różnią się one rodzajem użytych struktur danych. W algorytmie
przeszukiwania w głąb użyjemy stosu, a w algorytmie przeszukiwania wszerz użyjemy
kolejki.
1.8.1 Przeszukiwanie drzewa w głąb
Algorytm przeszukiwania drzewa w głąb.
Dane wejściowe: drzewo T .
Odwiedzamy korzeń  i wkładamy go na STOS;
dopóki STOS nie jest pusty, powtarzamy:
Niech v będzie wierzchołkiem na wierzchu STOSU,
1.8. Przeszukiwanie drzew binarnych 11
sprawdzamy, czy istnieje syn u wierzchołka v, który nie był jeszcze odwiedzony,
jeżeli takie u się znajdzie, to
odwiedzamy u i wkładamy go na wierzch STOSU,
jeżeli takiego u nie ma, to
zdejmujemy v ze STOSU;
cofamy się do wierzchołka będącego na stosie pod spodem.
Algorytm powinien dodatkowo zapamiętywać, jaki wierzchołek był ostatnio zdjęty ze
stosu. Pozwala to stwierdzić, który z synów wierzchołka znajdującego się na stosie pod
spodem należy teraz rozpatrzeć.
Przykład 1.7 Poniższa tabela pokazuje jaki wierzchołek jest odwiedzany i jaka jest za-
wartość stosu po każdej kolejnej iteracji pętli algorytmu, gdy przeszukiwane jest drzewo
z rysunku 1.1.
Wierzchołek STOS
 
0 ,0
00 ,0,00
0 ,0
01 ,0,01
0 ,0
 
1 ,1
10 ,1,10
1 ,1
11 ,1,11
110 ,1,11,110
11 ,1,11
111 ,1,11,111
11 ,1,11
1 ,1
 
W metodzie przeszukiwania w głąb po każdym kroku algorytmu wierzchołki znajdują-
ce się na stosie tworzą ścieżkę od wierzchołka wejściowego do wierzchołka aktualnie
odwiedzanego.
1.8.2 Przeszukiwanie drzewa wszerz
Następny algorytm przeszukiwania drzew używa kolejki jako pomocniczej struktury da-
nych.
Algorytm przeszukiwania wszerz.
Dane wejściowe: drzewo T .
12 Rozdział 1. Stosy, kolejki i drzewa
Odwiedzamy korzeń drzewa  i wkładamy go do KOLEJKI.
Dopóki KOLEJKA nie jest pusta, powtarzamy:
bierzemy jeden wierzchołek v z początku KOLEJKI,
odwiedzamy wszystkich synów wierzchołka v
każdego wkładamy na koniec kolejki.
Poniżej przedstawiono odwiedzane wierzchołki oraz zawartość kolejki po każdej kolejnej
iteracji pętli algorytmu przeszukiwania wszerz drzewa przedstawionego na rysunku 1.1.
wierzchołki KOLEJKA
 
0,1 0,1
00,01 1,00,01
10,11 00,01,10,11
- 01,10,11
- 10,11
- 11
110,111 110,111
- 111
- -
W metodzie przeszukiwania wszerz wierzchołki są przeszukiwane w kolejności od wierz-
chołków będących najbliżej wierzchołka początkowego do wierzchołków będących dalej.
1.9 Drzewa decyzyjne
Rysunek 1.5 przedstawia drzewo decyzyjne dla pewnego sposobu posortowania trzech
elementów a, b, c, które pochodzą z jakiegoś uporządkowanego zbioru. W korzeniu drze-
wa porównujemy elementy a i b. Jeżeli a < b, to idziemy do następnego wierzchołka w
lewo wzdłuż krawędzi z etykietą <. Jeżeli a > b, to idziemy w prawo wzdłuż krawędzi z
etykietą >. Podobnie postępujemy w innych wierzchołkach wewnętrznych. Liście drzewa
odpowiadają ostatecznym decyzjom i mówią jak należy uporządkować elementy a, b i c,
aby tworzyły one ciąg rosnący. Drzewo z rysunku 1.5 opisuje pewien sposób postępowa-
nia. Jak widać ten sposób wymaga maksymalnie trzech porównań. Można zadać pytanie,
czy istnieje inny schemat postępowania wymagający mniej porównań. Aby odpowiedzieć
na to pytanie, przypuśćmy, że na zmienne a, b, c podstawiamy wartości kolejnych permu-
tacji Ą zbioru {1, 2, 3}. Zauważmy, że każda permutacja Ą powinna prowadzić do innego
liÅ›cia. RzeczywiÅ›cie, przypuśćmy bowiem, że mamy dwie różne permutacje Ä„ i Ä, które
prowadzą do tego samego liścia. Ponieważ prowadzi je do tego samego liścia, to będą
one tak samo posortowane. Ale z drugiej strony, ponieważ są one różne więc istnieją
1 d" i < j d" 3 takie, że Ä„(i) < Ä„(j) i Ä(i) > Ä(j). Z czego wynika, że nie powinny
one być tak samo posortowane. Tak więc drzewo dowolnego schematu sortującego trzy
elementy musi mieć 6 = 3! liści i głębokość co najmniej 3.
Drzewo decyzyjne z rysunku 1.6 przedstawia schemat postępowania w następującym
problemie. Mamy trzy monety a, b, c. Jedna z nich jest fałszywa, to znaczy trochę cięższa
1.9. Drzewa decyzyjne 13
Rysunek 1.5: Drzewo decyzyjne
a?b
< >
b?c a?c
< > < >
abc a?c bac b?c
< > < >
acb cab bca cba
Rysunek 1.6: Drzewo decyzyjne
a?b
< = >
a?c a?c a?c
< = < > = >
a- b+ c+ c- b- a+
14 Rozdział 1. Stosy, kolejki i drzewa
lub trochę lżejsza od dwóch pozostałych. Schemat pokazuje jak za pomocą wagi szalko-
wej bez odważników znalez
ć fałszywą monetę. W korzeniu na lewej szalce kładziemy
monetą a, na prawej b. Jeżeli a okaże się lżejsz od b, to idziemy w dół wzdłuż krawędzi
z etykietą <. Jeżeli a jest ciższa od b, idziemy wzdłuż krawędzi >, a jeżeli szalki będą
w równowadze, to idziemy wzdłuż krawędzi =. W innych wewnętrznych wierzchołkach
postępujemy podobnie. W liściach mamy ostateczne decyzje, która moneta jest fałszywa,
oraz czy jest ona cięższa (znak +), czy lżejsza (znak -).
1.10 Drzewo gry
Rozważmy następującą grę. Mamy trzy kupki kamyków. Gracze po kolei zabierają ka-
mienie z kupek, przy czym wolno brać kamienie tylko z jednej kupki i oczywiście jakieś
kamienie trzeba zabrać. Gra ta jest podobna do gry rozważanej w rozdziale o funkcjach
boolowskich, tylko inna jest zasada, kto wygrywa. Teraz przegrywa gracz, który zabiera
ostatnie kamienie.
Rysunek 1.7: Drzewo gry
1(2, 1)
2(1, 1) 2(2, 0) 2(0, 1)
1(1, 0) 1(1, 0) 1(0, 0) 1(0, 0)
2(0, 0) 2(0, 0)
Rysunek 1.7 przedstawia drzewo dla tej gry. Dla uproszczenia przyjęto, że są tylko
dwie kupki, w jednej są dwa kamienie, a w drugiej jeden. Wierzchołki drzewa posiadają
etykiety postaci x(y, z); gdzie x oznacza, czyja jest kolej na wykonanie ruchu, pierwsze-
go czy drugiego gracza; y i z oznaczajÄ… liczby kamieni w kupkach. W korzeniu pierwszy
gracz ma ruch, na kupkach są 2 i 1 kamień. Trzej synowie korzenia odpowiadają sytu-
acjom po wykonaniu pierwszego ruchu. W liściach mamy puste kupki.
1.10. Drzewo gry 15
Rysunek 1.8: Drzewo gry z waluacjÄ…
1(2, 1)+
2(1, 1)- 2(2, 0)- 2(0, 1)+
1(1, 0)- 1(1, 0)- 1(0, 0)+ 1(0, 0)+
2(0, 0)- 2(0, 0)-
Każdemu wierzchołkowi drzewa przypisujemy teraz wartość 1 lub -1, w zależności
czy jest to konfiguracja wygrywajÄ…ca, czy przegrywajÄ…ca dla pierwszego gracza. Przypi-
sywanie wartości zaczynamy od liści. Jeżeli w liściu ruch ma pierwszy gracz, to nadajemy
mu wartość 1, ponieważ wygrał on grę, przed chwilą drugi gracz zabrał ostatnie kamienie.
Jeżeli ruch należy do drugiego gracza, to liść dostaje wartość -1. Następnie nadajemy war-
tości wewnętrznym wierzchołkom. Jeżeli wszyscy synowie jakiegoś wierzchołka v mają
już wartości, to można przypisać wartość wierzchołkowi v. Jeżeli ruch ma pierwszy gracz,
to wierzchołkowi v nadajemy wartość równą największej wartości synów v. Jeżeli ruch
należy do drugiego gracza, to bierzemy minimum. Na rysunku 1.8 zaznaczono wartości
wszystkich wierzchołków. Znak + oznacza wartość +1, znak - wartość -1. Korzeń ma
wartość +1, co oznacza, że gracz pierwszy może wygrać tą grę. Powinien w pierwszym
ruchu przejść do wierzchołka z wartością 1 (w tym wypadku do trzeciego syna).
1.10.1 Algorytm waluacji drzewa gry
Opiszemy teraz algorytm, który oblicza wartości wszystkich wierzchołków w drzewie
gry. Używając stosu będzie on przeszukiwał w głąb drzewo gry. Elementy na stosie są
następującej postaci:
x = (cr(x), konf(x), war(x), nr(x)),
gdzie
16 Rozdział 1. Stosy, kolejki i drzewa
" cr(x) oznacza, czyj ruch,
" konf(x) oznacza konfigurację kamieni, czyli ile kamieni jest w poszczególnych
kupkach.
" war(x) oznacza wartość wierchołka,
" nr(x) oznacza, numer następnego do rozpatrzenia ruchu.
Algorytmu waluacji drzewa gry
Tworzymy elemenet dla konfiguracji rozpoczynaąjcej grę i wkładamy go na stos.
Dopóki stos nie jest pusty
obrabiamy element x z na wierzchu stosu.
Procedura obróbki elementu x z wierzchu stosu
Jeżeli element x jest liściem, to:
nadajemy mu wartość według zasady:
jeżeli cr(x) = 2, to war(x) := -1,
jeżeli cr(x) = 1, to war(x) := 1,
zdejmujemy x ze stosu.
Jeżeli poprzednią operacją na stosie było zdjęcie elementu z, to:
uaktualniamy wartość war(x) według zasady:
Jeżeli cr(x) = 1, to war(x) := max(war(x), war(z)).
Jeżeli cr(x) = 2, to war(x) := min(war(x), war(z)).
Jeżeli można wykonać następny ruch (z numerem nr(x)), to
tworzymy nowy element y z polami:
cr(y) := 3 - cr(x);
konf(y) := conf(x) po wykonaniu ruchu nr(x);
jeżeli cr(y) = 2, to war(y) := 1,
jeżeli cr(y) = 1), to war(y) = -1.
nr(y) := 1.
nr(x) := nr(x) + 1
wkładamy element y na stos (element x nie jest zdejmowany ze stosu i y jest kładzione na nim.
Jeżeli ruchu o numerze nr(x) nie można wykonać, to
zdejmujemy x ze stosu.
Pierwszy element odpowiadajÄ…cy poczÄ…tkowej konfiguracji jest ze stosu zdejmowany
na samym końcu. Jego wartość w chwili zdjęcia ze stosu jest końcową wartością. Jeżeli
jest ona równa 1, to gracz pierwszy posiada w tej grze strategię wygrywającą. Strategia ta
polega na wybieraniu takiego ruchu, który w drzewie gry prowadzi do stanu z największą
wartością.
W czasie algorytmu waluacji całe drzewo nie jest zapamiętywane. Nawet dla niewiel-
kiej gry może ono być bardzo duże. W każdym momencie pamiętana jest na stosie tylko
ścieżka od korzenia do bieżącej konfiguracji. Aby wiedzieć jak pierwszy gracz powinien
grać, dobrze jest zapamiętywać numer ruchu, który prowadzi z korzenia do elementu z
1.10. Drzewo gry 17
wartością 1. Dla innych elementów taka informacja nie może być zapamiętywana, bo wy-
magałoby to zbyt duęj pamięci. Dlatego po wykonaniu pierwszego ruchu i po odpowiedzi
drugiego gracza pierwszy gracz musi znowu obliczać wartosc dla bieżącej konfiguracji.
Przykład 1.8 Zobaczmy jaka będzie zawartość stosu po kolejnych krokach algorytmu
waluacji dla gry opisanej wyżej. Zaczynamy od konfiguracji początkowej
" [1, (2, 1), -1, 1], która odpowiada początkowi gry. Przypominamy, że pierwsza je-
dynka oznacza, że ruch należy do pierwszego gracza, para (2, 1) oznacza konfigurację
kamieni, -1 jest wstępną waluacją korzenia gry, a ostatnia jedynka oznacza, że następny
do rozpatrzenia jest pierwszy syn. Po trzech kolejnych iteracjach głównej pętli algorytmu
stos wygląda następująco:
" [1, (2, 1), -1, 2] [2, (1, 1), +1, 1]
" [1, (2, 1), -1, 2] [2, (1, 1), +1, 2] [1, (1, 0), -1, 1]
" [1, (2, 1), -1, 2] [2, (1, 1), +1, 2] [1, (1, 0), -1, 2] [2, (0, 0), +1, 1]
Ostatni element na stosie jest liściem. Można teraz obliczyć jego wartość -1.
" [1, (2, 1), -1, 2] [2, (1, 1), +1, 2] [1, (1, 0), -1, 2] [2, (0, 0), +1, -1]
W następnych iteracjach zdejmowane są kolejne elementy ze stosu:
" [1, (2, 1), -1, 2] [2, (1, 1), +1, 2] [1, (1, 0), -1, 2]
" [1, (2, 1), -1, 2] [2, (1, 1), -1, 2]
" [1, (2, 1), -1, 2]
Nastąpił powrót do korzenia. Teraz rozważany będzie drugi ruch w konfiguracji począt-
kowej.
" [1, (2, 1), -1, 3] [2, (2, 0), +1, 1]
" [1, (2, 1), -1, 3] [2, (2, 0), +1, 2] [1, (1, 0), -1, 1]
" [1, (2, 1), -1, 3] [2, (2, 0), +1, 2] [1, (1, 0), -1, 2] [2, (0, 0), +1, 1]
Ostatni element na stosie jest liściem. Obliczamy jego wartość -1.
" [1, (2, 1), -1, 3] [2, (2, 0), +1, 2] [1, (1, 0), -1, 2] [2, (0, 0), +1, -1]
W następnych krokach zdejmowane są kolejne elementy ze stosu:
" [1, (2, 1), -1, 3] [2, (2, 0), +1, 2] [1, (1, 0), -1, 2]
" [1, (2, 1), -1, 3] [2, (2, 0), -1, 3]
Nastąpił powrót do drugiego syna konfiguracji początkowej. Teraz rozpatywany będzie
drugi ruch z tej konfiguracji.
" [1, (2, 1), -1, 3] [2, (2, 0), -1, 3] [1, (0, 0), -1, 1]
Znowu dotarliśmy do liścia; jego wartość wunosi +1.
" [1, (2, 1), -1, 3] [2, (2, 0), -1, 3] [1, (0, 0), -1, 1]
Zdejmujemy dwa elementy ze stosu
" [1, (2, 1), -1, 3] [2, (2, 0), -1, 3]
" [1, (2, 1), -1, 3]
Znowy jesteśmy w korzeniu drzewa. Do rozpatrzenia został trzeci ruch
" [1, (2, 1), -1, 4] [2, (1, 0), -1, 1]
" [1, (2, 1), -1, 4] [2, (1, 0), +1, 1] [1, (0, 0), -1, 1]
Znowu dotarliśmy do liścia; jego wartość wynosi +1
" [1, (2, 1), -1, 4] [2, (1, 0), +1, 1] [1, (0, 0), -1, 1]
Teraz zostaną po kolei zdjęte wszystkie elementy ze stosu
" [1, (2, 1), -1, 4] [2, (1, 0), +1, 1]
18 Rozdział 1. Stosy, kolejki i drzewa
" [1, (2, 1), +1, 4]
Koniec pracy algorytmu; ostateczna wartość korzenia wynosi +1.
1.11 Zadania
1. Ile wierzchołków może mieć drzewo binarne wysokości h?
2. Przeszukaj metodą  w głąb ( wszerz ) drzewo z rysunku ??.
3. Narysuj drzewo dla wyrażenie 2(a + 3)/(b + 4). Przedstaw to wyrażenie w postaci
postfixowej i prefixowej.
4. Narysuj drzewo dla wyrażenie 2, 3+5/7"3, 1-". Przedstaw to wyrażenie w postaci
infixowej i prefixowej. Oblicz wartość tego wyrażenia. Przedstaw to wyrażenie w
postaci infixowej i prefixowej.
5. Udowodnij, że każde pełne drzewo binarne o n liściach ma n - 1 wierzchołków
wewnętrznych. Drzewo binarne nazywa się pełne, jeżeli każdy jego wierzchołek
ma albo dwóch synów, albo nie ma synów wcale (jest liściem).
6. Narysuj drzewo decyzyjne dla sortowania czterech elementów.
7. Jak implementować drzewo binarne za pomocą tablic.
1.12 Problemy
1.12.1 Szukanie fałszywej monety
1. Zaprojektuj drzewo decyzyjne dla szukania jednej fałszywej spośród 9 monet, jeżeli
wiadomo, że fałszywa moneta jest lżejsza.
2. Opisz jak za pomocą k ważeń wyszukać lżejszą spośród 3k monet.
3. Zaprojektuj drzewo decyzyjne dla szukania jednej fałszywej (lżejszej lub cięzszej)
spośród monet a, b, c i d, jeżeli mamy dodatkowo do dyspozycji dobrą monetę x.
4. Pokaż, że jeżeli mamy dodatkowe dobre monety, to za pomocą k ważeń możemy
zidentyfikować fałszywą monetę (i powiedzieć, czy jest lżejsza, czy cięższa) dla co
(3k-1)
najwyżej monet.
2
5. Pokaż, że jeżeli nie mamy dodatkowych monet, to za pomocą k ważeń możemy
(3k-3)
zidentyfikować fałszywą monetę dla co najwyżej monet.
2