Clasa a VI-a lecția 12 - 08 dec 2015
Tema Rezolvari
- codificare
- pătrate 1
- medalion dată la ONI 2012 clasa a 6a
- Agent 007 dată la Olimpiada locala 2015, Clasa a 6-aa
Rezolvari aici: [1]
Lecție
Vectori de direcţie
Atunci cînd avem de parcurs o matrice într-o ordine complexă, sau atunci cînd avem de simulat deplasarea unui obiect pe o tablă, trebuie să codificăm într-un fel direcţia de mers. Aceasta se poate face folosind teste multiple, cu instrucţiuni if sau switch. Programul nostru devine mai mare şi mai lent.
Soluţia? Vom codifica direcţiile posibile folosind doi vectori preiniţializaţi, care memorează valorile de adunat la linie, respectiv la coloană. De exemplu, dacă un obiect se poate deplasa într-o matrice pe linie sau pe coloană, vom declara vectorii diferenţă pe linie, respectiv pe coloană astfel:
int dlin[4] = { 0, 1, 0, -1 };
int dcol[4] = { 1, 0, -1, 0 };Dacă codificăm direcţiile astfel:
0 - dreapta 1 - jos 2 - stînga 3 - sus
Atunci, pentru a ne deplasa în direcţia d va trebui să adunăm dlin[d] la linie şi dcol[d] la coloană:
lin = lin + dlin[d];
col = col + dcol[d];Dar dacă ne putem deplasa şi pe diagonale? Atunci vom avea opt direcţii şi opt elemente în vector. De exemplu:
int dlin[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
int dcol[8] = { 1, 1, 0, -1, -1, -1, 0, 1 };
Bordarea matricelor
Atunci cînd avem de parcurs o matrice într-o ordine complexă, sau atunci cînd avem de simulat deplasarea unui obiect pe o tablă, trebuie să testăm dacă nu cumva coordonatele actuale sînt în afara matricei. Aceasta înseamnă că în bucla noastră va trebui să avem patru teste: dacă linia este mai mică decît zero sau mai mare decît numărul de linii, sau coloana este prea mică sau prea mare. Aceste patru condiţii trebuie testate la fiecare iteraţie, încetinind programul nostru şi adăugînd cod suplimentar. De exemplu, dacă vrem să executăm o buclă while pînă ce ieşim din matrice vom scrie ceva de genul:
int tabla[200][200];
while ( lin >= 0 && lin <= m && col >= 0 && col <= n ) {
// execută corpul buclei
}Soluţia? Vom declara matricea cu o bordură de un element, avînd grijă ca acea bordură să conţină valori care nu se pot afla în matrice. Astfel, testele de ieşire din matrice se transformă într-unul singur: vom verifica dacă elementul curent este diferit de cel din bordură. De asemenea, bordura poate sa reprezinte si o valoare de initializare, cad calculam de pilda suma elementelor de pe o linie, pana la o pozitie data.
int tabla[202][202];
while ( tabla[lin][col] != bordura ) {
// execută corpul buclei
}Observaţie 1: matricea se declară cu două elemente în plus pe fiecare dimensiune. De asemenea, coordonatele în matrice vor începe de la unu. Cum de permitem acest lucru, cînd de peste un an vorbim despre faptul ca vectorii încep de la zero? Deoarece în acest caz elementele zero sînt folositoare pentru detecţia ieşirii din matrice, nu sînt aruncate!
Observaţie 2: elementele din bordură sînt elemente santinelă. Ele ne "păzesc" să nu ieşim din matrice. Ce alte exemple de folosire a santinelei mai cunoaşteţi?
Observaţie 3:: uneori bordura poate fi de două elemente "grosime", ca atunci cînd avem de deplasat un cal pe tabla de şah. În rare ocazii ea poate fi chiar şi mai mare.
Tema
Rezolvări aici [2]
