Clasa a VII-a lecția 7 - 24 oct 2019

From Algopedia
Jump to navigationJump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Tema - rezolvări

Suma cifrelor unui număr

Problema sumacfnr: să se scrie o funcție recursivă care să calculeze suma cifrelor unui număr. Ea a fost rezolvată la clasă, trebuia doar să aveți grijă să folosiți tipul long long.

Comentarii generale

  • Problema cerea să faceți un copy/paste din lecție. În mod uimitor mulți nu ați fost în stare de acest lucru. Nu ați citit cu atenție enunțul și nu ați observat că un int trebuia schimbat în long long. Sînteți cam ușor de păcălit :)

Comentarii individuale

Prima grupă

  • Badea: else nenecesar:
int sum(long long n){
  if(n==0)
    return 0;
  else
    return sum(n/10)+n%10;
}
  • Chivu: else nenecesar:
int suma_cif(long long n){
    if(n==0){
        return 0;
    }else{
        return n%10+suma_cif(n/10);
    }
}
  • Dobre: este corect, dar de ce să te oprești la n/10 == 0? De ce nu la n == 0?
int sumacifre( long long n ){
  if( n/10 == 0)
    return n;
  return n%10+sumacifre( n/10 );
}
  • Hossu: program corect, dar se cerea să scrii o funcție care să returneze suma cifrelor numărului. Funcția ta folosește o variabilă globală și nu returnează nimic:
int sum;

void sumaCfNr (long long n) {
  if (n != 0) {
    sum = sum + (n % 10);
    sumaCfNr(n / 10);
  }
}
  • Mocanu: foarte corectă funcția, dar e bine să tratezi cazurile de ieșire la început, nu la final.

Sumadiv

Problema sumadiv: să se scrie o funcție recursivă care să calculeze suma divizorilor unui număr.

Comentarii individuale

Prima grupă

  • Aizic: folosește else cînd ai if-uri exclusive!
  • Benescu: else-uri nenecesare:
int sumd(int n, int d){
  if(d*d>n)
    return 0;
  else if(d*d==n)
    return d;
  else if(n%d==0)
    return sumd(n, d+1)+d+n/d;
  else
    return sumd(n, d+1);
}
  • Burac: else-uri nenecesare:
int sumd ( int n, int d ) {
  if ( d * d > n )
    return 0;
  else if ( d * d == n )
    return d + sumd ( n, d + 1 );
  else if ( d * d < n && n % d == 0 )
    return d + n / d + sumd ( n, d + 1 );
  return sumd ( n, d + 1 );  // daca d * d < n, dar n % d != 0
}
  • Chivu: rezolvarea e OK, cu următoarele probleme: folosești return în mijlocul funcției, nu avem voie. Iar atunci cînd găsim că d*d==n nu are sens să mai intrăm în recursivitate, căci vom ieși imediat din funcție:
int sumdiv(int n, int d){
    int sum=0;
    if(d*d<n){
        if(n%d==0){
            sum+=d+n/d;
        }
        sum+=sumdiv(n, d+1);
    }else if(d*d==n){
        sum+=d;
        sum+=sumdiv(n, d+1);
    }else
        return 0;
    return sum;
}
  • Cojocariu: nu folosi return unde vrei tu în funcție! Doar la început, la tratarea cazurilor de ieșire imediată (de terminare a recursiei).
  • Dobre: soluție încîlcită, care repetă condiții de test. Ai else-uri nenecesare. Nu folosi return unde vrei tu în funcție! Doar la început, la tratarea cazurilor de ieșire imediată (de terminare a recursiei):
int sumadiv( int n,int d){
  if( d*d <= n && n % d == 0 )
    if( d*d < n)
      return d + n/d + sumadiv(n,d+1);
    else
      return d + sumadiv(n,d+1);
  else{
    if(d*d <= n)
      return sumadiv(n,d+1);
    return 0;
  }
}
  • Iordache: else-uri nenecesare și return în mijlocul funcției. Atenție!
  • Mocanu: foarte corectă funcția, ultimul else este nenecesar.
  • Mușat: funcție corectă, dar care nu returnează suma divizorilor. Folosești o variabilă globală. Nu ții cont de enunțul problemei, care cere o anumită funcție, nu orice funcție!
  • Petcu: program bun, atenție la else-uri nenecesare după return.
  • Togan: ai uitat să incluzi <math.h>, mare atenție! Funcția este matematic corectă, dar:
    • Folosești sqrt() cînd puteai să îl eviți, el fiind foarte "scump". Îl folosești într-un singur loc unde puteai să testezi d*d, mult mai "ieftin".
    • Încîlceală ineficientă: aduni d și n/d, pentru ca apoi, dacă divizorul este chiar radicalul, să îl scazi înapoi pe d. Nu era mami normal pe dos, aduni doar dacă nu este egal cu radicalul?

A doua grupă

  • Asgari: atenție la else-uri inutile:
int sumd( int n, int d ) {
    if ( d * d > n )
        return 0;
    if ( d * d == n )
        return d + sumd ( n , d + 1 );
    else if ( n % d != 0 )
        return sumd ( n , d + 1 ) + 0;
    else
        return sumd ( n , d + 1 ) + d + n / d;
}
  • Cadîr: program bun! Atenție la else-uri inutile.
  • Fares: Nu tratezi cazurile de ieșire din recursivitate primele. În acest caz trebuia să tratezi mai întîi dacă d*d>n. Nu așa se întîmplă și într-un program iterativ? Dacă n este prim funcția va merge pînă găsește un divizor, deci devine liniară:
