Kombinatorično drevo

Kombinatorično drevo

Avtor: E-um (vsebinsko), Skupina NAUK (tehnično)

Več o projektu...

Uvod

Pri šahovskem dvoboju imamo več možnih potekov dogajanja, saj se lahko vsaka partija konča z zmago enega ali drugega šahista ali pa z remijem. Če začnemo vse možne poteke kar brezglavo naštevati, se zelo hitro izgubimo. Poglejmo, kako v tem in podobnih primerih sistematično prikažemo vse možnosti.


Ali si že kdaj pomislil, na koliko različnih načinov lahko razdeliš karte za igro pokra, zložiš zgoščenke na polico, posedeš prijatelje na zabavi za rojstni dan, razporediš sošolce v vrsto za malico ali izbereš jedilnik na slavnostnem kosilu? S temi in podobnimi problemi se pogosto srečujemo v vsakdanjem življenju. Z njimi pa se ukvarja področje matematike, ki ga imenujemo kombinatorika.


 
Kombinatorika je matematično področje, ki raziskuje število možnih razporeditev ali izborov danih elementov (ljudi, knjig, kart, oblačil ...).


V nadaljevanju bomo spoznali, kako sistematično uredimo vse možne razporeditve ali izbore danih elementov.

Urnik

Timi ima na urniku tri šolske ure: matematiko, kemijo in geografijo. S kombinatoričnim drevesom predstavimo vse možne razporeditve šolskih ur.

Aplikacija RiŠ se ni mogla zagnati. Prosim preverite, ali imate v brskalniku namescen program Java 1.4.2 (ali novejsi) (Kliknite tu za namestitev Jave)

Riš datoteka

Dodatna razlaga

Dodatna razlaga

Najprej ugotovimo, koliko je možnosti za izbiro predmeta za prvo šolsko uro. Ker imamo tri predmete, je lahko prvo šolsko uro na urniku kateri koli od teh treh predmetov. Torej rastejo iz "korenin" drevesa tri veje: "matematika", "kemija" in "geografija". Za drugo šolsko uro imamo na izbiro različne možnosti, odvisno od tega, kateri predmet je bil na urniku prvo šolsko uro. Tako rasteta iz veje "matematika" veji "kemija" in "geografija", iz veje "kemija" veji "matematika" in "geografija" in iz veje "geografija" veji "matematika" in "kemija". Tretjo šolsko uro je na urniku tisti predmet, ki ga še ni bilo: kjer sta na poti od "korenin" do vrha drevesa veji "matematika" in "kemija", raste še veja "geografija" itd. Te veje pomenijo tretjo učno uro na Timijevem urniku. (Število različnih razporeditev danih predmetov je enako številu načinov, na katere lahko pridemo od "korenin" kombinatoričnega drevesa do skrajnih vej. Teh je v našem primeru .)

Urejanje izložbe

Živa ureja izložbo otroške trgovine. Izbira lahko med štirimi igračami: medvedkom, avtomobilčkom, kocko in vlakcem. Odločila se je, da bo razstavila le tri igrače, in sicer tako, da bo vlakec stal na sredini med drugima razstavljenima igračama. S kombinatoričnim drevesom predstavimo vse možne razporeditve igrač v izložbenem oknu.

Aplikacija RiŠ se ni mogla zagnati. Prosim preverite, ali imate v brskalniku namescen program Java 1.4.2 (ali novejsi) (Kliknite tu za namestitev Jave)

Riš datoteka

Urejanje izložbe

Odgovori na naslednja vprašanja.



1. Na koliko različnih načinov lahko Živa razstavi igrače?


Preveri

Pravilno

Tako je. Živa lahko razstavi igrače na enega od naslednjih načinov:

- medvedek, vlakec, avtomobilček,
- medvedek, vlakec, kocka,
- avtomobilček, vlakec, medvedek,
- avtomobilček, vlakec, kocka,
- kocka, vlakec, medvedek ali
- kocka, vlakec, avtomobilček.

