Clasa VII/VIII lecția 6 - 28 oct 2014

From Algopedia
Jump to navigationJump to search

Tema - rezolvări

Rezolvări probleme de recursie aici [1]

Rezolvări la celelalte probleme aici [2]

Lecție - recursivitate, continuare

Exerciții

Rezolvați în clasă următoarele exerciții:

Palindrom

Verificare palindrom:

#include <stdio.h>

int putere( int n ) {             // calculam recursiv cea mai mare
  int p = 1;                      // putere a lui 10 mai mica decit n

  if ( n < 10 )                   // cind n are o singura cifra
    return 1;                     // cea mai mare putere este 1
  return 10 * putere( n / 10 );   // adaugam un zero si taiem o cifra
}

int palindrom( int n, int p10 ) { // pe baza lui n si a puterii lui 10
  if ( n < 10 )                   // un numar de o cifra este palindrom
    return 1;
  if ( n / p10 != n % 10 )        // testam prima si ultima cifra
    return 0;
  return palindrom( n % p10 / 10, p10 / 100 ); // taie prima si ultima cifra
}

int main() {
  int n, pow10;

  scanf( "%d", &n );
  pow10 = putere( n );
  if ( palindrom( n, pow10 ) )
    printf( "%d este palindrom\n", n );
  else
    printf( "%d nu este palindrom\n", n );
  return 0;
}

an î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

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

#include <stdio.h>

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

int main() {
  int a, n;

  scanf( "%d%d", &a, &n );
  printf( "%d\n", putere( a, n ) );

  return 0;
}

Permutări

Dîndu-se n să se afișeze toate permutările mulțimii numerelor de la 1 la n în ordine lexicografică.

#include <stdio.h>

int v[10];
char folosit[10];

void perm( int n, int pos ) {
  int i;

  if ( pos >= n ) {             // daca am umplut n pozitii
    for ( i = 0; i < n; i++ )   // afiseaza combinarea curenta
      printf( "%d ", v[i] );
    printf( "\n" );
  } else
    for ( v[pos] = 1; v[pos] <= n; v[pos]++ )
      if ( !folosit[v[pos]] ) { // daca elementul curent nu e deja folosit
        folosit[v[pos]] = 1;    // marcheaza-l ca folosit
        perm( n, pos + 1 );     // genereaza restul permutarii
        folosit[v[pos]] = 0;    // demarcheaza elementul
      }
}

int main() {
  int n;

  scanf( "%d", &n );
  perm( n, 0 );
  return 0;
}

Plată suma

Moduri plată suma cu monede 1, 2, 5:

#include <stdio.h>

int mon[3] = { 1, 2, 5 };

int suma( int s, int nrmon ) { // in cite feluri platim s folosind nrmon monede
  if ( nrmon == 0 )            // daca nu mai avem monede
    return 0;                  // nu putem plati (zero moduri de plata)
  if ( s < 0 )                 // o suma negativa nu se poate plati
    return 0;
  if ( s == 0 )                // o suma de zero se plateste intr-un singur fel
    return 1;
  // putem plati in doua feluri de combinatii
  // - fie in combinatii care se termina cu ultima moneda din vector
  // - fie in combinatii care nu folosesc deloc ultima moneda din vector
  return suma( s - mon[nrmon - 1], nrmon ) + suma( s, nrmon - 1 );
}

int main() {
  int s;

  scanf( "%d", &s );
  printf( "%d este platibila in %d moduri\n", s, suma( s, 3 ) );
  return 0;
}

Tipuri de recursie

Există două moduri de implementare a unei soluții recursive:

Recursie Top-Down

Recursie Top-Down: cînd pornim cu o problemă mai mare și apelăm funcția pentru probleme mai mici pe care le folosim ulterior în apelul curent. În subproblema de bază returnăm un rezultat de bază, cum ar fi zero sau unu. În această categorie sînt toate exemplele de mai sus cu excepția combinărilor, permutărilor si sumei de monede.

Recursie Bottom-Up

Recursie Bottom-Up: cînd pornim cu o problemă mai mare și cu un acumulator de soluție, care inițial este vid (zero sau unu), iar în apelurile ulterioare reducem mărimea problemei adăugînd (construind) soluția finală în acumulator. Exemplele de combinări și permutări sînt Bottom-Up în care acumulatorul este vectorul și nu este transmis în mod explicit, deși am putea face acest lucru.

Exemple de recursie Bottom-Up cu acumulator

Încercați să rezolvați în clasă următoarele exerciții:

Factorial

Funcția factorial implementată recursiv bottom-up cu acumulator:

#include <stdio.h>

int fact( int n, int ac ) {
  if ( n == 1 )                 // cind n = 1 am terminat calculul in ac
    return ac;
  return fact( n - 1, n * ac ); // adaugam n la acumulator
}

int main() {
  int n;

  scanf( "%d", &n );
  printf( "%d! = %d\n", n, fact( n, 1 ) );

  return 0;
}

