Clasa a IX-a lecția 16 - 22 feb 2020

From Algopedia
Revision as of 20:42, 22 February 2020 by Teodor (talk | contribs) (→‎Pe categorii)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Clasament teme lecțiile 1 - 15

Pe categorii

Divizori / Primalitate / Ciur
Sortari
Matrici
Cautare binara
Stivă
Recursivitate
Generale

Concursuri

Probleme OȘI
Probleme OJI

Lecție

Recursivitate

Recursivitatea este o tehnică utilă pe care o putem folosi în multe cazuri. În general, vrem să spargem o problemă mai complicată în mai multe probleme mai simple, la care putem răspunde rapid, fără prea mult efort.

O funcție recursivă este o funcție care se apelează pe ea însăși. Pentru a o scrie, trebuie să avem în vedere următoarele:

  • Formula recurentă bine stabilită.
  • Cazurile simple pentru care știm deja să rezolvăm problema.
  • Considerând că funcția ne furnizează deja rezultatul dorit pentru cazurile "mai mici", cum ne folosim de rezultatul acestora pentru a răspunde corect la cazul curent.

Exemple

Factorial

Calcul n! Ne vom folosi de definiția recursivă:

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

Explicație

Funcția trebuie să ne calculeze n!. Un caz simplu la care știm să răspundem este: 1! = 1. Pentru toate celelalte cazuri, ne vom baza pe faptul că funcția va returna răspunsul corect pentru n - 1 și anume (n - 1)!, rezultat pe care îl vom lua și îl vom înmulți cu n pentru a obține n!.

Suma cifrelor unui număr

Problema este și pe varena: sumacfnr.

int sumcf(int n) {
  if (n < 10)
    return n;
  return n % 10 + sumcf(n / 10);
}

Explicație

Cazul simplu la care știm să răspundem este acela în care numărul nostru este format dintr-o singură cifră, suma cifrelor unui astfel de număr fiind chiar numărul. Pentru celelalte numere, suma cifrelor lor este egală cu ultima cifră plus suma cifrelor numărului din care ștergem ultima cifră.

Scrierea numerelor în ordinea inversă citirii

Se citește de la tastatură un număr N și un șir de N numere naturale. Să se scrie numerele în ordinea inversă citirii:

#include <stdio.h>

void afisare(int n) { // n reprezintă numarul de valori ramase de citit
  if (n == 0) // daca nu mai avem nimic de citit, intrerupem functia.
    return;

  int x;
  scanf("%d", &x); // citim o valoare
  afisare(n - 1); // trecem mai departe pentru a citi restul valorilor
  printf("%d ", x); // afisam valoarea la intoarcerea din apelurile recursive
}

int main() {
  int n;
  scanf("%d", &n);
  afisare(n); // initial, mai avem de citit n valori

  return 0;
}

Descompunerea în baza 2

void baza2(int n) {
  if (n <= 1) { // daca n este 0 sau 1
    printf("%d", n); // descompunerea lui in baza 2 este chiar n
    return;
  }

  baza2(n / 2);
  printf("%d", n % 2);
}

O altă variantă de a scrie această funcție:

void baza2(int n) {
  if (n > 1)
    baza2(n / 2);
  printf("%d", n % 2);
}

Top-Down vs Bottom-Up

Am discutat despre cele două metode de implementare ale funcțiilor recursive și diferențele între acestea. O sursă în care sunt explicate foarte fain conceptele și în care găsiți multe exemple: IQAcademy.

Aplicații

varena - sumacfnr
varena - sumadiv
varena - nset

Temă

Recursivitate

varena - sumacfnr
varena - sumadiv
varena - nset
varena - invector
varena - maxrec
varena - primrec
varena - factorizare
varena - fibonacci

OJI

infoarena - pic