int sumd( int n, int d ) {
  if (n % d == 0) {
    if (d * d < n)
      return d + n / d + sumd(n, d + 1);
    else if (d * d == n)
      return d;
    else
      return 0;
  }
  else
    return sumd(n, d + 1);
}
  • Ghica: program foarte bun, dar atenție la încîlceală: tu aduni d + n / d pentru ca apoi să îl scazi dacă este pătrat perfect. Nu aproxima programul în iterații succesive :) Sau dacă faci asta, uită-te ce a ieșit la final:
int sumd( int n, int d ) {
  if( d * d > n)
    return 0;
  int s;
  s = 0;
  if( n % d == 0 )
    s = d + n / d;
  if( d * d == n )
    s -= d;
  return s + sumd( n, d + 1 );
}
  • Grecu: program bun, cu o observație: dacă d*d==n nu are sens să mai reapelezi funcția, este inutil.
  • Ilie: programul este bun, dar atenție la folosirea gratuită a funcției sqrt(), care este "sumpă". Puteai să înlocuiești cu d*d>n, mult mai "ieftin".
  • Marcu: ai avertisment important de compilare: funcția care trebuia să returneze ceva, nu returnează nimic pe o anumită ramură. Din fericire el nu este real. Din nefericire, motivul pentru care compilatorul nu se prinde că nu este o problemă este programarea ta neglijentă. Ai multe if-uri inutile. Dacă un număr nu este nici mai mare nici egal cu altul, ce mai rămîne? Că este mai mic, nu trebuie să testezi, nu? Iată:
int sumd( int n, int d ) {
  if ( d * d > n )
    return 0;
  if ( d * d == n )
    return d;
  if ( d * d < n ) {
    if ( n % d != 0 )
      return sumd( n, d + 1 );
    if ( n % d == 0 )
      return d + n / d + sumd( n, d + 1 );
  }
}

Puteai scrie mai eficient și mai elegant:

int sumd( int n, int d ) {
  if ( d * d > n )
    return 0;
  if ( d * d == n )
    return d;
  if ( n % d != 0 )
    return sumd( n, d + 1 );
  return d + n / d + sumd( n, d + 1 );
}
  • Moroșan: Funcția ta returnează suma divizorilor minus 1. De ce nu chiar suma divizorilor, tu știi. Ai else-uri inutile, după return. Ai multe instrucțiuni return. Dacă i*i nu este mai mare decît a rezultă că i*i este mai mic sau egal cu a, nu trebuie să mai testezi inutil acest lucru. Dacă i==a/i nu ai de ce să mami apelezi recursiv funcția. Iată:
int sumadiv ( int a, int i ) {
  if ( i * i > a )
    return a;
  else if ( a % i == 0 && i * i <= a ) {
    if ( i != a / i )
      return i + a / i + sumadiv ( a, i + 1 );
    else
      return i + sumadiv ( a, i + 1 );
  }
  return sumadiv ( a, i + 1 );
}

Puteai să scrii mai simplu:

int sumadiv ( int a, int i ) {
  if ( i * i > a )
    return a;
  if ( a % i == 0 ) {
    if ( i == a / i )
      return i;
    return i + a / i + sumadiv ( a, i + 1 );
  }
  return sumadiv ( a, i + 1 );
}
  • Nicu: program bun, cu observația că dacă d == n / d nu are sens să mai intrăm în recursivitate, returnăm chiar d. Funcție cam încîlcită, vezi soluția mai jos.

Nset

Problema nset: să se scrie o funcție recursivă care să calculeze numărul de cifre distincte ale unui număr.

Comentarii generale

  • Mulți dintre voi folosiți else după un if ce conține un return. Nu este necesar. Dar nu pot să mă supăr, deoarece aceasta înseamnă că aveți structurarea în sînge! :-)
  • Grav: unii din voi ați folosit return în mijlocul funcțiilor recursive! Aceasta este o nestructurare. Ați înțeles greșit excepția de la regulă: aveți voie să folosiți return doar la început de funcție, cînd tratați cazuri de ieșire imediată. În rest, veți avea un singur return la finalul funcției, ca la orice altă funcție. Dacă nu sînteți siguri pe voi mai bine nu folosiți return' decît la final.
  • Avertisment lui Moroșan care nu a trimis nici o rezolvare.

Comentarii individuale

Prima grupă

  • Aizic: Ai folosit return în mai multe locuri. Nestructurare, nu ai voie decît în cazurile de bază! Iată:
int aparut(long long n,int cif){
  if(n>0 && n%10!=cif)
    return aparut(n/10,cif);
  if(n==0)
    return 0;
  else
    return 1;
}
int difcif(long long n,int cif){
  if(cif<10){
    if(aparut(n,cif)==1){
      return  difcif(n,cif+1)+1;
    }
    return  difcif(n,cif+1);
  }
  return 0;
}
  • Badea: else-uri nenecesare:
