Clasa a VI-a lecția 14 - 20 dec 2018

From Algopedia
Jump to: navigation, search

Tema - rezolvări

Problema figura

Comentarii generale

  • Felicitări celor ce au reușit o soluție optimă: Grecu, Mușat, Rebengiuc, Ilie (surprinzător de puțini).
  • Unii din voi ați declarat matricea mai mare pentru a nu avea excepții la testarea punctelor de pe margini. Dar ați declarat-o greșit cu doar o linie și o coloană în plus. Trebuia să o declarați cu două linii și coloane în plus.
  • Mulți dintre voi testat cele patru puncte din jurul punctului curent pentru a aduna sau a scădea unu la rezultatul final, dar nu v-ați prins că nu erau necesare teste, ci puteați scrie o formulă. Vedeți soluția de mai jos.
  • Unii din voi au căutat perechi de puncte adiacente. Pentru aceasta au generat toate perechile de puncte. Atenție, complexitatea acestei soluții este foarte rea: 'O(D4)!
  • Avertisment pentru programe aproape identice: Calotă și Stoian.
  • Avertismente celor ce nu au trimis nici o soluție la această problemă: Coman.

Comentarii individuale

Grupa de dimineață

  • Aizic: ai declarat matricea de latură 21. Pentru a putea accesa elementul n+1 trebuia să o declari de latură 22. Atenție! Motivul pentru care soluția nu funcționează este faptul că modifici valorile din matrice. Uneori un element '4' poate să ajungă la zero (atunci cînd este înconjurat de pătrate pline). Drept care elementele învecinate lui vor apărea ca neavînd vecin, motiv pentru care nu scazi laturile comune. Soluția ta este una încîlcită. Era mai bine să memorezi în matrice doar 1 sau zero, dacă aveai sau nu căsuța marcată.
  • Badea: simpatică metoda. Ai grijă la complexitate, cît este ea? O(D4). Dacă D ar fi puțin mai mare nu te-ai încadra în timp. Condiția de vecinătate poate fi simplificată puțin: (abs(x[i]-x[j])+abs(y[i]-y[j]))==1)
  • Benescu: însănătoșire grabnică!
  • Burac: program foarte bun, bravo. Însă la citire ai o goangă mare. În loc să scrii:
  for ( i = 0; i < n; i++ )
    fscanf ( fin, "%d%d", &v1[i], &v2[i] );

  for ( i = 0; i < d; i++ ) {
    for ( j = 0; j < d; j++ ) {
      for ( x = 0; x < n; x++ ) {
        if ( i + 1 == v1[x] && j + 1 == v2[x] )
          a[i][j] = 1;
      }
    }
  }

Era mai simplu și mult mai eficient să citești cele două valori și să le folosești direct ca linie și coloană în matrice, nu? Adică:

  for ( i = 0; i < n; i++ ) {
    fscanf ( fin, "%d%d", &l, &c );
    a[l-1][c-1] = 1;
  }
  • Calotă: program identic cu al lui Stoian. Aveți inclusiv aceeași ciudățenie, scădeți inutil unu din linie și din coloană. Cine este originalul? Ai grijă la complexitate, cît este ea? O(D4). Dacă D ar fi puțin mai mare nu te-ai încadra în timp.
  • Chivu: program aproape perfect, bravo! Păcat că nu ai închis fișierele.
  • Cojocariu: foarte drăguță metoda. O singură observație, în loc să scrii
    if(f[l-1][c]==0)
      p++;
    else
      p--;

era mai simplu și mai eficient să scrii:

    p += 1 - 2 * f[l-1][c];

Mai mult, cele patru adunări s-ar fi transformat într-una singură:

    p += 4 - 2 * (f[l-1][c] + f[l+1][c] + f[l][c-1] + f[l][c+1]);

Ai grijă la matematică, este necesară foarte des.

  • Cojocaru: o soluție bună, sper că este a ta. Indentarea este absolut neglijentă, ceea ce tu nu greșești. Ca observație, codul:
