Clasa a VII-a lecția 9 - 7 nov 2019

From Algopedia
Revision as of 14:23, 10 November 2019 by Cristian (talk | contribs)

Jump to: navigation, search

Tema 7 - rezolvări

Fibonacci

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.

Soluție

#include <stdio.h>

#define BIG_PRIME 982451653

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

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

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

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

  return 0;
}

Ce complexitate are această soluție?

  • Timp O(n)
  • Memorie O(1)

Se poate mai bine?

  • Formula lui Binet - nepractică
  • Metoda lui Dijkstra - recurență în timp logaritmic
  • Folosind matrice și exponențiere logaritmică

Pentru cei interesați citiți A Formula for the n-th Fibonacci number.

Primrec

Problema primrec este clasică. Ea cere testarea primalității unui număr folosind o funcție recursivă. Deoarece numerele sînt mari o soluție liniară va depăși timpul. O soluție optimă, radical din n, va trece toate testele. Ea poate să fie recursivă la coadă sau nu. Iată o soluție bottom-up, recursivă la coadă:

Soluție

#include <stdio.h>

int prim( int n, int divizor ) {
  if ( divizor * divizor > n )
    return 1;
  if ( n % divizor == 0 )
    return 0;
  return prim( n, divizor + 1 );
}

int main() {
  FILE *fin, *fout;
  int a, b, c;

  fin = fopen( "primrec.in", "r" );
  fscanf( fin, "%d%d%d", &a, &b, &c );
  fclose( fin );

  fout = fopen( "primrec.out", "w" );
  fprintf( fout, "%d %d %d\n", prim( a, 2 ), prim( b, 2 ), prim( c, 2 ) );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

  • Timp O({\sqrt  {a}})
  • Memorie O(1)

Maxrec

Problema maxrec este altă problemă clasică. Ea cere aflarea maximului unei secvențe de numere de la intrare folosind o funcție recursivă.

Soluție

Iată o soluție bottom-up, recursivă la coadă:

#include <stdio.h>

FILE *fin, *fout;

int maxim( int n, int maxpartial ) {
  int e;

  if ( n == 0 )
    return maxpartial;
  fscanf( fin, "%d", &e );
  if ( maxpartial < e )
    maxpartial = e;
  return maxim( n-1, maxpartial );
}

int main() {
  int n, e;

  fin = fopen( "maxrec.in", "r" );
  fout = fopen( "maxrec.out", "w" );

  fscanf( fin, "%d%d", &n, &e );
  fprintf( fout, "%d\n", maxim( n-1, e ) );

  fclose( fout );
  fclose( fin );

  return 0;
}

Ce complexitate are această soluție?

  • Timp O(n)
  • Memorie O(1)

Atenție! O soluție recursivă la coadă, ca cea de mai sus, necesită memorie O(1). Însă poate unii din voi au remarcat în monitorul de evaluare faptul că soluția ocupă, în fapt, mult mai multă memorie. Care este explicația?

Din nefericire pare că fscanf() nu eliberează memoria folosită, drept care orice program recursiv ce folosește fscanf() va folosi O(n) memorie. Pe de altă parte, fgetc() nu pare a avea această problemă. Un program ce folosește citire cu caractere va folosi memorie O(1).

Factorizare

Problema factorizare este altă problemă clasică. Ea cere să se afișeze descompunerea în factori primi a unui număr folosind recursivitate. Deoarece n este mare, 1014, este necesar un algoritm ce merge pînă la maxim radical din n.

Iată o soluție bottom-up, recursivă la coadă:

Soluție

#include <stdio.h>

FILE *fin, *fout;

void factorizare( long long n, long long d, int p ) {
  if ( n % d == 0 )                       // se imparte n la d?
    factorizare( n / d, d, p + 1 );       // daca da, continua impartirea
  else {                                  // n nu se imparte la d
    if ( p > 0 )                          // n s-a impartit la d in trecut?
      fprintf( fout, "%lld %d\n", d, p ); // afiseaza factorul
    if ( d * d > n ) { // incercam doar factorii pina in radical din n
      if ( n > 1 )                        // daca a ramas ceva in n
        fprintf( fout, "%lld 1\n", n );   // este un numar prim la puterea 1
    } else                                // d*d<=n si n nu se imparte la d
      factorizare( n, d + 1, 0 );         // trecem la urmatorul divizor
  }
}

int main() {
  long long n;

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

  fout = fopen( "factorizare.out", "w" );
  factorizare( n, 2LL, 0 ); // pornim cu primul factor prim la puterea 0
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

  • Timp O({\sqrt  {N}})
  • Memorie O(1)

Tema 7 opțională - rezolvări

Permutări1

Problema permutări1 este o problemă clasică. Ea cere să se calculeze suma anumitor permutări specificate la intrare. Soluția clasică de generare a permutărilor, ce folosește vectori de frecvență, nu este suficient de rapidă și va lua circa jumate din punctaj. Este necesară o generare eficientă, folosind liste.

Iată o soluție posibilă:

Soluție

#include <stdio.h>

#define NIL 0
#define N_MAX 10

FILE *fin, *fout;

int curent, // numarul permutarii (citit la intrare in ordine crescatoare)
  np;       // numarul permutarii generate
long long s;         // suma permutarilor cerute la intrare
int next[N_MAX + 1]; // lista de numere 0..n-1

void permutari( int poz, int n, long long xpart ) {
  int i, aux;
  
  if ( poz >= n ) {
    np++;
    if ( np == curent ) {
      fscanf( fin, "%d", &curent ); // citim noul element la intrare
      s += xpart;
    }
  } else {
    i = 0;
    while ( next[i] != NIL ) {
      aux = next[i];
      next[i] = next[next[i]];
      permutari( poz + 1, n, xpart * 10 + aux - 1 );
      i = next[i] = aux;
    }
  }
}

int main () {
  int n, i;

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

  // initializare lista numere
  for ( i = 0; i < n; i++ )
    next[i] = i + 1;
  next[n] = NIL;

  np = 0;
  s = 0LL;
  permutari( 0, n, 0LL );
  fclose( fin );

  fout = fopen( "permutari1.out", "w" );
  fprintf( fout, "%lld\n", s );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

  • Timp O(n!)
  • Memorie O(n)

Aranjamente

Problema aranjamente este o problemă clasică. Ea cere să se calculeze proprietățile unor aranjamente. Soluția clasică de generare a aranjamentelor, ce folosește vectori de frecvență, nu este suficient de rapidă și va lua circa jumate din punctaj. Este necesară o generare eficientă, folosind liste sau swap.

Iată o soluție posibilă:

Soluție

#include <stdio.h>

#define NIL -1

int next[11] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, NIL};
int frecv[65536];

void genAranjamente( int poz, int n, int k, int p, long long acc ) {
  int i, save;

  if ( poz == k )
    frecv[(acc + (acc >> p)) & ((1 << p) - 1)]++;
  else {
    i = 0;
    acc *= 10;
    while ( (save = next[i]) != NIL ) {
      next[i] = next[save];
      genAranjamente( poz + 1, n, k, p, acc + save - 1 );
      i = next[i] = save;
    }
  }
}

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

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

  next[n] = NIL;
  genAranjamente( 0, n, k, p, 0 );
  p = 1 << p;
  max = 0;
  for ( k = 0; k < p; k++ )
    if ( max < frecv[k] )
      max = frecv[k];

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

  return 0;
}

Ce complexitate are această soluție?

  • Timp O(n!/(n-k)! + 2p) (discutabil dacă shift cu p se face în timp constant)
  • Memorie O(k + 2p)

Optim

Problema optim a fost dată la ONI 2012 clasa a 8a. Ea are o soluție recursivă și una pe bază de programare dinamică.

Soluție recursivă

Ideea de rezolvare bazată pe recursivitate este să scriem o funcție recursivă similară cu cea de combinări sau permutări, care construiește toate variantele și le calculează valorile, ținînd minte minimul și maximul. Funcția primește ca parametri poziția curentă în vectorul soluție construit, numărul de semne plus și înmulțit rămase de folosit, suma expresiei curente mai puțin ultimul produs din expresie și ultimul produs din expresie separat.

Iată o soluție bazată pe această idee:

#include <stdio.h>

int nr[30], max, min, n;

void cauta( int i, int ad, int mul, int sum, int p ) {
  if ( i == n ) {    // am pus toate semnele, expresia are valoarea sum + p
    sum += p;
    if ( sum < min )
      min = sum;
    if ( sum > max )
      max = sum;
    return;
  }
  if ( ad > 0 )
    // inaintea numarului i punem +
    // produsul vechi se incheie, deci il putem adauga la sum
    // produsul actual este format doar din numarul curent
    cauta( i + 1, ad - 1, mul, sum + p, nr[i] );
  if ( mul > 0 )
    // inaintea numarului i punem *
    // sum ramine neschimbat, caci inmultim produsul curent
    // produsul se actualizeaza cu numarul curent
    cauta( i + 1, ad, mul - 1, sum, p * nr[i] );
}

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

  fin = fopen( "optim.in", "r" );
  fscanf( fin, "%d%d", &n, &k );
  for ( i = 0; i < n; i++ )
    fscanf( fin, "%d", &nr[i] );
  fclose( fin );

  // nu stim cu cit sa initializam valorile max si min dar putem calcula
  // ca expresia nu are cum sa depaseasca un miliard, plus/minus
  // deci putem initializa linistiti cu doua miliarde plus/minus
  max = -2000000000;
  min = 2000000000;
  cauta( 1, n - k - 1, k, 0, nr[0] );

  fout = fopen( "optim.out", "w" );
  fprintf( fout, "%d %d\n", min, max );
  fclose( fout );
  return 0;
}

