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

From Algopedia
Jump to: navigation, search

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.

Soluție

Iată o soluție posibiă:

#include <stdio.h>

// calculeaza recursiv suma cifrelor lui n
int suma( long long n ) {
  if ( n == 0 ) // daca numarul este zero
    return 0;   // suma cifrelor lui este zero
  // altfel vom aduna ultima sa cifra la suma cifrelor numarului ramas
  // prin eliminarea ultimei cifre
  return n % 10 + suma( n / 10 );
}

int main() {
  FILE *fin, *fout;
  long long n;

  fin = fopen( "sumacfnr.in", "r" );
  fscanf( fin, "%lld", &n );
  fclose( fin );

  fout = fopen( "sumacfnr.out", "w" );
  fprintf( fout, "%d\n", suma( n ) );
  fclose( fout );

  return 0;
}

Ce complexitate are acest algoritm?

Desigur O(log n).

Cîtă memorie ocupă?

Deoarece la fiecare apel memorăm n și adresa de revenire din recursivitate memoria ocupată este tot O(log n).

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.

Soluție

O rezolvare forță brută ar apela recursiv sumd pînă ce divizorul d ar depăși n. Această soluție are complexitate O(n) ca timp și va dura destul de mult pe numere mari. Dar problema reală este alta: memoria ocupată va fi de asemenea O(n), din cauza stivei*! Ceea ce înseamnă că nu se va încadra în memorie. Optimizarea este cea clasică: știm că orice divizor d mai mic decît {\sqrt  {n}} are un divizor pereche n / d mai mare decît {\sqrt  {n}}. Putem itera cu d numai pînă la {\sqrt  {n}} și aduna la sumă atît d cît și n / d. Atenție la cazul cînd n este pătrat perfect, cînd adunăm numai d. Iată soluția:

int sumd( int n, int d ) {
  if ( d * d > n )
    return 0;
  if ( d * d == n )
    return d;
  if ( n % d == 0 )
    return d + n / d + sumd( n, d + 1 );
  return sumd( n, d + 1 );
}

Ce complexitate are acest algoritm?

Ca și algoritmul clasic, iterativ el este O({\sqrt  {n}}) timp.

Dar memoria?

Dacă ne uităm la lanțul maxim de apeluri, datorită ultimului apel, care pentru fiecare candidat la divizor apelează o nouă funcție, pare că memoria ocupată pentru adresa de revenire din recursivitate este tot O({\sqrt  {n}}). Acesta ar fi un dezavantaj față de algoritmul clasic, iterativ, care ocupă O(1) memorie.

În realitate, precum vom vedea în lecția de azi, memoria ocupată este doar cea datorată primului apel recursiv, care se face doar pentru divizori. Ea va fi, deci, O(log n) (numărul de divizori ai lui n). Vom vedea cum putem reduce în continuare memoria la O(1).

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.

Soluții

Avem mai multe abordări, voi prezenta aici două.

Soluție ce încearcă apariția fiecărei cifre

Vom testa toate cifrele. Pentru fiecare cifră ce apare în număr vom aduna unu la sumă. La final afișăm acea sumă. Pare complicat să scriem o funcție recursivă care să testeze și fiecare cifră și să și caute pentru fiecare cifră dacă apare în număr. De aceea vom folosi *două funcții* recursive:

  • O funcție recursivă care ne spune cîte din cele zece cifre apar în număr - funcția nset(). Semnificația apelului nset( n, cf) este cîte cifre mai mari sau egale cu cf apar în n. De aceea apelul inițial al funcției pornește cu cifra zero.
  • O funcție recursivă care ne spune dacă o cifră apare în număr - funcția apare(). Semnificația apelului apare( cf, n) este apare cifra cf în n?

Iată o variantă de program:

#include <stdio.h>

// apare cifra cf in n?
int apare( int cf, long long n ) {
  if ( n == 0 )       // în zero nu apare nici o cifra
    return 0;

  if ( cf == n % 10 ) // daca cifra cautata este ultima inseamna ca apare
    return 1;
  
  return apare( cf, n / 10 ); // altfel, poate apare in restul numarului
}

