Anunț

Deoarece nu toți cei care veniți la cerc v-ați înscris pe grupul de discuții, deși era obligatoriu, vă anunț și aici: temele la cerc nu sînt opționale. Sînt obligatorii. Ceea ce este opțional este venitul la acest cerc, nu temele. Aveți două opțiuni: veniți si faceți tema, sau nu veniți. Ați fost avertizați în repetate rînduri. Data viitoare voi face trierea, vor rămîne doar cei ce arată interes pentru acest cerc.

Tema - rezolvări

Remarci generale:

Nu uitați: rezolvările la sumadiv si invector trebuia să fie fără bucle. Altfel își pierd sensul. Unii din voi ați uitat și mi-ați dat rezolvări parțial iterative, cu bucle.
Combinări este o problemă grea. Dar asta nu este o scuză să scrieți un program încercînd să duplicați altul. Asta e programare aproximativă. Încercați să-l scrieți voi, gîndindu-vă de la zero, chiar dacă aveți un alt program în cap. Unii din voi mi-ați scris un program pornit cu ideea de la permutări, care ține cont ce elemente au fost folosite în trecut. La combinări nu este necesar, deoarece ele sînt sortate. Elementul actual fiind mai mare decît toate cele din-nainte este evident ca nu a mai fost folosit. Alții ați iterat corect, începînd cu elementul anterior plus unu, dar ați mers pînă la n. Aceasta este o ineficiență, căci știm că pe o poziție dată nu putem pune elemente mai mari ca n minus numărul de elemente rămase la dreapta acelei poziții.
V este o problemă la care, fără excepție, v-ați păcălit la un amănunt de nivel foarte jos! Și anume faptul că matricea nu trebuie nici măcar citită în totalitate. De exemplu, dacă matricea este pătratică nu aveți nevoie decît de prima jumate pentru a răspunde la problemă. Este hilar că mulți dintre voi au găsit soluția O(n²), iar apoi nu și-au dat seama că dublează timpul de execuție citind toată matricea. Atenție mare: propunătorii de probleme de olimpiadă au în tolbă un arsenal întreg de trucuri ieftine, care să păcălească elevul care este vigilent numai la trucurile șmechere.

Am rugămintea să vă uitați pe soluțiile propuse de mine. Vă garantez că veți avea ce învăța, chiar dacă ați luat deja 100p la temă.

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

aⁿ în O(log n)

Calculați aⁿ în mod cît mai eficient (a și n numere naturale). Problema este cunoscută şi sub numele de ridicare la putere în timp logaritmic. Ideea din spatele acestei rezolvări este următoarea:

Dacă n este par, atunci aⁿ = a^2*n/2 = (a²)^n/2
Dacă n este impar, atunci n-1 este par și avem aⁿ = a * a^n-1 = a * a^2*(n-1)/2 = a * (a²)^(n-1)/2 = a * (a²)^n/2

În formulele de mai sus am considerat că / este împărțirea întreagă din limbajul C. Se observă că indiferent de paritatea lui n, la fiecare pas al iterației putem transforma a în a * a și apoi putem împărți n la 2. Doar în cazurile cînd n este impar vom acumula valoarea curentă a lui a la produsul calculat. Iată soluția bazată pe această idee:

#include <stdio.h>

int putere( int a, int n ) {
  int p;

  if ( n == 0 )
    return 1;
  p =  putere( a * a, n / 2 );
  if ( n % 2 ) // n impar?
    p *= a;

  return p;
}

int main() {
  int a, n;

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

  return 0;
}

Permutări

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

#include <stdio.h>

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

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

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

int main() {
  int n;

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

Plată suma

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

#include <stdio.h>

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

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

int main() {
  int s;

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

Tipuri de recursie

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

Recursie Top-Down

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

Recursie Bottom-Up

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

Exemple de recursie Bottom-Up cu acumulator

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

Factorial

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

#include <stdio.h>

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

int main() {
  int n;

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

  return 0;
}

Palindrom

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

#include <stdio.h>

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

int main() {
  int n;

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

aⁿ în O(n)

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

#include <stdio.h>

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

int main() {
  int n, a;

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

aⁿ în O(log n)

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

#include <stdio.h>

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

int main() {
  int n, a;

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

Transformarea recursiei in Top-Down

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 (tehnic 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ă

Temă comună

Rezolvați următoarele probleme cu metoda bottom-up cu acumulator și recursie la coadă:

Fibonacci: afișare termenul n din șirul lui Fibonacci modulo număr prim. Deoarece n este mare această problemă nu se poate rezolva recursiv decît cu recursie la coadă, altfel veți depăși memoria.
Suma cifrelor unui număr

De asemenea rezolvați o problemă celebră de recursivitate:

Hanoi 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.

Clasa a 7-a

Aranjamente. Este în regulă să luați doar 50p. Încercați să luați 100p.
Opțional: problemele de clasa a 8-a, mai jos

Clasa a 8-a

Hanoi turnurile din Hanoi, trimiteți și un program nerecursiv (iterativ).
Optim (ONI 2012 clasa a 8-a). Încercați să o rezolvați folosind o funcție recursivă.

Rezolvări aici [2]

Clasa VII/VIII lecția 4 - 22 oct 2013

Contents

Anunț

Tema - rezolvări

Lecție - recursivitate, continuare

Exerciții

Palindrom

aⁿ în O(log n)

Permutări

Plată suma

Tipuri de recursie

Recursie Top-Down

Recursie Bottom-Up

Exemple de recursie Bottom-Up cu acumulator

Factorial

Palindrom

aⁿ în O(n)

aⁿ în O(log n)

Transformarea recursiei in Top-Down

Temă

Temă comună

Clasa a 7-a

Clasa a 8-a

Navigation menu

Page actions

Page actions

Personal tools

Navigation

Search

Tools

Clasa VII/VIII lecția 4 - 22 oct 2013

Anunț

Tema - rezolvări

Lecție - recursivitate, continuare

Exerciții

Palindrom

an în O(log n)

Permutări

Plată suma

Tipuri de recursie

Recursie Top-Down

Recursie Bottom-Up

Exemple de recursie Bottom-Up cu acumulator

Factorial

Palindrom

an în O(n)

an în O(log n)

Transformarea recursiei in Top-Down

Temă

Temă comună

Clasa a 7-a

Clasa a 8-a

Navigation menu

Search

aⁿ în O(log n)

aⁿ în O(n)

aⁿ în O(log n)