Balance

Problema balance a fost dată la Shumen 2013 juniori. Ea se poate rezolva cu backtracking, depășind nivelul acestui curs. De aceea nu voi explica soluția.

Soluție cu backtracking

Iată o soluţie posibilă:

#include <stdio.h>

int v[9];

int numara( int i, int n, int st, int dr ) {
  int aux, ret = 0, j;

  if ( i >= n ) // am gasit inca o solutie de a aseza greutatile
    return 1;
  // apeleaza cu greutatea urmatoare i
  if ( st + v[i] <= dr )
    ret += numara( i+1, n, st + v[i], dr );
  ret += numara( i+1, n, st, dr + v[i] );
  for ( j = i+1; j < n; j++ ) {
    // alege greutatea j ca urmatoarea greutate -> inlocuieste-o cu i
    aux = v[i];
    v[i] = v[j];
    v[j] = aux;
    if ( st + v[i] <= dr )
      ret += numara( i+1, n, st + v[i], dr );
    ret += numara( i+1, n, st, dr + v[i] );
    // pune la loc greutatea j
    aux = v[i];
    v[i] = v[j];
    v[j] = aux;
  }
  return ret;
}

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

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

  nr = numara( 0, n, 0, 0 );

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

  return 0;
}

Rezolvări aici [1]