// cite cifre distincte >= cf are n
int nset( long long n, int cf ) {
  if ( cf == 10 ) // am terminat cifrele, 10 apare de 10 ori in numar
    return 0;

  // apare sau nu cf in n (0 sau 1) + cite cifre distincte > cf avem in n
  return apare( cf, n ) + nset( n, cf + 1 );
}

int main() {
  FILE *fin, *fout;
  long long n;

  fin = fopen( "nset.in", "r" );
  fscanf( fin, "%lld", &n );
  fclose( fin );

  fout = fopen( "nset.out", "w" );
  fprintf( fout, "%d\n", nset( n, 0 ) );
  fclose( fout );

  return 0;
}

Ce complexitate are acest algoritm?

Pentru fiecare cifră este posibil să parcurgem toate cifrele numărului, deci O(Σ · log n), unde Σ, precum am mai discutat, este numărul de simboluri ale unui alfabet, în cazul nostru 10, deoarece avem zece cifre.

Soluție ce încearcă apariția ultimei cifre

O altă variantă este să facem același lucru doar pentru cifrele numărului. Mai exact, dacă o cifră din număr mai apare măcar o dată în acel număr, o eliminăm. Altfel, dacă este unică, o contorizăm și o eliminăm.

La fel, vom avea nevoie de două funcții recursive:

  • O funcție recursivă care ne spune cîte distincte are numărul - funcția nset(). Ea va primi ca parametru doar numărul n.
  • Aceeași funcție recursivă din soluția anterioară, care ne spune dacă o cifră apare în număr - funcția apare(). Semnificația apelului apare( cf, n) este apare cifra cf în n?

Iată o variantă de program:

// by Cristian Francu on 2019-10-16
#include <stdio.h>

// apare cifra cf in n?
int apare( int cf, long long n ) {
  if ( n == 0 )       // în zero nu apare nici o cifra
    return 0;

  if ( cf == n % 10 ) // daca cifra cautata este ultima inseamna ca apare
    return 1;
  
  return apare( cf, n / 10 ); // altfel, poate apare in restul numarului
}

// calculeaza numarul de cifre distincte ale lui n
int nset( long long n ) {
  if ( n == 0LL ) // 0 nu are nici o cifra
    return 0;

  // daca ultima cifra nu apare in restul lui n + nr. cf. distincte in n/10
  return (!apare( n % 10, n / 10 )) + nset( n / 10 );
}

int main() {
  FILE *fin, *fout;
  long long n;

  fin = fopen( "nset.in", "r" );
  fscanf( fin, "%lld", &n );
  fclose( fin );

  fout = fopen( "nset.out", "w" );
  fprintf( fout, "%d\n", nset( n ) );
  fclose( fout );

  return 0;
}

Ce complexitate are acest algoritm?

Fiecare cifră a numărului va fi căutată în restul cifrelor, deci pare O(log 2 n). În realitate, pentru fiecare cifră unică se va face o parcurgere a cifrelor numărului, deoarece căutarea se oprește la prima apariție. De aceea, în realitate algoritmul este tot O(Σ · log n).

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!

Soluție

Implementarea este elementară, nu necesită explicații. Dacă vectorul primit are cel puțin două elemente îi vom inversa capetele și apoi vom inversa restul vectorului printr-un apel recursiv:

#include <stdio.h>

int v[100000];

// rastoarna (inverseaza) recursiv elementele unui vector v[] intre pozitiile
// 'primul' si 'ultimul'
void inv( int primul, int ultimul, int v[] ) {
  int aux;

  if ( primul < ultimul ) { // daca mai avem ce rasturna
    aux = v[primul];        // interschimbam elementele la pozitiile date
    v[primul] = v[ultimul];
    v[ultimul] = aux;
    inv( primul + 1, ultimul - 1, v ); // reapelam pentru vectorul mai mic
  }
}

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

Ce complexitate are acest algoritm?

Ca și cel clasic, iterativ, O(n), sper că este evident.

Cîtă memorie va ocupa el?

Lanțul maxim de apeluri recursive este O(n/2), deci aceasta ar părea că este și memoria folosită. Vom vedea în lecția de azi că în anumite cazuri speciale (și în acest caz) memoria este, de fapt, O(1).

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!

