View source for Clasa VII/VIII lecția 3 - 7 oct 2014

= Tema - rezolvări =

Rezolvări aici [http://solpedia.francu.com/wiki/index.php/Clasa_VII/VIII_lec%C8%9Bia_2_-_30_sep_2014]

= 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ă: <math>n! = \begin{cases} 1, & \mbox{dacă }  n = 1  \\ n \cdot (n - 1)!,  & \mbox{dacă } n > 1. \end{cases}</math><pre>int fact( int n ) {&#10;  if ( n == 1 )&#10;    return 1;&#10;  return n * fact( n - 1 );&#10;}</pre>
==== Putere ====
Calcul a<sup>n</sup>. Ne vom folosi de definiția recurentă: <math>a^{n} = \begin{cases} 1, & \mbox{dacă }  n = 0  \\ a \cdot a^{n-1},  & \mbox{dacă } n > 0. \end{cases}</math><pre>int putere( int a, int n ) {&#10;  if ( n == 0 )&#10;    return 1;&#10;  return a * putere( a, n - 1 );&#10;}</pre>

==== Cmmdc ====
Calcul cmmdc a două numere. Ne vom folosi de definiția recursivă a lui Euclid: <math>cmmdc(a, b) = \begin{cases} a, & \mbox{dacă }  b = 0  \\ cmmdc(b, a \bmod b),  & \mbox{dacă } b > 0. \end{cases}</math><pre>int cmmdc( int a, int b ) {&#10;  if ( b == 0 )&#10;    return a;&#10;  return cmmdc( b, a % b );&#10;}</pre>
=== Exerciții ===
Încercați în clasă să scrieți următoarele funcții recursive.
==== Fibonacci ====
Să se scrie o funcție recursivă care, dat <tt>n</tt>, calculează al <tt>n</tt>-lea termen din șirul lui Fibonacci: <tt>0 1 1 2 3 5 8 13...</tt>. Ne vom folosi de definiția recursivă: <math>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}</math>
<pre>int fib( int n ) {
  if ( n == 1 )
    return 0;
  if ( n == 2 )
    return 1;
  return fib( n - 1 ) + fib ( n - 2 );
}</pre>

==== Suma cifrelor ====
Să se scrie o funcție recursivă care calculează suma cifrelor unui număr <tt>n</tt>. Ne vom folosi de următoarea formulă recurentă: <math>suma(n) = \begin{cases} 0, & \mbox{dacă }  n = 0  \\ n % 10 + suma(n / 10),  & \mbox{dacă } n > 0. \end{cases}</math>
<pre>int sumac( int n ) {
  if ( n == 0 )
    return 0;
  return n % 10 + sumac( n / 10 );
}</pre>

==== Afișare ====
Să se afișeze un șir de caractere în ordine inversă. Șirul se termină cu <tt>'\n'</tt>. 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.
<pre>void afisare( FILE *fin, FILE *fout ) {
  char ch;

  ch = fgetc( fin );
  if ( ch != '\n' )
    afisare( fin, fout );
  fputc( ch, fout );
}</pre>

==== Descompunerea în baza 2 ====
Să se scrie o funcție recursivă care, dat <tt>n</tt>, î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 <tt>n / 2</tt>, iar la revenire vom afișa cifra.
<pre>void baza2( int n, FILE *fout ) {
  int cf2;

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

= Temă (comună claselor a 7-a și a 8-a) =
* [http://varena.ro/runda/2014-10-07-clasa-78-tema-3 Tema 3 clasele 7/8]:
** [http://varena.ro/problema/sumadiv Sumadiv]: să se scrie o funcție recursivă care să calculeze suma divizorilor unui număr. Ea va arăta astfel: <pre>int sumd( int n, int d ) {&#10;  ...&#10;}</pre> și va fi apelată inițial astfel: <pre>sum = sumd( n, 1 );</pre> 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 <tt>sumd</tt> din programul următor:<pre>#include <stdio.h>&#10;&#10;int sumd( int n, int d ) {&#10;  ...&#10;}&#10;&#10;int main() {&#10;  FILE *fin, *fout;&#10;  int n;&#10;&#10;  fin = fopen( "sumadiv.in", "r" );&#10;  fscanf( fin, "%d", &n );&#10;  fclose( fin );&#10;&#10;  fout = fopen( "sumadiv.out", "w" );&#10;  fprintf( fout, "%d\n", sumd( n, 1 ) );&#10;  fclose( fout );&#10;&#10;  return 0;&#10;}</pre> Atenţie mare la complexitatea algoritmului obţinut!
** [http://varena.ro/problema/invector 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: <pre>void inv( int primul, int ultimul, int v[] ) {&#10;  ...&#10;}</pre> unde <tt>primul</tt> și <tt>ultimul</tt> sînt indicii de început, respecitiv sfîrșit care definesc subvectorul de răsturnat. Funcția va fi apelată inițial astfel: <pre>inv( 0, n-1, v );</pre> Mai exact trebuie să completați funcția <tt>inv</tt> din programul următor: <pre>#include <stdio.h>&#10;&#10;int v[100000];&#10;&#10;void inv( int primul, int ultimul, int v[] ) {&#10;  ...&#10;}&#10;&#10;int main() {&#10;  FILE *fin, *fout;&#10;  int n, i;&#10;&#10;  fin = fopen( "invector.in", "r" );&#10;  fscanf( fin, "%d", &n );&#10;  for ( i = 0; i < n; i++ )&#10;    fscanf( fin, "%d", &v[i] );&#10;  fclose( fin );&#10;&#10;  inv( 0, n-1, v );&#10;&#10;  fout = fopen( "invector.out", "w" );&#10;  for ( i = 0; i < n; i++ )&#10;    fprintf( fin, "%d ", v[i] );&#10;  fprintf( fin, "\n" );&#10;  fclose( fout );&#10;&#10;  return 0;&#10;}</pre>
** [http://varena.ro/problema/v 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''': [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].

Rezolvări aici [http://solpedia.francu.com/wiki/index.php/Clasa_VII/VIII_lec%C8%9Bia_3_-_7_oct_2014]