[C++, programare dinamică] Numărul de numere de N cifre cu produsul cifrelor 0

Dându-se N, scrieți un program care determină câte numere de N cifre cu produsul cifrelor 0 există.

·        N este numărul de cifre ale numerelor cerute

Fiindcă sunt în discuție numere în baza 10, rezultatul este întotdeauna 0 dacă produsul este mai mare decât 9N, 9 fiind cea mai mare cifră în baza 10. Pentru algoritmul naiv, folosit pentru verificare, este important că dacă un număr conține cel puțin o cifră 0 atunci produsul cifrelor sale este 0 și numărul de numere căutat crește cu 1.

Stabilirea formulei de recurență

Dacă notăm:

·        A[x] = câte numere de x cifre au produsul cifrelor 0, și

·        B[i] = câte numere de i cifre există

Cazurile de bază ale recurenței sunt:

·        A[0] = 0 (nu există nr. de 0 cifre)

·        A[1] = 1 (cazul numărului 0)

·        Mai rămâne cazul general A[x] = ?, tratat în continuare.

Pentru ca un număr să aibă x cifre, trebuie ca prima cifră să fie diferită de 0, deci pentru prima cifră există 9 posibilități (cazurile celor 10 cifre din baza 10, mai rămân 9 cifre dacă 0 se exclude). Din acest paragraf rezultă următoarele valori pentru B:

B[1] = nr. de nr. de 1 cifră posibile = 10,

               B[2] = 9 * 10 nr. de 2 cifre posibile,

               B[3] = 9 * 10 * 10 numere de 3 cifre posibile

etc.

Urmează exprimări ale A[x].
A[2] se calculează manual mai jos și rezultă din calcule valoarea 9 * 1.
Prima cifră nu poate fi 0 deci pentru prima cifră sunt în total 9 posibilități. A doua cifră poate și reprezintă o singură posibilitate. Cazurile sunt: 10, 20, ….., 90.
A[3] = 9 * 1 * 9 (nr. de 3 cifre cu a doua cifră 0 = 9 * câte numere de 1 cifră există, minus 1, adică fără 0)
               + 9 * 9 * 1 (nr. de 3 cifre cu a treia cifră 0 = 9 * câte numere de 1 cifră există, minus 1, adică fără 0))
+ 9 * 1 * 1 (nr. de 3 cifre cu a doua și a treia cifră 0)
= nr. de numere de 3 cifre cu cel puțin o cifră 0

Intuitiv dar incorect:
= 9 * (B[1] – 1) + 9 * (B[1] – 1) + A[2] (ce e bold = 9 sau A[2], se aduna la fiecare A[x] pe lângă A[x – 1] și altele, la sfârșitul sumei)
Din formula generala gasita mai tarziu, rezulta aceasta relatie pt A[3]:
                                             = 9 * A[2] + 9 * A[2] + 9
Apoi:
               B[4] = 9 * 10 * 10 * 10,
               Dintre care A[4] = 9 * 1 * 9 * 9 + 9 * 9 * 1 * 9 + 9 * 9 * 9 * 1 +
                                             9 * 1 * 1 * 9 + 9 * 9 * 1 * 1 + 9 * 1 * 9 * 1 +
                                             9 * 1 * 1 * 1 // o notație mai scurtă: 9199, 9919, 9991, 9119, 9911, 9191, 9111, ce e cu bold face împreună valoarea (9 * A[3]).
                                             = 9 * A[3][0] + 9*1*9*9 + 9*1*1*9 + 9*1*9*1 + 9 ( 9*1*1*1 ) =
A[4] = 9*(991+919+911) + 9*(99+91) + 9*(19) + 9*(11)
O exprimare incompletă dar care aduce înțelesuri noi:
                              A[4] = 9 * A[3] + 9 * A[3] / 9 (nr. de nr. de 3 cifre cu a doua cifră 0)
