Drzewka możliwości

Wyobraź sobie labirynt, w którym na każdym skrzyżowaniu wybierasz jedną z kilku dróg. Każda pełna trasa od wejścia do wyjścia oznacza jeden możliwy wynik. Drzewko możliwości działa dokładnie tak samo — porządkuje kolejne etapy wyboru.

Konkret: ścieżki kolejnych decyzji

• Rzucasz monetą dwa razy.
• Wybierasz bluzę, a potem spodnie.
• Tworzysz kod z kilku znaków.
• Losujesz kulę, a następnie wykonujesz kolejny wybór.

Reprezentacja: jak zbudować drzewko

• Zaczynasz od jednego punktu — początku doświadczenia.
• Dla każdego pierwszego wyboru rysujesz osobną gałąź.
• Z końca każdej gałęzi rysujesz możliwości następnego etapu.
• Pełna ścieżka od początku do końca oznacza jeden wynik.
• Liczba końcowych gałęzi odpowiada liczbie możliwości, jeśli wszystkie ścieżki są dozwolone.

Abstrakcja: połączenie z regułą mnożenia

Jeżeli na pierwszym etapie mamy a możliwości, a na drugim z każdej gałęzi b możliwości, to liczba końcowych ścieżek wynosi a·b. Drzewko jest więc obrazowym odpowiednikiem reguły mnożenia.

• Równa liczba rozgałęzień na każdym etapie prowadzi do prostego iloczynu.
• Różna liczba gałęzi wymaga zliczenia końcowych ścieżek osobno.
• Gałęzie niespełniające warunku można przekreślić lub pominąć.

FAJNY TRIK EDUKACYJNY

Zapamiętaj akronim D-R-Z-E-W-O: Dane etapy, Rysuj gałęzie, Zapisuj wyniki, Eliminuj niedozwolone, Wlicz końce, Oceń wynik. W pałacu pamięci rośnie gigantyczne neonowe drzewo. Każda decyzja powoduje huk i wystrzelenie nowych konarów, a na końcu każdej gałęzi świeci jeden wynik jak owoc. Niedozwolone wyniki zjada ogromna gąsienica. To pomaga pamiętać, że liczymy tylko końcowe, poprawne ścieżki.

Przykład krok po kroku: dwa rzuty monetą

Rzucamy monetą dwa razy. Ile jest możliwych uporządkowanych wyników?

• Krok 1: pierwszy rzut daje O lub R — 2 gałęzie.
• Krok 2: z każdej gałęzi znów wychodzą O i R.
• Krok 3: końcowe ścieżki to OO, OR, RO, RR.
• Wynik: są 4 możliwości.

Przykład krok po kroku: stroje

Masz 2 bluzy i 3 pary spodni. Ile strojów możesz utworzyć?

• Krok 1: rysujesz 2 gałęzie dla bluz.
• Krok 2: z każdej bluzy rysujesz 3 gałęzie dla spodni.
• Krok 3: powstaje 2·3=6 końcowych ścieżek.
• Wynik: można utworzyć 6 strojów.

Przykład krok po kroku: kod bez powtórzeń

Tworzymy dwucyfrowy kod z cyfr 1, 2, 3 bez powtórzeń.

• Krok 1: pierwsza cyfra — 3 gałęzie.
• Krok 2: z każdej gałęzi wychodzą tylko 2 pozostałe cyfry.
• Krok 3: otrzymujemy 12, 13, 21, 23, 31, 32.
• Wynik: istnieje 6 kodów.

Przykład krok po kroku: warunek dodatkowy

Rzucamy dwiema monetami. Ile wyników zawiera dokładnie jednego orła?

• Krok 1: wypisujemy ścieżki OO, OR, RO, RR.
• Krok 2: odrzucamy OO, bo ma dwa orły.
• Krok 3: odrzucamy RR, bo nie ma orła.
• Krok 4: zostają OR i RO.
• Wynik: są 2 takie wyniki.

Kiedy drzewko jest szczególnie pomocne?

• Gdy doświadczenie ma kilka etapów.
• Gdy liczba możliwości zmienia się po wcześniejszym wyborze.
• Gdy występują warunki dodatkowe.
• Gdy trzeba uniknąć pomijania lub podwójnego liczenia.

Najczęstsze błędy

• Brak gałęzi dla jednej z możliwości.
• Rysowanie tych samych wyników kilka razy.
• Nieuwzględnianie zakazu powtórzeń.
• Liczenie punktów pośrednich zamiast końcowych ścieżek.
• Zapominanie o odrzuceniu wyników niespełniających warunku.

Kontrola wyniku

• Sprawdź, czy z każdego węzła wychodzą wszystkie dozwolone możliwości.
• Przeczytaj każdą ścieżkę od początku do końca.
• Porównaj liczbę końcowych gałęzi z regułą mnożenia.
• Przy zakazie powtórzeń upewnij się, że liczba gałęzi maleje.
• Przy warunku dodatkowym zaznacz osobno ścieżki odrzucone.

Najczęstsze pytania