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.

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ă).

Extratereștri

Comentarii generale

Avertismente: Nicola (nici o sursă).

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.

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.

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

<html5media height="720" width="1280">https://www.algopedia.ro/video/2019-2020/2019-10-17-clasa-7-lectie-info-06-720p.mp4</html5media>

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 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( 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 aⁿ î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 aⁿ = a^2*n/2 = (a²)^n/2
Dacă n este impar, atunci n-1 este par și avem aⁿ = a * a^n-1 = a * a^2*(n-1)/2 = a * (a²)^(n-1)/2 = a * (a²)^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 7^a:
- 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 7^a:
- 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]

Clasa a VII-a lecția 6 - 17 oct 2019

Contents

Tema - rezolvări

Intervale

Comentarii generale

Comentarii individuale

Prima grupă

A doua grupă

Pătrate1

Comentarii generale

Extratereștri

Comentarii generale

Tema opțională - rezolvări

Reginald

Flori 1

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

Lecție: recursivitate

Exemple introductive

Factorial

Putere

Cmmdc

Exerciții

Fibonacci

Suma cifrelor unui număr

Putere în O(log n)

Afișare

Descompunere în baza 2

Interclasare vectori ordonați

Temă

Navigation menu

Page actions

Page actions

Personal tools

Navigation

Search

Tools