| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
goranm
Forumaš(ica)
Pridružen/a: 12. 11. 2002. (20:09:12)
Postovi: (906)16
Spol: 
|
 Postano: 22:22 uto, 13. 12. 2005 Naslov: O loncima i prelijevanju |
    |
|
|
http://web.math.hr/~caklovic/modeliranje/zadaci/mazadaci.pdf
Zadatak 13)
Na stolu su 3 lonca od 10, 7 i 4 litre. Na početku je 10 litreni lonac pun tekucine, a ostali prazni. Potrebno je prelijevanjem bez pomagala u nekom loncu dobiti 2 litre tekucine. Modelirati problem u teoriji grafova i BFS algoritmom naci najmanji broj prelijevanja.
Sad ovako:
Lonac od 10 litara - L1
Lonac od 7 litre - L2
Lonac od 4 litre - L3
Li(x) označava koliko je tekućine u kojem loncu (i=1,2,3)
1. korak) L1(10). Možemo napraviti dva poteza - preliti u L2 7 litara ili u L1 4 litre. znači imamo na jednoj grani
[code:1]
L1(3) L1(6)
L2(7) i na drugoj grani L2(0)
L3(0) L3(4)
[/code:1]
neću sad opisivati cijeli postupak, ima slika u attachmentu, ali krenimo od toga da smo izlili u L3 4 litre.
Sada u idućem koraku možemo 4 litre uliti u L2 iz L3 ili 6 litara u L2 iz L1.
Krenimo sada od koraka da smo 4 litre ulili u L2 iz L3.
Tada u L1 ima 6 litara. Od tih 6, 4 možemo uliti u L3 i tada je ostalo 2 litre.
E sada, kada dođemo do traženog rješenja, da li je potrebno dalje tražiti sve ostale kombinacije jer je jasno da neće biti bržeg puta od 3 koraka (jer u 2 koraka nismo ništa našli, možemo samo u 3 ili više od 3).
Za jasnije predočavanje, vidi attachment.
http://web.math.hr/~caklovic/modeliranje/zadaci/mazadaci.pdf
Zadatak 13)
Na stolu su 3 lonca od 10, 7 i 4 litre. Na početku je 10 litreni lonac pun tekucine, a ostali prazni. Potrebno je prelijevanjem bez pomagala u nekom loncu dobiti 2 litre tekucine. Modelirati problem u teoriji grafova i BFS algoritmom naci najmanji broj prelijevanja.
Sad ovako:
Lonac od 10 litara - L1
Lonac od 7 litre - L2
Lonac od 4 litre - L3
Li(x) označava koliko je tekućine u kojem loncu (i=1,2,3)
1. korak) L1(10). Možemo napraviti dva poteza - preliti u L2 7 litara ili u L1 4 litre. znači imamo na jednoj grani
| Kod: |
L1(3) L1(6)
L2(7) i na drugoj grani L2(0)
L3(0) L3(4)
|
neću sad opisivati cijeli postupak, ima slika u attachmentu, ali krenimo od toga da smo izlili u L3 4 litre.
Sada u idućem koraku možemo 4 litre uliti u L2 iz L3 ili 6 litara u L2 iz L1.
Krenimo sada od koraka da smo 4 litre ulili u L2 iz L3.
Tada u L1 ima 6 litara. Od tih 6, 4 možemo uliti u L3 i tada je ostalo 2 litre.
E sada, kada dođemo do traženog rješenja, da li je potrebno dalje tražiti sve ostale kombinacije jer je jasno da neće biti bržeg puta od 3 koraka (jer u 2 koraka nismo ništa našli, možemo samo u 3 ili više od 3).
Za jasnije predočavanje, vidi attachment.
_________________
The Dude Abides
| Description: |
|
Download |
| Filename: |
untitled.JPG |
| Filesize: |
93.79 KB |
| Downloaded: |
363 Time(s) |
|
|
| [Vrh] |
|
Grga
Forumaš(ica)
Pridružen/a: 23. 12. 2004. (23:05:23)
Postovi: (280)16
Spol: 
|
|
| [Vrh] |
|
goranm
Forumaš(ica)
Pridružen/a: 12. 11. 2002. (20:09:12)
Postovi: (906)16
Spol:
|
| Postano: 22:36 uto, 13. 12. 2005 Naslov: |
|
|
|
[quote="Grga"]Naravno da ne trebas, cim nades rjesenje, stanes traziti. Upravo zato BFS i je super, jer cim nades rjesenje, znas da je optimalno i odmah mozes stati :)[/quote]
Što točno znači "modelirati problem u teoriji grafova?" Pretpostavljam da je to samo ušminkana rečenica, no ja bih za sebe rekao da sam napravio samo BFS algoritam, bez da sam išta konkretno modelirao.
| Grga (napisa): | Naravno da ne trebas, cim nades rjesenje, stanes traziti. Upravo zato BFS i je super, jer cim nades rjesenje, znas da je optimalno i odmah mozes stati  |
Što točno znači "modelirati problem u teoriji grafova?" Pretpostavljam da je to samo ušminkana rečenica, no ja bih za sebe rekao da sam napravio samo BFS algoritam, bez da sam išta konkretno modelirao.
_________________
The Dude Abides
|
|
| [Vrh] |
|
Grga
Forumaš(ica)
Pridružen/a: 23. 12. 2004. (23:05:23)
Postovi: (280)16
Spol:
|
|
| [Vrh] |
|
vili
Forumaš(ica)
Pridružen/a: 08. 06. 2005. (22:40:59)
Postovi: (14A)16
Spol:
Lokacija: Keglić
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (355F)16
Spol: 
Lokacija: /sbin/init
|
|
| [Vrh] |
|
vili
Forumaš(ica)
Pridružen/a: 08. 06. 2005. (22:40:59)
Postovi: (14A)16
Spol:
Lokacija: Keglić
|
|
| [Vrh] |
|
|
pa nek me ispravi ako griješim 
