Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.
Ambele părți revizuirea anterioară Versiuni anterioare Urmatoarea versiune | Versiuni anterioare Ultima versiune Ambele părți următoarea reviziune | ||
teme:tema3 [2017/05/04 22:14] mihai.iacov [Iesire(fiecare pe un alt rand):] |
teme:tema3 [2017/05/07 11:21] iulian.matesica [Informații] |
||
---|---|---|---|
Linia 5: | Linia 5: | ||
*Adaptarea acestora la un caz concret | *Adaptarea acestora la un caz concret | ||
*Alegerea tehnicilor potrivite pentru rezolvare | *Alegerea tehnicilor potrivite pentru rezolvare | ||
+ | |||
+ | ===== Informații ===== | ||
+ | * Deadline **HARD**, **24 mai 2017, ora 23:59** (nu se mai aplica depunctari - acesta este ultimul termen de predare) | ||
+ | * Trimiterea temelor se face pe platforma [[https:// | ||
+ | * Există și un checker local pe care îl puteți descărca de [[http:// | ||
+ | * Pentru întrebări și nelămuriri utilizați forumul asociat temei [[http:// | ||
==== Descriere ==== | ==== Descriere ==== | ||
Linia 33: | Linia 39: | ||
- Aflaţi costul drumului valid ales după **optimul local** (la fiecare pas unde are de ales dintre stânga şi sus, alege treapta cu costul mai mic; preferă **SUS** când costurile sunt egale); | - Aflaţi costul drumului valid ales după **optimul local** (la fiecare pas unde are de ales dintre stânga şi sus, alege treapta cu costul mai mic; preferă **SUS** când costurile sunt egale); | ||
- Aflaţi costul drumului valid ales după **optimul global** (drumul cu cea mai mică sumă dintre cele posibile); | - Aflaţi costul drumului valid ales după **optimul global** (drumul cu cea mai mică sumă dintre cele posibile); | ||
- | - Simulaţi un număr de drumuri valide ca încercări pentru a găsi un drum sigur, | + | - Simulaţi un număr de drumuri valide ca încercări pentru a găsi **un drum sigur** (vă opriţi la primul drum sigur găsit), unde fiecare pas este ales “la întâmplare”(excepţie atunci când există o singură variantă pentru următorul pas - când am ajuns deja pe prima linie sau pe prima coloană) |
- | - (bonus) Aflaţi numărul de drumuri valide sigure. | + | - (bonus) Aflaţi |
<note important> | <note important> | ||
Linia 74: | Linia 80: | ||
-Dacă (C2 == 1): S2 = suma de la a doua cerinţă(drumul obţinut căutând optimul global) | -Dacă (C2 == 1): S2 = suma de la a doua cerinţă(drumul obţinut căutând optimul global) | ||
-Dacă (C3 == 1): nrIncercari sau 0; 0 la ieşire dacă **nrIncercari > nrMaxIncercari**, | -Dacă (C3 == 1): nrIncercari sau 0; 0 la ieşire dacă **nrIncercari > nrMaxIncercari**, | ||
- | -Dacă (C4 == 1): nrDrumuri = numărul de drumuri | + | -Dacă (C4 == 1): nrDrumuri = numărul de drumuri |
<note warning> | <note warning> | ||
Linia 88: | Linia 94: | ||
Punctul de sosire: **Colţul din vârful piramidei** este treapta notată cu 1. | Punctul de sosire: **Colţul din vârful piramidei** este treapta notată cu 1. | ||
- | Faraonul ajunge pe o “**margine**” a hărţii când ajunge pe una din treptele 5, 2, 4 sau 9. | + | Faraonul ajunge pe o “**margine**” a hărţii când ajunge pe una din treptele |
matricea asociată acestei hărţi este: | matricea asociată acestei hărţi este: | ||
Linia 133: | Linia 139: | ||
7-> | 7-> | ||
- | Avem 2 drumuri sigure | + | Dintre cele 6 drumuri, doar **2 sunt sigure** (**afişat 2** pe ultimul rând la ieşire). |
- | Observam că, **pentru acest exemplu**, alegerea optimului local duce la acelaşi rezultat cu optimul global (S1 = S2 = 21, afişat pe rândurile 1 şi 2). | + | Observam că, **pentru acest exemplu**, alegerea optimului local duce la acelaşi rezultat cu optimul global (**S1 = S2 = 21**, afişat pe rândurile 1 şi 2). |
- | Primele 12 valori obţinute la apelul rand() % 2 sunt: 1 1 0 1 0 1 1 1 1 0 0 1 | + | Primele 12 valori obţinute la apelul rand() % 2 sunt: |
+ | < | ||
+ | 1 1 | ||
+ | <font color=# | ||
+ | 1 1 | ||
+ | <font color=# | ||
+ | 0 0 1. | ||
+ | </ | ||
+ | De fapt, veţi ajunge să generaţi numai primele 9 valori (numai de atât aveţi nevoie pentru 4 simulări) pe acest exemplu, după cum urmează: | ||
Prima încercare de drum (primele 2 apeluri rand: 1 1): | Prima încercare de drum (primele 2 apeluri rand: 1 1): | ||
poziţia = 7, opţiuni = 6 şi 20. SUS -> 6. | poziţia = 7, opţiuni = 6 şi 20. SUS -> 6. | ||
Linia 156: | Linia 170: | ||
Aceeaşi situaţie ca la prima încercare | Aceeaşi situaţie ca la prima încercare | ||
Solutia: 7-> | Solutia: 7-> | ||
- | Deci: nu am găsit niciun drum sigur după 4 încercări (afişat 0 pe rândul 3). | + | Deci: **nu am găsit niciun drum sigur** după nrMaxIncercari = 4 încercări (**afişat 0** pe rândul 3). |
=== Variaţii la intrare === | === Variaţii la intrare === |