for ( i = 1; i <=n; i++ ){
  for ( j = 1; j <= n; j++ ){
    if(a[i][j]==1){
        if(a[i-1][j]==0)
            s++;
        if(a[i][j-1]==0)
            s++;
        if(a[i+1][j]==0)
            s++;
        if(a[i][j+1]==0)
            s++;
    }
}
}

ar fi putut fi scris mult mai simplu:

for ( i = 1; i <=n; i++ )
  for ( j = 1; j <= n; j++ )
    if(a[i][j]==1)
      s += 4 - a[i-1][j] - a[i+1][j] - a[i][j-1] - a[i][j+1];
  • Coman: nimic?
  • Dragomir: nu mi-e clar ce ai vrut să faci. Nu are sens să compari o linie cu ultima linie, căsuțele marcate nu vin în nici o ordine specială. Pe orice ai fi testat ai fi văzut că algoritmul nu funcționează. Cum e posibil să iei 100p la leduri și 10p la figura?
  • Grecu: rezolvare foarte bună, Bravo!
  • Hossu: Program foarte bun, bravo. Atenție la declararea matricei, trebuia de 22x22 elemente. În loc de:
  rez = 0;
  for (al = 1; al <= d; al++) {
    for (ac = 1; ac <= d; ac++) {
      if (v[al][ac] == 1) {
        if (v[al][ac - 1] == 0)
          rez++;
        if (v[al][ac + 1] == 0)
          rez++;
        if (v[al + 1][ac] == 0)
          rez++;
        if (v[al - 1][ac] == 0)
          rez++;
      }
    }
  }

puteai să scrii mai simplu:

  rez = 0;
  for (al = 1; al <= d; al++)
    for (ac = 1; ac <= d; ac++)
      if (v[al][ac] == 1)
        rez += 4 - v[al][ac - 1] - v[al][ac + 1] - v[al + 1][ac] - v[al - 1][ac];
  • Iordache: o soluție foarte bună. Vezi mai jos cum se poate simplifica în continuare.
  • Mocanu: o soluție foarte interesantă, în care parcurgi doar elementele unu din matrice. Se putea simplifica. În loc de:
  p=0;
  for(i=0;i<m1;i++){
    if(m[v[0][i]+1][v[1][i]]==0){
      p++;
    }
    if(m[v[0][i]-1][v[1][i]]==0){
      p++;
    }
    if(m[v[0][i]][v[1][i]+1]==0){
      p++;
    }
    if(m[v[0][i]][v[1][i]-1]==0){
      p++;
    }
  }

puteai scrie, mai simplu și mai eficient:

  p=0;
  for(i=0;i<m1;i++)
    p += 4 - m[v[0][i]+1][v[1][i]] - m[v[0][i]-1][v[1][i]] - m[v[0][i]][v[1][i]+1] - m[v[0][i]][v[1][i]-1];
  • Mușat: o soluție perfectă, bravo.
  • Nicola: însănătoșire grabnică!
  • Petcu: o soluție corectă, bravo! De ce ai declarat vectorii de 441 de elemente? Corect era de 400 de elemente. Ai grijă la complexitate, cît este ea? O(D4). Dacă D ar fi puțin mai mare nu te-ai încadra în timp. La testarea adiacenței a două puncte calculezi diferențele pe x si pe y, dar apoi nu le testezi pentru egalitatea cu zero, ci compari chiar liniile între ele, sau coloanele. Codul se poate simplifica. În loc de:
            if( ( l[i] == l[j] && x == 1 ) || ( c[i] == c[j] && y == 1 ) )
                p -= 2;