Tema 8 - rezolvări

Invcuv

Problema invcuv este o problemă tipică de recursivitate. Ea cere să se afișeze în ordine inversă mai multe cuvinte de la intrare.

Soluție

Iată o soluție posibilă (46 linii din care 31 linii cod efectiv):

#include <stdio.h>

FILE *fin, *fout;

// Afiseaza un cuvint inversat din fisierul fin
// - de_afisat: primul caracter din fin
// - return: primul caracter de dupa cuvintul afisat invers
int printCuvInv( int de_afisat ) {
  int aux;
  
  if ( de_afisat != ' ' && de_afisat != '\n' ) {
    aux = de_afisat; // memoram caracterul
    // tiparim restul cuvintului
    de_afisat = printCuvInv( fgetc( fin ) ); // primim primul caracter dupa cuv
    fputc( aux, fout );                      // afisam caracterul curent
  }
                                             // returnam caracterul
  return de_afisat;                          // de dupa cuvint
}

// Afiseaza textul din fisierul fin. Cuvintele vor fi afisate inversat.
// - de_afisat: primul caracter din fin
void printText( int de_afisat ) {
  if ( de_afisat == '\n' )                   // final de text?
    fputc( '\n', fout );                     // afisam \n
  else {                                     // mai avem ceva de afisat
    if ( de_afisat == ' ' ) {                // primul caracter este spatiu?
      fputc( ' ', fout );                    // afisam spatiile ca atare
      de_afisat = fgetc( fin );              // avansam la urmatorul caracter
    } else             // litera, inceput de cuvint, afisam cuvintul inversat
      de_afisat = printCuvInv( de_afisat );  // memoram primul car dupa cuvint
    printText( de_afisat );                  // continuam afisarea
  }
}

