Clasa VI/VII/VIII lecția 5 - 02 oct 2012

Introducere

• Nu citiți indicațiile de la campion. Se cheamă că trișați. Nu învățați nimic în acest fel. Încercați să vă descurcați singuri, căutînd pe web, de exemplu. Doar într-un final, dacă nu găsiți singuri soluția, puteți să vă uitați la descrierea soluției de la campion.
• Comentați codul cînd e ceva complicat, de exemplu o formulă. Scrieți ideea algoritmului, dacă nu e ceva trivial. Nu trebuie să umpleți de comentarii, dar minimal. Mă ajutați mult în corectarea temei.
• Denumiți variabilele mai clar. Nu lungi, dar să aibă semnificație: prod, sum, nrcf, etc.
• Cronometrați-vă. Veți afla ce ați fi făcut la concurs.
• Vă rog să citiți regulile de programare din lecția 2 și să le respectați. Fără break/continue! Nu abuzați stegulețele ☺ Felicitări lui Alex pentru adaptarea rapidă.
• Nu folosim funcții gen sort și qsort. Aveți nevoie de dispensă specială ☺
• Exemplu unde nu sînt necesare break sau stegulețe: căutarea unui element e în vectorul v:

  i = 0;
  while ( (i < n) && (v[i] != e) )
    i++;

Lecție

Recapitulare