Soluție

Funcția recursivă va primi ca parametri numărul n de discuri de mutat, precum și cele trei tije, cu semnificația "de pe tija1 pe tija2 folosind tija3. Rezolvarea este cu metoda divide et impera, despre care vom învăța: vom muta n - 1 discuri de pe tija1 pe tija3. Apoi vom muta ultimul disc, n, de pe tija1 pe tija2. În final vom muta cele n - 1 discuri de pe tija3 pe tija2. Iată implementarea:

#include <stdio.h>

FILE *fin, *fout;

void hanoi( int n, int tija1, int tija2, int tija3 ) {
  if ( n > 0 ) {
    hanoi( n - 1, tija1, tija3, tija2 );
    fprintf( fout, "%d %d %d\n", n, tija1, tija2 );
    hanoi( n - 1, tija3, tija2, tija1 );
  }
}

int main() {
  int n;

  fin = fopen( "hanoi.in", "r" );
  fscanf( fin, "%d", &n );
  fclose( fin );

  fout = fopen( "hanoi.out", "w" );
  hanoi( n, 1, 2, 3 );
  fclose( fout );

  return 0;
}

Ce complexitate are acest algoritm?

În mod clar timpul este dat de numărul de afișări, sau numărul de mutări. Care nu este chiar banal de calculat la clasa a șaptea. Observăm că timpul pentru apelul unei funcții cu parametrul n este 1 + de două ori timpul pentru apelul funcției cu parametrul n-1. Mai exact:

T(n) = 1 + 2 T(n-1)
T(n) = 1 + 2 (1 + 2 (1 + ... 1 + 2 (1 + 2 T(0)) ... ))
T(n) = 1 + 2 + 22 + ... + 2n-1 + 2n T(0)

Dar T(0) este 1, deci:

T(n) = 1 + 2 + 22 + ... + 2n-1 + 2n
T(n) = 2n+1

