Tema - comentarii

Problema şenila este o problemă de greutate medie la care ar fi trebuit să luaţi destule puncte la concurs deoarece:

Aţi avut 1h:50min. La olimpiada naţională aveţi 1h:20min de problemă. Aţi avut 30 de minute în plus.
Rezolvarea necesită exact elementele predate ultimele, respectiv matrice şi baze de numeraţie.
Problema este structurată pe puncte de dificultăţi diferite, tocmai pentru a putea lua punctaj parţial şi dacă nu aveaţi timp să terminaţi problema.

În aceste condiţii au fost doar nouă rezultate semnificativ diferite de zero (cele de sub 5 puncte sînt datorate norocului, ele nu reprezintă o soluţie viabilă).

Şi mai grav, la temă, unde aţi avut o săptămînă, s-au adăugat doar două rezultate, slabe şi ele. În total 11 copii au reuşit să "scoată ceva" la temă.

Aceste rezultate vin după cîteva luni în care mulţi dintre voi aţi rezolvat perfect temele date. În concluzie sînteţi lei la problemele vechi, dar nu faceţi aproape nimic la o problemă nouă, pe care nu aveţi de unde să o copiaţi.

La acest cerc nu tolerăm mediocritatea. Este cercul celor mai buni dintre cei buni. În săptămînile următoare voi studia îndeaproape comportamentul vostru şi voi începe să dau afară elevii mediocri, care copiază temele.

Nu este prea tîrziu! Trebuie, însă, ca acum să încetaţi copiatul şi să vă faceţi temele singuri. Singuri înseamnă fără a folosi nici un ajutor, oricît de mic!. Cei care nu încep să facă acest lucru vor pleca de la cercul nostru. Este singurul mod în care puteţi avea rezultate la concursuri, iar fără rezultate la concursuri nu puteţi fi cei mai buni, deci nu aveţi ce căuta la cerc. Temele nu contează pentru a rămîne la cerc. Ele sînt necesare pentru studiul vostru individual.

Observaţii

Acestea sînt observaţii generale asupra codului multora dintre voi:

Singurele rezolvări complete, care au sens de la cap la coadă, sînt cele ale elevilor Tiberiu Muşat, Matei Tinca şi Tudor Roman. Felicitări!
În continuare unii din voi trimit surse C++.
În continuare unii din voi nu indentează! Poate ar trebui să vă întoarceţi la clasa a 5^a.
În continuare văd instrucţiuni for folosite pentru cicluri cu număr necunoscut de paşi!
Nu aţi folosit baza patru, ci doi, drept care mulţi aţi greşit.
Aţi folosit vectori, drept care programul a ieşit încîlcit şi aţi greşit. Unii din voi au şi rotit aceşti vectori!
Mulţi dintre voi nu aţi folosit tipul long long deşi era evident că numerele pot depăşi int.
Mulţi dintre voi aveţi warnings de compilare care constituie erori. De exemplu afişaţi un long long folosind %d în loc de %lld. Aceasta înseamnă că în continuare nu setaţi opţiunile -Wall şi -O2 şi că ignoraţi avertismentele de compilare din Code::Blocks.
Unii dintre voi aţi scris nişte aberaţii incredibile. Aceiaşi dintre voi faceţi perfect temele: Băncuţă, Ichim, Piţur.

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 };

Vom vedea exemple mai jos.

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ă. Pentru cazul anterior, presupunînd că matricea nu poate conţine zerouri, vom folosi o bordură cu elemente zero, iar codul se poate scrie astfel:

int tabla[202][202];