9 * A[3]: Cifra 1: 9 posibilități, cifra 2: 9 posibilități
9 * A[3] / 9: Cifra 1: 9 posibilități, cifra 2: 1 posibilitate (0),
    și prin împ. la 9 => Cifra 1: 1 posibilitate, cifra 2: 1 posibilitate,
    și prin înm. cu 9 se adaugă o cifră în față.
Împreună, cei doi termeni din expresia lui A[4] de mai sus însumează pt. a doua cifră 10 posibilități, câte sunt în general, dar în expresie, al doilea termen se împarte la 9 pentru ca posibilitățile din cifra 1 să devină 9/9 (9 împărțit din 9) din 9 adică 1. Astfel se tratează cazul când prima cifră e oricare poate fi în general (9 posibilități) și când prima cifră e oricare cifră din baza 10 (adică 10 posibilități).
Alte exprimări:
               = 9 * A[3] + 9 * (câte nr. de 2 cifre cu cifra unităților nenulă sunt) + 9 * (B[1] – 1) + 9
               = 9 * A[3] + 9 * (B[2] – 1) + 9 * (B[1] – 1) + 9.
Dintre care A[5] = 9 * A[4] + 9 * A[3] + 9 * A[2] + 9 * A[1] (am scos semnele de + și *, fiecare termen este sumă de produse de 9 și 1)
Încercare de a scrie formula generală: A[x] = A[x-1] + (A[x-2] – 1) + (A[x-3] – 1) + … + A[1] ;
Formula generală cu termeni crescători: A[x] = A[1] + … + (A[x-3] – 1) + (A[x-2] – 1) + A[x-1];
Verificare:
A[2] = 9 * A[1] + 0
A[3] = A[1] + A[2] = 9 * A[2] + 9 // (1) + (9*1)
A[4] = 9 * A[3] + 9
+ 9 * (nr. de 3 cifre cu cifra zecilor 0) + (nr. de 3 cifre cu cifra unităților 0) +
                                            
Având în vedere încercările de mai sus, mi-am dat seama este bine în produse să nu iau cele 10 posibilități de cifre direct, că e nevoie să iau 9 separat de unu-le care repr. cifra 0.
Exerciții:
A[2] = 91 = 9*A[1]
A[3] = 9*(91) + 9*(19) + 9*(11)
                              = 9*A[2] + 9*A[1] + 9
A[4] = 9*(991+919+911) + 9*(99+91) + 9*(19) + 9*(11)
                              = 9*A[3] + 9*(99 + A[2]) + 9*A[1] + 9
A[5] = 9*A[4][0] + 9*(999+991+919+911) + 9*(99+91) + 9*(9+1)
                              = 9*A[4] + 9*(999+A[3]) + 9*(99 + A[2]) + 9*A[1] + 9
Penultima încercare de a scrie o formulă de recurență corectă:
A[x] = 9 * A[x-1] + 9 * (_(x-2)cifreDe9_ + A[x-2])  +
               9 * (_(x-3)cifreDe9_ + A[x-3]) + … + 9*A[2] + 9
Exerciții:
A[1] = 1
A[2] = 9 * A[1]
A[3] = 9 * A[2] + 9 * A[2] + 9
               = 9*9 + 9 * 9 + 9= 81 +81+9
A[4] = 9 * A[3] + 9 * (99 + A[2]) + 9 * A[2] + 9
               = 9 * (A[3] + 9*9 + A[2] + A[2] + 1) =
               = 9 * (171 + 81 + 9 + 9 + 1) = 9(271) =  2439
A[5]= 9 * A[4] + 9 * (999 + A[3]) + 9 * (99 * A[2]) + 9 * A[2] + 9
               = 9 *(A[4] + 9*9*9 + A[3] + 9 * 9 + A[2] + A[2] + 1) =
               = 9 * ()
Formula finală:
A[x] = 9 * (A[x-1] + _(x-2)cifreDe9_ + A[x-2]  +
               _(x-3)cifreDe9_ + A[x-3] + … + A[2] + 1)

Codul sursă

#include
#include
#include
using namespace std;

