Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Ești aici: Structuri de date și algoritmi » Teme 2017 » Tema 3: Comoara faraonului
Traseu:
teme:tema3

Diferențe

Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.

Link către această vizualizare comparativă

Ambele părți revizuirea anterioară Versiuni anterioare
Urmatoarea versiune 		Versiuni anterioare
teme:tema3 [2017/05/04 22:19]
mihai.iacov [Cerințe] 		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://acs.curs.pub.ro/2016/mod/resource/view.php?id=4356|aici]]
 +  * Trimiterea temelor se face pe platforma [[https://vmchecker.cs.pub.ro/ui/#SDAAB|vmchecker]] (folosiți credențialele de pe acs.curs.pub.ro).
 +  * Există și un checker local pe care îl puteți descărca de [[http://acs.curs.pub.ro/2016/mod/resource/view.php?id=4354|aici]]
 +  * Pentru întrebări și nelămuriri utilizați forumul asociat temei [[http://acs.curs.pub.ro/2016/mod/forum/view.php?id=4353|aici]].
  
 ==== Descriere ==== ==== Descriere ====
Linia 33: Linia 40:
   - 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 (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ă) +  - 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 **numărul de drumuri valide sigure**.
  
 <note important> <note important>
Linia 74: 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**, nrIncercari la ieşire altfel, unde nrIncercari = numărul de încercări de la a treia cerinţă;   -Dacă (C3 == 1): nrIncercari sau 0; 0 la ieşire dacă **nrIncercari > nrMaxIncercari**, nrIncercari la ieşire altfel, unde nrIncercari = numărul de încercări de la a treia cerinţă;
-  -Dacă (C4 == 1): nrDrumuri = numărul de drumuri pe care se poate merge în siguranţă şi pe care poate merge faraonul+  -Dacă (C4 == 1): nrDrumuri = numărul de drumuri valide sigure;
  
 <note warning> <note warning>
Linia 88: 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 cu valorile 5, 2, 4 sau 9.
  
 matricea asociată acestei hărţi este:  matricea asociată acestei hărţi este: 
Linia 133: Linia 140:
  7->6->35->4->2 Suma = 54 > 24; nesigur  7->6->35->4->2 Suma = 54 > 24; nesigur
  
-Avem 2 drumuri sigure posibile pentru faraon (afişat 2 pe ultimul rând la ieşire).+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:  
 +<html> 
 +1 1  
 +<font color=#F00>0 1 0</font> 
 +1 1 
 +<font color=#F00> 1 1</font> 
 + 0 0 1. 
 +</html> 
 +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 171:
  Aceeaşi situaţie ca la prima încercare  Aceeaşi situaţie ca la prima încercare
  Solutia: 7->6->35->4->2 nesigur  Solutia: 7->6->35->4->2 nesigur
-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.1493925568.txt.gz · Ultima modificare: 2017/05/04 22:19 de către mihai.iacov

Unelte pagină

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
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki