Clasa a VI-a lecția 12 - 6 dec 2018

From Algopedia
Jump to: navigation, search

Tema - rezolvări

Problema em1 (exercițiu cu matrice nr. 1)

Problema em1 este un exercițiu de căutare și de parcurgere în matrice. Este banală, deci voi lăsa programul să explice soluția:

#include <stdio.h>

#define MAXN 1000
#define MAXM 350

char a[MAXN][MAXN], s[MAXM];

int main() {
  FILE *fin, *fout;
  int n, m, l, c, i, nrap, ch;

  fin = fopen( "em1.in", "r" );
  // citim prima linie a matricei
  n = 0;
  while ( (ch = fgetc( fin )) != '\n' ) {
    a[0][n] = ch;
    n++;
  }
  // citim restul liniilor matricei
  for ( l = 1; l < n; l++ ) {
    for ( c = 0; c < n; c++ )
      a[l][c] = fgetc( fin );
    fgetc( fin ); // citeste \n
  }
  // citim vectorul de cautat pe coloane
  m = 0;
  while ( (ch = fgetc( fin )) != '\n' ) {
    s[m] = ch;
    m++;
  }
  fclose( fin );
  // punctul a) de cite ori apare coloana s[] in a[][]
  nrap = 0;
  for ( l = 0; l <= n - m; l++ )
    for ( c = 0; c < n; c++ ) {
      i = 0;
      while ( i < m && a[l + i][c] == s[i] )
        i++;
      if ( i == m )
        nrap++;
    }
  fout = fopen( "em1.out", "w" );
  fprintf( fout, "%d\n", nrap );
  // punctul b) parcurgerea matricei
  // prima parte, deasupra diagonalei
  for ( l = 0; l < n - 1; l++ )
    for ( i = 0; i <= l; i++ )
      fputc( a[l - i][i], fout );
  // a doua parte, sub diagonala
  for ( l = n - 1; l >= 0; l-- )
    for ( i = 0; i < (n - l < l + 1 ? n - l : l + 1); i++ )
      fputc( a[l + i][n - 1 - l + i], fout );
  fputc( '\n', fout );
  fclose( fout );

  return 0;
}

Problema em2 (exercițiu cu matrice nr. 2)

Problema em2 este tot un exercițiu de căutare și de parcurgere în matrice, ca și em1. Este banală, deci voi lăsa programul să explice soluția:

#include <stdio.h>

#define MAXN 1000
#define MAXM 350

char a[MAXN][MAXN], s[MAXM];

int main() {
  FILE *fin, *fout;
  int n, m, l, c, i, nrap, ch;

  fin = fopen( "em2.in", "r" );
  // citim prima linie a matricei
  n = 0;
  while ( (ch = fgetc( fin )) != '\n' ) {
    a[0][n] = ch;
    n++;
  }
  // citim restul liniilor matricei
  for ( l = 1; l < n; l++ ) {
    for ( c = 0; c < n; c++ )
      a[l][c] = fgetc( fin );
    fgetc( fin ); // citeste \n
  }
  // citim vectorul de cautat pe linii
  m = 0;
  while ( (ch = fgetc( fin )) != '\n' ) {
    s[m] = ch;
    m++;
  }
  fclose( fin );
  // punctul a) de cite ori apare linia s[] in a[][]
  nrap = 0;
  for ( l = 0; l < n; l++ )
    for ( c = 0; c <= n - m; c++ ) {
      i = 0;
      while ( i < m && a[l][c + i] == s[i] )
        i++;
      if ( i == m )
        nrap++;
    }
  fout = fopen( "em2.out", "w" );
  fprintf( fout, "%d\n", nrap );
  // punctul b) parcurgerea matricei
  // prima parte, sub diagonala
  for ( l = 0; l < n; l++ )
    for ( i = 0; i < (n - l < l + 1 ? n - l : l + 1); i++ )
      fputc( a[l + i][l - i], fout );
  // a doua parte, deasupra diagonalei, de la stinga la dreapta, de jos in sus
  for ( l = n - 2; l >= 0; l-- )
    for ( i = 0; i <= l; i++ )
      fputc( a[l - i][n - 1 - i], fout );
  fputc( '\n', fout );
  fclose( fout );

  return 0;
}

Problema codificare

Problema codificare a fost dată la concursul .campion 2007.

Este o problemă introductivă în matrice, ea necesitînd două parcurgeri diferite ale matricei. Pentru a rezolva problema trebuie să completăm matricea pe linii, folosind șirul de la intrare, iar apoi să afișăm matricea pe coloane. Singurul aspect care merită detaliat este parcurgerea pe linii. În enunț se spune că liniile vor fi parcurse astfel: prima de la stînga la dreapta, a doua de la dreapta la stînga, a treia de la stînga la dreapta și așa mai departe. Cum facem această parcurgere?

Un mod direct este să scriem două bucle for: una pentru o parcurgere stînga-dreapta și una pentru o parcurgere dreapta-stînga. În acest caz va trebui să fim atenți să nu executăm a doua buclă dacă nu mai avem caractere la intrare. Citirea va arăta cam așa:

  fin = fopen( "codificare.in", "r" );
  fscanf( fin, "%d ", &n );
  // citim cite doua linii, una de la stinga la dreapta, alta de la dreapta
  // la stinga; nu citim a doua linie decit daca mai avem caractere
  l = 0;
  car = fgetc( fin );
  while ( car != '\n' ) {
    for ( c = 0; c < n; c++ ) { // citim prima linie, de la stinga la dreapta
      cod[l][c] = car;
      car = fgetc( fin );
    }
    l++;                             // trecem la linia urmatoare
    if ( car != '\n' ) {             // daca mai avem caractere la intrare
      for ( c = n-1; c >= 0; c-- ) { // citim linia de la dreapta la stinga
        cod[l][c] = car;
        car = fgetc( fin );
      }
      l++;
    }
  }
  fclose( fin );

Această rezolvare nu este cea mai elegantă, deoarece ea scrie de două ori aproximativ aceeași buclă for. Cum am putea să nu repetăm instrucțiuni? Putem să nu ne gîndim la citire linie cu linie, ci să ne concentrăm pe șirul de caractere la intrare. Citim cîte un caracter și calculăm locul unde trebuie pus în matrice. De la un caracter la altul coloana din matrice va varia cu 1 sau cu -1. Dacă am ajuns la capăt de linie atunci coloana rămîne pe loc și linia se mărește cu unu.

Vom proceda astfel: vom folosi o variabilă pas care va avea valoarea 1 atunci cînd citim o linie stînga-dreapta, sau -1 atunci cînd citim o linie dreapta-stînga. Atunci cînd ajungem la capăt de linie avem grijă ca pas să devină -pas, pentru a schimba direcția de parcurgere a liniei.

Iată un program bazat pe aceste idei:

#include <stdio.h>

char cod[100][20]; // matricea de criptare

int main() {
  FILE *fin, *fout;
  int n, m, l, c, pas;
  char car;

  fin = fopen( "codificare.in", "r" );
  fscanf( fin, "%d ", &n );
  l = c = 0;
  pas = 1;
  // citim cite o linie, sensul este dat de pas, care este 1 sau -1
  // de la o linie la alta schimbam sensul (pas devine -pas)
  car = fgetc( fin );
  while ( car != '\n' ) {
    cod[l][c] = car;
    c += pas;
    if ( c < 0 || c >= n ) { // am iesit din linie?
      c -= pas;   // ajustam c pentru a reintra in linie
      pas = -pas; // schimbam directia de parcurgere a liniei
      l++;        // trecem la linia urmatoare
    }
    car = fgetc( fin );
  }
  fclose( fin );

  m = l;
  fout = fopen( "codificare.out", "w" );
  // afisam caracterele pe coloane
  for ( c = 0; c < n; c++ )
    for ( l = 0; l < m; l++ )
      fputc( cod[l][c], fout );
  fputc( '\n', fout );
  fclose( fout );

  return 0;
}

Problema medalion

Problema medalion a fost dată la ONI 2012 clasa a 6a.

Punctul (a)

Pentru acest punct este necesară completarea unei matrice în spirală, pornind din centru. Una din metodele simple este să observăm că fiecare spiră de 360 grade este formată din 4 segmente egale. De exemplu, prima spiră este compusă din patru segmente de lungime doi: primul în jos, al doilea la stînga, al treilea în sus și al patrulea la dreapta. A doua spiră va avea patru segmente de lungime patru. A treia spiră va avea patru segmente de lungime 6 și așa mai departe. Toate spirele pornesc cu o pătrățică sub colțul din dreapta sus.