/// Prin algoritm naiv, intoarce nr. de numere de
/// N cifre cu produsul cifrelor 0. pow10 si pow9N sunt
/// valori precalculate pentru optimizarea for-ului din
/// functia main().
long long int naiv(int N,
 long long int pow10[18],
 long long int pow9N)
{
 if (N == 0) return 0;

 long long int j = 0, prod, ii, i, start;
 if (N == 1) start = 0;
 else start = pow10[N – 1];

 for (i = start; i < pow10[N]; ++i)
 {
  if (i == 0)
  {
   ++j;
  }
  else
  {
   ii = i;
   while (ii)
   {
    if (ii % 10 == 0)
    {
     ++j;
     break;
    }
    ii /= 10;
   }
  }
 }

 return j;
}


// cate numere de N cifre se pot face sa aiba produsul cifrelor 0
long long int pd(long long int N, vector &A)
{
 A[0] = 0;
 A[1] = 1;
 A[2] = 9;
 for (long long int i = 3; i <= N; ++i)
 {
  A[i] = 0;
  for (long long int j = 1; j <= i; ++j)
  {
   if (j == 1)
    A[i]++;
   else if (j == 2)
    A[i] += A[2];
   else if (j == 3)
   {
    if (i > 3)
    {
     A[i] += A[j – 1] +
      pow(9, j – 1);
    }
    else
    {
     A[i] += A[j – 1];
    }
   }
   else if (j >= 4)
   {
    if (j == i)
    {
     A[i] += A[j – 1];
    }
    else
    {
     A[i] += A[j – 1] +
      pow(9, j – 1);
    }
   }
  }
  A[i] *= 9;
 }

 return A[N];
}


int main()
{
 int N;

 cout << "Introduceti numarul de cifre: " << endl;
 cin >> N;

 vector A(N + 1);
 // contine puteri ale lui 10 pt. calcul mai rapid in algoritmul naiv
 long long int pow10[] = {
  1,
  10,
  100,
  1000,
  10000,
  100000,
  1000000,
  10000000,
  100000000,
  1000000000,
  10000000000,
  100000000000,
  1000000000000,
  10000000000000,
  100000000000000,
  1000000000000000,
  10000000000000000,
  100000000000000000,
  1000000000000000000,
  10000000000000000000
 };

 long long int pow9N = pow(9, N);
 ofstream out(„Text.txt”);
 long long int rezultat = pd(N, A);
 // compara rezultatele alg. naiv cu cel de pd.
 for (int i = 0; i <= N; ++i)
 {
  long long int rn = naiv(i, pow10, pow9N);
  out << "A[" << i << "] = " <<
   A[i] << " (pd)\t\t|\t\t" << rn <<
   ” (naiv)\t\t|\t\t” <<
   (rn == A[i] ? „CORECT” : „___GRESIT”) << endl;
 }
 out.close();

 cout << "Rezultatele au fost afisate in fisier." << endl;
 return 0;
}

Capturi de ecran

Ieșire

O parte din ce afiseaza programul in fisier:
A[0] = 0 (pd)  |  0 (naiv)  |  CORECT
A[1] = 1 (pd)  |  1 (naiv)  |  CORECT
A[2] = 9 (pd)  |  9 (naiv)  |  CORECT
A[3] = 171 (pd)  |  171 (naiv)  |  CORECT
A[4] = 2439 (pd)  |  2439 (naiv)  |  CORECT
A[5] = 30951 (pd)  |  30951 (naiv)  |  CORECT
A[6] = 368559 (pd)  |  368559 (naiv)  |  CORECT
A[7] = 4217031 (pd)  |  4217031 (naiv)  |  CORECT
A[8] = 46953279 (pd)  |  46953279 (naiv)  |  CORECT
A[9] = 512579511 (pd)  |  512579511 (naiv)  |  CORECT
A[10] = 5513215599 (pd)  |  5513215599 (naiv)  |  CORECT

Lasă un răspuns

Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare /  Schimbă )

Fotografie Google

Comentezi folosind contul tău Google. Dezautentificare /  Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare /  Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare /  Schimbă )

Conectare la %s

%d blogeri au apreciat: