Unelte utilizator
teme:tema3
Diferențe
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 | ||
|
teme:tema3 [2017/05/04 21:54] mihai.iacov [Indicaţii] |
teme:tema3 [2017/05/07 11:54] (curent) 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) | ||
| + | * Puteți rezolva tema, dacă doriți, pornind de la scheletul de cod pus la dispoziție [[http:// | ||
| + | * 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 18: | Linia 25: | ||
| - | ==== Indicaţii ==== | + | ===== Indicaţii |
| *desenul de pe hartă poate fi reprezentat folosind o matrice **bidimensională** pătratică de latură **n**. | *desenul de pe hartă poate fi reprezentat folosind o matrice **bidimensională** pătratică de latură **n**. | ||
| *Pentru fiecare drum, colţul **stânga-sus** din matrice va fi **punctul destinaţie**(vârful) şi colţul **dreapta-jos** din matrice va fi **punct de plecare**. | *Pentru fiecare drum, colţul **stânga-sus** din matrice va fi **punctul destinaţie**(vârful) şi colţul **dreapta-jos** din matrice va fi **punct de plecare**. | ||
| *faraonul poate " | *faraonul poate " | ||
| - | *atunci când, în urma unui pas, ajunge pe o " | + | *Excepţie: |
| + | *numim drum **valid** un drum pe care poate " | ||
| *numim **cost al unui drum** suma tuturor valorilor din matrice de la poziţiile incluse în acel drum. | *numim **cost al unui drum** suma tuturor valorilor din matrice de la poziţiile incluse în acel drum. | ||
| *un drum va fi **sigur** dacă are un cost mai mic decât (sau egal cu) suma maximă admisă. | *un drum va fi **sigur** dacă are un cost mai mic decât (sau egal cu) suma maximă admisă. | ||
| Linia 30: | Linia 38: | ||
| ===== Cerințe ===== | ===== Cerințe ===== | ||
| - | - Aflaţi | + | - Aflaţi costul drumului |
| - | - Aflaţi | + | - Aflaţi costul drumului |
| - | - Simulaţi un număr de încercări pentru a găsi un drum (pe care poate merge faraonul) pe care se poate merge, în siguranţă, unde fiecare pas este ales “la întâmplare”(excepţie atunci când există o singură variantă pentru următorul pas - prima linie sau prima coloană) | + | - Simulaţi un număr de drumuri valide ca încercări pentru a găsi **un drum sigur** |
| - | - (bonus) Aflaţi numărul de drumuri | + | - (bonus) Aflaţi |
| <note important> | <note important> | ||
| Linia 73: | Linia 81: | ||
| -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> |
| + | NU se lasă rând liber pentru Ci == 0. La ieşire vor fi atâtea rânduri câte valori ale indicatorilor (Ci) sunt 1. | ||
| + | </ | ||
| ==== Exemple ==== | ==== Exemple ==== | ||
| Linia 85: | Linia 95: | ||
| 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 122: | Linia 132: | ||
| Explicaţii: | Explicaţii: | ||
| - | Toate drumurile | + | Toate drumurile |
| 7-> | 7-> | ||
| 7-> | 7-> | ||
| Linia 130: | Linia 140: | ||
| 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 153: | Linia 171: | ||
| 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 === | ||
teme/tema3.1493924058.txt.gz · Ultima modificare: 2017/05/04 21:54 de către mihai.iacov
Exceptând locurile unde este altfel specificat, conținutul acestui wiki este licențiat sub următoarea licență: CC Attribution-Share Alike 4.0 International
