Difference between revisions of "Clasa VII/VIII lecția 3 - 7 oct 2014"

From Algopedia
Jump to: navigation, search
 
 
Line 70: Line 70:
 
* '''Opțional, grea''': [http://varena.ro/problema/combinari Combinări] <math>{C}_{n}^{k}</math><nowiki>- combinări de n luate cîte k. Date numerele naturale n și k, k &le; n, să se afișeze toate submulțimile mulțimii {1, 2, 3, ..., n} de k elemente.</nowiki>
 
* '''Opțional, grea''': [http://varena.ro/problema/combinari Combinări] <math>{C}_{n}^{k}</math><nowiki>- combinări de n luate cîte k. Date numerele naturale n și k, k &le; n, să se afișeze toate submulțimile mulțimii {1, 2, 3, ..., n} de k elemente.</nowiki>
  
* '''Clasa a 8<sup>a</sup>, opţional''': probleme ONI 2014 baraj gimnaziu: [http://varena.ro/problema/agenda agenda], [http://varena.ro/problema/opmult opmult], [http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=1605 monede2].
+
* '''Clasa a 8<sup>a</sup>, opţional''': probleme ONI 2014 baraj gimnaziu: [http://varena.ro/problema/agenda agenda], [http://varena.ro/problema/opmult opmult], [http://varena.ro/problema/monede monede].
  
 
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_VII/VIII_lec%C8%9Bia_3_-_7_oct_2014]

Latest revision as of 00:10, 5 November 2019

Tema - rezolvări

Rezolvări aici [1]

Lecție

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 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 recursivă: 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

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

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

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

Temă (comună claselor a 7-a și a 8-a)

  • Tema 3 clasele 7/8:
    • 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!
    • 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( fin, "%d ", v[i] );
        fprintf( fin, "\n" );
        fclose( fout );
      
        return 0;
      }
    • V (ONI 2004 clasa a 7-a) Clasa a 7-a poate să ia doar 50% din punctaj. Clasa a 8-a trebuie să ia 100%
  • Opțional, grea: 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.

Rezolvări aici [2]