int cifra(long long n, int cf){ /// functia returneaza 1 daca am gasit cifra cf in n, in caz contrar 0
  if(n==0)
    return 0;
  else if(n%10==cf)
    return 1;
  else
    return cifra(n/10, cf);
}
int dis(long long n, int cf){ /// calculez numarul de cifre distincte
  if(cf>9)
    return 0;
  else
    return cifra(n, cf)+dis(n, cf+1);
}
  • Benescu: Comentariile m-ar fi ajutat mult. Ideea drăguță, bravo! Folosești, în fapt, vectori mascați. Tu ții un vector de frecvență într-un long long ce conține cifre 1 și 0. Dacă tot ai "trișat", un pic, era mai eficient să le ții într-un număr binar, nu zecimal. Puteai folosi un întreg. În orice caz, o soluție specială :)
  • Burac: Program bun, ai un else nenecesar:
int seafla ( long long n, int cf ) {
  if ( n == 0 )
    return 0;
  else if ( n % 10 == cf )
    return 1;
  return seafla( n / 10, cf );
}
  • Calotă: Program foarte bun, cu observația că te-ai încîlcit puțin, ai creat un caz particular acolo unde el nu există:
int isthere ( long long n, int cf ){ /// cifra cf apare in n ?
   if ( n < 10 ){
     if ( n == cf ) /// daca n este chiar cifra
       return 1;
     return 0;
   }

   if ( n % 10 == cf )
     return 1;
   return isthere ( n / 10, cf );
}

Cazul cînd n are o singură cifră este înglobat în cazul următor. Trebuia să testezi cazul cînd n este zero, cînd returnai zero.

  • Chivu: Idee drăguță! Programul este bun. Gîndirea un pic încîlcită, nu e grav, ești la începuturile recursivității. Ca observații:
    • Instrucțiuni return în mijlocul funcțiilor - grav, nestructurare
    • Introduci cazuri particulare unde nu există - te oprești cu n la 1 în loc de 0 ceea ce îți complică viața.
    • Ai codificat cazul cînd nu mai ai cifre în n cu -1. Dacă îl codai cu 0 codul se simplifica. Ține cont de înțeles, un număr zero nu are, în fapt, cifre, am mai discutat asta. Trebuie să îți pui mereu întrebarea: ce returnează funcția mea pentru zero, sau pentru unu? Ea are mereu un înțeles, o semnificație, nu renunța ușor la ea introducînd -1. Altfel, recursivitatea se va transforma dintr-un ajutor într-un coșmar :)
long long elim(long long n, int cif){
    long long  r;
    int uc;

    if(n<=9){
        if(n!=cif)
            r=n;
        else
            r=-1; // nu a mai ramas nicio cifra
    }else{
        uc=n%10;
        r=elim(n/10, cif);
        if(uc!=cif)
        {
            if(r<0)
                return uc;
            else
                r=r*10+uc;
        }
    }

    return r;
}

este, de fapt:

long long elim(long long n, int cif){
    long long  r;
    int uc;

    if(n==0)
      return 0; // nu avem ce elimina

    uc=n%10;
    r=elim(n/10, cif);
    if(uc!=cif)
      r=r*10+uc;

    return r;
}

... cu condiția ca elim(n,cif) să returneze totdeauna numărul din care am eliminat cifra cif, nu erori gen -1.

  • Cojocariu: Program foarte bun, bravo!
  • Dobre: Program bun, cu următoarele observații:
    • Instrucțiuni return în mijlocul funcțiilor, nu ai voie așa ceva, aruncăm structurarea pe fereastră? :-)
    • Instrucțiuni else nenecesare după if cu return
    • Tratezi cazul de ieșire din recursivitate la final, nu e greșit, dar e mai greu de citit codul
int cif (unsigned long long n ,int cf){
  if (n == 0)
    return 0;
  if(n % 10 == cf )
    return 1;
  else
    return cif(n/10,cf);
}
int nset(unsigned long long n,int cf){
  if(cf<=9)
    return cif(n,cf)+nset(n,cf+1);
  return 0;
}
  • Hossu: rezolvare simpatică, similară cu a lui Benescu. "Trișezi", folosind un vector de frecvență într-un întreg. Nu acesta era scopul, din moment ce v-am interzis vectorii probabil că era de preferat să folosești recursivitate :-) Ca obiecții, nu îmi place că folosești variabile globale, iar funcția nu returnează nimic. Chiar și în rezolvarea ta altfel trebuia să trimiți masca și numărul de cifre ca parametru, ceea ce ar fi fost mai greu, te-ar fi solicitat:
int nrCifDistincte;
int numarDeCifre;    // bitii 0...9 sunt 1 pentru cifrele 0...9 existente

void calcCifDistincte (unsigned long long n) {
  int masca;
  if (n > 0) {
    masca = 1 << (n % 10);
    if ((numarDeCifre & masca) == 0) {
      nrCifDistincte++;
      numarDeCifre = numarDeCifre | masca;
    }
    calcCifDistincte(n / 10);
  }
}
  • Iordache: program bun, dar ai else-uri nenecesare și return în mijlocul funcției.
  • Mocanu: interesantă idee. Ai folosit o variabilă globală, martor, ce ține permanent o copie intactă a lui n. Era și mai drăguț dacă trimiteai acea copie ca parametru al funcției, dar oricum e interesant că ai reușit o rezolvare într-o singură funcție recursivă, bravo! Ai else-uri nenecesare, ce complică citirea.
unsigned long long n;

