Tema - rezolvări

Rezolvări bitonă, majoritar, selecție aici [1])

Rezolvări probleme ONI 2012 aici [2]

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

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

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

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

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.
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%

Rezolvări aici [3]

Clasa VII/VIII lecția 3 - 15 oct 2013

Contents