UL/FRI/UN-RI/2/APS/Izpiti/2011-02-07
Iz E-študij, proste zakladnice študentskega znanja
|
Izpit z dne 07.02.2011
Čas pisanja: 60 minut.
|
1. naloga
Uporabite zunanje uravnoteženo zlivanje za urejanje zaporedja števil:
- 1,6,1,8,0,3,3,9,8,8,7,4,9,8,9,4,8,4,8,2,0,4,5,8,6,8,3,4,3
(a) z navadnim zlivanjem na 5 trakovih; in
(b) z naravnim zlivanjem na 4 trakovih.
(a) zunanje uravnoteženo navadno zlivanje na 5 trakovih:
Razporejamo čete:
1: 1;3;7;4;0;8
2: 6;3;4;8;4;3
3: 1;9;9;4;5;4
4: 8;8;8;8;8;3
5: 0;8;9;2;6
Zlivamo:
1: 0,1,1,6,8 ; 3,3,4,8
2: 3,3,8,8,9
3: 4,7,8,9,9
4: 2,4,4,8,8
5: 0,4,5,6,8
Razporejamo čete:
1: 0,0,1,1,2,3,3,4,4,4,4,5,6,6,7,8,8,8,8,8,8,8,9,9,9
2: 3,3,4,8
Zlivamo:
1: 0,0,1,1,2,3,3,3,3,4,4,4,4,4,5,6,6,7,8,8,8,8,8,8,8,8,9,9,9
Zaporedje je urejeno.
(b) zunanje uravnoteženo naravno zlivanje na 4 trakovih:
Razporejamo čete:
1: 1,6,8,8; 4,8; 6,8
2: 1,8; 7; 4,8; 3,4
3: 0,3,3,4,9; 2,3
4: 9; 8,9; 0,4,5,8
Zlivamo:
1: 0,1,1,3,3,4,6,8,8,8,9,9
2: 0,2,3,4,4,5,7,8,8,8
3: 4,6,8,8
4: 3,4,6,8
Razporejamo čete:
1: 0,0,1,1,2,3,3,3,3,4,4,4,4,4,5,6,6,7,8,8,8,8,8,8,8,8,9,9,9
Zaporedje je urejeno.
2. naloga
S postopkom dinamičnega programiranja napolnite 0-1 nahrbtnik velikosti 9 prostorninskih enot s predmeti velikosti 3,2,2,1,2,2,3 in cenami 1,2,2,3,2,2,1. Pravilno odstranjujte pare in določite, kateri predmeti sodijo v nahrbtnik!
0:
(0,0)
(3,1)
1:
(0,0),(3,1)
(2,2),(5,3)
2:
(0,0),(2,2),(3,1),(5,3)
(2,2),(4,4),(5,3),(7,5)
3:
(0,0),(2,2),(3,1),(4,4),(5,3),(7,5)
(1,3),(3,5),(4,4),(5,7),(6,6),(8,8)
4:
(0,0),(1,3),(2,2),(3,5),(4,4),(5,7),(6,6),(7,5),(8,8)
(2,2),(3,5),(4,4),(5,7),(6,6),(7,9),(8,8),(9,7),(10,10)
5:
(0,0),(1,3),(2,2),(3,5),(4,4),(5,7),(6,6),(7,9),(8,8),(9,7)
(2,2),(3,5),(4,4),(5,7),(6,6),(7,9),(8,8),(9,11),(10,10),(11,9)
6:
(0,0),(1,3),(2,2),(3,5),(4,4),(5,7),(6,6),(7,9),(8,8),(9,11)
(3,1),(4,4),(5,3),(6,6),(7,5),(8,8),(9,7),(10,10),(11,9),(12,12)
Predmeti v nahrbtniku: (2,2),(2,2),(1,3),(2,2),(2,2)
3. naloga
Z najhitrejšim znanim algoritmom poiščite najkrajšo pot iz točke 1 v 7 v omrežju s povezavami
- (1,2),(1,5),(2,6),(3,2),(3,6),(3,8),(4,3),(4,8),(5,2),(5,3),(5,4),(6,7),(8,7),
kjer je cena povezave (i,j) enaka
4. naloga
Za uspešno opravljen izpit nameravate povabiti prijatelje na pecivo. Speči znate dve vrsti peciva: sončke in lunice. Pri čemer za en sonček potrebujete 90g testa in 40g sladkorja, za eno lunico pa 30g testa in 20g sladkorja. Za pecivo v povračilu dobite prijateljske točke (srčke). Pri čemer za sonček dobite 3 srčke, za lunico pa 2. Koliko sončkov in koliko lunic speči, če želite dobiti čimveč srčkov, v shrambi pa imate na voljo 630g testa in 400g sladkorja. Rešitev podajte grafično in tabelarično.