De acum este simplu. Am putea sa avem o buclă mare, în care desenăm o spiră. Iar pentru fiecare spiră cîte patru bucle în care desenăm cele patru segmente. Dar cele patru bucle ar fi aproape identice, cu excepția faptului că vom varia fie linia fie coloana. Pentru a nu repeta cod putem să procedăm altel. Vom coda cele patru direcții cu patru numere, de la zero la trei. Pentru fiecare din direcții cu cît variază linia și în alt vector cu cît variază coloana. Observăm că linia va varia pe direcția zero și doi, iar coloana pe direcția 1 și trei. Pentru a evita testele vom înmulți incrementele de linie cu (dir + 1) % 2 și incrementele de coloană cu dir % 2. În acest fel ne asigurăm că adunăm la linie doar pe direcțiile zero și doi, iar pe coloană doar pe direcțiile unu și trei. Ce valori pot avea incrementele? Unu sau minus unu. Formulele lor sînt relativ simple, 1 - dir pentru linie și dir - 2 pentru coloană.

Aveți o implementare a punctului (a) bazată pe aceste idei mai jos.

Punctul (b)

Să formulăm problema în limbaj informatic: dată o spirală infinită cu numere de la 1 la k și o poziție aflată cu p elemente mai sus decît primul element al spiralei să se spună ce valoare are elementul de pe acea poziție. Deoarece p poate fi 500000 este exclus să completăm matricea, deoarece vom depăși timpul: 1 milion2 = 1000 miliarde, de circa 2000 de ori mai multe operații decît putem face într-o secundă. Trebuie să găsim o formulă matematică. Vom calcula numărul de elemente ale spiralei începînd cu primul element și pînă la elementul cerut:
Medalion punctul b
Observăm din figură că numărul de elemente este cel din pătratul de latură 2p + 1 din care scădem zona gri închis de p elemente. Rezultă numărul de elemente nr = (2p + 1)2 – p. Dacă considerăm spirala conținînd elemente de la 0 la k - 1, în loc de elemente de la 1 la k, rezultă că elementul căutat va avea valoarea (nr - 1) % k. Matricea conținînd numere de la 1 la k trebuie să adunăm 1: e = (nr - 1) % k + 1. Rezultă formula finală e = [(2p + 1)2 – p - 1] % k + 1. Mare grijă trebuie avută la calculul lui e deoarece formula poate depăși tipul int. Fie lucrați cu tipul long long, fie folosiți (2p + 1) % k înainte de ridicarea la pătrat.

Iată o implementare completă:

#include <stdio.h>

int a[301][301];

int main() {
  FILE *fin, *fout;
  int k, n, p, l, c, i, cristal, sum, maxsum, e, len, dir;

  fin = fopen( "medalion.in", "r" );
  fscanf( fin, "%d%d%d", &k, &n, &p );
  fclose( fin );

  // punctul (a) generam matricea spirala
  cristal = 0;
  l = c = n / 2;
  a[l][c] = 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-dreapta
    c++;
    for ( dir = 0; dir < 4; dir++ ) // cele patru segmente ale spirei curente
      for ( i = 0; i < len; i++ ) { // trasam len patratele
        l +=  (dir + 1) % 2 * (1 - dir); // ajustam linia
        c += dir % 2 * (dir - 2);        // ajustam coloana
        cristal = (cristal + 1) % k;
        a[l][c] = cristal + 1;
      }
  }
  maxsum = 0;
  for ( l = 0; l < n; l++ ) {
    sum = 0;
    for ( c = 0; c < n; c++ )
      sum += a[l][c];
    if ( sum > maxsum )
      maxsum = sum;
  }

  // punctul (b), calculam elementul de deasupra
  e = 1 + ((2 * p + 1) % k * (2 * p + 1) % k - p % k - 1 + k) % k;

  fout = fopen( "medalion.out", "w" );
  fprintf( fout, "%d\n%d\n", maxsum, e );
  fclose( fout );

  return 0;
}

Vom vedea în cursurile următoare că pentru parcurgerea celor patru segmente ale unei spire avem și o soluție mai generală, bazată pe vectori de direcție.

Ce complexitate are această soluție? Pentru punctul a observăm că avem un număr constant de calcule pentru fiecare element al matricei, drept care complexitatea va fi O(n). Pentru punctul b complexitatea va fi, desigur, O(1). Maximul lui n fiind 301 este destul de clar că rezolvarea se va încadra lejer în timpul alocat, de 0.1s.

Rezolvări aici: [1]

Lecție

Test matrice.

Grupa de dimineață

Grupa de după-amiază

Tema

Aveți ca temă cele patru probleme date la concursurile de azi:

Tema 12 clasa a 6a

Rezolvări aici [2]