while ( tabla[lin][col] > 0 ) {
  // 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.

Vom vedea şi alte exemple de bordare în continuare.

Simulare

Simularea pe calculator înseamnă reprezentarea unor aspecte din lumea reală într-un program pe calculator. Programul de simulare îşi propune să calculeze nu numai rezultatele finale, cît şi rezultate de pe parcursul simulării. Deşi simularea variază în funcţie de sistemul simulat, există unele caracteristici comune:

Trebuie să avem un model, numit sistem. Sistemul evoluează, își schimbă starea. Deci avem o stare a sistemului. Ea trebuie descrisă complet, prin variabile.
Avem un ceas, așa numitul tact al sistemului, bătaia lui de inimă, precum are și procesorul. De obicei tactul sistemului este impus de problemă.
Avem o buclă, care avansează timpul cu un tact și modifică starea sistemului. Bucla testează un steguleț de oprire. În buclă se determină condiția de terminare și se setează stegulețul.

Aplicaţii

Aplicații, cu explicația variabilelor care descriu complet starea:

Problema robinson

Problema robinson a fost dată la ONI 2005 clasa a 6-a. Este o problemă tipică de parcurgere a unui drum în matrice. Drumul este predeterminat, nu avem opţiuni. Care este starea sistemului nostru? Ea este linia şi coloana lui Robinson precum şi matricea ce ţine minte pe unde a mai fost.

Iată un model de simulare clasică:

  // incepe simularea
  gata = 0;
  while ( !gata ) {
    // avem coordonate valide, deci le afisam
    fprintf( fout, "%d %d\n", l, c );
    dir = teren[l-1][c-1] % 4; // calculam restul
    teren[l-1][c-1] = -1;      // marcam faptul ca am mai fost aici
    l += ldif[dir]; // calculam noua linie
    c += cdif[dir]; // calculam noua coloana
    if ( l < 1 || l > m || c < 1 || c > m ) // setam conditia de oprire
      gata = 1;
    else if ( teren[l-1][c-1] == -1 )
      gata = 1;
  }

Acesta este un program didactic, şcolăresc. Desigur că în acest caz putem simplifica foarte mult codul, deviind de la simularea standard. În primul rînd putem folosi tehnica bordării. Vom înconjura matricea cu o bordură de elemente -1. În acest caz condiţia de oprire este cînd întîlnim un element -1. Această condiţie se poate testa direct în bucla while. Încercaţi voi această metodă.

Problema joc3

Problema joc3 a fost dată la ONI 2011 clasa a 6-a. Starea constă din poziția celor doi copii și din cîte un vector de fiecare copil care memorează pentru fiecare poziție dacă copilul a fost acolo. Simularea se termină fie cind indicii celor doi copii devin egali, fie cînd unul din copii sare pe un element 1 în vectorul său. Vom număra de cîte ori s-a executat bucla pentru a putea răspunde de cîte ori au sărit copiii. La ieșirea din bucla de simulare, vom calcula numărul de elemente zero în ambii vectori.

  // incepe simularea
  b = r = 0;
  bogdan[b] = 1; // bogdan a fost aici
  rares[r] = 1;  // rares a fost aici
  sarituri = 0;
  gata = 0;
  while ( !gata ) {
    b = (b + x) % n;     // il avansam pe Bogdan
    r = (r - y + n) % n; // il avansam pe Rares
    sarituri++; // am mai avansat o saritura pina la pozitia curenta
    if ( bogdan[b] == 1 || rares[r] == 1 || b == r )
      gata = 1;
    bogdan[b] = 1; // bogdan a fost aici
    rares[r] = 1;  // rares a fost aici
  }

Din nou, acesta este un exemplu şcolăresc de simulare. Şi în acest caz putem simplifica programul observînd că dacă un copil se întoarce pe propriile sale urme aceasta se poate întîmpla numai pe căsuţa unu. Astfel condiţia de oprire devine fie ca unul din copii sa ajunga la unu fie ca ambii copii să fie pe aceeaşi căsuţă, condiţie ce poate fi incorporată chiar în while.

Tema - şenila

Problema șenila necesită cunoștințe de baze de numerație și matrice.

Pentru a rezolva problema trebuie să observăm o mică păcăleală: deşi enunţul specifică o codificare a şenilei în baza 2, în realitate fiecare segment al şenilei este o cifră în baza 4. Drept care toate operaţiile din rezolvare trebuie efectuate în baza 4.

Punctul 1: codificarea şenilei

Pentru a rezolva primul punct, codificarea şenilei după K rotaţii va trebui să mutăm ultima cifră a numărului în baza patru de la finalul numărului la începutul numărului. Am mai rezolvat această problemă cu numere zecimale. Vom calcula puterea lui 4 necesară, respectiv 4^S-1, deoarece avem S segmente de şenilă. Ultima cifră a numărului în baza 4 este desigur z % 4. Pentru a elimina ultima cifră şi a deplasa numărul spre dreapta vom calcula z / 4. Astfel, formula care roteşte numărul în baza 4 este:

z = z / 4 + z % 4 * p4;

Rămîne de observat că nu are rost să rotim şenila de mai mult de S ori, deoarece o vom lua de la capăt, iar acest calcul poate depăşi timpul. Este suficient să o rotim de K % S ori. Complexitatea va fi O(S), faţă de O(K). Vom face maxim S-1 rotaţii.

Observaţie: putem fi tentaţi să rezolvăm această problemă cu vectori. Este o soluţie posibilă, dar programul va fi mai lung şi mai ineficient. Este o soluţie fie pentru leneşii care nu vor să gîndească, fie pentru cei ce nu stăpînesc bazele de numeraţie.

Punctul 2: coordonatele finale

Pentru a calcula coordonatele finale ale şenilei după A deplasări am putea să efectuăm A deplasări ale şenilei. Această soluţie are complexitatea O(A). Deoarece A poate fi un miliard evident că va depăşi timpul. Ce putem face? Să observăm că după o rotaţie completă a şenilei mişcarea acesteia se va repeta. Drept care putem calcula deplasarea şenilei după o rotaţie completă şi apoi să repetăm această deplasare de cîte ori se execută o rotaţie completă. Deplasarea înseamnă diferenţele pe linie şi pe coloană între punctul de start şi punctul de final. Pentru a repeta deplasarea vom înmulţi aceste diferenţe cu numărul de rotaţii complete. Ultima parte, rotaţia incompleta, va fi simulată separat.

Pentru calculul noii poziţii putem folosi vectori de direcţie. Segmentul de pe pămînt este o cifră în baza patru, ea putînd avea patru valori, corespunzătoare celor patru direcţii.

Complexitatea acestei soluţii este O(S).

Punctul 3: simularea mişcării în matrice

La acest punct trebuie să efectuăm toate mişcările cerute, deoarece ni se cere să calculăm matricea finală. Vom proceda similar cu punctul 2, însă vom efectua R rotaţii. De asemenea, vom avea grijă să înscriem codificarea şenilei la fiecare deplasare în matrice. Vom folosi din nou vectorii de direcţie. În plus, vom folosi tehnica bordării matricei, pentru a simplifica testul de ieşire de pe tablă. Deoarece matricea poate conţine elemente mai mari sau egale cu zero vom iniţializa bordura cu elemente negative, de exemplu cu -1.

Complexitate

Complexitatea totală a acestei rezolvări pare a fi O(S + S + R) care este totuna cu O(S + R) deoarece constanta 2 cu care se înmulţeşte S poate fi ignorată. Dar, deoarece avem de afişat matricea, avem de efectuat M x N operaţii de afişare, care trebuie adăugate la complexitatea finală care este O(S + R + MxN).

Rezolvări aici [1]

Probleme din urmă

În măsura în care apucăm vom vorbi despre probleme din urmă: pătrate1 şi Cartier.

Temă

Rezolvaţi următoarele probleme introductive de simulare. Folosiţi tehnicile noi învăţate, vectori de direcţie şi bordarea matricei.

Tema 14 clasa a 6^a

robinson dată la ONI 2005 clasa a 6^a
joc3 dată la ONI 2011 clasa a 6^a
furnica dată la OJI 2007 clasa a 6^a

Rezolvări aici [2]

Clasa a VI-a lecția 14 - 8 ian 2015

Contents