Prethodna tema :: Sljedeća tema |
Autor/ica |
Poruka |
JV Forumaš(ica)
Pridružen/a: 07. 02. 2011. (11:13:19) Postovi: (5C)16
|
Postano: 13:35 pon, 26. 3. 2012 Naslov: 2. zadaća - često postavljena pitanja |
|
|
Ovdje ću stavljati neka važnija pitanja koja dobijem u mailovima i greške koje se potkradu u zadacima (kodu), a mislim da će pomoći svima razjasniti neke stvari.
[b]FAQ:[/b]
[b]Q1:[/b] Da li postoji ograničenje na broj elemenata u listi, tj. treba li paziti na složenost implementacije u funkcijama [tt]maxZarada[/tt], [tt]pametniObilazak[/tt] i [tt]optimalnaIgra[/tt]?
[b]A1:[/b] Pošto u zadatku ne piše nikakvo ograničenje to znači da ga ni nema tj. vaša implementacija treba biti najbolja moguća jer je uvjet da se program izvrši u manje od 5s. U praksi će to izgledati da će prvih pet test primjera samo provjeravati da li funkcije dobro rade i liste će sadržavati manje od 100 elemenata. Šesti test primjer će provjeravati brzinu vašeg algoritma i tu možete očekivat veliki broj elemenata (reda 10^4). Drugim riječima, najjednostavnije rješenje koje se može implementirati sa složenošću O(n^2) neće biti dovoljno brzo.
[b]Q2:[/b] Neke funkcije trebaju vraćati element ili kolekciju elemenata sa određenim svojstvima. Što vratiti ako takav element ne postoji ili ako je lista elemenata prazna.
[b]A2:[/b] Takvih test primjera neće biti. Liste nikad neće biti prazne i uvijek će sadržavati elemente s tim svojstvima. Znači da možete vratiti bilo što (nula ako je int, ili praznu riječ ako je tipa string) jer to i tako nećemo provjeravati.
[b]Q3:[/b] Da li se mogu koristiti i druge funkcije (bilo globalne, bilo dio strukture)?
[b]A3:[/b] Možete koristiti i druge funkcije (iako ne vidim neki razlog za njih).
[b]Q4:[/b] Može li se za minimalni int uzeti -32767.
[b]A4:[/b] To bi bilo u redu kad bi int bio 16 bitni. Da li je int 16 bitni ili 32 bitni ovisi o kompajleru i procesoru. U većini slučajeva je int 32 bitni, tj. ide od −2,147,483,648 do 2,147,483,647. Također, uzmite da je naš int 32 bitni. Inače, za dohvatiti minimum bilo kojeg tipa možete iskoristiti sljedeći kod (ovdje dohvaćamo za int):
[code:1]#include <limits>
int minInt = numeric_limits<int>::min();
[/code:1]
[b]Q5:[/b] Nekoliko pitanja u vezi što vraćaju funkcije [tt]maxZarada[/tt], [tt]pametniObilazak[/tt] i [tt]optimalnaIgra[/tt] kada ima više mogućih rješenja. Većinom su svi slučajevi obrađeni u test primjerima (jedino za igru nedostaje jedan slučaj) ali ću ovdje napisati po još jedan primjer i objašnjenje.
[b]A5:[/b]
[i]BANKOMATI:[/i]
Neka imamo niz bankomata (ime bankomata pa novac koji skida ili stavlja i tako redom)
A -5 B 1 C 2 D 1 H -3 G 3 K -50 P 1 Q 3 Z -10
Postoje 3 rješenja: (B, D), (B, G), (P, Q).
Sva tri daju ukupnu sumu novca koja se položi na račun jednaku 4. Prvo eliminiramo rješenje (P, Q) jer rješenja (B,D) i (B,G) imaju prvi bankomat(B) bliži početku liste. Od ta dva rješenja uzimamo rješenje (B,D) jer je sadrži manje bankomata.
[i]IGRA:[/i]
Neka imamo niz polja (prvo ID polja, zatim broj bodova na tom polju i tako redom)
333 -4 100 1 80 2 120 1 101 4 222 -2 504 2 339 10 666 -20 82 4
Promatrajmo samo prvog igrača (tj. polja s parnim ID). Znači da možemo zamisliti da polja 333, 101 i 339 ne postoje.
Postoje 3 optimalne igre za prvog igrača: (100, 120), (100, 504), (82, 82).
Sve tri igre daju ukupan broj bodova 4. Zadnje rješenje (82, 82) odbacujemo jer rješenja (100, 120) i (100, 504) imaju prvo polje bliže početku liste. Od ta dva rješenja biramo ono s najmanje polja tj. biramo rješenje (100, 120).
[i]MASKARE:[/i]
Neka imamo niz kuća (prvo ime vlasnika, a zatim koliko novaca daje ili uzima i tako redom)
Ante -10 Josip 3 Maja 2 Ivan -1 Ana 2 Marko -4 Jelena 4 Mate -100 Igor 3 Branka 3 Filip -50 Petar 6
Postoje 4 najbolja obilaska kuća: (Josip, Ana), (Josip, Jelena), (Igor, Branka), (Petar, Petar).
Dijete će nakon ovih obilazaka biti u plusu 6 kuna. Prvo odbacimo rješenja (Igor, Branka) i (Petar, Petar) jer se u prva dva rješenja vlasnik Josip nalazi u listi prije Igora i Petra. Od ta dva prva rješenja uzimemo (Josip, Ana) jer je kraće.
[color=red][b]GREŠKE:[/b][/color]
U kodu za zadatak BANKOMATI nakon linije [tt]ispisiListu(B.vratiListu());[/tt] piše
// otp4 3 zaba3 -20 pbz1 10 zaba -2 splitska 5 bks 4 credo1 -2 erste2 2 pbz3 -30 [color=red]12 pbz[/color] 10 erste -3 otp 10
a trebalo bi pisati
// otp4 3 zaba3 -20 pbz1 10 zaba -2 splitska 5 bks 4 credo1 -2 erste2 2 pbz3 -30 [color=blue]12pbz[/color] 10 erste -3 otp 10
Ovdje ću stavljati neka važnija pitanja koja dobijem u mailovima i greške koje se potkradu u zadacima (kodu), a mislim da će pomoći svima razjasniti neke stvari.
FAQ:
Q1: Da li postoji ograničenje na broj elemenata u listi, tj. treba li paziti na složenost implementacije u funkcijama maxZarada, pametniObilazak i optimalnaIgra?
A1: Pošto u zadatku ne piše nikakvo ograničenje to znači da ga ni nema tj. vaša implementacija treba biti najbolja moguća jer je uvjet da se program izvrši u manje od 5s. U praksi će to izgledati da će prvih pet test primjera samo provjeravati da li funkcije dobro rade i liste će sadržavati manje od 100 elemenata. Šesti test primjer će provjeravati brzinu vašeg algoritma i tu možete očekivat veliki broj elemenata (reda 10^4). Drugim riječima, najjednostavnije rješenje koje se može implementirati sa složenošću O(n^2) neće biti dovoljno brzo.
Q2: Neke funkcije trebaju vraćati element ili kolekciju elemenata sa određenim svojstvima. Što vratiti ako takav element ne postoji ili ako je lista elemenata prazna.
A2: Takvih test primjera neće biti. Liste nikad neće biti prazne i uvijek će sadržavati elemente s tim svojstvima. Znači da možete vratiti bilo što (nula ako je int, ili praznu riječ ako je tipa string) jer to i tako nećemo provjeravati.
Q3: Da li se mogu koristiti i druge funkcije (bilo globalne, bilo dio strukture)?
A3: Možete koristiti i druge funkcije (iako ne vidim neki razlog za njih).
Q4: Može li se za minimalni int uzeti -32767.
A4: To bi bilo u redu kad bi int bio 16 bitni. Da li je int 16 bitni ili 32 bitni ovisi o kompajleru i procesoru. U većini slučajeva je int 32 bitni, tj. ide od −2,147,483,648 do 2,147,483,647. Također, uzmite da je naš int 32 bitni. Inače, za dohvatiti minimum bilo kojeg tipa možete iskoristiti sljedeći kod (ovdje dohvaćamo za int):
Kod: | #include <limits>
int minInt = numeric_limits<int>::min();
|
Q5: Nekoliko pitanja u vezi što vraćaju funkcije maxZarada, pametniObilazak i optimalnaIgra kada ima više mogućih rješenja. Većinom su svi slučajevi obrađeni u test primjerima (jedino za igru nedostaje jedan slučaj) ali ću ovdje napisati po još jedan primjer i objašnjenje.
A5:
BANKOMATI:
Neka imamo niz bankomata (ime bankomata pa novac koji skida ili stavlja i tako redom)
A -5 B 1 C 2 D 1 H -3 G 3 K -50 P 1 Q 3 Z -10
Postoje 3 rješenja: (B, D), (B, G), (P, Q).
Sva tri daju ukupnu sumu novca koja se položi na račun jednaku 4. Prvo eliminiramo rješenje (P, Q) jer rješenja (B,D) i (B,G) imaju prvi bankomat(B) bliži početku liste. Od ta dva rješenja uzimamo rješenje (B,D) jer je sadrži manje bankomata.
IGRA:
Neka imamo niz polja (prvo ID polja, zatim broj bodova na tom polju i tako redom)
333 -4 100 1 80 2 120 1 101 4 222 -2 504 2 339 10 666 -20 82 4
Promatrajmo samo prvog igrača (tj. polja s parnim ID). Znači da možemo zamisliti da polja 333, 101 i 339 ne postoje.
Postoje 3 optimalne igre za prvog igrača: (100, 120), (100, 504), (82, 82).
Sve tri igre daju ukupan broj bodova 4. Zadnje rješenje (82, 82) odbacujemo jer rješenja (100, 120) i (100, 504) imaju prvo polje bliže početku liste. Od ta dva rješenja biramo ono s najmanje polja tj. biramo rješenje (100, 120).
MASKARE:
Neka imamo niz kuća (prvo ime vlasnika, a zatim koliko novaca daje ili uzima i tako redom)
Ante -10 Josip 3 Maja 2 Ivan -1 Ana 2 Marko -4 Jelena 4 Mate -100 Igor 3 Branka 3 Filip -50 Petar 6
Postoje 4 najbolja obilaska kuća: (Josip, Ana), (Josip, Jelena), (Igor, Branka), (Petar, Petar).
Dijete će nakon ovih obilazaka biti u plusu 6 kuna. Prvo odbacimo rješenja (Igor, Branka) i (Petar, Petar) jer se u prva dva rješenja vlasnik Josip nalazi u listi prije Igora i Petra. Od ta dva prva rješenja uzimemo (Josip, Ana) jer je kraće.
GREŠKE:
U kodu za zadatak BANKOMATI nakon linije ispisiListu(B.vratiListu()); piše
// otp4 3 zaba3 -20 pbz1 10 zaba -2 splitska 5 bks 4 credo1 -2 erste2 2 pbz3 -30 12 pbz 10 erste -3 otp 10
a trebalo bi pisati
// otp4 3 zaba3 -20 pbz1 10 zaba -2 splitska 5 bks 4 credo1 -2 erste2 2 pbz3 -30 12pbz 10 erste -3 otp 10
|
|
[Vrh] |
|
googol Forumaš(ica)
Pridružen/a: 29. 09. 2011. (21:23:09) Postovi: (71)16
Spol:
|
Postano: 16:31 pon, 26. 3. 2012 Naslov: |
|
|
Evo maina za igru. Samo convertajte pdf u word i c/p.
[code:1]#include <iostream>
#include <map>
#include <vector>
#include <list>
#include <utility>
using namespace std;
void ispisiListu(list<pair<int, int> > L)
{
list<pair<int, int> >::iterator it;
for(it = L.begin(); it != L.end(); it++)
cout << it->first << " " << it->second << " ";
}
void ispisiMap(map<int, int> M)
{
map<int, int>::iterator it;
for(it = M.begin(); it != M.end(); it++)
cout << it->first << " " << it->second << " ";
}
void ispisiVector(vector<pair<int, int> > V)
{
for(int i = 0; i < V.size() ; i++)
cout << V[i].first << " " << V[i].second << " ";
}
int main(void)
{
igra game;
game.dodajPolje(112, -4); game.dodajPolje(226, 5); game.dodajPolje(327, 2); game.dodajPolje(158, -3); game.dodajPolje(445, 5); game.dodajPolje(649, 7); game.dodajPolje(654, 4); game.dodajPolje(120, -2); game.dodajPolje(821, -4); game.dodajPolje(415, -1); game.dodajPolje(117, 4); game.dodajPolje(926, 1); game.dodajPolje(258, -15); game.dodajPolje(202, 6); game.izbrisiPolje(445);
ispisiListu(game.vratiListu());
// 112 -4 226 5 327 2 158 -3 649 7 654 4 120 -2 821 -4 415 -1 117 4 926 1 258 -15 202 6
cout << endl;
ispisiVector(game.polja(1));
// 112 -4 226 5 158 -3 654 4 120 -2 926 1 258 -15 202 6
cout << endl;
ispisiVector(game.polja(2));
// 327 2 649 7 821 -4 415 -1 117 4
cout << endl;
ispisiMap(game.viseOd(2));
// 117 4 202 6 226 5 649 7 654 4
cout << endl;
cout << game.pobjednik(226, 120, 649, 117) << endl;
// 2
pair<int, int> p = game.optimalnaIgra(1);
cout << p.first << " " << p.second << endl;
// 226 654
p = game.optimalnaIgra(2);
cout << p.first << " " << p.second << endl;
// 327 649
return 0;
}[/code:1]
Evo maina za igru. Samo convertajte pdf u word i c/p.
Kod: | #include <iostream>
#include <map>
#include <vector>
#include <list>
#include <utility>
using namespace std;
void ispisiListu(list<pair<int, int> > L)
{
list<pair<int, int> >::iterator it;
for(it = L.begin(); it != L.end(); it++)
cout << it->first << " " << it->second << " ";
}
void ispisiMap(map<int, int> M)
{
map<int, int>::iterator it;
for(it = M.begin(); it != M.end(); it++)
cout << it->first << " " << it->second << " ";
}
void ispisiVector(vector<pair<int, int> > V)
{
for(int i = 0; i < V.size() ; i++)
cout << V[i].first << " " << V[i].second << " ";
}
int main(void)
{
igra game;
game.dodajPolje(112, -4); game.dodajPolje(226, 5); game.dodajPolje(327, 2); game.dodajPolje(158, -3); game.dodajPolje(445, 5); game.dodajPolje(649, 7); game.dodajPolje(654, 4); game.dodajPolje(120, -2); game.dodajPolje(821, -4); game.dodajPolje(415, -1); game.dodajPolje(117, 4); game.dodajPolje(926, 1); game.dodajPolje(258, -15); game.dodajPolje(202, 6); game.izbrisiPolje(445);
ispisiListu(game.vratiListu());
// 112 -4 226 5 327 2 158 -3 649 7 654 4 120 -2 821 -4 415 -1 117 4 926 1 258 -15 202 6
cout << endl;
ispisiVector(game.polja(1));
// 112 -4 226 5 158 -3 654 4 120 -2 926 1 258 -15 202 6
cout << endl;
ispisiVector(game.polja(2));
// 327 2 649 7 821 -4 415 -1 117 4
cout << endl;
ispisiMap(game.viseOd(2));
// 117 4 202 6 226 5 649 7 654 4
cout << endl;
cout << game.pobjednik(226, 120, 649, 117) << endl;
// 2
pair<int, int> p = game.optimalnaIgra(1);
cout << p.first << " " << p.second << endl;
// 226 654
p = game.optimalnaIgra(2);
cout << p.first << " " << p.second << endl;
// 327 649
return 0;
} |
|
|
[Vrh] |
|
<3Luka<3 Forumaš(ica)
Pridružen/a: 06. 11. 2010. (14:44:03) Postovi: (12)16
|
|
[Vrh] |
|
googol Forumaš(ica)
Pridružen/a: 29. 09. 2011. (21:23:09) Postovi: (71)16
Spol:
|
|
[Vrh] |
|
JV Forumaš(ica)
Pridružen/a: 07. 02. 2011. (11:13:19) Postovi: (5C)16
|
|
[Vrh] |
|
googol Forumaš(ica)
Pridružen/a: 29. 09. 2011. (21:23:09) Postovi: (71)16
Spol:
|
|
[Vrh] |
|
JV Forumaš(ica)
Pridružen/a: 07. 02. 2011. (11:13:19) Postovi: (5C)16
|
|
[Vrh] |
|
kb Forumaš(ica)
Pridružen/a: 17. 01. 2012. (18:26:12) Postovi: (4)16
|
|
[Vrh] |
|
JV Forumaš(ica)
Pridružen/a: 07. 02. 2011. (11:13:19) Postovi: (5C)16
|
|
[Vrh] |
|
kkarlo Forumaš(ica)
Pridružen/a: 19. 05. 2010. (08:43:59) Postovi: (1B2)16
Spol:
|
|
[Vrh] |
|
kobila krsto Forumaš(ica)
Pridružen/a: 02. 07. 2009. (16:55:08) Postovi: (6A)16
|
|
[Vrh] |
|
JV Forumaš(ica)
Pridružen/a: 07. 02. 2011. (11:13:19) Postovi: (5C)16
|
|
[Vrh] |
|
mapat Forumaš(ica)
Pridružen/a: 01. 11. 2010. (15:31:40) Postovi: (10)16
Spol:
|
|
[Vrh] |
|
JV Forumaš(ica)
Pridružen/a: 07. 02. 2011. (11:13:19) Postovi: (5C)16
|
|
[Vrh] |
|
mapat Forumaš(ica)
Pridružen/a: 01. 11. 2010. (15:31:40) Postovi: (10)16
Spol:
|
|
[Vrh] |
|
notGost Gost
|
Postano: 13:00 ned, 1. 4. 2012 Naslov: maxZarada |
|
|
Moze li se u zadatku sa bankomatima na racun staviti 0 kn?
Preciznije, ako imam bankomate A 0 ,B 1, C 2, je li onda maxZarada (A,C) ili (B,C) ?
Moze li se u zadatku sa bankomatima na racun staviti 0 kn?
Preciznije, ako imam bankomate A 0 ,B 1, C 2, je li onda maxZarada (A,C) ili (B,C) ?
|
|
[Vrh] |
|
JV Forumaš(ica)
Pridružen/a: 07. 02. 2011. (11:13:19) Postovi: (5C)16
|
Postano: 7:35 pon, 2. 4. 2012 Naslov: Re: maxZarada |
|
|
[quote="notGost"]Moze li se u zadatku sa bankomatima na racun staviti 0 kn?
Preciznije, ako imam bankomate A 0 ,B 1, C 2, je li onda maxZarada (A,C) ili (B,C) ?[/quote]
Neće biti bankomata s 0kn.
notGost (napisa): | Moze li se u zadatku sa bankomatima na racun staviti 0 kn?
Preciznije, ako imam bankomate A 0 ,B 1, C 2, je li onda maxZarada (A,C) ili (B,C) ? |
Neće biti bankomata s 0kn.
|
|
[Vrh] |
|
Gost
|
Postano: 20:45 pon, 2. 4. 2012 Naslov: Re: 2. zadaća - često postavljena pitanja |
|
|
[quote="JV"][i]MASKARE:[/i]
Neka imamo niz kuća (prvo ime vlasnika, a zatim koliko novaca daje ili uzima i tako redom)
Ante -10 Josip 3 Maja 2 Ivan -1 Ana 2 Marko -4 Jelena 4 Mate -100 Igor 3 Branka 3 Filip -50 Petar 6
Postoje 4 najbolja obilaska kuća: (Josip, Ana), (Josip, Jelena), (Igor, Branka), (Petar, Petar).
Dijete će nakon ovih obilazaka biti u plusu 6 kuna. Prvo odbacimo rješenja (Igor, Branka) i (Petar, Petar) jer se u prva dva rješenja vlasnik Josip nalazi u listi prije Igora i Petra. Od ta dva prva rješenja uzimemo (Josip, Ana) jer je kraće.
[/quote]
Koliki je tu pocetniIznos? Odnosno vrijedi li ovo kao rjesenje i za pocetniIznos=0? I moze li uopce biti pocetniIznos=0?
Takoder smije li neki vlasnik "davati" 0 kn?
JV (napisa): | MASKARE:
Neka imamo niz kuća (prvo ime vlasnika, a zatim koliko novaca daje ili uzima i tako redom)
Ante -10 Josip 3 Maja 2 Ivan -1 Ana 2 Marko -4 Jelena 4 Mate -100 Igor 3 Branka 3 Filip -50 Petar 6
Postoje 4 najbolja obilaska kuća: (Josip, Ana), (Josip, Jelena), (Igor, Branka), (Petar, Petar).
Dijete će nakon ovih obilazaka biti u plusu 6 kuna. Prvo odbacimo rješenja (Igor, Branka) i (Petar, Petar) jer se u prva dva rješenja vlasnik Josip nalazi u listi prije Igora i Petra. Od ta dva prva rješenja uzimemo (Josip, Ana) jer je kraće.
|
Koliki je tu pocetniIznos? Odnosno vrijedi li ovo kao rjesenje i za pocetniIznos=0? I moze li uopce biti pocetniIznos=0?
Takoder smije li neki vlasnik "davati" 0 kn?
|
|
[Vrh] |
|
drugi_gost Gost
|
Postano: 23:10 pon, 2. 4. 2012 Naslov: Re: 2. zadaća - često postavljena pitanja |
|
|
[quote="Anonymous"][quote="JV"][i]MASKARE:[/i]
Neka imamo niz kuća (prvo ime vlasnika, a zatim koliko novaca daje ili uzima i tako redom)
Ante -10 Josip 3 Maja 2 Ivan -1 Ana 2 Marko -4 Jelena 4 Mate -100 Igor 3 Branka 3 Filip -50 Petar 6
Postoje 4 najbolja obilaska kuća: (Josip, Ana), (Josip, Jelena), (Igor, Branka), (Petar, Petar).
Dijete će nakon ovih obilazaka biti u plusu 6 kuna. Prvo odbacimo rješenja (Igor, Branka) i (Petar, Petar) jer se u prva dva rješenja vlasnik Josip nalazi u listi prije Igora i Petra. Od ta dva prva rješenja uzimemo (Josip, Ana) jer je kraće.
[/quote]
Koliki je tu pocetniIznos? Odnosno vrijedi li ovo kao rjesenje i za pocetniIznos=0? I moze li uopce biti pocetniIznos=0?
Takoder smije li neki vlasnik "davati" 0 kn?[/quote]
koji je uopce smisao pocetniIznos-a?
rijesenje je neovisno o pocetniIznos :?: wtf?
Anonymous (napisa): | JV (napisa): | MASKARE:
Neka imamo niz kuća (prvo ime vlasnika, a zatim koliko novaca daje ili uzima i tako redom)
Ante -10 Josip 3 Maja 2 Ivan -1 Ana 2 Marko -4 Jelena 4 Mate -100 Igor 3 Branka 3 Filip -50 Petar 6
Postoje 4 najbolja obilaska kuća: (Josip, Ana), (Josip, Jelena), (Igor, Branka), (Petar, Petar).
Dijete će nakon ovih obilazaka biti u plusu 6 kuna. Prvo odbacimo rješenja (Igor, Branka) i (Petar, Petar) jer se u prva dva rješenja vlasnik Josip nalazi u listi prije Igora i Petra. Od ta dva prva rješenja uzimemo (Josip, Ana) jer je kraće.
|
Koliki je tu pocetniIznos? Odnosno vrijedi li ovo kao rjesenje i za pocetniIznos=0? I moze li uopce biti pocetniIznos=0?
Takoder smije li neki vlasnik "davati" 0 kn? |
koji je uopce smisao pocetniIznos-a?
rijesenje je neovisno o pocetniIznos wtf?
|
|
[Vrh] |
|
kobila krsto Forumaš(ica)
Pridružen/a: 02. 07. 2009. (16:55:08) Postovi: (6A)16
|
|
[Vrh] |
|
|