int nset(unsigned long long sn,int nr){
  if(nr==10){
    return 0;
  }
  if(sn==0){
    return nset(n,nr+1);
  }else{
    if(sn%10==nr){
      return 1+nset(n,nr+1);
    }else{
      return nset(sn/10,nr);
    }
  }
}
  • Mușat: program bun, comentariul greșit: funcția f() returnează 1 atunci cînd cifra nu apare în număr, nu atunci cînd apare o singură dată. Oare cum se întîmplă un comentariu greșit la un program corect, dacă se presupune că ai înțeles programul? Vrei să vezi dacă mă fentez? :-) Te rog denumește funcțiile cu sens. Atenție la else inutil, după un if cu return.
int f( long long n, int cf ) { /// Aceasta functie returneaza 1 daca cf ( 0 <= cf < 10 ) apareo singura data in numarul n;
    if ( n == 0 ) /// Daca este 0 inseamna ca apare o singura data
        return 1;
    if ( n % 10 == cf ) /// Daca este cifra inseamna ca nu apare
        return 0;
    return f( n / 10, cf );
}
  • Nicola: Program foarte bun, ca și toate celelalte! Atenție la repetiția de condiții în funcția exista(). E bine să ai o gîndire simplă cînd scrii funcții recursive, altfel ele scapă rapid de sub control.
  • Petcu: Program foarte bun, bravo!
  • Ștefănescu: Program foarte bun, bravo!
  • Togan: Ideea este bună. Nu-mi place că ai folosit variabile globale inutile, este periculos, te poți încurca ușor. E preferabil să transmiți parametri în acest caz. Te-ai complicat și cu puterile lui 10, apoi resetezi la zero cfe după ce este folosit, în loc să-l resetezi înainte. Din păcate nu am timp să depanez programul să ne dăm seama unde e greșeala, dar ai testele, te rog să îl depanezi tu.
  • Voicu: Program foarte bun, bravo!

A doua grupă

  • Asgari: Program foarte bun, bravo!
  • Cadîr: Program bun. Dar atenție la încîlceală, recursivitatea este suficient de grea. În funcția apare() ai tratat cazul special n==1, care este inclus în cazul cînd testezi ultima cifră. De aceea ai atîtea ramuri și codul se lungește și poți să îl greșești. Ai și else-uri inutile, după return. Iată:
int apare (long long n, int c) {
  if (n <= 9 && n == c)
    return 1;
  else if (n <= 9 && n != c)
    return 0;
  else if (n % 10 == c)
    return 1;
  return apare (n / 10, c);
}

puteai să scrii, mai simplu:

int apare (long long n, int c) {
  if (n == 0)
    return 0;
  if (n % 10 == c)
    return 1;
  return apare (n / 10, c);
}
  • Dimulescu: Programul este bun, dar: ai avertisment de compilare important, nu le ignora! Setezi opțiuni de compilare în CodeBlocks? -O2 și -Wall, te rog să le setezi și să te uiți cînd compilezi programul (dai build, nu build and run, iar apoi te uiți în fereastra de jos, unde ai avertismente sau erori de compilare). Avertismentul spune că deși funcția returnează o valoare, tu nu returnezi nici o valoare la final de funcție. Nu mi-e deloc clar cum de iei 100p, cred că varena ține cu tine :-)
int exista( long long n, int c){      //aceasta fucntie ne spune daca in numarul n exista cifra c
  if( n == 0)
    return 0;
  if( c == n%10 )
    return 1 + exista( n/10 , c);
  exista( n/10, c );
}
  • Fares: Program bun. Dar cu multe probleme mărunte:
    • Funcția nrcifdist() nu returnează nimic. Ai folosit o variabilă globală, neelegant și periculos.
    • În funcția find() nu tratezi toate cazurile de ieșire la început, unul din ele este la final, nu e este bine.
    • În funcția find() ai else-uri după return, sînt inutile.
  • Ghica: Program bun! Atenție, ai multe else-uri după return, sînt inutile. Și nu îți complica viața introducînd cazuri particulare care nu există: cazul cînd n este cifră este totuna cu cazul cînd testezi ultima cifră a lui n:
int existacif( long long n, int c ) {
  if( n <= 9 )
    return n == c;
  if( n % 10 == c )
    return 1;
  else
    return existacif( n / 10, c );
}

puteai scrie:

int existacif( long long n, int c ) {
  if( n % 10 == c )
    return 1;
  return existacif( n / 10, c );
}
  • Grecu: Program foarte bun, bravo! Ca observație de eficiență, în loc să numeri de cîte ori apare o cifră în n te puteai opri la prima apariție în n/10.
  • Ilie: Program bun. Dar cu o oarecare încîlceală la testul dacă o cifră apare într-un număr. Tu scrii:
int comp( int a, long long n ) {
    if ( n == 0 )
        return 1;
    if ( a == n % 10 || comp( a, n / 10 ) == 0 )
        return 0;
    return 1;
}

Condiția compusă nu se justifică, nu duce la ceva mai clar și mai scurt. Puteai scrie așa:

int comp( int a, long long n ) {
    if ( n == 0 )
        return 1;
    if ( a == n % 10 )
        return 0;
    return comp( a, n / 10 );
}
  • Ipate: Program foarte bun, bravo!
  • Marcu: Programul tău este destul de încîlcit ca logică. În recursivitate este bine să tratezi cazurile simple la început și mai ales să nu complici lucrurile. Vezi te rog soluțiile de mai jos. Ai avertismente de compilare. Unul îți spune ceva banal, anume că ai un fprintf() la linia 32 care primește două expresii de afișat dar are doar un "%d". Cam neglijent. Celelalte îți spun că există posibilitatea ca o funcție care ar trebui să returneze ceva să nu returneze nimic pe anumite ramuri. Asta deoarece tu apelezi la linia 16 cifredist( n / 10, n / 10 % 10 ); fără să stochezi rezultatul. Nu înțeleg cum de ai luat 100p, te place varena :) Atenție la else-uri inutile, complici programul.
int existacifra( long long n, int cf ) { // verificam daca cf exista in n / 10
  if ( n == 0 )
    return 0;
  if ( n % 10 == cf )
    return 1;
  else
    existacifra( n / 10, cf );
}

int cifredist( long long n, int cf ) {
  if( n == 0 )
    return 0;
  if ( existacifra( n / 10 , cf) == 1 ) // exista in stanga numarului cf
    cifredist( n / 10, n / 10 % 10 );
  else {
    if ( n % 10 == cf )
      return 1 + cifredist( n / 10, n / 10 % 10 );
    else
      return cifredist( n / 10, n / 10 % 10 );
  }
}
  • Moroșan: nimic? Nu cred că problema e atît de grea încît să nu încerci absolut nimic.
  • Nicu: Ce e programul tău, o glumă? Ai scris acel for scriind fiecare iterație a sa. Iar funcția ap() este foarte ineficientă, numeri de cîte ori apare o cifră ca mai apoi să te întreb doar dacă apare o dată. Puteai să te oprești din recursivitate cînd dădeai de prima apariție, nu? Nicu, dacă scriem un program recursiv nu înseamnă că aruncăm la gunoi tot ce am învățat pînă acum! De la tine am pretenții mai mari, codul tău este neglijent și ineficient:
int ap( long long n, int cif ) {
	if ( n == 0 )
		return 0;
  if ( n % 10 == cif )
		return 1 + ap ( n / 10, cif );
  else
    return ap ( n / 10, cif );
}

int main()
{
    int ans, i;
	  long long n;
    FILE *fin, *fout;
    fin = fopen( "nset.in", "r" );
    fout = fopen( "nset.out", "w" );
    fscanf( fin, "%lld", &n );
    ans = 0;
    ans = ( ap ( n, 0 ) > 0 ) + ( ap ( n, 1 ) > 0 ) + ( ap ( n, 2 ) > 0 ) + ( ap ( n, 3 ) > 0 ) + ( ap ( n, 4 ) > 0 ) + ( ap ( n, 5 ) > 0 ) + ( ap ( n, 6 ) > 0 ) + ( ap ( n, 7 ) > 0 ) + ( ap ( n, 8 ) > 0 ) + ( ap ( n, 9 ) > 0 );
    fprintf( fout, "%d", ans );
    fclose( fin );
    fclose( fout );
    return 0;
}
  • Petrescu: Program foarte bun, bravo! Ca și celelalte rezolvări de la temă!
  • Popescu: Program bun. Dar te-ai complicat puțin. Mai întîi, nu sînt de acord cu denumirea funcției maiApare(). Ea returnează 1 dacă cifra nu apare! Deci trebuia denumită nuApare() :-) Vrei să vezi dacă mă fentez? Sau testezi dacă pot citi programe care fac inversul decît ceea ce promit? :-) Acum: parametrul aparut din funcție este mereu 1. Deci este inutil. Și complică codul. Iată:
int maiApare( int cif, long long n, int aparut ) {
  if ( n == 0 )
    return 1;
  if ( n % 10 == cif ) {
    if ( aparut == 1 )
      return 0;
    else
      aparut = 1;
  }
  return maiApare( cif, n / 10, aparut );
}

era, de fapt, după simplificări:

int nuApare( int cif, long long n ) {
  if ( n == 0 )
    return 1;
  if ( n % 10 == cif )
    return 0;
  return nuApare( cif, n / 10, aparut );
}
  • Rebengiuc:
  • Rughiniș:
  • Stancu:
  • Tatomir:
  • Teodorescu:
  • Voicu: Program bun! Idee drăguță, "trișezi", folosind un vector de frecvență într-un întreg. Nu acesta era scopul, din moment ce v-am interzis vectorii probabil că era de preferat să folosești recursivitate :-) Ca obiecții, ai grijă, ai avertismente de compilare! Trebuie să le citești. Setează în CodeBlocks opțiunile de compilare -O2 și -Wall, apoi nu compila cu Build&Run ci doar Build. Apoi te uiți cu atenție la mesajele din fereastra de jos, erori și avertismente. Ai un avertisment deoarece tipărești un long long cu "%d". Care nu trebuia să fie acolo, ai lăsat printf-ul de depanare în cod, foarte rău. Te rog să declari toate variabilele de care ai nevoie la începutul funcției, nu pe parcurs.

Invector

Problema invector: să se răstoarne un vector folosind o funcție recursivă. Vectorul trebuie modificat, nu doar afișat invers.

Comentarii individuale

Prima grupă

  • Benescu: else nenecesar:
void inv(int primul, int ultimul, int v[]){
  int aux;
  if(primul>ultimul)
    return;
  else{
    aux=v[primul];
    v[primul]=v[ultimul];
    v[ultimul]=aux;
    return inv(primul+1, ultimul-1, v);
  }
}
  • Iordache: ce valoare returnezi tu în funcție, dacă funcția e void?
