10 2018 Lectia20
Tema - rezolvări
Rezolvări probleme de recursie aici [1]
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
- fibonacci
- suma cifrelor unui număr
- turnurile din Hanoi , animatie :http://www.puzzle.ro/ro/play_toh.htm
- aranjamente
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 [2]