ai putea scrie altceva. Tu ai deja diferențele în valoare absolută în x și y. Vrei să testezi ca una din ele să fie 0 și cealaltă să fie 1. Singurul mod în care acest lucru este posibil este dacă suma lor este 1. Deci:

            if( ( x + y == 1 ) )
                p -= 2;
  • Rebengiuc: Program perfect, bravo! Comentarii bune.
  • Rughiniș: vacanță plăcută. Era bine să faci tema.
  • Stoian: program identic cu al lui Calotă. Aveți inclusiv aceeași ciudățenie, scădeți inutil unu din linie și din coloană. Cine este originalul? Ai grijă la complexitate, cît este ea? O(D4). Dacă D ar fi puțin mai mare nu te-ai încadra în timp.
  • Ștefănescu: program foarte bun, bravo. Atenție mare la copy/paste, ultimul if din buclele de calcul al perimetrului este incorect, ai duplicat penultimul if dar ai uitat să schimbi semnul minus în plus. Programul se poate simplifica. În loc de:
    for (l=1; l<=d; l++) {
        for (c=1; c<=d; c++) {
            if (a[l][c] == 1) {
                if (a[l-1][c] == 0) {
                    nr++;
                }
                
                if (a[l+1][c] == 0) {
                    nr++;
                }
                
                if (a[l][c-1] == 0) {
                    nr++;
                }
                
                if (a[l][c-1] == 0) {
                    nr++;
                }
            }
        }
    }