void inv(int pr, int u, int v[]){
    int a;
    if(pr<u){
        a=v[pr];
        v[pr]=v[u];
        v[u]=a;
        return inv(pr+1, u-1, v);
    }

}
  • Mocanu: drăguț programul, dar se cerea să scrii o funcție care răstoarnă un vector, se dădea și corpul programului principal. Tu ai făcut citire plus răsturnare. Pe de altă parte programul e pur recursiv, apreciez!

A doua grupă

  • Dimulescu: if( primul == ultimul || primul > ultimul)? Serios? :-) Recursivitatea e ușoară, matematica ne omoară!
  • Nicu: returnezi zero într-o funcție void. Bun!

Turnurile din Hanoi

Problema hanoi este un exemplu unde rezolvarea recursivă este banală, în vreme ce cea iterativă ar da un pic de furcă.

Problema turnurilor din hanoi: Fie trei tije și n discuri perforate de diametre diferite. Discurile sînt așezate inițial pe tija 1 în ordinea descrescătoare a diametrelor acestora, considerînd sensul de la bază la vîrf. Problema constă în a muta turnul de n discuri de pe tija 1 pe tija 2 ținînd cont de următoarele reguli:

  • La fiecare mutare se mută un singur disc, care se află în vîrful unui turn
  • În permanență, pe fiecare tijă, deasupra unui disc pot fi mutate numai discuri de diametre mai mici.

Comentarii generale

  • Unii din voi v-ați oprit din recursivitate la n == 1. Nu este greșit, țineți însă cont că vă puteați opri la n == 0 și programul se simplifica.

Comentarii individuale

Prima grupă

  • Benescu: drăguț că ai găsit o variantă iterativă. Doar că nu asta era tema, trebuia să dai o soluție recursivă. În plus, sînt convins că nu este rezolvarea ta, ai fost ajutat. V-am dat eu voie să folosiți funcția pow()? Ai idee cum funcționează? Te rog nu folosi așa ceva. Iată:
#include <stdio.h>
#include <math.h>
int v[3]={3, 1, 2};
int p2(int n){
  int r;
  r=1;
  while(n%2==0){
    r++;
    n/=2;
  }
  return r;
}
int main(){
  FILE *fin, *fout;
  int n, moves, i, p, q, x, z;
  fin=fopen("hanoi.in", "r");
  fscanf(fin, "%d", &n);
  fclose(fin);
  moves=pow(2, n)-1;
  fout=fopen("hanoi.out", "w");
  for(i=1; i<=moves; i++){
    z=p2(i);
    p=(n%2+z%2)%2+1;
    q=pow(2, z);
    x=p*(i/q)+1;
    fprintf(fout, "%d %d %d\n", z, v[x%3], v[(p+x)%3]);
  }
  fclose(fout);
  return 0;
}
  • Chivu: drăguță implementarea cu stivă și se vede că ai muncit la ea și ai făcut-o să funcționeze, deloc ușor. Are și sens să folosești o stivă, nu? Din moment ce totdeauna vei lua discul din vîrf. Nu vreau să te dezamăgesc, dar motivul pentru care nu este nevoie de stivă este pentru că odată ce ai mutat n-1 discuri de deasupra este clar că vei muta dicul n. Stiva este implicită în recursivitate. Vezi soluția mai simplă mai jos.
  • Cojocariu: complicat, dar funcționează, bravo! Nu uita: recursivitatea are rostul de a ne ușura viața, nu de a ne-o complica. Totul depinde de cum gîndești folosind-o! Vezi te rog soluția mai jos.
  • Mușat: ideea funcției și forma ei este bună. Dar te-ai complicat cu calculul celei de-a doua tije. Puteai să o trimiți ca parametru. Dacă totuși nu voiai să o trimiți, cea de-a treia tijă se calculează cu formula notto = 3 - from - to;
int not_to( int from, int to ) {
    int notto = 2;
    while ( notto == to || notto == from )
        notto --;
    return notto;
}

void Hanoi( int n, int from, int to ) {
    if ( n == 1 ) {
        fprintf( fout, "%d %d %d\n", n, from + 1, to + 1 );
    } else {
        Hanoi( n - 1, from, not_to( from, to ) );
        fprintf( fout, "%d %d %d\n", n, from + 1, to + 1 );
        Hanoi( n - 1, not_to( from, to ), to );
    }
}
  • Togan: felicitări, ai dus la capăt o implementare deloc ușoară. Nu vreau să îți diminuez elanul, dar stiva nu este necesară, deoarece dacă muți n-1 discuri de deasupra, obligatoriu vei muta discul n. Știi și de unde pînă unde. Stiva este implicită în recursivitate. Vezi soluția de mai jos.

A doua grupă

  • Moroșan: nimic?
  • Nicu: îți plac cazurile particulare și repetiția de cod. Faci în main() ceea ce faci și în funcție. Pare că pînă la recursivitate ai probleme cu programarea de bază. Stiva nu este necesară, ea e menținută implicit în recursivitate (de aceea programul recursiv iese mai simplu cînd ai o astfel de stivă în programul iterativ).
  • Voicu: foarte bun programul, dar închide te rog fișierele!

Tema opțională - rezolvări

Combinări

Problema combinări: - combinări de n luate cîte k. Date numerele naturale n și k, kn, să se afișeze toate submulțimile mulțimii {1, 2, 3, ..., n} de k elemente.

V

Problema v (ONI 2004 clasa a 7-a).

Rezolvări aici [1]

Lecție - recursivitate, continuare