Rešitev

Na različnih načinov.
Živa lahko razstavi igrače na enega od naslednjih načinov:

- medvedek, vlakec, avtomobilček,
- medvedek, vlakec, kocka,
- avtomobilček, vlakec, medvedek,
- avtomobilček, vlakec, kocka,
- kocka, vlakec, medvedek ali
- kocka, vlakec, avtomobilček.

Napačno

Pomagaj si z aplikacijo.

Aplikacija RiŠ se ni mogla zagnati. Prosim preverite, ali imate v brskalniku namescen program Java 1.4.2 (ali novejsi) (Kliknite tu za namestitev Jave)

Riš datoteka

Urejanje izložbe

2. V koliko primerih Živa razstavi medvedka?


Preveri

Pravilno

Tako je. Medvedka lahko razstavi v naslednjih razporeditvah:

- medvedek, vlakec, avtomobilček,
- medvedek, vlakec, kocka,
- avtomobilček, vlakec, medvedek in
- kocka, vlakec, medvedek.

Napačno

Pomagaj si z aplikacijo.

Aplikacija RiŠ se ni mogla zagnati. Prosim preverite, ali imate v brskalniku namescen program Java 1.4.2 (ali novejsi) (Kliknite tu za namestitev Jave)

Riš datoteka

Rešitev

V primerih.
Medvedka lahko razstavi v naslednjih razporeditvah:

- medvedek, vlakec, avtomobilček,
- medvedek, vlakec, kocka,
- avtomobilček, vlakec, medvedek in
- kocka, vlakec, medvedek.

Urejanje izložbe

3. Ali je število možnosti na vsaki stopnji izbiranja neodvisno od izbranih možnosti na prejšnjih stopnjah?


Preveri

Simetrično kombinatorično drevo

Pravilno

Napačno

Poskusi ponovno.

 
Kombinatorično drevo, pri katerem je število možnosti na vsaki stopnji izbiranja neodvisno od izbranih možnosti na prejšnjih stopnjah, imenujemo simetrično kombinatorično drevo.

Igra biljarda

Zarja in Peter sta se dogovorila, da bosta igrala biljard, in sicer tako dolgo, da bo Zarja zmagala dvakrat ali Peter dvakrat zaporedoma. S kombinatoričnim drevesom predstavimo vse možne poteke dogajanja.

Aplikacija RiŠ se ni mogla zagnati. Prosim preverite, ali imate v brskalniku namescen program Java 1.4.2 (ali novejsi) (Kliknite tu za namestitev Jave)

Riš datoteka

Igra biljarda

Odgovori na naslednja vprašanja.

1. Koliko je vseh možnih potekov dogajanja?


Preveri

Pravilno

Tako je. Možni so naslednji poteki dogajanja:

- Z, Z,
- Z, P, Z,
- Z, P, P,
- P, Z, Z,
- P, Z, P, Z,
- P, Z, P, P in
- P, P,

kjer Z predstavlja Zarjino, P pa Petrovo zmago.

Napačno

Pomagaj si z aplikacijo.

Aplikacija RiŠ se ni mogla zagnati. Prosim preverite, ali imate v brskalniku namescen program Java 1.4.2 (ali novejsi) (Kliknite tu za namestitev Jave)

Riš datoteka

Rešitev

7 potekov dogajanja.
Možni so naslednji poteki dogajanja:

- Z, Z,
- Z, P, Z,
- Z, P, P,
- P, Z, Z,
- P, Z, P, Z,
- P, Z, P, P in
- P, P,

Igra biljarda

2. V koliko primerih zmaga pri biljardu Zarja, če je končni zmagovalec tisti, ki je zmagal večkrat?


Preveri

Pravilno

Tako je. Zarja zmaga v naslednjih primerih:

- Z, Z,
- Z, P, Z in
- P, Z, Z.

Napačno

Pomagaj si z aplikacijo.