Palindrom

Verificarea că un număr este palindrom este, în fapt, mai ușor de scris bottom-up. În acumulator vom construi inversul numărului n. La final vom compara inversul cu originalul. Iată implementarea (comparați cu implementarea top-down):

#include <stdio.h>

int palindrom( int n, int nc, int ac ) {
  if ( n == 0 )            // cind n=0 ac este inversul lui nc
    return nc == ac;       // daca sint egale, returnam 1, altfel 0
  return palindrom( n / 10, nc, ac * 10 + n % 10 ); // taiem o cifra tin n
}                                                   // si o adaugam la ac

int main() {
  int n;

  scanf( "%d", &n );
  if ( palindrom( n, n, 0 ) )
    printf( "%d este palindrom\n", n );
  else
    printf( "%d nu este palindrom\n", n );
  return 0;
}

an în O(n)

Iată varianta recursivă bottom-up cu acumulator a funcției putere:

#include <stdio.h>

int putere( int a, int n, int ac ) {
  if ( n == 0 ) // cind puterea e zero acumulatorul are rezultatul
    return ac;
  return putere( a, n - 1, a * ac ); // acumuleaza a la rezultat
}

int main() {
  int n, a;

  scanf( "%d%d", &a, &n );
  printf( "%d^%d = %d\n", a, n, putere( a, n, 1 ) );
  return 0;
}

an în O(log n)

Iată varianta recursivă bottom-up cu acumulator a funcției putere calculată în timp logaritmic:

#include <stdio.h>

// in permanenta a^n * ac detine rezultatul
// cind n devine zero a^n * ac = ac, deci rezultatul este chiar ac
int putere( int a, int n, int ac ) {
  if ( n == 0 ) // cind puterea e zero acumulatorul are rezultatul
    return ac;
  if ( n % 2 )                         // cind n impar
    ac *= a;                           // acumuleaza a la rezultat
  return putere( a * a, n / 2, ac );   // totuna cu (a*a)^(n/2)
}

int main() {
  int n, a;

  scanf( "%d%d", &a, &n );
  printf( "%d^%d = %d\n", a, n, putere( a, n, 1 ) );
  return 0;
}

Transformarea recursiei din Top-Down în Bottom-Up

Orice funcție recursivă de tip Top-Down care pe orice cale de execuție are un singur apel recursiv se poate transforma într-o funcție de tip Bottom-Up prin adăugarea unui parametru acumulator. De ce ne interesează acest lucru? Datorită recursiei la coadă. Recursia la coadă este definită ca un apel recursiv exact la ieșirea din funcție. Toate exemplele pe care le-am dat la recursia bottom-up sînt recursive la coadă. Exemplele date la top-down nu sînt recursive la coadă, cu excepția lui cmmdc.

Recursia la coadă este foarte utilă, deoarece nu consumă stivă. În mod normal fiecare apel de funcție consumă cel puțin patru octeți pe stivă (adresa de întoarcere). Ei bine, în cazul apelurilor recursive la coadă stiva consumată este zero (ca să fim exacţi nu este zero, ci O(1)). Explicația acestui fapt este prea tehnică pentru a o detalia aici. Ea ține de modul în care este organizat calculatorul modern Von Neumann și de modul în care se execută apelurile de funcții.

Ce înseamnă pentru noi acest lucru? Înseamnă că putem chema o funcție, recursiv, de un milion de ori, fără să depășim memoria stivă. Ce înseamnă pentru omenire acest lucru? Înseamnă că putem avea întregi limbaje care nu conțin instrucțiuni de ciclare (while sau for), cum ar fi limbajele funcționale (Scheme, Lisp) sau limbajele logice (Prolog). Acest lucru este posibil deoarece recursivitatea la coadă poate înlocui cu succes buclele. Aceste limbaje se bazează pe definiția recursivă a algoritmului. În unele cazuri programele sînt mai clare într-o gîndire recursivă.

Temă

Clasa a 7-a

Tema 6 clasa a 7a

Tema constă din patru probleme. Primele două trebuie rezolvate folosind recursivitate bottom-up cu acumulator și recursie la coadă. A treia este o problemă celebră de introducere în recursivitate. A patra problemă este foarte grea. La această problemă este în regulă să luați doar 50p. Încercați să luați 100p.

Rezolvări aici [3]

Clasa a 8-a

Tema 6 clasa a 8a

  • run dată la concursul Shumen juniori 2013
  • channels dată la concursul Shumen juniori 2012

De asemenea, deoarece sîntem la capitolul recursivitate, opţional, asiguraţi-vă că aţi rezolvat anul trecut următoarele probleme:

  • Optim (ONI 2012 clasa a 8-a). Încercați să o rezolvați folosind o funcție recursivă. Problema admite şi o rezolvare mai eficientă prin programare dinamică.
  • Hanoi turnurile din Hanoi, trimiteți și un program nerecursiv (iterativ).

Rezolvări aici [4]