Difference between revisions of "Clasa a VII-a lecția 6 - 17 oct 2019"

From Algopedia
Jump to: navigation, search
(A doua grupă)
 
Line 744: Line 744:
 
** [http://varena.ro/problema/v v] (ONI 2004 clasa a 7-a) Problema este modificată. Puteți lua doar 50% din punctaj. Pentru 100% '''nu este nevoie de parsing'''. Dacă introduceam cerință de parsing aș fi scăzut timpul permis.
 
** [http://varena.ro/problema/v v] (ONI 2004 clasa a 7-a) Problema este modificată. Puteți lua doar 50% din punctaj. Pentru 100% '''nu este nevoie de parsing'''. Dacă introduceam cerință de parsing aș fi scăzut timpul permis.
  
Rezolvări aici [http://solpedia.francu.com/wiki/index.php/Clasa_VII/VIII_lec%C8%9Bia_3_-_7_oct_2014]
+
Rezolvări aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_VII-a_lec%C8%9Bia_6_-_17_oct_2019]

Latest revision as of 11:52, 7 November 2019

Tema - rezolvări

Intervale

Problema intervale este o problemă de precalculare. Ea cere să se răspundă la maxim 100 000 de întrebări de forma "cîte numere naturale cu exact K divizori primi se află în intervalul [A, B]".

Comentarii generale

  • Mențiuni speciale lui Mircea Rebengiuc și Teo Tatomir, singurii care a reușit o soluție optimă, ce folosește două precalculări și liste!
  • Felicitări celor ce au reușit o soluție foarte bună și ordonată: Tudor Voicu, Fares, Ilie, Petrescu, Rebengiuc, Tatomir.
  • Încă nu știți fscanf, rău! Majoritatea ați avut probleme la citire, dar v-ați descurcat cu o complicație.
  • Mulți dintre voi ați declarat vectorul ciur de întregi. El putea fi de caractere. Este o risipă de 3MB de memorie, vă poate duce la 0p la problemă la olimpiadă. Mare atenție!
  • Mulți dintre voi ați risipit 14% din memorie, un milion de întregi = 4MB. Cum? Memorînd un vector de sume parțiale cu elemente 1, pentru K=0. Nice :-)
  • Unii dintre voi ați dat o rezolvare ineficientă, răspunzînd la întrebări prin parcurgerea ciurului de la A la B. Era clar că o asemenea soluție va depăși timpul. Trebuia să folosiți sume parțiale, precalculare, pentru a răspunde la întrebări în O(1).

Comentarii individuale

Prima grupă

  • Aizic: Program foarte bun, bravo! Observații minore: puteai să faci citirea cu un singur fscanf, citind trei valori și întrebînd dacă valoarea de return este 3. Doi, ai folosit o linie a matricei pentru K=0, cînd doar 1 va avea 0 divizori. Ai risipit 14% din memorie stocînd un vector cu unu-uri.
  • Badea: Program foarte bun, bravo! Observații minore: puteai să faci citirea cu un singur fscanf, citind trei valori și întrebînd dacă valoarea de return este 3. Doi, ai folosit o linie a matricei pentru K=0, cînd doar 1 va avea 0 divizori. Ai risipit 14% din memorie stocînd un vector cu unu-uri.
  • Benescu: Program foarte bun, bravo! Observație importantă: ciurul putea fi de tip caracter, dar tu ai folosit tip întreg! Atenție la genul acesta de erori, te pot descalifica! Observații minore: puteai să faci citirea cu un singur fscanf, citind trei valori și întrebînd dacă valoarea de return este 3. Doi, ai folosit o linie a matricei pentru K=0, cînd doar 1 va avea 0 divizori. Ai risipit 14% din memorie stocînd un vector cu unu-uri.
  • Burac: Program foarte bun, bravo! Observații minore: puteai să faci citirea cu un singur fscanf, citind trei valori și întrebînd dacă valoarea de return este 3. Doi, ai folosit o linie a matricei pentru K=0, cînd doar 1 va avea 0 divizori. Ai risipit 14% din memorie stocînd un vector cu unu-uri.
  • Calotă: Program foarte bun, bravo! Observație importantă: ciurul putea fi de tip caracter, dar tu ai folosit tip întreg! Atenție la genul acesta de erori, te pot descalifica la olimpiadă! Observații minore: puteai să faci citirea cu un singur fscanf, citind trei valori și întrebînd dacă valoarea de return este 3. Doi, ai folosit o linie a matricei pentru K=0, cînd doar 1 va avea 0 divizori. Ai risipit 14% din memorie stocînd un vector cu unu-uri.
  • Chivu: Ideea programului tău este foarte interesantă: memorezi întrebările pe liste după K. Pînă aici este foarte bine, deoarece folosești puțină memorie. Dar apoi ai o greșeală, nu observi că K este, în fapt, limitat la 7. Valoarea 1000 este aruncată la păcăleală. Atenție la matematică! Dar asta nu e grav, deoarece nu afectează algoritmul, doar ocupi ceva mai multă memorie în vectorul de liste. Algoritmul tău este ceva mai lent deoarece faci o căutare liniară în liste pentru fiecare element al ciurului. Trebuia să faci invers, să parcurgi listele și să răspunzi la întrebări în O(1). Pentru aceasta aveai nevoie de sume parțiale pe vectorul ciur. Vezi soluția. Observații: ciurul nu este vector de întregi, ci de caractere! Atenție! puteai să faci citirea cu un singur fscanf, citind trei valori și întrebînd dacă valoarea de return este 3. Vectorii a[], b[], r[] și next[] au toți aceeași dimensiune, dar tu ai declarat a[] mult mai mare.
  • Cojocariu: Program foarte bun, bravo! Observații minore: puteai să faci citirea cu un singur fscanf, citind trei valori și întrebînd dacă valoarea de return este 3. Doi, ai folosit o linie a matricei pentru K=0, cînd doar 1 va avea 0 divizori. Ai risipit 14% din memorie stocînd un vector cu unu-uri.
  • Dobre: Program bun, bravo! Citire corectă și simplă cu fscanf, bravo! Observație importantă: ciurul putea fi de tip caracter, dar tu ai folosit tip întreg! Atenție la genul acesta de erori, te pot descalifica la olimpiadă! Tu nu folosești linia 0 a matricei v[]. Deci risipeși 14% din memorie. Cam urît, nu? Te-ai complicat și la afișare, nu ai de ce să testezi dacă ciur[a]==k. În sumele parțiale scădem elementul din-naintea capătului de interval, adică v[k][a-1]. Motivul pentru care ratezi un test este pentru că te oprești cu calculul sumelor parțiale la BMAX-1. Trebuia să mergi pînă la BMAX inclusiv! Atenție la neatenție, te costă!
  • Hossu: Programul este OK ca idee, dar, precum ți-ai dat seama, are complexitate prea mare. Pentru a răspunde la o întrebare parcurgi ciurul de la a la b, complexitate O(MAXB), adică circa un milion. Trebuia să folosești sume parțiale pentru a răspunde la întrebări în O(1). Citire corectă și simplă cu fscanf, bravo! Observație importantă: ciurul putea fi de tip caracter, dar tu ai folosit tip întreg! Atenție la genul acesta de erori, te pot descalifica la olimpiadă!
  • Iordache: Program foarte bun, bravo! Observații minore: puteai să faci citirea cu un singur fscanf, fără feof(), care este periculos de folosit (de aceea nici nu l-am predat). Citeai trei valori și întrebai dacă valoarea de return este 3. Doi, ai folosit o linie a matricei pentru K=0, cînd doar 1 va avea 0 divizori. Ai risipit 14% din memorie stocînd un vector cu unu-uri.
  • Mocanu: Program foarte bun, bravo! Observații minore: puteai să faci citirea cu un singur fscanf, fără feof(), care este periculos de folosit (de aceea nici nu l-am predat). Citeai trei valori și întrebai dacă valoarea de return este 3. Doi, ai folosit o linie a matricei pentru K=0, cînd doar 1 va avea 0 divizori. Ai risipit 14% din memorie stocînd un vector cu unu-uri.
  • Mușat: Program bun, păcat că dimensionezi greșit matricea de sume parțiale. Interesant că iei 100p. K poate fi maxim 1000, iar tu ai dimensionat matricea de 9 elemente, deci ieși cu mult afară din ea. Observație importantă: ciurul putea fi de tip caracter, dar tu ai folosit tip întreg! Atenție la genul acesta de erori, te pot descalifica la olimpiadă! Puteai să faci citirea cu un singur fscanf, citind trei valori și întrebînd dacă valoarea de return este 3.
  • Nicola: Program foarte bun, bravo! Observații minore: ai folosit o linie a matricei pentru K=0, cînd doar 1 va avea 0 divizori. Ai risipit 14% din memorie stocînd un vector cu unu-uri. Observație majoră: programul nu funcționează corect deoarece ciurul se oprește la i * i <= n. Trebuia să mergi pînă la n.
  • Petcu: Program foarte bun, bravo! Observație minoră: ai folosit o linie a matricei pentru K=0, cînd doar 1 va avea 0 divizori. Ai risipit 14% din memorie stocînd un vector cu unu-uri. Observație majoră: numărul maxim de divizori este 7, nu 9! Matematica!
  • Ștefănescu: Program bun, bravo! Observații minore: te-ai complicat cu citirea. Puteai să faci citirea cu un singur fscanf, citind trei valori și întrebînd dacă valoarea de return este 3. Doi, ai folosit o linie a matricei pentru K=0, cînd doar 1 va avea 0 divizori. Ai risipit 14% din memorie stocînd un vector cu unu-uri. Observație majoră: programul nu funcționează corect deoarece ciurul se oprește la d*d<=1000000. Trebuia să mergi pînă la d<=1000000.
  • Togan: Program foarte bun, bravo! Citire corectă și simplă cu fscanf, bravo! Observație minoră: ai folosit o linie a matricei pentru K=0, cînd doar 1 va avea 0 divizori. Ai risipit 14% din memorie stocînd un vector cu unu-uri. Observație majoră: la final, la afișări, testezi k<9, în vreme ce peste tot în restul programului ai k<8. De mirare că nu pierzi puncte! Folosește constante pentru ca nu te mai încurca!
  • Voicu: Program foarte bun, bravo!

A doua grupă

  • Asgari: Program foarte bun, bravo! Observații minore: citirea cu fgetc() e o idee bună, pentru viteză. Dar e ineficientă. Pe de o parte folosești isdigit() pentru viteză, pe de altă parte testezi în buclă dacă dai de EOF. Există și o funcție isspace() pentru a sări peste caractere spațiu și \n. Doi, ai folosit o linie a matricei pentru K=0, cînd doar 1 va avea 0 divizori. Ai risipit 14% din memorie stocînd un vector cu unu-uri. De ce ai mai rezolvat separat intervale, dacă ai rezolvat reginald?
  • Cadîr: Nu închizi fișiere! Foarte urît! Observație importantă: ciurul putea fi de tip caracter, dar tu ai folosit tip întreg! Atenție la genul acesta de erori, te pot descalifica la olimpiadă! Programul este OK ca idee, dar, precum ți-ai dat seama, are complexitate prea mare. Pentru a răspunde la o întrebare parcurgi ciurul de la a la b, complexitate O(MAXB), adică circa un milion. Trebuia să folosești sume parțiale pentru a răspunde la întrebări în O(1).
  • Dimulescu: Indentarea e bună, variabilele au denumiri bune, bravo, bun! Observații importante: ciurul putea fi de tip caracter, dar tu ai folosit tip întreg! Atenție la genul acesta de erori, te pot descalifica la olimpiadă! Doi, calculezi ciurul pînă la 500 000. Trebuia să îl calculezi pînă la 1 000 000. Programul este OK ca idee, dar, precum ți-ai dat seama, are complexitate prea mare. Pentru a răspunde la o întrebare parcurgi ciurul de la a la b, complexitate O(MAXB), adică circa un milion. Trebuia să folosești sume parțiale pentru a răspunde la întrebări în O(1).
  • Fares: Program foarte bun, bravo! Ai folosit soluția de la reginald ;-) Observații minore: puteai să faci citirea cu un singur fscanf, citind trei valori și întrebînd dacă valoarea de return este 3.
  • Ghica: Program foarte bun, bravo! Citire corectă și simplă cu fscanf, bravo! Atenție, nu închizi fișierul output! Numărul maxim de divizori este 7, nu 9, atenție la dimensionări! Atenție, k este maxim 1000! Indicele va depăși matricea v[][]! De mirare că ai luat 100p. Trebuia să testezi dacă valoarea lui k depășește 9, caz în care răspundeai cu 0.
  • Grecu: Program foarte bun, bravo! Observație importantă: ciurul putea fi de tip caracter, dar tu ai folosit tip întreg! Atenție la genul acesta de erori, te pot descalifica la olimpiadă! Doi, ai folosit o linie a matricei pentru K=0, cînd doar 1 va avea 0 divizori. Ai risipit 14% din memorie stocînd un vector cu unu-uri.
  • Ilie: Program foarte bun, bravo! Ai folosit soluția de la reginald ;-)
  • Ipate: Program foarte bun, bravo! Nu închizi fișiere! Ne supărăm! Ai folosit o linie a matricei pentru K=0, cînd doar 1 va avea 0 divizori. Ai risipit 14% din memorie stocînd un vector cu unu-uri.
  • Marcu: Observații importante: ciurul putea fi de tip caracter, dar tu ai folosit tip întreg! Atenție la genul acesta de erori, te pot descalifica la olimpiadă! Programul este OK ca idee, dar, precum ți-ai dat seama, are complexitate prea mare. Pentru a răspunde la o întrebare parcurgi ciurul de la a la b, complexitate O(MAXB), adică circa un milion. Trebuia să folosești sume parțiale pentru a răspunde la întrebări în O(1).
  • Moroșan: Soluție forță brută, care nu folosește nici ciurul lui Eratostene, nici sume parțiale pe vector. În plus, nici nu este corectă.
  • Nicu: Program foarte bun, bravo! Observație minoră: ai folosit o linie a matricei pentru K=0, cînd doar 1 va avea 0 divizori. Ai risipit 14% din memorie stocînd un vector cu unu-uri.
  • Petrescu: Program foarte bun, bravo! Observație minoră: puteai să faci citirea cu un singur fscanf, citind trei valori și întrebînd dacă valoarea de return este EOF, sau 3.
  • Popescu: Te rog nu trimite soluții la arhivă! Atenție! (le-ai trimis înainte să înceapă tema, nu ești un bun oracol, nu prevezi viitorul - sau îl prevezi prea bine :-) Program foarte bun, bravo! Ai folosit o linie a matricei pentru K=0, cînd doar 1 va avea 0 divizori (așa cum ai și testat în program). Ai risipit 14% din memorie stocînd un vector cu zerouri.
  • Rebengiuc: Rezolvare excepțională, bravo! Optimă, folosind rezolvarea de la reginald. Atenție la readInt(). Dacă vrei să fii eficient trebuie să folosești isdigit(), iar, în cazul acesta și isspace().
  • Rughiniș: Observație importantă: ciurul putea fi de tip caracter, dar tu ai folosit tip întreg! Atenție la genul acesta de erori, te pot descalifica la olimpiadă! Programul este OK ca idee, dar, precum ți-ai dat seama, are complexitate prea mare. Pentru a răspunde la o întrebare parcurgi ciurul de la a la b, complexitate O(MAXB), adică circa un milion. Trebuia să folosești sume parțiale pentru a răspunde la întrebări în O(1). Măcar dacă programul ar fi funcționat...
  • Stancu: Soluție care nu folosește ciurul lui Eratostene decît pentru calculul numerelor prime, nu pentru calculul numărului de divizori primi. Nu folosește nici sume parțiale pe vector. David, tu poți mai mult de atît, dă-ți te rog silința. Rezolvarea asta nu îți face cinste.
  • Tatomir: Rezolvare excepțională, bravo! Optimă, folosind soluția de la Reginald. Te-ai chinuit puțin la citire, recapitulează fscanf(). Vezi ce înseamnă să nu folosești constante? Ai modificat una din limite, dar nu și a doua, numărul de întrebări nu este un milion, ci 100 000.
  • Teodorescu: Program foarte bun, bravo! Citire corectă și simplă cu fscanf, bravo! Observație importantă: ciurul putea fi de tip caracter, dar tu ai folosit tip întreg! Atenție la genul acesta de erori, te pot descalifica la olimpiadă! Ai folosit o linie a matricei pentru K=0, cînd doar 1 va avea 0 divizori. Ai risipit 14% din memorie stocînd un vector cu unu-uri.
  • Voicu: Program bun, bravo! Îmi place că te gîndești la optimizări. Dar înainte să te apuci de ele, ce-ar fi să optimizezi lucrurile simple? Cum ar fi faptul că ciurul este un vector de elemente caracter, nu întregi! Sau cum ar fi faptul că tu folosești o matrice cu o linie în plus: linia zero nu este folosită. Asta duce la o risipă de memorie de 14%! Ideea de memoizare, calcul la cerere, nu e rea! Te-ai complicat la calculul diferențelor de sume parțiale, ai scris:
                _included=0;
                if(part[k][a]!=part[k][a-1])
                    _included=1;///astfel, a se include in [a,b]
                fprintf(out,"%d\n",_included+part[k][b]-part[k][a]);

