Silviu Bogan: [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 9^N, 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 <iostream>
#include <vector>
#include <fstream>
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<long long int> &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<long long int> 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:

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

Codul sursă

Capturi de ecran

Ieșire

Niciun comentariu:

Trimiteți un comentariu

Totalul afișărilor de pagină

Reclame