Aplikacija RiŠ se ni mogla zagnati. Prosim preverite, ali imate v brskalniku namescen program Java 1.4.2 (ali novejsi) (Kliknite tu za namestitev Jave)

Riš datoteka

Rešitev

V primerih. Zarja zmaga v naslednjih primerih:

- Z, Z,
- Z, P, Z in
- P, Z, Z.

Igra biljarda

3. Ali je število možnosti na vsaki stopnji izbiranja neodvisno od izbranih možnosti na prejšnjih stopnjah?


Preveri

Nesimetrično kombinatorično drevo

Pravilno

Napačno

Poskusi ponovno.

 
Kombinatorično drevo, pri katerem obstaja stopnja izbiranja, kjer je število možnosti odvisno od izbranih možnosti na prejšnjih stopnjah, imenujemo nesimetrično kombinatorično drevo.

Šahovski dvoboj

Šahistka Ema igra šah proti računalniku. Dvoboj se bo končal, ko bo Ema prvič premagala računalnik, vendar najkasneje po treh partijah. S kombinatoričnim drevesom predstavimo vse možne poteke dvoboja.

Aplikacija RiŠ se ni mogla zagnati. Prosim preverite, ali imate v brskalniku namescen program Java 1.4.2 (ali novejsi) (Kliknite tu za namestitev Jave)

Riš datoteka

Šahovski dvoboj

Odgovori na naslednja vprašanja.

1. Kaj pomeni znak v zelenem krogu?


Preveri

Pravilno

Napačno

Pomagaj si z aplikacijo.

Aplikacija RiŠ se ni mogla zagnati. Prosim preverite, ali imate v brskalniku namescen program Java 1.4.2 (ali novejsi) (Kliknite tu za namestitev Jave)

Riš datoteka

Rešitev

Zmago dekleta.

Šahovski dvoboj

2. Koliko je vseh možnih potekov dogajanja?


Preveri

Pravilno

Napačno

Pomagaj si z aplikacijo.

Aplikacija RiŠ se ni mogla zagnati. Prosim preverite, ali imate v brskalniku namescen program Java 1.4.2 (ali novejsi) (Kliknite tu za namestitev Jave)

Riš datoteka

Rešitev

Vseh možnih potekov dogajanja je 15.

Igra biljarda

3. Ali je kombinatorično drevo simetrično ali nesimetrično?


Preveri

Pravilno

Napačno

Poskusi ponovno.

Dodatne naloge

1. naloga

Trikrat zaporedoma vržemo kovanec za en cent. Katero kombinatorično drevo ustreza vsem možnim potekom metanja?

(2.PNG)
(prva.JPG)

Pravilno

Napačno

Dodatne naloge

2. naloga

Iz Barcelone v Trst lahko potujemo z ladjo ali letalom, iz Trsta v Dravograd se peljemo z osebnim avtomobilom in iz Dravograda v Maribor s čolnom, z vlakom ali jezdimo na konju. S kombinatoričnim drevesom prikaži vse možne načine potovanja iz Barcelone v Maribor.

(3.PNG)
(druga.JPG)

Pravilno

Napačno

Dodatne naloge

3. naloga

S kombinatoričnim drevesom prikaži pot zmag in porazov igralca na teniškem turnirju. Igralec lahko igra največ krogov, pri čemer z zmago napreduje v naslednji krog, ob porazu pa zapusti tekmovanje.

(4.PNG)
(tretja.JPG)

Pravilno

Napačno

Dodatne naloge

4. naloga

Anže v slaščičarni naroča sadno kupo. Izbira lahko med tremi vrstami sadja: jagodami, bananami in ananasom, med dvema okusoma sladoleda: jagodnim in kivijevim in med dvema prelivoma: čokoladnim in borovničevim. S kombinatoričnim drevesom prikaži vse možnosti, če se je Anže odločil, da bo jagodo zagotovo okusil.

(5.PNG)
(cetrta.JPG)

Pravilno

Napačno

0%
0%