Dacă ai fi scris cum am învățat la oră, era deajuns să scrii:

                fprintf(out,"%d\n", part[k][b]-part[k][a-1]);

Mihai, încearcă să aplici întîi cunoștințele de bază. Nu te complica. Abia la final optimizezi.

Soluție

Să observăm unele lucruri evidente:

  • Deoarece avem multe întrebări asupra numărului de divizori primi rezultă că trebuie să folosim ciurul lui Eratostene.
  • Deoarece intervalele [A, B] au capetele între unu și un milion vom calcula ciurul pînă la un milion.
  • Deoarece ne întreabă cîte numere cu K divizori există într-un interval ne vine ideea să folosim sume parțiale pe vector.
  • Vectorul de sume parțiale va avea un milion de elemente, adica maximul capetelor de interval (tehnic, 1 000 001).

Ce vom însuma în sumele parțiale? Pentru fiecare număr K ne putem imagina un vector în care pentru fiecare pozitie X vom memora 1 dacă X are K divizori, 0 în caz contrar. Acest vector este un vector de frecvență al numerelor ce au fix K divizori. În acest caz sumele parțiale ale acestui vector, să spunem S[X], vor calcula numărul de numere care au K divizori între 1 și X.

Aici apare problema: avem nevoie de cîte un vector pentru fiecare K. Ceea ce nu ne convine deoarece K poate fi 1000. O mie de vectori a cîte un milion de elemente înseamnă un miliard de elemente! Avem o problemă de memorie.