int main() {
  fin = fopen( "invcuv.in", "r" );
  fout = fopen( "invcuv.out", "w" );

  printText( fgetc( fin ) );

  fclose( fin );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

  • Timp O(N), unde N este numărul de caractere de la intrare. Remarcați că este optimă!
  • Memorie O(M), unde M este lungimea maximă a unui cuvînt.

Palindromuri

Problema palindromuri este o problemă aproape tipică de recursivitate. Ea cere aproximativ același lucru ca și problema invcuv, doar că testăm simetria cuvintelor după inversare. Acest lucru ne cere memorarea lor. Aparent avem o problemă, deoarece un long long nu poate memora 36 de cifre. Dar doi long long pot :-) si aceasta era și mica chichiță a problemei.

Soluție

Iată o soluție posibilă (68 linii din care 40 linii cod efectiv):

#include <stdio.h>

#define NMAXCF 36
#define JUMNMAXCF ((NMAXCF + 1) / 2)

FILE *fin, *fout;

// Inverseaza un long long (cifrele sale vor fi in ordine inversa)
// - x: numarul de inversat
// - r: acumulatorul, la final este rezultatul, initial zero
// - return: numarul inversat
long long inv( long long x, long long r ) {
  if ( x == 0 )
    return r;

  return inv( x / 10, r * 10 + x % 10 );
}

// Testeaza daca numarul format din rasturnatul lui x concatenat cu y
// este palindrom
// - return: 1 daca este palindrom, 0 in caz contrar
int epalindrom( long long x, long long y ) {
  if ( y == 0LL )            // nu avem ce concatena la inversul lui x
    return x == inv( x, 0 ); // deci testam daca x este palindrom

  if ( x % 10 != y % 10 )    // daca nu se potrivesc cifrele nu e palindrom
    return 0;

  return epalindrom( x / 10, y / 10 ); // taiem din x cifra care se potriveste
}

// Calculeaza numarul de palindromuri din fisierul fin
// - x concatenat cu y: numarul curent la intrare in fin
// - ncf: numarul de cifre ale lui x concatenat cu y
// - ac: numarul de palindromuri gasite pina acum
// - return: numarul de palindromuri din fin (variabila globala)
int npali( long long x, long long y, int ncf, int ac ) {
  int ch;

  ch = fgetc( fin );
  if ( ch == '\n' ) // final de text, returnam palindromurile gasite
    return ac + (x > 0LL ? epalindrom( inv ( x, 0 ), y ) : 0 ); 

  if ( ch == ' ' ) { // posibil final de numar, testam x si y
    // e posibil ca spatiul sa vina dupa alt spatiu (si nu incrementam ac)
    ac += x > 0LL ? epalindrom( inv ( x, 0 ), y ) : 0; 
    x = y = 0LL;     // resetam x si y
    ncf = 0;         // si numarul de cifre al lor
  } else {           // ch este cifra, parte din numar
    // adunam la x daca sintem in prima jumate a numarului, altfel la y
    if ( ncf++ < JUMNMAXCF ) // sintem in prima jumatate a lui x concat cu y?
      x = x * 10 + ch - '0'; // adaugam cifra la sfirsitul lui x
    else                     // altfel
      y = y * 10 + ch - '0'; // adaugam cifra la sfirsitul lui y
  }

  return npali( x, y, ncf, ac ); // continuam parcurgerea caracterelor
}