<html5media height="720" width="1280">https://www.algopedia.ro/video/2019-2020/2019-10-24-clasa-7-lectie-info-07-720p.mp4</html5media>

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

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 poz ) {
  int i;

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

int main() {
  int n;

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

Ce complexitate are acest algoritm?

Calculul depășește nivelul acestei lecții. Dar putem vedea că este ineficient: pe măsură ce plasăm numere în vector și vectorul folosit[] se "umple", vom plasa pe poziția curentă tot mai puține numere, dar le vom parcurge pe toate n. Cum am putea îmbunătăți algoritmul? Cumva ar fi bine să parcurgem doar elementele pe care le vom plasa. Avem, deci, nevoie ca la fiecare poziție să avem o mulțime a numerelor rămase de plasat, mulțime pe care să o putem parcurge în O(n - poz) și nu în O(n).

Avem două idei:

Permutări cu interschimbare (swap)

Am putea să menținem acea mulțime chiar în vectorul v[]. Convenția este că dacă am ajuns la poziția poz am plasat deja poz elemente, iar cifrele rămase for fi în vector la pozițiile poz..n-1.

Vom scrie, la început, numerele de la 1 la n în vectorul v[]. Vrem să plasăm un element pe poziția poz. El va fi ales de pe o poziția i care se află după poz, i ≤ poz. Vom interschimba, deci, elementele aflate pe pozițiile poz și i. Aceasta îmi garantează că elementele rămase pe pozițiile poz+1..n-1 sînt elemente încă nefolosite în permutare. Putem apela recursiv funcția. La revenire vom repune elementele în poziția originală, prin încă o interschimbare a elementelor la poziția poz și i.

Avantajul acestei metode este clar, va parcurge doar elementele plasate. Are și vreun dezavantaj?

Dezavantajul este că permutările nu vor fi generate în ordine lexicografică. În funcție de aplicație acest lucru s-ar putea să nu conteze.

Permutări cu liste

Am putea să menținem elementele în ordinea lor crescătoare într-o listă. Atunci cînd folosim un element, plasîndu-l pe poziția poz, îl eliminăm din listă. Apoi reapelăm. La revenirea din apel plasăm elementul înapoi în listă și trecem la următorul element.

Această metodă, implementată corect, este mai rapidă și generează și permutările în ordine lexicografică, deoarece elementele din listă sînt permanent în ordinea inițială.

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

Memoizare - continuare

Anul trecut am vorbit despre memoizare. Am spus atunci că este o metodă de a face un program mai rapid fără a-i schimba modul în care el funcționează. Ideea ei este ca atunci cînd efectuăm un calcul scump să păstrăm valoarea calculată într-un tablou pentru a economisi timp în cazul cînd în viitor vom avea din nou nevoie de acea valoare.

Tot atunci am prezentat un exemplu avansat de memoizare folosit într-o funcție recursivă, mai exact în calculul recursiv al unui element din șirul lui Fibonacci.

Merită menționat că tehnica memoizării se aplică mai ales în funcții recursive. Ea ne permite foarte simplu să scădem timpul de execuție al programului folosind mai multă memorie. Această tehnică este cu atât mai eficientă cu cât ne așteptăm să apelăm de multe ori aceeași funcție cu aceiași parametri. De aceea funcția trivială de calcul al unui termen din șirul lui Fibonacci este un exemplu perfect de memoizare, ea avînd un număr exponențial de apeluri, în varianta nememoizată.

Important: memoizarea nu schimbă logica sau structura algoritmului folosit. Acesta este un mare avantaj. Avem o opțiune între cîtă memorie folosim și cît timp cîștigăm. Aceste tehnici, în care putem alege între timp și memorie, sînt destul de rare în algoritmică.

Să vedem două exemple clasice de memoizare.

Factorial

Algoritmul simplu pentru calculul lui n!, fără memoizare, este:

long long fact( int n ) {
  if ( n == 1 )
    return 1;
  return n * fact( n - 1 );
}

Cel cu memoizare va folosi un vector ce va stoca elementele deja calculate:

long long val[20] = { 1 };

// exemplu de funcție factorial implementată folosind memoizare
long long fact( int n ) {
  if ( val[n] == 0 )             // valoare inca necalculata
    val[n] = n * fact( n - 1 );  // o calculam in tabel

  return val[n];
}

Fibonacci

Algoritmul direct de calcul al celui de-al n-lea termen al șirului lui Fibonacci:

int fib( int n ) {
  if ( n == 1 || n == 2 )
    return 1;
  return fib( n-1 ) + fib( n-2 );
}

Cel cu memoizare va folosi un vector ce va stoca elementele deja calculate:

int val[1000] = { 1, 1 };

// exemplu de funcție fibonacci implementată folosind memoizare
int fib( int n ) {
  if ( val[n] == 0 ) // inca necalculat
    val[n] = fib( n-1 ) + fib( n-2 ); // il calculam in tabel
  return val[n]; // returnam valoarea din tabel
}

Recursie Top-Down

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

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 aproape toate exemplele de pînă acum cu excepția cmmdc, interclasare vectori, combinări, permutări si sumă 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

Rezolvați în clasă: implementați bottom-up cu acumulator exemplele făcute pînă acum.

Factorial

Iată o comparație a celor două implementări ale funcției factorial, implementată recursiv top-down și bottom-up cu acumulator:

Top-down Bottom-up
#include <stdio.h>

int fact( int n ) {
  if ( n == 1 )
    return 1;
  return n * fact( n - 1 );
}

int main() {
  int n;

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

  return 0;
}
#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;
}

Putere

Iată o comparație a celor două implementări ale funcției putere, implementată recursiv top-down și bottom-up cu acumulator:

Top-down Bottom-up
#include <stdio.h>

int putere( int a, int n ) {
  if ( n == 0 )
    return 1;
  return a * putere( a, n - 1 );
}

int main() {
  int n, a;

  scanf( "%d%d", &a, &n );
  printf( "%d^%d = %d\n", a, n, putere( a, n ) );
  return 0;
}
#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;
}