Sau poate nu? Ce reprezintă K? Numărul de divizori primi ai unui număr. Știm că el este O(log X). X fiind maxim un milion vorbim de numere K foarte mici, gen 20. În realitate, dacă calculăm numărul maxim de divizori primi posibili el va fi 7. Cum calculăm acest număr? Înmulțim primele șapte numere prime:

2 * 3 * 5 * 7 * 11 * 13 * 17 = 510510

Dacă am înmulți cu 19 am depăși un milion.

Revenind la soluție, observăm în continuare:

  • orice întrebare cu K mai mare sau egal cu opt va avea răspunsul zero.
  • orice întrebare cu K zero va avea ca răspuns zero, cu excepția cazului cînd A este 1, deoarece 1 este singurul număr nenul care are zero divizori primi.
  • întrebările la care are sens să calculăm ceva au 1 ≤ K ≤ 7

De aici rezultă următorul algoritm:

# Calculăm numărul de divizori primi ai tuturor numerelor de la 1 la un milion folosind ciurul lui Eratostene
# Calculăm o matrice cu 7 linii și un milion de coloane: această matrice conține 7 vectori de sume parțiale ale vectorilor de frecvență.
# Răspundem la întrebările "cîte numere naturale cu exact ''K'' divizori primi se află în intervalul ''[A, B]''" folosind sume parțiale în linia ''K'' a matricei.