int main() {
  fin = fopen( "palindromuri.in", "r" );
  fout = fopen( "palindromuri.out", "w" );
  fprintf( fout, "%d\n", npali( 0LL, 0LL, 0, 0 ) );
  fclose( fin );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

  • Timp O(N), unde N este numărul de caractere de la intrare. Remarcați că este optimă!
  • Memorie O(1). Tehnic, ea este O(M), unde M este lungimea maximă a unui număr.

Partiții

Problema partitii este o problemă clasică. Ea cere să se afișeze toate partițiile unui număr.

Soluție

Problema este similară cu plata unei sume cu trei monede prezentată la lecție. În loc de trei tipuri de monede avem N tipuri, toate numerele între 1 și N. În loc să numărăm partițiile, le vom genera. Formula de recurență este similară.

Pentru a introduce un element surpriză în această problemă (prea) clasică am cerut ca afișarea să fie eficientă. Dacă ați folosit fprintf() ați luat 90p cu o soluție corectă.

Cum ne dădeam seama că este nevoie de o afișare rapidă? Calculînd mărimea outputului. Vi se spune că aveți de afișat circa 200000 de linii. Aceasta se întîmplă pentru N = 50. Avem trei caractere per număr din partiție, două cifre și un spațiu. Aproximînd grosier lungimea unei partiții ca fiind jumate din N, adică 25, rezultă o lungime medie de 75 de caractere și o lungime totală a output-ului de 75·200000 caractere adică 15MB! Realitatea este undeva sub jumate, circa 6MB, dar oricum suficient cît să conteze.

Cum afișăm eficient ieșirea? O posibilitate este să memorăm caracterele fiecarui număr. Vom avea, deci, o matrice de caractere de 50 de linii și două coloane.

Iată o soluție posibilă (70 linii din care 45 linii cod efectiv):

#include <stdio.h>

#define MAXN 50

char sol[MAXN];
char digits[MAXN + 1][2];
FILE *fin, *fout;

// Initializeaza reprezentarea zecimala a numerelor de la 0 la n
// - n: numarul pina la care se calculeaza reprezentarea
void initDigits( int n ) {
  int i, tencf, unitcf;

  tencf = unitcf = 0;             // zecile si unitatile sint zero
  for ( i = 0; i <= n; i++ ) {    // pentru fiecare numar
    if ( tencf )                  // daca avem zeci
      digits[i][0] = '0' + tencf; // pastram caracterul corespunzator
    digits[i][1] = '0' + unitcf;  // pastram caracterul unitatilor
    if ( ++unitcf == 10 ) {       // avansam unitatile si zecile
      tencf++;
      unitcf = 0;
    }
  }
}

// Genereaza partitiile unui numar
// - n: numarul de partitionat
// - max: numarul maxim pe care il putem folosi in partitionare
// - poz: pozitia in solutie de unde incepem partitionarea
void genpart( int n, int max, int poz ) {
  int i;

  if ( n == 0 ) { // am partitionat tot numarul, afisam partitia
    for ( i = 0; i < poz; i++ ) {         // pentru fiecare numar din solutie
      if ( digits[sol[i]][0] )            // daca avem cifra zecilor
        fputc( digits[sol[i]][0], fout ); // o afisam
      fputc( digits[sol[i]][1], fout );   // afisam cifra unitatilor
      fputc( ' ', fout );                 // si un spatiu separator
    }
    fputc( '\n', fout );                  // final de partitie
  } else {
    // afisam mai intii partiile ce incep cu termenul max (invers lexicografic)
    // plasam cel mai mare termen, max, apoi reapelam pentru poz + 1
    sol[poz] = max;
    // max este cel mult n, deci dupa ce efectuam scaderea n - max
    // trebuie sa avem grija ce parametru trimitem ca termen maxim
    genpart( n - max, max < n - max ? max : n - max, poz + 1 );

    // apoi afisam partitiile care nu contin termenul max
    // ce vor fi mai mici lexicografic si pornesc tot de la pozitia poz
    if ( max > 1 )
      genpart( n, max - 1, poz );
  }
}

int main() {
  int n;

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

  initDigits( n );
  
  fout = fopen( "partitii.out", "w" );
  genpart( n, n, 0 );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

Timpul este dominat de output. Deși generarea partițiilor este O(număr partiții) (nu este chiar banal de demonstrat), afișarea va fi mai mare.

  • Timp O(N·L), unde N este numărul de partiții și L lungimea medie a unei partiții.
  • Memorie O(N)

Partprim

Problema partprim este o problemă clasică. Ea cere să se calculeze numărul de partiții ale unui număr în sumă de numere prime.

Soluție

Problema este similară cu plata unei sume cu trei monede prezentată la lecție și cu problema partiții. În loc de trei tipuri de monede avem P tipuri, numerele prime între 1 și N. Vom număra partițiile folosind o formula de recurență similară.

Ce trebuia să ne dăm seama este faptul că avem aceeași problemă ca și în calculul recursiv al șirului lui Fibonacci: numărul de apeluri crește exponențial cu N. De aceea soluția recursivă trebuie să folosească memoizare pentru a nu recalcula elemente. Pentru aceasta avem nevoie de o matrice de N×P elemente (P este numărul de numere prime mai mici sau egale cu N).

Odată ce decidem că vom folosi o tabelă de memoizare observăm că există și posibilitatea unei soluții iterative.

Iată o soluție posibilă recursivă (73 linii din care 47 linii cod efectiv):

#include <stdio.h>

#define MAXN 1280
#define MAXNP 207

long long memo[MAXN + 1][MAXNP];
char ciur[MAXN + 1];
int prime[MAXNP];

// Calculeaza numerele prime mai mici sau egale cu n in vectorul prime[]
// Returneaza numarul de numere prime
// - n: numărul pina la care dorim calculul numerelor prime
// - return: numarul de numere prime pina la n, precum si vectorul prime[]
int eratostene( int n ) {
  int p, d;
  
  for ( p = 2; p * p <= n; p++ )
    if ( ciur[p] == 0 )
      for ( d = p * p; d <= n; d += p )
        ciur[d] = 1;

  // colectam numerele prime in vectorul prime[] cu nprime elemente
  d = 0;
  for ( p = 2; p <= n; p++ )
    if ( ciur[p] == 0 )
      prime[d++] = p;

  return d;
}

// Calculeaza numarul de partitii de numere prime ale numarului n
// Partitiile sint formate cu primele np numere prime
// - n: numarul de partitionat
// - np: putem folosi primele np numere prime in partitionare
// - return: numarul de partitii
long long npart( int n, int np ) {
  int i, rest;

  if ( !memo[n][np - 1] ) { // daca nu e calculat
    // mai intii numaram partitiile care contin al np-lea numar prim
    rest = n - prime[np - 1];             // rest de partitionat
    if ( rest == 0 )                      // am terminat partitionarea?
      memo[n][np - 1] = 1;                // o contorizam
    else if ( rest > 1 ) {                // nu putem partitiona numarul 1
      i = np;
      while ( prime[i - 1] > rest )       // cautam noul prim maxim
        i--;
      memo[n][np - 1] = npart( rest, i ); // numaram partitiile mai mici
    }
    // la final numaram partitiile formate cu primele np - 1 numere prime
    if ( np > 1 ) 
      memo[n][np - 1] += npart( n, np - 1 );
  }

  return memo[n][np - 1];
}

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

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

  nprime = eratostene( n );
  
  fout = fopen( "partprim.out", "w" );
  fprintf( fout, "%lld\n", npart( n, nprime ) );
  fclose( fout );

  return 0;
}

Iată o soluție posibilă iterativă (64 linii din care 45 linii cod efectiv):

#include <stdio.h>

#define MAXN 1280
#define MAXNP 207

long long memo[MAXN + 1][MAXNP];
char ciur[MAXN + 1];
int prime[MAXNP];

// Calculeaza numerele prime mai mici sau egale cu n in vectorul prime[]
// Returneaza numarul de numere prime
// - n: numărul pina la care dorim calculul numerelor prime
// - return: numarul de numere prime pina la n, precum si vectorul prime[]
int eratostene( int n ) {
  int p, d;
  
  for ( p = 2; p * p <= n; p++ )
    if ( ciur[p] == 0 )
      for ( d = p * p; d <= n; d += p )
        ciur[d] = 1;

  // colectam numerele prime in vectorul prime[] cu nprime elemente
  d = 0;
  for ( p = 2; p <= n; p++ )
    if ( ciur[p] == 0 )
      prime[d++] = p;

  return d;
}

int main() {
  FILE *fin, *fout;
  int n, nprime, rest, i, k, np;

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

  nprime = eratostene( n );

  // completam matricea memo[n][nprime]
  for ( k = 2; k <= n; k++ ) { // pentru fiecare linie a matricei
    memo[k][0] = 1 - k % 2;    // poate fi scris ca suma de 2?
    for ( np = 2; np <= nprime; np++ ) { // pentru fiecare coloana
      memo[k][np - 1] = memo[k][np - 2]; // partitii cu primele np-1 numere
      // numaram partitiile care contin al np-lea numar prim
      rest = k - prime[np - 1];               // rest de partitionat
      if ( rest == 0 )                        // am terminat partitionarea?
        memo[k][np - 1]++;                    // o contorizam
      else if ( rest > 1 ) {                  // nu putem partitiona numarul 1
        i = np;
        while ( prime[i - 1] > rest )         // cautam noul prim maxim
          i--;
        memo[k][np - 1] += memo[rest][i - 1]; // numaram partitiile mai mici
      }
    }
  }
  
  fout = fopen( "partprim.out", "w" );
  fprintf( fout, "%lld\n", memo[n][nprime-1] );
  fclose( fout );

  return 0;
}

Ce complexitate au aceaste soluții?

Timpul nu este evident. Să analizăm programul iterativ, deoarece pare ceva mai ușor de analizat. La prima vedere avem trei bucle imbricate ce se repetă de N, P, respectiv P ori. Pare că avem o complexitate O(N·P2). În realitate ea nu este așa mare, vom vedea astfel de exemple cînd vom vorbi despre analiză amortizată. Cazul cel mai rău se întîmplă doar pentru O(N) elemente, deci complexitatea este, de fapt, O(N·P).

Chiar și fără a ști analiză amortizată, deoarece numerele prime sînt ordonate în vector, putem înlocui căutarea liniară a următorului număr prim cu o căutare binară, caz în care obținem o soluție O(N·P log P).

  • Timp O(N·P)
  • Memorie O(N·P)

Simplificări

La curs am analizat aceste soluții și unii dintre voi mi-au sugerat simplificări ale acestor soluții. Mulțumiri în special lui Tudor Voicu și Armin Asgari, care (împreună?) au găsit o soluție elegantă și simplă.

Putem simplifica foarte mult funcția recursivă de calcul al partițiilor dacă:

  • Apelăm funcția (și memoizăm) pentru toate combinațiile de n și np, fără a pune condiția ca prim[np] să fie mai mic sau egal cu n. În acest caz nu vom avea partiții care să conțină termenul prim[np].
  • Memoizăm (calculăm) 'de mînă' apelul cu n = 0 și np == 1, respectiv vom atribui înainte de apelul funcției recursive memo[0][0] = 1.

În acest caz funcția se transformă astfel:

Funcție originală Funcție simplificată
// Calculeaza numarul de partitii de numere prime ale numarului n
// Partitiile sint formate cu primele np numere prime
// - n: numarul de partitionat
// - np: putem folosi primele np numere prime in partitionare
// - return: numarul de partitii
long long npart( int n, int np ) {
  int i, rest;

  if ( !memo[n][np - 1] ) { // daca nu e calculat
    // mai intii numaram partitiile care contin al np-lea numar prim
    rest = n - prime[np - 1];             // rest de partitionat
    if ( rest == 0 )                      // am terminat partitionarea?
      memo[n][np - 1] = 1;                // o contorizam
    else if ( rest > 1 ) {                // nu putem partitiona numarul 1
      i = np;
      while ( prime[i - 1] > rest )       // cautam noul prim maxim
        i--;
      memo[n][np - 1] = npart( rest, i ); // numaram partitiile mai mici
    }
    // la final numaram partitiile formate cu primele np - 1 numere prime
    if ( np > 1 ) 
      memo[n][np - 1] += npart( n, np - 1 );
  }

  return memo[n][np - 1];
}

Ea va fi apelată astfel:

npart( n, nprime );
// Calculeaza numarul de partitii de numere prime ale numarului n
// Partitiile sint formate cu primele np numere prime
// - n: numarul de partitionat
// - np: putem folosi primele np numere prime in partitionare
// - return: numarul de partitii
long long npart( int n, int np ) {
  if ( !memo[n][np - 1] ) { // daca nu e calculat
    if ( np > 1 ) // numaram partitiile formate cu primele np - 1 numere prime
      memo[n][np - 1] = npart( n, np - 1 );
    if ( n - prime[np - 1] >= 0 )            // putem folosi al np-lea nr prim?
      memo[n][np - 1] += npart( n - prime[np - 1], np ); // folosim si reapelam
  }

  return memo[n][np - 1];
}

Ea va fi apelată astfel:

  memo[0][0] = 1; // santinela
  nprime = eratostene( n );

Prin analogie, această simplificare se aplică și variantei iterative, astfel:

Iterații originale Iterații simplificate
  // completam matricea memo[n][nprime]
  for ( k = 2; k <= n; k++ ) { // pentru fiecare linie a matricei
    memo[k][0] = 1 - k % 2;    // poate fi scris ca suma de 2?
    for ( np = 2; np <= nprime; np++ ) { // pentru fiecare coloana
      memo[k][np - 1] = memo[k][np - 2]; // partitii cu primele np-1 numere
      // numaram partitiile care contin al np-lea numar prim
      rest = k - prime[np - 1];               // rest de partitionat
      if ( rest == 0 )                        // am terminat partitionarea?
        memo[k][np - 1]++;                    // o contorizam
      else if ( rest > 1 ) {                  // nu putem partitiona numarul 1
        i = np;
        while ( prime[i - 1] > rest )         // cautam noul prim maxim
          i--;
        memo[k][np - 1] += memo[rest][i - 1]; // numaram partitiile mai mici
      }
    }
  }
  // completam matricea memo[n][nprime]
  memo[0][0] = 1; // santinela
  for ( k = 0; k <= n; k++ ) { // pentru fiecare linie a matricei
    // numaram partitiile care contin al np-lea numar prim
    if ( k - prime[0] >= 0 )
      memo[k][0] += memo[k - prime[0]][0];
    for ( np = 2; np <= nprime; np++ ) { // pentru fiecare coloana
      memo[k][np - 1] = memo[k][np - 2]; // partitii cu primele np-1 numere
      // numaram partitiile care contin al np-lea numar prim
      if ( k - prime[np - 1] >= 0 )
        memo[k][np - 1] += memo[k - prime[np - 1]][np - 1];
    }
  }

Dacă ne uităm cu atenție la varianta iterativă simplificată observăm că:

  • Un element al matricei se calculează pe baza elementului din-naintea sa pe linie și un element aflat deasupra sa pe coloană.
  • Acest lucru ne dă ideea să încercăm o completare pe coloane a acestei matrice.
  • În acest caz putem să memorăm doar o coloană a matricei, cea care se calculează în prezent.
  • Cazul de recurență în care numărul prim nu este folosit este cel în care adunăm la elementul curent cel aflat înaintea sa pe linie.
  • Acest caz nu necesită un calcul explicit dacă memorăm doar o coloană. Ea va fi implicit "copiată" cînd trecem la coloana următoare.
  • Testul k - prime[np - 1] >= 0 poate fi eliminat pornind bucla lui k chiar de la prime[np - 1].
  • Deoarece bucla exterioară va parcurge numerele prime o singură dată nu se mai justifică extragerea numerelor prime într-un vector separat. Vom face parcurgerea întregului ciur. Astfel, în loc de prime[np - 1] vom avea direct un număr prim p preluat din ciur.

Codul rezultat este mult mai simplu:

Iterații simplificate Iterații simplificate mai mult
  // completam matricea memo[n][nprime]
  memo[0][0] = 1; // santinela
  for ( k = 0; k <= n; k++ ) { // pentru fiecare linie a matricei
    // numaram partitiile care contin al np-lea numar prim
    if ( k - prime[0] >= 0 )
      memo[k][0] += memo[k - prime[0]][0];
    for ( np = 2; np <= nprime; np++ ) { // pentru fiecare coloana
      memo[k][np - 1] = memo[k][np - 2]; // partitii cu primele np-1 numere
      // numaram partitiile care contin al np-lea numar prim
      if ( k - prime[np - 1] >= 0 )
        memo[k][np - 1] += memo[k - prime[np - 1]][np - 1];
    }
  }
  // completam matricea memo[n][nprime]
  // in fapt vom memora doar cite o coloana din ea
  memo[0] = 1; // santinela
  for ( p = 2; p <= n; p++ )
    if ( ciur[p] == 0 )          // pentru fiecare numar prim p (coloana)
      for ( k = p; k <= n; k++ ) // pentru fiecare linie a matricei
        memo[k] += memo[k - p];  // partitiile care contin numarul prim p

Putem face un ultim pas în simplificare, anume să observăm că putem combina calculul matricei de memoizare cu calculul ciurului lui Eratostene. Pe măsură ce descoperim numere prime în ciur le folosim pentru a mai calcula o coloană din matricea originală.

Iată o soluție iterativă finală (32 linii din care 23 de linii de cod efectiv):

#include <stdio.h>

#define MAXN 1280

long long memo[MAXN + 1];
char ciur[MAXN + 1];

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

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

  // calculam ciurul si in acelasi timp completam matricea memo[n][nprime]
  // in fapt vom memora doar cite o coloana din ea
  memo[0] = 1; // santinela
  for ( p = 2; p <= n; p++ )
    if ( ciur[p] == 0 ) { // pentru fiecare numar prim (original coloane)
      for ( k = p * p; k <= n; k += p )
        ciur[k] = 1;
      for ( k = p; k <= n; k++ ) // pentru fiecare linie a matricei
        memo[k] += memo[k - p];  // partitiile care contin numarul prim p
    }

  fout = fopen( "partprim.out", "w" );
  fprintf( fout, "%lld\n", memo[n] );
  fclose( fout );

  return 0;
}

Rezolvări aici [2]

Notă: filmul lecției este incomplet din cauza unei defecțiuni tehnice.

Temă

Tema 9 clasa a 7a