Please enable JavaScript.
Coggle requires JavaScript to display documents.
Dyskusja nad Problemem 4 "Łyżeczki", Wizualizacja Problemu…
Dyskusja nad Problemem 4 "Łyżeczki"
Ilość sposobów wyboru filiżanki
Możesz wybrać filiżankę na
trzy różne sposoby.
Ilość wyborów przyporządkowujących łyżeczkę do filiżanki
Na
każdą
filiżankę
możesz
wybrać
łyżkę
na
dwa
sposoby
.
Działanie
wynikające
z powyższych wniosków
To proste rozumowanie prowadzi do
odpowiedzi 3x2 = 6.
Wizualizacja Problemu Drugie podejście (I)
Diagram Drzewa
Schematy
tego rodzaju oraz
pojęcie drzew abstrakcyjnych
są szeroko
stosowane
w
matematyce
,
informatyce
i
innych dyscyplinach.
Terminologia drzew matematycznych
Korzystamy więc z okazji, aby
wprowadzić terminologię związaną z drzewami matematycznymi.
Katalog główny
Schemat
drzewa
rozpoczyna się od
pojedynczego
węzła
, nazywanego jego
katalogiem
głównym
.
Strzałki
Strzałki
prowadzą do
dodatkowych
węzłów
.
Węzły pierwszego poziomu
Węzły
, które są
bezpośrednio
połączone z
korzeniem
, nazywane są
węzłami pierwszego poziomu.
Węzły drugiego poziomu itd...
Węzły
połączone
z
węzłami
pierwszego
poziomu
nazywane są
węzłami drugiego poziomu
i tak dalej.
Pochodne węzła
Wszystkie
węzły
, które
pochodzą
z
określonego
węzła
, są nazywane
pochodnymi tego węzła
.
Liście
Węzły
, które
nie mają gałęzi
od nich pochodzących,
nazywane są liśćmi
.
Wizualizacja Problemu Drugie podejście (II)
Powrót do problemu 4
Teraz, gdy skończymy z terminologią, przedyskutujmy, jak powyższy diagram drzewa ilustruje
problem z herbaciarnią
.
Strategia wyboru
Ten diagram odzwierciedla
strategię
"
wybierz
najpierw
filiżankę
,
wybierz
łyżkę
następną
".
Początek procesu selekcji
Podstawa
drzewa
oznacza
początek
procesu
selekcji
.
Co oznaczają gałęzie?
Gałęzie
wychodzące z
korzenia
i
kończące
się w
węzłach
kubka
oznaczają
trzy możliwe sposoby wyboru filiżanki herbaty.
Sposoby wyboru łyżki
Gałęzie
pochodzące od
węzła kubkowego
odpowiadają wszystkim
możliwym
sposobom
wyboru
łyżki po wybraniu już filiżanki.
Wizualizacja Problemu Pierwsze podejście
Wniosek końcowy
Dlatego, aby obliczyć odpowiedź, powinniśmy zastosować tę samą operację, co w Problem 1:
powinniśmy pomnożyć 3 przez 2.
Na czym polega wizualizacja?
Polega na
przekształceniu
tego
problemu
w
znany
już
problem miast i dróg.
Wizualizacja Filiżanek na drodze :P
Wyobraźmy sobie, że
jadąc samochodem od A do C
,
bierzemy
filiżankę
na
odcinku A-B drogi
i
łyżkę
na odcinku
B-C drogi
. Następnie
każda inna trasa od A do C
odpowiada innej kombinacji typu kubek-łyżka.
Zatem
całkowita liczba możliwych kombinacji kubków i łyżek jest taka sama jak całkowita liczba różnych tras od A do C.
Jak będzie wyglądać konwersja dla tego przykładu?
Konwersja
jest
łatwa
: po prostu
bierzemy
mapę
z
Problemu
1
,
umieszczamy
inną
filiżankę
na
każdej
drodze
prowadzącej
z A do B
, i
inną łyżeczkę do herbaty na każdej drodze łączącej B i C:
Wizualizacja Problemu Drugie podejście (III)
Węzeł drugiego poziomu od nasady do łopatki
Każda
inna
kombinacja
łyżeczki
odpowiada
trasie
od nasady do łopatki
(
węzeł drugiego poziomu
).
Jak
obliczyć
liczbę
węzłów
drugiego
poziomu
?
Ponieważ
każdy węzeł
pierwszego
poziomu
generuje
dwa węzły drugiego poziomu
, ta
liczba
jest
dwa
razy
większa
od liczby
węzłów
pierwszego
poziomu
(
równej 3
). Dlatego, ku zaskoczeniu, otrzymujemy
tę samą formułę i tę samą odpowiedź: 3x2 = 6.
Wybory=liczba tras
Dlatego
liczba
sposobów
wyborów
jest
równa
całkowitej
liczbie
różnych
tras
od
węzła
głównego
do
węzłów
drugiego
poziomu
.
Liczba węzłów drugiego poziomu
Ta
liczba
z
kolei
jest
równa całkowitej liczbie węzłów drugiego poziomu.