Cmmdc

De remarcat că funcția recursivă care calculează cmmdc a două numere, prezentată în lecția trecută, este deja bottom-up cu acumulator:

int cmmdc( int a, int b ) {
  if ( b == 0 )
    return a;
  return cmmdc( b, a % b );
}

Fibonacci

Iată o comparație a celor două implementări ale șirului lui Fibonacci, implementat recursiv top-down și bottom-up cu acumulator:

Top-down Bottom-up
int fib( int n ) {
  if ( n == 1 )
    return 0;
  if ( n == 2 )
    return 1;
  return fib( n - 1 ) + fib ( n - 2 );
}

Ea va fi apelată astfel:

f = fib( 15 );

Unde 15 este numărul termenului dorit.

int fib( int n, int f1, int f2 ) {
  if ( n == 1 )
    return f1;
  return fib( n - 1, f2, f1 + f2 );
}

Ea va fi apelată astfel:

f = fib( 15, 0, 1 );

Unde 0 și 1 sînt primii doi termeni ai șirului, iar 15 este numărul termenului dorit.

Suma cifrelor unui număr

Iată o comparație a celor două implementări ale sumei cifrelor unui număr, implementată recursiv top-down și bottom-up cu acumulator:

Top-down Bottom-up
int sumac( int n ) {
  if ( n == 0 )
    return 0;
  return n % 10 + sumac( n / 10 );
}

Ea va fi apelată astfel:

s = sumac( 2324103 );

Unde 2324103 este numărul căruia îi calculăm suma cifrelor.

int sumac( int n, int suma ) {
  if ( n == 0 )
    return suma;
  return sumac( n / 10, suma + n % 10 );
}

Ea va fi apelată astfel:

s = sumac( 2324103, 0 );

Unde 2324103 este numărul căruia îi calculăm suma cifrelor, iar 0 este inițializarea acumulatorului sumă.

Putere în O(log n)

Iată o comparație a celor două implementări ale funcției putere, implementată O(log n) recursiv top-down și bottom-up cu acumulator:

Top-down Bottom-up
#include <stdio.h>

// a este numărul de ridicat la putere
// n este puterea
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 n, a;

  scanf( "%d%d", &a, &n );
  printf( "%d^%d = %d\n", a, n, putere( a, n ) );
  return 0;
}
#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;
}

Interclasare vectori ordonați

De remarcat că interclasarea a doi vectori ordonați, prezentată data trecută, este bottom-up cu acumulator (vectorul v3[] este acumulatorul).

Funcția va primi ca parametri cei trei vectori și pozițiile curente în ei (inițial pozițiile de start, 0). La fiecare apel va alege un element pe care îl va copia. Apoi se va reapela cu indici actualizați (i1 și i3 sau i2 și i3).

void interclaseaza( int n1, int v1[], int n2, int v2[], int v3[],
                   int i1, int i2, int i3 ) {
  if ( i1 < n1 ) { // mai avem elemente in primul vector?
    if ( i2 < n2 && v2[i2] < v1[i1] ) { // v2[i2] exista si e mai mic?
      v3[i3] = v2[i2];                  // copiem v2[i1]
      interclaseaza( n1, v1, n2, v2, v3, i1, i2 + 1, i3 + 1 );
    } else {
      v3[i3] = v1[i1];                  // copiem v1[i1]
      interclaseaza( n1, v1, n2, v2, v3, i1 + 1, i2, i3 + 1 );
    }
  } else if ( i2 < n2 ) { // mai avem elemente in v2? (v1 s-a terminat)
    v3[i3] = v2[i2];
    interclaseaza( n1, v1, n2, v2, v3, i1, i2 + 1, i3 + 1 );
  }
}

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ă o comparație a celor două implementări ale testului de palindrom, implementat recursiv top-down și bottom-up cu acumulator:

Top-down Bottom-up
#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;
}
#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;
}

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ă

Tema constă din patru probleme. Ele trebuie rezolvate folosind recursivitate bottom-up cu acumulator și recursie la coadă.

Tema opțională constă din patru probleme grele:

  • Tema 7 opțională clasa a 7a:
    • permutări1 Problema cere ca, dîndu-se indicii anumitor permutări să se calculeze suma acelor permutări.
    • aranjamente Problema cere generarea eficientă a tuturor aranjamentelor și a calculului unor proprietăți ale lor.
    • optim dată la ONI 2012 clasa a 8a, problemă ce se poate rezolva recursiv.
    • balance dată la Shumen 2012 juniori, problemă pentru avansați, deoarece ea necesită backtracking, ceea ce nu am predat.

Temă de gîndire, opțională: Care ar fi un algoritm iterativ de rezolvare a turnurilor din Hanoi? Încercați să găsiți reguli simple, nu doar să mimați algoritmul recursiv folosind o stivă.

Rezolvări aici [2]