puteai să scrii mai simplu:

    for (l=1; l<=d; l++) {
        for (c=1; c<=d; c++) {
            if (a[l][c] == 1)
                nr += 4 - a[l-1][c] - a[l+1][c] - a[l][c-1] - a[l][c+1];
  • Togan: program foarte bun. Atenție mare la limitele buclelor for! Ele nu sînt de la zero la d+1 ci de la 1 la d. Programul se poate simplifica. În loc de:
    a=0;
    for(l=0;(d+2)>l;l++){
      for(c=0;(d+2)>c;c++){
        if(m[l][c]==0){
          if((m[l+1][c]==1)&&(l+1<(d+2))){
            a++;
          }
          if((m[l][c-1]==1)&&(c-1>=0)){
            a++;
          }
          if((m[l-1][c]==1)&&(l-1>=0)){
            a++;
          }
          if((m[l][c+1]==1)&&(c+1<(d+2))){
            a++;
          }
        }
      }
    }

puteai să scrii mai simplu:

    a=0;
    for(l=1;l<=d;l++)
      for(c=0;c<=d;c++)
        if(m[l][c]==0)
          a += m[l+1][c] + m[l][c-1] + m[l-1][c] + m[l][c+1];
  • Voicu: programul este foarte bun. Dar atenție la limitele matricei, ai declarat-o de dimensiune 21, dar trebuia de 22. Ai grijă că !a[i][j+1] este mai ineficient decît 1-a[i][j+1], deoarece conține teste.

Grupa de după-amiază

  • Asgari: program foarte bun. Parantezele pătrate ale vectorilor se lipesc de expresia din interior, nu mai lăsa spații. Programul se poate simplifica. Dacă nu foloseai funcții te prindeai de asta. În loc de:
    p = 0;
    for( i = 1; i <= d; ++i )
      for( j = 1; j <= d; ++j )
        if( mat[ i ][ j ] == 1 )
          p = p + test( i - 1, j ) + test( i, j - 1 ) + test( i + 1, j ) + test( i, j + 1 );

puteai să scrii:

    p = 0;
    for( i = 1; i <= d; ++i )
      for( j = 1; j <= d; ++j )
        if( mat[ i ][ j ] == 1 ) 
          p = p + 4 - mat[i-1][j] - mat[i][j-1] - mat[i+1][j] - mat[i][j+1];

Această variantă este mai eficientă pentru că nu conține teste.

  • Cadîr: o soluție corectă, bravo! Codul se poate simplifica. În loc de:
    sol = 0;
    for (i = 1; i <= d; i++){
      for (j = 1; j <= d; j++){
        if (a[i][j] == 1){
          if (a[i][j - 1] == 0)
            sol++;
          if (a[i - 1][j] == 0)
            sol++;
          if (a[i + 1][j] == 0)
            sol++;
          if (a[i][j + 1] == 0)
            sol++;
        }
      }
    }

puteai scrie:

    sol = 0;
    for (i = 1; i <= d; i++){
      for (j = 1; j <= d; j++){
        if (a[i][j] == 1)
          sol += 4 - a[i][j - 1] - a[i - 1][j] - a[i + 1][j] - a[i][j + 1];
  • Dobre: ideea este foarte bună. Dar implementarea este cam încîlcită. Tu cauți în matrice primul element nenul. Pe care îl prelucrezi testînd dacă și vecinii lui la dreapta și jos sînt și ei unu. Apoi treci la următorul element 1. Puteai să faci același lucru, mai simplu, parcurgînd matricea pe linii, în două bucle for, și testînd valoarea fiecărui element. Dacă este 1 îl prelucrezi.
  • Fares: o soluție corectă, bravo! Codul se poate simplifica. În loc de:
  sol = 0;
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++)
      if (mat[i][j] == 1) {
        if (mat[i + 1][j] == 0)
          sol++;
        if (mat[i - 1][j] == 0)
          sol++;
        if (mat[i][j + 1] == 0)
          sol++;
        if (mat[i][j - 1] == 0)
          sol++;
      }

puteai scrie:

  sol = 0;
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++)
      if (mat[i][j] == 1)
        sol += 4 - mat[i + 1][j] - mat[i - 1][j] - mat[i][j + 1] - mat[i][j - 1];
  • Ilie: Program perfect, bravo!
  • Ipate: foarte drăguță metoda. O singură observație, în loc să scrii
        if( l == 0 )
            rez ++;
        else if( m[l-1][c] == 0 )
            rez ++;
        else
            rez --;

era mai simplu și mai eficient să scrii:

    rez += 1 - 2 * m[l-1][c];

Pentru a scăpa de cazul limită (l == 0) puteai să declari matricea mai mare cu două elemente pe fiecare direcție. Apoi, cele patru adunări s-ar fi transformat într-una singură:

    rez += 4 - 2 * (m[l-1][c] + m[l+1][c] + m[l][c-1] + m[l][c+1]);

Atenție la matematică.

  • Marcu: rezolvare foarte bună. Vezi mai jos cum puteai face ceva mai simplu și fără condiții.
  • Nicu: codul tău este aiurit. Declari 5 matrice în loc de una singură, din care folosești doar 4. Îmi este neclar cum funcționează, dar pare că e corect. Vezi mai jos o soluție mai simplă.
  • Stancu: un program foarte bun, bravo! Ar fi luat 100p dacă parcurgeai toată matricea. Însă ai uitat că ai două coloane și două linii în plus, iar parcurgerea trebuia făcută de la 1 la d, nu de la 0 la d-1.
  • Tatomir: program aproape perfect. Păcat că ai declarat matricea prea mică și ieși din ea (dimensiune 21 în loc de 22).
  • Teodorescu: soluție foarte bună, bravo! Ai fi putut simplifica programul dacă observai că poți scrie o formulă. Vezi mai jos cum.

Rezolvare

Problema figura a fost dată la ONI 2010 clasa a 6a. O rezolvare simplă folosind matrice este: citim coordonatele i și j și setăm a[i][j] = 1. Fiecare căsuța adaugă 4 la perimetru, cu excepția laturilor pe care are vecini. De aceea vom parcurge matricea și pentru fiecare element 1 adunăm 4 – nr vecini la perimetru. Pentru a nu avea cazuri limită la frontiera matricei vom lăsa o "bordură" de zero în jur dimensionînd matricea cu 2 in plus față de maxim. În felul acesta toate elementele 1 vor avea vecini.

Iată un program posibil:

#include <stdio.h>

char a[22][22];

int main() {
  FILE *fin, *fout;
  int n, d, i, l, c, per;

  fin = fopen( "figura.in", "r" );
  fscanf( fin, "%d%d", &d, &n );
  for ( i = 0; i < n; i++ ) {
    fscanf( fin, "%d%d", &l, &c );
    a[l][c] = 1;
  }
  fclose( fin );

  per = 0;
  for ( l = 1; l <= d; l++ )
    for ( c = 1; c <= d; c++ )
      if ( a[l][c] == 1 )
        per = per + 4 - a[l-1][c] - a[l+1][c] - a[l][c-1] - a[l][c+1];

  fout = fopen( "figura.out", "w" );
  fprintf( fout, "%d\n", per );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție? Destul de ușor de calculat, O(D2), atît ca timp cît și ca memorie.

Suprapuneri 1

Comentarii generale

  • Avertismente celor ce nu au trimis nici o soluție la această problemă, sau au trimis o soluție de zero puncte: Aizic, Coman, Cojocariu (0p), Cojocaru, Grecu (0p), Iordache (0p), Stoian, Cadîr.

Rezolvări

Problema suprapuneri 1 a fost dată la OJI 2007 clasa a 9a. Cum rezolvăm această problemă?

Rezolvare 1

Rezolvarea comisiei este cea clasică: citim şablonul, apoi citim pe rînd mostrele. Pentru fiecare mostră citită efecutăm toate rotaţiile posibile, apoi răsturnăm matricea şi iar efectuăm toate rotaţiile posibile. După fiecare transformare verificăm dacă şablonul şi mostra sînt egale, caz în care ne oprim şi afişăm 1. Dacă nu am găsit nici o egalitate afişăm 0.

Rezolvare 2

O rezolvare ceva mai simplă se bazează pe faptul că, avînd destulă memorie la dispoziţie, putem stoca nu numai șablonul, ci şi toate poziţiile sale, rotații și răsturnare pe dos. Vor fi cu totul opt poziţii, incluzînd originalul. Vom stoca aceste matrice ca un vector de matrice, sau un tablou tridimensional. Cele opt transformări ale matricei originale șablon pot fi calculate chiar în timpul citirii: fiecare element citit va fi depus atît la poziţia l,c, cît şi la poziţiile corespunzătoare în celelalte matrice, precum se vede în programul de mai jos.

Odată create toate variantele de șablon putem proceda ca la rezolvarea 1: vom compara element cu element matricele mostră cu toate pozițiile șablonului, oprindu-ne cînd găsim una identică.

Această rezolvare este ceva mai scurtă, nemaiavînd nevoie de liniile de program care rotesc matricea si o inversează. În schimb necesită atenţie mare la jocul de indici care permite completarea în paralel a celor opt matrice.

Iată programul care implementează aceste idei:

#include <stdio.h>

int sablon[8][50][50], cartela[50][50];

int main() {
  FILE *fin, *fout;
  int n, nc, l, c, i, poz;

  fin = fopen( "suprapuneri1.in", "r" );
  fout = fopen( "suprapuneri1.out", "w" );
  fscanf( fin, "%d%d", &n, &nc );
  // citeste sablonul si genereaza cele 8 pozitii ale lui
  for ( l = 0; l < n; l++ )
    for ( c = 0; c < n; c++ ) {
      fscanf( fin, "%d", &sablon[0][l][c] );
      sablon[1][c][n-l-1] =
        sablon[2][n-l-1][n-c-1] =
        sablon[3][n-c-1][l] =
        sablon[4][c][l] =
        sablon[5][n-l-1][c] =
        sablon[6][n-c-1][n-l-1] =
        sablon[7][l][n-c-1] = sablon[0][l][c];
    }
  for ( i = 0; i < nc; i++ ) {
    // citeste cartela
    for ( l = 0; l < n; l++ )
      for ( c = 0; c < n; c++ )
        fscanf( fin, "%d", &cartela[l][c] );
    // comparam cartela cu sablonul rotit in toate pozitiile
    poz = l = 0;
    while ( l < n && poz < 8 ) {
      l = c = 0;
      while ( l < n && sablon[poz][l][c] == cartela[l][c] ) {
        c++;
        if ( c >= n ) {
          l++;
          c = 0;
        }
      }
      poz++;
    }
    // daca s-a potrivit la vreuna din pozitii inseamna ca l a depasit n
    if ( l < n )
      fprintf( fout, "0\n" );
    else
      fprintf( fout, "1\n" );
  }
  fclose( fin );
  fclose( fout );

  return 0;
}

Ce complexitate are soluția? Citirea unei mostre este O(N2), la fel și comparația unei mostre cu șablonul. Ambele se execută de M ori. Complexitatea finală este O(M·N2). Memoria este O(N2) deși avem opt astfel de matrice, deoarece 8 este o constantă. Desigur că în practică vom avea 4·8·N2 octeți necesari, adică circa 80KB.

Problema Leduri

Problema leduri a fost dată la .campion 2003. Dacă memorăm zece matrice de cifre ale ceasului problema devine una de comparare de matrice. Pentru simplificare putem memora cele zece matrice ca vector de matrice, adică un tablou tridimensional preinițializat.

Iată un program posibil:

#include <stdio.h>

char cifre[10][5][3] = {
  { "###",
    "#.#",
    "#.#",
    "#.#",
    "###" },
  { ".#.",
    ".#.",
    ".#.",
    ".#.",
    ".#." },

  { "###",
    "..#",
    "###",
    "#..",
    "###" },

  { "###",
    "..#",
    "###",
    "..#",
    "###" },

  { "#.#",
    "#.#",
    "###",
    "..#",
    "..#" },

  { "###",
    "#..",
    "###",
    "..#",
    "###" },

  { "###",
    "#..",
    "###",
    "#.#",
    "###" },

  { "###",
    "..#",
    "..#",
    "..#",
    "..#" },

  { "###",
    "#.#",
    "###",
    "#.#",
    "###" },

  { "###",
    "#.#",
    "###",
    "..#",
    "###" } };

char ora[4][5][3];
int minh[4];

int main() {
  FILE *fin, *fout;
  int l, c, poz, cf;

  fin = fopen( "leduri.in", "r" );
  // citim cifrele in ordinea data
  // fiecare rind contine cite o linie din cele patru cifre
  for ( l = 0; l < 5; l++ )
    for ( poz = 0; poz < 4; poz++ ) {
      for ( c = 0; c < 3; c++ )
        ora[poz][l][c] = fgetc( fin );
      fgetc( fin );
    }
  fclose( fin );

  for ( poz = 0; poz < 4; poz++ ) {
    cf = -1;
    do {
      cf++;
      // compara ora[poz][*][*] cu cifre[cf][*][*]
      l = c = 0;
      while ( l < 5 && (ora[poz][l][c] == '.' || cifre[cf][l][c] == '#') )
        if ( ++c >= 3 ) {
          c = 0;
          l++;
        }
    } while ( l < 5 );
    minh[poz] = cf;
  }

  fout = fopen( "leduri.out", "w" );
  fprintf( fout, "%d%d:%d%d\n", minh[0], minh[1], minh[2], minh[3] );
  fclose( fout );

  return 0;
}

Rezolvări 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, posibil, 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 };

Exemplu: problema medalion

Pentru a rezolva primul punct al problemei medalion, completarea matricei spirală, vom declara matricea și apoi vectorii de direcție astfel:

int a[301][301];
int dlin[4] = { 1, 0, -1, 0 };
int dcol[4] = { 0, -1, 0, 1 };

Pentru a completa o matrice de dimensiune nxn:

  l = c = n / 2;
  a[l][c] = contor = 1;
  for ( len = 2; len < n; len += 2 ) {
    // trasam patru segmente de lungime len incepind cu patratica imediat 
    // la dreapta ultimei patratele
    l--; // ne deplasam diagonal in sus
    c++;
    for ( dir = 0; dir < 4; dir++ ) // pentru fiecare din cele patru directii
      for ( i = 0; i < len; i++ ) { // trasam len patratele
        l += dlin[dir];             // avansam conform vectorului de directie
        c += dcol[dir];
        contor++;
        if ( contor > k )
          contor = 1;
        a[l][c] = contor;
      }
  }

Vom vedea și alte 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 exemplul anterior, presupunînd că matricea conține doar elemente strict mai mari decît zero, 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
}

Exemplu: problema ținta

Iată un mod în care am putea face punctul a) al problemei ținta: deoarece matricea este inițial preinițializată cu zero, o vom borda pe cele patru laturi cu patru valori diferite, numerele de la 1 la 4. De asemenea vom memora o pereche de vectori care pentru fiecare din acele valori ne spune ce trebuie să adunăm la linie, respectiv coloană, pentru a ajunge în matrice la poziția următoare locului de unde s-a ieșit din matrice.