• Probleme de bază cu secvențe (șiruri de numere care nu necesită stocare în vectori):
  • Verificare secvență crescătoare prin rotație. O secvență este crescătoare prin rotație dacă fie este crescătoare, fie poate fi făcută crescătoare prin rotații succesive (permutări circulare). Am discutat despre rezolvarea liniară, care nu necesită vectori.
  • Verificare secvență bitonă prin rotație. O secvență este bitonă dacă mai întîi crește și apoi, eventual, descrește. O secvență bitonă prin rotație este o secvență care fie este bitonă, fie poate fi făcută bitonă prin rotații succesive. Am discutat foarte pe scurt soluția liniară, fără vectori.
  • Verificare expresie cu paranteze. Se dă o expresie cu paranteze rotunde și pătrate () și []. Ele pot să apară în orice ordine, adică și ) după ]. Să se spună dacă o expresie este corectă. Exemple: ([()[]()]())[] este corectă, ([)], )(, ([()] nu sînt corecte. Am discutat despre cazul mai simplu, în care avem doar paranteze rotunde, apoi am generalizat la cazul cu două tipuri de paranteze, folosind o stivă.

• Elementul majoritar. Dat un vector cu n elemente să se spună dacă conține un element majoritar. Un element majoritar este un element care apare de cel puțin n/2 + 1 ori. Am discutat variante de algoritmi:
  • Forță brută: luăm fiecare element din vector și vedem de cîte ori apare. Complexitate O(n²).
  • Prin sortare: sortăm vectorul și căutăm subsecvența de elemente egale de lungime maximă. Complexitate: O(n²) cu sortare prin selecție, O(n log n) cu quicksort.
  • Algoritmul optim: considerăm primul element drept candidat, iar apoi parcurgem vectorul, numărînd de cîte ori apare candidatul. De fiecare dată cînd apare un element diferit de candidat decrementăm contorul. Dacă contorul ajunge negativ repornim procedura cu elementul curent drept nou candidat. În final dacă candidatul are măcar o apariție îl verificăm de cîte ori apare în vector. Complexitate O(n).

Clasa a șasea: matrice

• Citire matrice, scriere matrice
• Căutare element în matrice:

i = j = 0;
while ( (i < m) && (a[i][j] != e) ) {
  j++;
  if ( j >= n ) {
    j = 0;
    i++;
  }
}

• Temă în clasă: se dă o matrice pătrată, să se modifice astfel încît în final elementele ei să fie oglindite față de diagonala principală (transpunere).

for ( i = 1; i < n; i++ )
  for ( j = 0; j < i; j++ ) {
    aux = a[i][j];
    a[i][j] = a[j][i];
    a[j][i] = aux;
  }

• Aceeași problemă pentru diagonala secundară.

for ( i = 0; i < (n - 1); i++ )
  for ( j = 0; j < (n - i); j++ ) {
    aux = a[i][j];
    a[i][j] = a[n - 1 - j][n - 1 - i];
    a[n - 1 - j][n - 1 - i] = aux;
  }

Clasa a șaptea și a opta: Recursivitate

• O funcție este recursivă dacă se autoapelează. A scrie o funcție recursivă necesită, inițial, o încredere în faptul că funcția funcționează. În fapt, cînd pornim să scriem o funcție recursivă este bine să considerăm că ea deja funcționează! Reguli:
• Înainte de a scrie cod este bine să ne clarificăm formula recurentă.
• Tratăm mai întîi cazurile simple, atunci cînd funcția poate returna o valoare fără a se autoapela.
• În final tratăm cazul de recursie, considerînd că funcția este deja scrisă pentru cazurile "mai mici", folosindu-ne de formula recurentă găsită la început.
• Exemple introductive:
  • Calcul n! Ne vom folosi de definiția recursivă: $n!={\begin{cases}1,&{\mbox{dacă }}n=1\\n\cdot (n-1)!,&{\mbox{dacă }}n>1.\end{cases}}$

    int fact( int n ) {
      if ( n == 1 )
        return 1;
      return n * fact( n - 1 );
    }

  • Calcul aⁿ. Ne vom folosi de definiția recurentă: $a^{n}={\begin{cases}1,&{\mbox{dacă }}n=0\\a\cdot a^{n-1},&{\mbox{dacă }}n>0.\end{cases}}$

    int putere( int a, int n ) {
      if ( n == 0 )
        return 1;
      return a * putere( n - 1 );
    }

  • Calcul cmmdc a două numere. Ne vom folosi de definiția recursivă a lui Euclid: $cmmdc(a,b)={\begin{cases}a,&{\mbox{dacă }}b=0\\cmmdc(b,a{\bmod {b}}),&{\mbox{dacă }}b>0.\end{cases}}$

    int cmmdc( int a, int b ) {
      if ( b == 0 )
        return a;
      return cmmdc( b, a % b );
    }

Temă

Clasa a 6-a

• Ce v-a rămas nefăcut din problemele medalion, cartier, numar5 (rezolvări medalion și numar5 aici [1])
• Problemă cu matrice: se citește o matrice pătrată de caractere 0 și 1, astfel: pe prima linie se va citi n, iar pe următoarele n linii se vor citi n caractere 0 sau 1. Afișați numărul de subpătrate ale matricei care conțin numai 1. De exemplu o matrice de dimensiune 4 care are toate elementele 1 are 16 + 9 + 4 + 1 = 30 de pătrate pline cu 1.
• problema figura de pe campion (rezolvare aici [2])

Clasa a 7-a și a 8-a

• Să se verifice dacă un număr este palindrom folosind o funcție recursivă. Definiție: un număr palindrom (sau simetric) este un număr care este identic cu răsturnatul lui. Cu alte cuvinte el arată la fel dacă îi scriem cifrele de la stînga la dreapta sau de la dreapta la stînga. Exemple de numere palindrom sînt 1221, 5229225, 27272, 44, 1.
• Să se răstoarne un vector folosind o funcție recursivă. Vectorul trebuie modificat, nu doar afișat invers.
• Opțional, grea: ${C}_{n}^{k}$- combinări de n luate cîte k. Date numerele naturale n și k, k <= n, să se afișeze toate submulțimile mulțimii {1, 2, 3, ..., n} de k elemente.
• clasa a 7-a: ce a rămas din bile6, proiecte, zigzag
• clasa a 8-a: ce v-a rămas din alune, cuburi4, optim (încercați să folosiți recursivitate) (rezolvare optim aici [3])

Rezolvări la problemele de recursivitate aici: [4]