Iată un program posibil (41 linii, din care 31 de program efectiv):

#include <stdio.h>

#define MAX_N 1000000
#define MAX_K 7

char nrdp[MAX_N + 1];        // nrdp[x] = numarul de divizori primi ai lui x
int spart[MAX_N + 1][MAX_K]; // spart[x][d] = numarul de numere mai mici
                             // sau egale cu x care au exact d divizori primi
int main() {
  FILE *fin, *fout;
  int p, k, a, b;

  // ciurul lui Eratostene modificat sa calculeze numarul de divizori primi
  for ( p = 2; p <= MAX_N; p++ )
    if ( nrdp[p] == 0 )
      for ( k = p; k <= MAX_N; k += p )
        nrdp[k]++;

  // calcul sume partiale pentru fiecare nr posibil de divizori (1..7)
  for ( p = 1; p <= MAX_N; p++ ) {
    for ( k = 0; k < MAX_K; k++ )    // linia are un singur element non-zero
      spart[p][k] = spart[p - 1][k]; // deci copiem sumele anterioare
    spart[p][nrdp[p] - 1]++;         // p are nrdp[p] divizori
  }

  // raspundem la interbari
  fin = fopen( "intervale.in", "r" );
  fout = fopen( "intervale.out", "w" );
  while ( fscanf( fin, "%d%d%d", &a, &b, &k ) == 3 ) { // mai avem o intrebare?
    if ( k == 0 )     // doar 1 are zero divizori primi
      fprintf( fout, "%d\n", a == 1 ? 1 : 0 );
    else if ( k > 7 ) // nu exista numere cu mai mult de 7 divizori primi
      fprintf( fout, "0\n" );
    else              // ne bazam pe sumele partiale
      fprintf( fout, "%d\n", spart[b][k - 1] - spart[a - 1][k - 1] );
  }
  fclose( fin );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

  • Precalcularea ciurului lui Eratostene este O(MAXN log MAXN) unde MAXN este maximul lui B, adică un milion.
  • Calculul sumelor parțiale este O(MAXN * log MAXN) unde log MAXN este numărul maxim de divizori, adică șapte.
  • Citirea este O(1) per întrebare
  • Răspunsul este O(1) per întrebare

Rezultă o complexitate în timp de O(MAXN log MAXN + Q) unde Q este numărul de întrebări. Dacă înlocuim cu valorile maxime rezultă 1 000 000 * 7 + 100 000, adică aproximativ 7 milioane de operații.

Cîtă memorie ocupăm?

Vom folosi O(MAXN log MAXN) memorie pentru sumele parțiale și pentru ciur. Calculul exact pentru programul de mai sus este 29 milioane octeți.

Pătrate1

Problema pătrate1 de la vianuarena cere ca, dîndu-se o matrice pătrată de latură maxim 200 cu elemente 0 și 1, să se calculeze numărul de submatrice pătrate pline cu elemente 1.

Comentarii generale

  • Avertismente: Cadîr (nici o sursă).

Soluție forță brută

Soluția forță brută are cinci bucle și complexitate O(n5).

În această variantă pur și simplu luăm în calcul toate pătratele posibile (cîte astfel de pătrate avem?). Primele trei bucle fac exact acest lucru: fixează colțul de sus-stînga al pătratului în toate punctele posibile ale matricei, variind latura de la 1 la maxim posibil pentru a nu ieși din matrice. Apoi, pentru fiecare pătrat de latură lat, calculăm suma elementelor sale. Dacă ea este egală cu lat * lat înseamnă că toate elementele sînt 1.

Această soluție va lua 50-60p. O puteți vedea mai jos:

  nrpat = 0;
  for ( lin = 0; lin < n; lin++ )
    for ( col = 0; col < n; col++ ) {
      maxlat = n - lin;
      if ( n - col < maxlat )
        maxlat = n - col;
      for ( lat = 1; lat <= maxlat; lat++ ) {
        // verificam patratul de latura 'lat' care incepe la (lin, col)
        nr1 = 0;
        for ( l = 0; l < lat; l++ )
          for ( c = 0; c < lat; c++ )
            nr1 += a[lin + l][col + c];
        if ( nr1 == lat * lat )
          nrpat++;
      }
    }

Soluție forță brută optimizată

Putem optimiza această soluție, astfel:

Oprire la 0

Atunci cînd verificăm un pătrat nu are rost să facem suma pînă la capăt. Dacă am găsit un element zero ne putem opri.

Oprire la primul pătrat neplin

Verificarea pătratelor se face în ordine, de la latură 1 pînă la latură maxlat. Însă aceste pătrate sînt incluse unul într-altul. Drept care, dacă găsim un pătrat neplin cu 1, rezultă că nici pătratele mai mari nu pot fi pline cu 1, așa încît ne putem opri la primul pătrat neplin.

Iată cum arată optimizarea forței brute:

  nrpat = 0;
  for ( lin = 0; lin < n; lin++ )
    for ( col = 0; col < n; col++ ) {
      maxlat = n - lin;
      if ( n - col < maxlat )
        maxlat = n - col;
      lat = 1;
      l = 0;
      while ( lat <= maxlat && l == lat - 1 ) {
        // verificam patratul de latura 'lat' care incepe la (lin, col)
        l = c = 0;
        while ( l < lat && a[lin + l][col + c] == 1 ) {
          c++;
          if ( c >= lat ) {
            c = 0;
            l++;
          }
        }
        if ( l == lat )
          nrpat++;
        lat++;
      }
    }

Atenție! Dacă toată matricea este plină cu 1 această soluție face la fel de multe calcule ca și prima. Complexitatea ei este tot O(n5).

Această soluție va lua 70-80p.

Soluție O(n4)

Să observăm un lucru la soluția forță brută optimizată: ea verifică pătratele de la mic la mare, în ordinea incluziunii lor. Drept care atunci cînd verificăm un pătrat știm deja că pătratul de latură mai mică inclus în el este plin cu 1, căci altfel ne-am fi oprit. Așa încît, pentru a verifica acest pătrat nu e nevoie să o luăm de la zero. Este de ajuns să verificăm doar acele elemente neacoperite de pătratul anterior, adică latura de jos și latura din dreapta. Avem în total 2 * lat - 1 elemente. Această soluție nu reface calcule făcute anterior și de aceea este mai bună, avînd complexitate O(n4). Iată o implementare cu această idee:

  nrpat = 0;
  for ( lin = 0; lin < n; lin++ )
    for ( col = 0; col < n; col++ ) {
      maxlat = n - lin;
      if ( n - col < maxlat )
        maxlat = n - col;
      lat = 1;
      l = 0;
      while ( lat <= maxlat && l == lat - 1 ) {
        // verificam patratul de latura 'lat' care incepe la (lin, col)
        // nu are sens sa verificam decit linia de jos si coloana din dreapta
        l = c = 0;
        while ( c < lat && a[lin + lat - 1][col + c] == 1 )
          c++;
        if ( c == lat )
          while ( l < lat && a[lin + l][col + lat - 1] == 1 )
            l++;
        if ( l == lat )
          nrpat++;
        lat++;
      }
    }

Această soluție va lua 100p.

Soluție O(n3)

Folosind precalcularea putem optimiza soluția O(n4) foarte ușor: folosind sume parțiale pe matrice putem testa dacă un pătrat este plin de 1 în O(1), verificînd dacă suma elementelor sale este egală cu produsul laturii lui.

Iată o implementare:

#include <stdio.h>

unsigned short a[201][201];

int main() {
  FILE *fin, *fout;
  int n, l, c, lat, maxlat, nrpat;

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

  nrpat = 0;
  for ( l = 0; l < n; l++ )
    for ( c = 0; c < n; c++ ) {
      maxlat = l < c ? n - c : n - l;
      lat = 1;
      while ( lat <= maxlat &&
              a[l + lat][c + lat] - a[l][c + lat] - a[l + lat][c] + a[l][c]
              == lat * lat )
        // verificam patratul de latura 'lat' care incepe la (l, c)
        lat++;
      nrpat += lat - 1;
    }

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

  return 0;
}

Ce complexitate are această soluție?

Ea este O(n3) ca timp și folosește O(n2) memorie suplimentară. Chiar dacă ar părea că refolosește matrice originală, ceea ce ar însemna că nu folosește memorie suplimentară, în realitate nu este așa: matricea originală este de caractere, cea de sume parțiale este de short int.

Putem scurta puțin programul dacă ne folosim de "forma" sumelor parțiale: date un element în matrice avem deja calculate sumele parțiale spre punctul din stînga-sus. Putem, deci, să modificăm puțin modul de generare a pătratelor: fixăm colțul din dreapta-jos al pătratului și căutăm laturi din ce în ce mai mari. Astfel putem factoriza codul de citire al matricei, cu cel de calcul al sumelor parțiale și cu cel de calcul al pătratului maximal.

Iată un astfel de program (34 de linii, din care 27 linii cod efectiv):

#include <stdio.h>

unsigned short a[201][201];

int main() {
  FILE *fin, *fout;
  int n, l, c, lat, maxlat, nrpat;

  fin = fopen( "patrate1.in", "r" );
  fscanf( fin, "%d ", &n );
  nrpat = 0;
  for( l = 1; l <= n; l++ ) {
    for ( c = 1; c <= n; c++ ) {
      a[l][c] = fgetc( fin ) - '0' + a[l-1][c] + a[l][c-1] - a[l-1][c-1];
      // verificam patratele de latura 1, 2, 3, ...  care se termina la (l, c)
      maxlat = l < c ? l : c;
      lat = 1;
      while ( lat <= maxlat &&
              a[l][c] - a[l][c - lat] - a[l - lat][c] + a[l - lat][c - lat]
              == lat * lat )
        // verificam patratul de latura 'lat' care se termina la (l, c)
        lat++;
      nrpat += lat - 1;
    }
    fgetc( fin );
  }
  fclose( fin );

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

  return 0;
}

Există și o soluție mai bună. Vom discuta despre ea mai tîrziu în acest an.

Extratereștri

Comentarii generale

  • Avertismente: Nicola (nici o sursă).

Soluție

Problema extratereștri poate părea foarte complicată, dar, în realitate, ea are o rezolvare foarte simplă, de cîteva linii. Să începem cu începutul: enunțul.

Enunțul problemei este încîlcit. OZN-uri, soldați, raze laser. Să-l traducem în limbaj matematic: se dau N segmente în plan prin capetele lor, împreună cu numere întregi asociate. De asemenea se dau K drepte verticale infinite prin intersecția lor cu dreapta Ox. Pentru fiecare din aceste drepte trebuie să răspundem la întrebarea care este suma numerelor segmentelor pe care le intersectează acea dreaptă.

Observație: să facem o observație simplă dar importantă: problema nu este plană (2D) ci este liniară (1D). Observăm că coordonatele y ale segmentelor nu influențează intersecțiile cu dreptele verticale. Drept pentru care putem re-enunța problema pe dreapta Ox: date N intervale, cu numere asociate lor și K puncte, să se calculeze pentru fiecare punct suma numerelor asociate intervalelor care trec prin acel punct.

Soluția forță brută este să verificăm pentru fiecare punct ce segmente trec prin el și să însumăm numerele asociate lor. Această soluție este O(KN) și nu se va încadra în cele 0.2s pentru teste mari.

Soluția forță brută nr. 2 dar care ne duce într-o direcție bună, este următoarea: putem să creăm un vector de frecvență al coordonatelor, care pentru fiecare coordonată va memora numărul de extratereștri ce pot fi doborîți la acea coordonată. Construcția acestui vector se face parcurgînd intervalele și adunînd numărul asociat intervalului la fiecare coordonată de la x1 la x2, capetele intervalului. În final vom afișa valorile din acel vector în cele K puncte. Această soluție este O(CN+K), unde C este coordonata maximă, drept care va depăși timpul pe teste mari.

Optimizarea soluției 2 ne duce la o soluție care se încadrează în timp. Vom încerca să reducem timpul necesar "așezării" fiecărui interval în vectorul de frecvență. Acest timp este O(C) în cazul cel mai rău, adică două milioane. Dar dacă am amîna această așezare? Să presupunem că avem intervalul (a, b, p). Intervalul începe în a și se termină la b, iar numărul asociat este p. Am putea să marcăm în acel vector primul element la care vom începe să adunăm p, adica la v[a]. Apoi vom marca primul element în vector unde nu vom mai aduna p, adica v[b+1]. Ce înseamnă această marcare? Dacă în elementul v[a] depunem p, aceasta are semnificaţia că v[a] va trebui adunat la toate elementele următoare în vector, v[a+1], v[a+2]... Pînă cînd? Pînă ce vom anula acest efect depunînd la un element valoarea ce anulează efectul, adică -p. Unde trebuie depusă această valoare? La elementul v[b+1], deoarece v[b] trebuie să beneficieze de acest efect. Astfel, pentru fiecare interval (a, b, p) vom avea de făcut două operaţii:

v[a] += p;
v[b+1] -= p;

Observăm că putem combina mai multe intervale, iar efectul lor se va însuma corect.

În final vom reconstrui vectorul v aşa cum ar trebui el să arate la finalul soluţiei 2. Pentru fiecare element vom aduna toate elementele anterioare:

for ( i = 1; i <= C; i++ )
  v[i] += v[i-1];

Continuăm la fel ca în soluţia 2, afişînd valorile din vector în cele K puncte cerute. Iată programul bazat pe aceste idei:

#include <stdio.h>

#define MAX_COORD 2000000

int e[MAX_COORD + 2];

int main() {
  FILE *fin, *fout;
  int n, k, i;
  int x1, x2, y1, y2, nr;

  fin = fopen( "extraterestri.in", "r" );
  fscanf( fin, "%d%d", &n, &k );
  for ( i = 0; i < n; i++ ) {
    fscanf( fin, "%d%d%d%d%d", &x1, &y1, &x2, &y2, &nr );
    e[x1] += nr;
    e[x2+1] -= nr;
  }
  // recalculare numar total de extraterestri
  for ( i = 1; i <= MAX_COORD; i++ )
    e[i] += e[i-1];
  // citire si afisare query-uri
  fout = fopen( "extraterestri.out", "w" );
  for ( i = 0; i < k; i++ ) {
    fscanf( fin, "%d", &x1 );
    fprintf( fout, "%d\n", e[x1] );
  }
  fclose( fin );
  fclose( fout );

  return 0;
}

Această soluţie este O(N+K+C), încadrîndu-se în timpul cerut de 0.2s, avînd avantajul suplimentar al unui program scurt.

Soluţia foloseşte O(C) memorie.

Tema opțională - rezolvări

Reginald

Problema Reginald este exact problema intervale, cu mai puţină memorie disponibilă. Mai exact, nu mai putem stoca matricea de sume parțiale. Capetele intervalelor sînt maxim 4 milioane în loc de 1 milion, iar numărul de întrebări este 1 milion în loc de 100 000.

Soluție

Vom proceda similar cu problema intervale pînă la momentul calculului sumelor parțiale ale celor 7 vectori. Deoarece putem stoca doar unul din vectori la un moment dat vom răspunde doar la acele întrebări corespunzătoare vectorului. Mai precis, vom răspunde mai întîi întrebărilor pentru care pi este 1, apoi cele pentru care este 2 și așa mai departe. Pentru fiecare vom calcula suma parțială a vectorului de frecvență pi.

Pentru a răspunde doar acelor întrebări, vom memora întrebările într-un vector de liste q[], unde q[i] este o listă formată din toate întrebările cu numere ce au exact i divizori primi. Pentru aceasta, la citire vom distribui întrebările în lista corespunzătoare.

Iată o variantă posibilă (68 de linii, din care 47 linii program efectiv):

#include <stdio.h>

#define MAX_N 4000000
#define MAX_K 7
#define MAX_QUERY 1000000
#define NIL -1

char nrdp[MAX_N + 1]; // nrdp[x] = numarul de divizori primi ai lui x
int spart[MAX_N + 1]; // spart[x] = numarul de numere mai mici
                      // sau egale cu x care au exact k divizori primi
// q[k] = primul element in lista de intrebari de tip (x, y, k)
int q[MAX_K] = { NIL, NIL, NIL, NIL, NIL, NIL, NIL },
  a[MAX_QUERY], b[MAX_QUERY], // (a[i], b[i]) = intrebarea i
  r[MAX_QUERY],               // r[i] = raspunsul la intrebarea i
  next[MAX_QUERY];            // next[i] = urmatoarea intrebare cu acelasi k

int main() {
  FILE *fin, *fout;
  int p, suma, n, k;

  // ciurul lui Eratostene modificat sa calculeze numarul de divizori primi
  for ( p = 2; p <= MAX_N; p++ )
    if ( nrdp[p] == 0 )
      for ( k = p; k <= MAX_N; k += p )
        nrdp[k]++;

  fin = fopen( "reginald.in", "r" );
  fscanf( fin, "%d", &n );
  for ( p = 0; p < n; p++ ) {
    fscanf( fin, "%d%d%d", &a[p], &b[p], &k );
    // raspundem la intrebari nestandard (k == 0 sau k > 7 )
    if ( k == 0 ) // doar 1 are zero divizori primi
      r[p] = (a[p] == 1);
    else if ( k > 7 ) // nu exista numere cu mai mult de 7 divizori primi
      r[p] = 0;
    else { // raspuns ce se va baza pe sume partiale
      // depunem intrebarile standard in coada la indexul k - 1
      next[p] = q[k - 1];
      q[k - 1] = p;
    }
  }
  fclose( fin );

  // raspundem la intrebari standard (k = [1..7])
  for ( k = 1; k <= MAX_K; k++ ) {
    // calcul sume partiale pentru numerele cu exact k divizori primi
    suma = 0;
    for ( p = 1; p <= MAX_N; p++ ) {
      if ( nrdp[p] == k )
        suma++;
      spart[p] = suma;
    }
    // pentru fiecare intrebare de k, putem raspunde pe baza sumelor partiale
    p = q[k-1];
    while ( p != NIL ) {
      r[p] = spart[b[p]] - spart[a[p] - 1];
      p = next[p];
    }
  }

  // afisam raspunsurile la intrebari
  fout = fopen( "reginald.out", "w" );
  for ( p = 0; p < n; p++ )
    fprintf( fout, "%d\n", r[p] );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție? Similar cu intervale:

  • Precalcularea ciurului lui Eratostene este O(MAXN log MAXN) unde MAXN este maximul lui B, adică un milion.
  • Calculul sumelor parțiale este O(MAXN * log MAXN) unde log MAXN este numărul maxim de divizori, adică șapte.
  • Citirea este O(1) per întrebare
  • Răspunsul este O(1) per întrebare

Rezultă o complexitate în timp de O(MAXN log MAXN + Q) unde Q este numărul de întrebări. Dacă înlocuim cu valorile maxime rezultă 4 000 000 * 7 + 1 000 000, adică aproximativ 29 milioane de operații.

Cîtă memorie ocupăm?

Vom folosi O(MAXN) memorie pentru sumele parțiale și pentru ciur și O(Q) pentru stocarea întrebărilor, adică O(MAXN + Q). Calculul exact pentru programul de mai sus este 36 milioane octeți.

Flori 1

Problema flori 1 este intenţionată ca o continuare a problemei flori, în care memoria a fost restricţionată drastic, de la 16MB la 2.5MB.

Soluție

Problema flori1 este foarte grea ca structură de date. Vom folosi de un vector de liste, cîte o listă pentru fiecare linie a matricei. Pe o linie vom memora dreptunghiuri care încep pe acea linie, precum și dreptunghiuri care se termină pe linia anterioară. Ce anume avem nevoie să memorăm într-o celulă? Trei valori, coloana de început a segmentului, cea de final, și valoarea de adăugat în vectorul de markeri. Apoi vom "plimba" de sus în jos vectorul de markeri (v[] din varianta 1D a lui Mars). El se va actualiza cu perechile din lista liniei curente. Pe baza lui v[] vom calcula sumele parțiale s[] într-un vector diferit, pentru a nu îl influența pe v[], de care vom avea nevoie la linia următoare. În final vom vedea că nici nu avem nevoie de s[] deoarece ni se cere să calculăm un maxim.

Iată o soluție posibilă:

#include <stdio.h>

#define MAX_COORD 1000
#define MAX_DREPT 10000

short h[MAX_COORD][MAX_COORD];
short start[2 * MAX_DREPT + 1], end[2 * MAX_DREPT + 1], 
  uda[2 * MAX_DREPT + 1], next[2 * MAX_DREPT + 1];
short ind[MAX_COORD + 1];
int dif[MAX_COORD + 1];

int main() {
  FILE *fin, *fout;
  int n, m, z, i, j, aloc, p, hc, hmax, nmax, sumdif;
  short int l1, c1, l2, c2, x;

  aloc = 1;
  fin = fopen( "flori1.in", "r" );
  fscanf( fin, "%d%d", &n, &m );
  for ( i = 0; i < n; i++ )
    for ( j = 0; j < m; j++ )
      fscanf( fin, "%hd", &h[i][j] );
  // citim cele z dreptunghiuri si introducem doua segmente, unul cu +x
  // la coordonala l1-1 si unul cu -x la coordonata l2
  fscanf( fin, "%d", &z );
  for ( i = 0; i < z; i++ ) {
    fscanf( fin, "%hd%hd%hd%hd%hd", &l1, &c1, &l2, &c2, &x );
    // plasam inceputul dreptunghiului
    start[aloc] = c1 - 1;
    end[aloc] = c2;
    uda[aloc] = x;
    next[aloc] = ind[l1 - 1];
    ind[l1 - 1] = aloc++;
    // plasam finalul dreptunghiului
    start[aloc] = c1 - 1;
    end[aloc] = c2;
    uda[aloc] = -x;
    next[aloc] = ind[l2];
    ind[l2] = aloc++;
  }
  fclose( fin );

  // parcurgem liniile matricei de flori, plasind segmentele existente
  // pe acea linie
  hmax = nmax = 0;
  for ( i = 0; i < n; i++ ) {
    // plasam dreptunghiurile noi (care se termina sau incep) pe vectorul de
    // diferente dif[]
    p = ind[i];
    while ( p != 0 ) {
      dif[start[p]] += uda[p];
      dif[end[p]] -= uda[p];
      p = next[p];
    }
    // testam florile maxime adunind suma(diff[0..j]) cu h[i][j]
    sumdif = 0;
    for ( j = 0; j < m; j++ ) {
      sumdif += dif[j];
      if ( (hc = (sumdif + h[i][j])) > hmax ) {
        hmax = hc;
        nmax = 1;
      } else if ( hc == hmax )
        nmax++;
    }
  }
  fout = fopen( "flori1.out", "w" );
  fprintf( fout, "%d %d\n", hmax, nmax );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

  • Citirea matricei de flori este O(N · M)
  • Citirea dreptunghiurilor și distribuirea lor în liste este O(Z)
  • Parcurgerea listelor și calculul înălțimilor florilor este O(N · M + Z)

Complexitatea totală este, deci O(N · M + Z).

Cîtă memorie folosește algoritmul? O(N · M + Z). Dacă matricea de înălțimi ale florilor era la final în fișierul de intrare am fi folosit doar O(M + Z). Programul acesta folosește aproximativ 2.2 milioane octeți.

Tema opțională de gîndire - discuții

Am discutat idei pentru cele două probleme de gîndire.

Rezolvări aici [1]

Lecție: 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 de scriere a unei funcții recursive:

  • Î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

Factorial

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

Putere

Calcul an. 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( a, n - 1 );
}

Cmmdc

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

Exerciții

Încercați în clasă să scrieți următoarele funcții recursive.

Fibonacci

Să se scrie o funcție recursivă care, dat n, calculează al n-lea termen din șirul lui Fibonacci: 0 1 1 2 3 5 8 13.... Ne vom folosi de definiția recurentă: fib(n)={\begin{cases}0,&{\mbox{dacă }}n=1\\1,&{\mbox{dacă }}n=2\\fib(n-1)+fib(n-2),&{\mbox{dacă }}n>2.\end{cases}}

int fib( int n ) {
  if ( n == 1 )
    return 0;
  if ( n == 2 )
    return 1;
  return fib( n - 1 ) + fib ( n - 2 );
}

Suma cifrelor unui număr

Să se scrie o funcție recursivă care calculează suma cifrelor unui număr n.

Ne vom folosi de următoarea formulă recurentă: suma(n)={\begin{cases}0,&{\mbox{dacă }}n=0\\n\%10+suma(n/10),&{\mbox{dacă }}n>0.\end{cases}}

int sumac( int n ) {
  if ( n == 0 )
    return 0;
  return n % 10 + sumac( n / 10 );
}

Putere în O(log n)

Calculați an în mod cît mai eficient (a și n numere naturale). Problema este cunoscută şi sub numele de ridicare la putere în timp logaritmic. Ideea din spatele acestei rezolvări este următoarea:

  • Dacă n este par, atunci an = a2*n/2 = (a2)n/2
  • Dacă n este impar, atunci n-1 este par și avem an = a * an-1 = a * a2*(n-1)/2 = a * (a2)(n-1)/2 = a * (a2)n/2

Rezultă formula de recurență:

a^{{n}}={\begin{cases}1,&{\mbox{dacă }}n=0\\{(a^{{2}})}^{{n/2}},&{\mbox{dacă }}n>0,n\%2=0\\a\times {(a^{{2}})}^{{n/2}},&{\mbox{dacă }}n>0,n\%2=1\end{cases}}

În formulele de mai sus am considerat că / este împărțirea întreagă din limbajul C. Se observă că indiferent de paritatea lui n, la fiecare pas al iterației putem transforma a în a * a și apoi putem împărți n la 2. Doar în cazurile cînd n este impar vom acumula valoarea curentă a lui a la produsul calculat. Iată soluția bazată pe această idee:

int putere( int a, int n ) {
  int p;

  if ( n == 0 )
    return 1;
  p =  putere( a * a, n / 2 );
  if ( n % 2 ) // n impar?
    p *= a;

  return p;
}

Afișare

Să se afișeze un șir de caractere în ordine inversă. Șirul se termină cu '\n'.

Ne vom folosi de următoarea idee: citim un caracter, apoi chemăm funcția recursivă pentru a afișa restul caracterelor, apoi afișăm caracterul.

void afisare( FILE *fin, FILE *fout ) {
  char ch;

  ch = fgetc( fin );
  if ( ch != '\n' ) {
    afisare( fin, fout );
    fputc( ch, fout );
  }
}

Descompunere în baza 2

Să se scrie o funcție recursivă care, dat n, îl afișează în baza 2.

Similar cu exercițiul precedent, vom calcula ultima cifră a descompunerii (restul împărțirii la doi), apoi vom chema funcția cu n / 2, iar la revenire vom afișa cifra.

void baza2( int n, FILE *fout ) {
  int cf2;

  if ( n > 0 ) {
    cf2 = n % 2;
    baza2( n / 2, fout );
    fprintf( fout, "%d", cf2 );
  }
}

Interclasare vectori ordonați

Dîndu-se doi vectori ordonați să se calculeze un al treilea vector ordonat ce conține elementele lor.

Funcția va primi ca parametri cei trei vectori și pozițiile curente în ei (inițial pozițiile de start, 0). La fiecare apel va alege un element pe care îl va copia. Apoi se va reapela cu indici actualizați (i1 și i3 sau i2 și i3).

void interclaseaza( int n1, int v1[], int n2, int v2[], int v3[],
                   int i1, int i2, int i3 ) {
  if ( i1 < n1 ) { // mai avem elemente in primul vector?
    if ( i2 < n2 && v2[i2] < v1[i1] ) { // v2[i2] exista si e mai mic?
      v3[i3] = v2[i2];                  // copiem v2[i1]
      interclaseaza( n1, v1, n2, v2, v3, i1, i2 + 1, i3 + 1 );
    } else {
      v3[i3] = v1[i1];                  // copiem v1[i1]
      interclaseaza( n1, v1, n2, v2, v3, i1 + 1, i2, i3 + 1 );
    }
  } else if ( i2 < n2 ) { // mai avem elemente in v2? (v1 s-a terminat)
    v3[i3] = v2[i2];
    interclaseaza( n1, v1, n2, v2, v3, i1, i2 + 1, i3 + 1 );
  }
}

Temă

  • Tema 6 clasa a 7a:
    • sumacfnr: să se scrie o funcție recursivă care să calculeze suma cifrelor unui număr.
    • sumadiv: să se scrie o funcție recursivă care să calculeze suma divizorilor unui număr. Ea va arăta astfel:
      int sumd( int n, int d ) {
        ...
      }
      și va fi apelată inițial astfel:
      sum = sumd( n, 1 );
      Semnificaţia este suma divizorilor lui n care sînt mai mari sau egali cu d şi mai mici sau egali cu n / d. Mai exact trebuie să completați funcția sumd din programul următor:
      #include <stdio.h>
      
      int sumd( int n, int d ) {
        ...
      }
      
      int main() {
        FILE *fin, *fout;
        int n;
      
        fin = fopen( "sumadiv.in", "r" );
        fscanf( fin, "%d", &n );
        fclose( fin );
      
        fout = fopen( "sumadiv.out", "w" );
        fprintf( fout, "%d\n", sumd( n, 1 ) );
        fclose( fout );
      
        return 0;
      }
      Atenţie mare la complexitatea algoritmului obţinut!
    • nset: să se scrie o un program care să calculeze numărul de cifre distincte ale unui număr, folosind recursivitate.
    • invector să se răstoarne un vector folosind o funcție recursivă. Vectorul trebuie modificat, nu doar afișat invers. Funcția va arăta astfel:
      void inv( int primul, int ultimul, int v[] ) {
        ...
      }
      unde primul și ultimul sînt indicii de început, respecitiv sfîrșit care definesc subvectorul de răsturnat. Funcția va fi apelată inițial astfel:
      inv( 0, n-1, v );
      Mai exact trebuie să completați funcția inv din programul următor:
      #include <stdio.h>
      
      int v[100000];
      
      void inv( int primul, int ultimul, int v[] ) {
        ...
      }
      
      int main() {
        FILE *fin, *fout;
        int n, i;
      
        fin = fopen( "invector.in", "r" );
        fscanf( fin, "%d", &n );
        for ( i = 0; i < n; i++ )
          fscanf( fin, "%d", &v[i] );
        fclose( fin );
      
        inv( 0, n-1, v );
      
        fout = fopen( "invector.out", "w" );
        for ( i = 0; i < n; i++ )
          fprintf( fout, "%d ", v[i] );
        fprintf( fout, "\n" );
        fclose( fout );
      
        return 0;
      }
    • turnurile din Hanoi: exemplu de animație joc aici să se scrie un program care să rezolve jocul turnurile din Hanoi (să efectueze mutările care duc la soluție).
  • Tema 6 opțională clasa a 7a:
    • combinări {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.
    • v (ONI 2004 clasa a 7-a) Problema este modificată. Puteți lua doar 50% din punctaj. Pentru 100% nu este nevoie de parsing. Dacă introduceam cerință de parsing aș fi scăzut timpul permis.

Rezolvări aici [2]