Complexitatea este, deci, O(2n+1, totuna cu O(2n.

Cîtă memorie ocupă acest algoritm?

Vom căuta lanțul cel mai lung de apel. Deoarece avem n discuri, lanțul are lungime n, deci memoria ocupată este O(n).

Tema opțională - rezolvări

Combinări

Problema combinări: {C}_{{n}}^{{k}}- 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.

Este un alt exemplu de problemă unde recursivitatea duce la un program mai simplu și mai clar.

Iată două posibilități de soluție.

Varianta hibridă (recursivitate + buclă)

Vom folosi un vector global int v[19] în care vom stoca combinarea în curs de generare. Funcția recursivă de generare a combinărilor va primi, pe lîngă evidentele valori n și k, indicele de completat în combinarea în curs de generare, s. La acest indice vom plasa, pe rînd, valori plauzibile pentru acea poziție, apoi vom reapela comb() cu următorul indice s + 1. Valorile plauzibile pe poziția s sînt astfel:

  • Valoarea minimă de pornire este cu unu mai mare decît valoarea anterioară în vector, cu excepția primei poziții unde putem porni cu valoarea 1. Pentru a nu avea un caz particular putem declara vectorul cu un element în plus, sacrificînd v[0] care va rămîne fix, pe valoarea 0 (setată înainte de a intra în recursivitate).
  • Valoarea maximă este astfel încît să mai putem completa numere pînă la finalul combinării. Dacă pe ultima poziție se va afla n, mergem înapoi pînă la poziția s scăzînd unu la fiecare devansare. Astfel, pe poziția s putem avea valoarea maximă n - (k - s).

Atunci cînd s iese în afara combinării, adică atunci cînd este mai mare decît k, ne oprim din recursie și afișăm combinarea generată.

Iată o soluție posibilă:

#include <stdio.h>

int v[19];

void comb( int n, int k, int pos, FILE *fout ) {
  if ( pos > k ) { // afisam o combinare
    int i;
    for ( i = 1; i <= k; i++ )
      fprintf( fout, "%d ", v[i] );
    fprintf( fout, "\n" );
  } else {
    for ( v[pos] = v[pos-1] + 1; v[pos] <= n - (k - pos); v[pos]++ )
      comb( n, k, pos + 1, fout ); // porneste de la pozitia urmatoare
  }
}

int main() {
  FILE *fin, *fout;
  int n, k;

  fin = fopen( "combinari.in", "r" );
  fscanf( fin, "%d%d", &n, &k );
  fclose( fin );

  fout = fopen( "combinari.out", "w" );
  v[0] = 0;
  comb( n, k, 1, fout );
  fclose( fout );

  return 0;
}

Varianta pur recursivă (fără bucle)

Această variantă este foarte asemănătoare cu cea de mai sus. În continuare vom avea un vector completat poziție cu poziție. Dar, în loc să completăm poziția curentă într-o buclă, plasînd pe rînd toate elementele posibile, vom simula for-ul recursiv, transmițînd încă un parametru funcției: cifra de la care putem începe restul combinării. Cu alte cuvinte

comb( n, k, pos, cifra, fout )

va genera toate combinările de n luate cîte k, și anume începînd cu poziția pos a vectorului, avînd voie să folosim elemente în intervalul [cifra..n].

Avem două cazuri de recursie:

  1. Plasăm cifra curentă pe poziție și apoi chemăm recursiv funcția de la poziția următoare, dar cu cifre strict mai mari:
    comb( n, k, pos + 1, cifra + 1, fout )
    .
  2. Ignorăm cifra curentă, generînd de la poziția curentă combinări cu elemente din intervalul [cifra+1..n]:
    comb( n, k, pos, cifra + 1, fout )
    . În acest caz trebuie să avem grijă să mai avem destule elemente în intervalul [cifra+1..n] pentru a umple cele k - pos poziții rămase.

Iată o soluție posibilă:

#include <stdio.h>

int v[18];

void comb( int n, int k, int pos, int cifra, FILE *fout ) {
  if ( pos == k ) { // afisam o combinare
    int i;
    for ( i = 0; i < k; i++ )
      fprintf( fout, "%d ", v[i] );
    fprintf( fout, "\n" );
  } else {
    v[pos] = cifra;                         // plaseaza cifra pe pozitie
    comb( n, k, pos + 1, cifra + 1, fout ); // porneste de la pozitia urmatoare, cu cifra urmatoare
    if ( n - cifra >= k - pos )             // daca mai avem destule cifre
      comb( n, k, pos, cifra + 1, fout );   // incercam si cu cifra urmatoare, de la aceeasi pozitie (fara for)
  }
}

int main() {
  FILE *fin, *fout;
  int n, k;

  fin = fopen( "combinari.in", "r" );
  fscanf( fin, "%d%d", &n, &k );
  fclose( fin );

  fout = fopen( "combinari.out", "w" );
  comb( n, k, 0, 1, fout );
  fclose( fout );

  return 0;
}

Ce complexitate au acești algoritmi?

Nu este simplu de analizat la clasa a șaptea, dar, intuitiv, deoarece avem O(1) operații per plasare de element în vector complexitatea va fi numărul de combinări înmulțit cu afișarea unei combinări. Pentru cazul cel mai rău ea este O(n · 2n).

Cîtă memorie folosim?

Vectorul v[] ocupă O(n). Lungimea maximă a lanțului de apel este k. Memoria folosită va fi, deci O(n + k), pe cazul cel mai rău O(n).

V

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

Avem două variante de soluție. Iată-le mai jos:

Varianta cubică

Prima soluție este forța brută, în care parcurgem V-urile și calculăm sumele elementelor pe parcurs, alegînd suma maximă întîlnită. Această variantă are complexitate O(n3) și folosește O(n2) memorie pentru a stoca matricea. Aceasta este și soluția comisiei. Este o soluție rezonabilă pentru clasa a 7a, dar nu este optimă. Va trece 50% din teste. Iată o implementare posibilă:

#include <stdio.h>

int a[1000][1000];

int main() {
  FILE *fin, *fout;
  int m, n, l, c, lun, lmax, startc, sum, maxsum, maxc, maxl;

  fin = fopen( "v.in", "r" );
  fscanf( fin, "%d%d", &m, &n );
  for ( l = 0; l < m; l++ )
    for ( c = 0; c < n; c++ )
      fscanf( fin, "%d", &a[l][c] );
  fclose( fin );

  lmax = n;
  if ( 2 * m - 1 < lmax )
    lmax = 2 * m - 1;

  maxsum = -2000000000;
  for ( lun = 3; lun <= lmax; lun += 2 ) {
    for ( startc = 0; startc <= n - lun; startc++ ) {
      sum = 0;
      for ( l = 0; l < lun / 2; l++ ) // aduna elementele mai putin virful
        sum = sum + a[l][startc + l] + a[l][startc + lun - l - 1];
      sum += a[lun / 2][startc + lun / 2]; // aduna virful
      if ( sum > maxsum ) {
        maxsum = sum;
        maxc = startc;
        maxl = lun / 2;
      }
    }
  }

  fout = fopen( "v.out", "w" );
  fprintf( fout, "%d %d %d\n", maxsum, maxc + 1, maxl + 1 );
  fclose( fout );

  return 0;
}

Varianta pătratică (optimă)

În această variantă calculăm o construcție auxiliară: pentru fiecare element al matricei originale vom memora încă două numere: suma lanțului diagonal de elemente către stînga-sus și suma lanțului diagonal de elemente către dreapta-sus. Aceste numere se pot calcula în O(1) printr-o parcurgere a matricei. Avînd aceste două numere putem ușor calcula pentru fiecare element care este suma V-ului care are vîrful în acel element. Trebuie să avem grijă să nu calculăm sumele decît pentru acele vîrfuri al căror V nu iese din matrice.

Această soluție are complexitate O(n2). Aceasta este o soluție optimă pentru că numai citirea matricei are această complexitate, deci nu se poate mai bine. Memoria folosită este O(n2), dar poate fi îmbunătățită la O(n) observînd că nu avem nevoie, în calcule, decît de ultima linie a matricei originale și ultimele două linii ale matricelor auxiliare.

Această soluție va trece 100% din teste, dar numai implementată cu O(n) memorie. Iată o implementare posibilă:

#include <stdio.h>

int stinga[2][2000], dreapta[2][2000];

int main() {
  FILE *fin, *fout;
  int m, n, l, c, vsel, elem, sumv, maxsum, maxc, maxl, limita;

  fin = fopen( "v.in", "r" );
  fscanf( fin, "%d%d", &m, &n );
  for ( c = 0; c < n; c++ ) { // citim prima linie
    fscanf( fin, "%d", &stinga[0][c] );
    dreapta[0][c] = stinga[0][c];
  }
  vsel = 1;
  maxsum = -2000000000;
  limita = m - 1;   // calculam linia maxima care poate fi atinsa de un v
  if ( n / 2 < m )  // este fie numarul de linii
    limita = n / 2; // fie numarul de coloane supra doi
  for ( l = 1; l <= limita; l++ ) {
    for ( c = 0; c < l; c++ ) // citim in gol, elemente nefolositoare
      fscanf( fin, "%d", &elem );
    for ( c = l; c < n - l; c++ ) { // pentru elementele virf pe linie
      fscanf( fin, "%d", &elem );
      // calculam v-ul care se termina in punctul curent
      sumv = elem + stinga[1 - vsel][c-1] + dreapta[1-vsel][c+1];
      if ( sumv > maxsum ) { // testam daca avem un v mai mare
        maxsum = sumv;
        maxc = c - l;
        maxl = l;
      }
      // actualizam vectorii de sume diagonale
      stinga[vsel][c] = stinga[1 - vsel][c-1] + elem;
      dreapta[vsel][c] = dreapta[1 - vsel][c+1] + elem;
    }
    for ( c = n - l; c < n; c++ ) // citim in gol, elemente nefolositoare
      fscanf( fin, "%d", &elem );

    vsel = 1 - vsel;
  }
  fclose( fin );

  fout = fopen( "v.out", "w" );
  fprintf( fout, "%d %d %d\n", maxsum, maxc + 1, maxl + 1 );
  fclose( fout );

  return 0;
}

Rezolvări 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;
}

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]