De exemplu, dacă ieșim din matrice pe latura de sus (linia devine -1), va trebui să adunăm unu la linie, iar coloana rămîne neschimbată (deja am incrementat-o cînd am ieșit din matrice). Cele două valori corespunzătoare în cei doi vectori vor fi 1 și 0. Similar, dacă ieșim din matrice pe latura din dreapta (coloana devine n), va trebui să micșorăm coloana și să mărim linia cu doi, deci valorile de adunat în cei doi vectori vor fi 2 și -1. Procedăm similar pentru celelalte două laturi ale matricei.

Codul va fi următorul:

Mai întîi matricea și vectorii de incremente de linie și coloană:

// incremente de linie si coloana cind iesim din matrice
int incl[5] = { 0, 1, 2, -1, 0 };
int incc[5] = { 0, 0, -1, 2, 1 };
int a[1002][1002]; // matricea plus bordura de latime 1

Iar apoi parcurgerea matricei și înscrierea valorilor:

for ( c = 2; c <= n ; c++ )     // cind iesim in sus - tip 1
    a[0][c] = 1;
  for ( l = 0; l <= n - 1; l++ )  // cind iesim in dreapta - tip 2
    a[l][n+1] = 2;
  for ( c = n - 1; c >= 0 ; c-- ) // cind iesim in jos - tip 3
    a[n+1][c] = 3;
  for ( l = n; l >= 3; l-- )      // cind iesim in stinga - tip 4
    a[l][0] = 4;

  // completeaza matricea ceruta la punctul a)
  // incepem completarea
  l = c = 1; // pornim dincoltul din stinga-sus
  d = -1;    // incrementul de linie (cel de coloana este negativul lui)
  for ( i = 1; i <= n * n; i++ ) { // pentru fiecare numar de asezat, i
    a[l][c] = i;         // il asezam in matrice
    l += d;              // avansam la urmatoarea pozitie
    c -= d;
    if ( a[l][c] > 0 ) { // daca am iesit din matrice
      d = -d;            // schimbam directia
      aux = a[l][c];
      l += incl[aux];    // ajustam (l c) conform incrementelor prestabilite
      c += incc[aux];
    }
  }

}

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.

Codul rezultat va fi:

  // incepe simularea
  while ( teren[l][c] != -1 ) { // nu am mai fost aici, continuam
    // avem coordonate valide, deci le afisam
    fprintf( fout, "%d %d\n", l, c );
    dir = teren[l][c] % 4; // calculam restul
    teren[l][c] = -1;      // marcam faptul ca am mai fost aici
    l += ldif[dir]; // calculam noua linie
    c += cdif[dir]; // calculam noua coloana
  }

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:

  // incepe simularea
  b = r = 0;
  t = n - 1; // n - 1 sectoare necalcate
  calcat[0] = 1; // sector calcat de macar unul din copii
  sarituri = 0;
  do {
    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 ( calcat[b] == 0 ) // scadem numar sectoare calcate
      t--;
    if ( r != b && calcat[r] == 0 ) // scadem numar sectoare calcate
      t--;
    calcat[b] = calcat[r] = 1; // marcam sectoare calcate
  } while ( b != 0 && r != 0 && b != r );

Temă

Rezolvaţi următoarele probleme introductive de simulare. Folosiţi tehnicile nou învăţate: vectori de direcţie și bordarea matricei.

Tema 14 clasa a 6a

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

Rezolvări aici [2]