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

Enunțul problemei:

Dându-se N și K, scrieți un program care determină câte numere de N cifre cu suma cifrelor K există. Analog pentru produs.

În acest articol rezolvăm varianta problemei care ține cont de suma cifrelor, nu de produs. În primul rând remarcăm că rezultatul este întotdeauna 0 dacă K > 9 * N.

După stabilirea acestor formule de recurență, se observă că matricea-rezultat depinde doar de 2 numere, N și K, crescând de sus în jos și de la stânga la dreapta, deci dacă dorim să facem un program care răspunde la mai multe întrebări de felul celei din enunț (Câte numere de N cifre cu suma cifrelor K există?), e suficientă o singură calculare a matricei-rezultat, cu dimensiunile N și K (în acest caz fiind indicii maximi necesari). Răspunsul la o întrebare de forma celei din enunț va fi A[N][K] valoare care se obține în timp O(1).

Cazurile de bază ale recurenței:

1.       A[1][y] = 1, dacă y <= 9; 0, dacă y >= 10;

2.       A[0][y] = 0;

3.       A[x][1] = 1;

4.       A[x][0] = 0, dacă x == 0 || x >= 2; 1, dacă x == 1.

Astfel se ajunge la cazul 3:

O întrebare care se poate pune este: Câte numere de 2 cifre cu suma 1 există? Intuitiv, numerele cu suma cifrelor 1 sunt: 1, 10, 100 etc. adică puteri ale lui 10. Pentru fiecare număr de cifre există o singură putere a lui 10 cu suma cifrelor 1. Rezultă că A[2][1] = 1, la fel pentru oricare A[x][1].

Intersecția cazurilor de bază ale recurenței:

·         A[0][0] = 0 sau 0;

·         A[1][1] = 1 sau 1;

·         A[0][1] = 1 sau 0 (corect: 0);

·         A[1][0] = 1 sau 1.

Începem să calculăm manual matricea-rezultat pornind de la relațiile de mai sus pentru N = 4, K = 4. Notăm matricea rezultat cu A.

A	Suma cifrelor:
Nr. de cifre:	x \ y	0	1	2	3	4
	0	0	0	0	0	0
	1	1	1	1	1	1
	2	0	1
	3	0	1
	4	0	1

Celulele necompletate pot fi exercițiu pentru cititor.

Apoi se ia un exemplu de valoare necalculată din tabel care nu este calculată doar cu relațiile de bază ale recurenței: A[2][y], mai exact valoarea necalculată A[2][2] = nr. de nr.-e de 2 cifre cu suma cifrelor 2.

Se observă ușor că dacă luăm cifra dintr-un număr de 2 cifre care e în partea lui extremă stângă, obținem o valoare de care depinde A[2][y].

Astfel:

A[2][2] = A[1][1] + A[1][0] = 1 + 1 = 2 (numerele sunt 11, 20).

Se observă că A[3][4] se calculează în funcție de A[2][3], A[2][2], A[2][1], A[2][0].

Câte numere de 2 cifre cu suma cifrelor 3 există? (calcularea lui A[2][3])

Se gândește matematic. Numerele de 2 cifre sunt în total 90:

10 11 12 13 .. 19

20 21 22 23 .. 29

30 31 32 33 .. 39

40 41 42 43 .. 49

..

90 91 92 93 .. 99

Dintre ele, 3 au suma cifrelor 3: 12, 21, 30.

Câte numere de 3 cifre cu suma cifrelor 4 există? (calcularea lui A[3][4])

100 101 102.. 110 111 112.. 120 121 122.. .. 190 191 192.. 199

                – se știe că luând prima cifră din stânga a numerelor din acest rând rămân A[2][4 - 1] = A[2][3], + 1 (extras din 03) = 4 numere

200 201 202.. 210 211 212.. 220 221 222.. .. 290 291 292.. 299

                – asemănător A[2][4-2] = A[2][2] + 1 (extras din 02, 20, 11) = 3 numere

300 301 302.. 310 311 312.. 320 321 322.. .. 390 391 392.. 399

                – A[2][4-3] = A[2][1], + 1 (din 01, 10) = 2 numere

400 401 402.. 410 411 412.. 420 421 422.. .. 490 491 492.. 499

                – A[2][4-4] = A[2][0] + 1 (acest 1 este cazul lui 400 în care 00 este tratat ca un număr de 2 cifre) = 1 număr

500 501 502.. 510 511 512.. 520 521 522.. .. 590 591 592.. 599

600 601 602.. 610 611 612.. 620 621 622.. .. 690 691 692.. 699

700 701 702.. 710 711 712.. 720 721 722.. .. 790 791 792.. 799

800 801 802.. 810 811 812.. 820 821 822.. .. 890 891 892.. 899

900 901 902.. 910 911 912.. 920 921 922.. .. 990 991 992.. 999

Din acestea cele numărate sunt următoarele 10: 112, 121, 103, 130, 202, 211, 220, 301, 310, 400.

A[3][4] = A[2][3] + A[1][3] + A[0][3] + A[2][2] + A[1][2] + A[0][2] + A[2][1] + A[1][1] + A[0][1] + A[2][0] + A[1][0] + A[0][0] = 10.

Câte numere de 2 cifre cu suma cifrelor 4 există? (calcularea lui A[2][4])

13, 22, 31, 40 – în total 4.

A[2][4] = A[1][3] + A[1][2] + A[1][1] + A[1][0] = 1+1+1+1 = 4. Aici nu se mai adaugă un 1 a final deoarece 1 se adaugă doar când numărul de 0-uri este mai mare de 1 (altfel, se consideră numărul 0 suficient).

Câte numere de 4 cifre cu suma cifrelor 5 există? (calcularea lui A[4][5])

1000 1001 1002.. 1010 1011 1012.. 1200 1201 1202.. .. 1900 1901 1902.. 1999

                – A[3][5-1=4] + ..

2000 2001 2002.. 2010 2011 2012.. 2200 2201 2202.. .. 2900 2901 2902.. 2999

                – A[3][5-2=3] + ..

3000 3001 3002.. 3010 3011 3012.. 3200 3201 3202.. .. 3900 3901 3902.. 3999

                – A[3][5-3=2] + .. = 3 + 2 + 1 (002, 011, 101, 110, 020, 200) ¬ se adună aici răspunsul la întrebările: câte numere de 3-1 cifre (3 cifre, prima 0) au suma cifrelor 2? + câte numere de 3-2 cifre au suma cifrelor 2? + … + câte numere de 0 cifre au suma cifrelor 2? = A[2][2] + A[1][2] + [eventual puncte de suspensie dacă altul este primul indice în loc de 2] + A[0][2].

4000 4001 4002.. 4010 4011 4012.. 4200 4201 4202.. .. 4900 4901 4902.. 4999

                – A[3][5-4=1] + .. = 3 (001, 010, 100)

5000 5001 5002.. 5010 5011 5012.. 5200 5201 5202.. .. 5900 5901 5902.. 5999

                – A[3][5-5=0] + .. = 1 (000)

6000 6001 6002.. 6010 6011 6012.. 6200 6201 6202.. .. 6900 6901 6902.. 6999

7000 7001 7002.. 7010 7011 7012.. 7200 7201 7202.. .. 7900 7901 7902.. 7999

8000 8001 8002.. 8010 8011 8012.. 8200 8201 8202.. .. 8900 8901 8902.. 8999

9000 9001 9002.. 9010 9011 9012.. 9200 9201 9202.. .. 9900 9901 9902.. 9999

În rândurile de mai sus, unde am scris 5-1, 5-2 … 5-3, prin numerele în ordine crescătoare de la 1 la 5 în aceste expresii m-am referit la prima cifră a numerelor de pe respectivul rând. Numerele subliniate au mai puține cifre decât cum sunt prezentate (cu zerouri în față), dar se ține cont de ele.

Răspunsul este A[4][5] = 35.

Acum putem scrie cazuri particulare ale formulei finale:

O încercare de a scrie formula generală:

Și iată formula generală:

Câte numere de 4 cifre cu suma cifrelor 36 există? (calcularea lui A[4][36] = 1)

1000 1001 1002.. 1010 1011 1012.. 1200 1201 1202.. .. 1900 1901 1902.. 1999

                – A[3][36-1] = A[3][35] (+ ..)

2000 2001 2002.. 2010 2011 2012.. 2200 2201 2202.. .. 2900 2901 2902.. 2999

3000 3001 3002.. 3010 3011 3012.. 3200 3201 3202.. .. 3900 3901 3902.. 3999

4000 4001 4002.. 4010 4011 4012.. 4200 4201 4202.. .. 4900 4901 4902.. 4999

5000 5001 5002.. 5010 5011 5012.. 5200 5201 5202.. .. 5900 5901 5902.. 5999

6000 6001 6002.. 6010 6011 6012.. 6200 6201 6202.. .. 6900 6901 6902.. 6999

7000 7001 7002.. 7010 7011 7012.. 7200 7201 7202.. .. 7900 7901 7902.. 7999

8000 8001 8002.. 8010 8011 8012.. 8200 8201 8202.. .. 8900 8901 8902.. 8999

9000 9001 9002.. 9010 9011 9012.. 9200 9201 9202.. .. 9900 9901 9902.. 9999

                – A[3][36 – prima cifră] = A[3][36-9] = A[3][27] (+ ..)

În loc de punctele de suspensie se folosește restul formulei generale.

Câte numere de 2 cifre cu suma cifrelor 10 există? (calcularea lui A[2][10] = 9)

Programul dădea greșit rezultatul 10 în loc de 9, se vede ultimul rând: „A[1][10 – 10] = A[1][0] = 1 (0), acest caz nu se include. În total sunt 90 de nr. naturale cu 2 cifre:

10 11 12 13 .. 19 – A[1][10 – 1] = 1 (numărul este 9) + A[1 – 1][10 – 1]( = 0)

20 21 22 23 .. 29 – A[1][10 – 2] = 1 (8)

30 31 32 33 .. 39 – A[1][10 – 3] = 1 (7)

40 41 42 43 .. 49 – A[1][10 – 4] = 1 (6)

..

90 91 92 93 .. 99 – A[1][10 – 9] = 1 (1)

                               – A[1][10 – 10] = A[1][0] = 1 (0), acest caz nu se include

Cele 9 numere sunt:

                19 28 37 46 55

                64 73 82 91

Codul sursă de mai jos rezolvă problema pt. numere de până la 9 cifre inclusiv, și are funcția test care compară rezultatele algoritmului naiv cu rezultatele algoritmului de programare dinamica pentru date de intrare identice.

Codul sursă ca imagini cu colorare de sintaxă:

 

Mai jos se poate da Copy-Paste (e același cod):

1. #include <fstream>  
2. #include <iostream>  
3. using namespace std;  
4.   
5. const int maxn = 9;  
6. const int maxk = maxn * 9;  
7.   
8. // intoarce nr. de numere gasite  
9. int naiv(int N, int K, int pow10[10])  
10. {  
11.     if (N == 0 || K > 9 * N) return 0;  
12.     if (K == 0) return N == 0 || N >= 2 ? 0 : 1;  
13.       
14.     int j = 0, sum, ii, i;  
15.     for (i = pow10[N - 1]; i < pow10[N]; ++i)  
16.     {  
17.         sum = 0;  
18.         ii = i;  
19.         while (ii)  
20.         {  
21.             sum += ii % 10;  
22.             ii /= 10;  
23.         }  
24.         if (sum == K)  
25.         {  
26.             ++j;  
27.         }  
28.     }  
29.   
30.     return j;  
31. }  
32.   
33. // calculeaza matricea-rezultat prin programare dinamica  
34. void pregatire(int N, int K, int A[maxn + 1][maxk + 1])  
35. {  
36.     for (int i = 0; i <= N; ++i)  
37.     {  
38.         A[i][1] = 1;  
39.         A[i][0] = i == 0 || i >= 2 ? 0 : 1;  
40.     }  
41.     for (int j = 0; j <= K; ++j)  
42.     {  
43.         A[1][j] = j <= 9 ? 1 : 0;  
44.         A[0][j] = 0;  
45.     }  
46.     A[0][1] = 0;  
47.   
48.     int j, i, k, l, val;  
49.     for (i = 2; i <= N; ++i)  
50.     {  
51.         for (j = 2; j <= K; ++j)  
52.         {  
53.             val = 0;  
54.   
55.             // j > 9 este ignorat in calcul  
56.   
57.             // pt. fiecare cifra cu care poate incepe  
58.             // un nr. cu 2+ cifre..  
59.             for (k = 1; k <= (j >= 10 ? 9 : j); ++k)  
60.             {  
61.                 for (l = 1; l <= i; ++l)  
62.                 {  
63.                     val += A[i - l][j - k];  
64.                 }  
65.             }  
66.   
67.             A[i][j] = val;  
68.         }  
69.     }  
70. }  
71.   
72. // aceasta functie testeaza pana la numere cu 9 cifre  
73. // (din cauza valorii maxime pe care o poate retine  
74. // un nr. de tip int)  
75. // rezultatul testelor este ca algoritmul de programare dinamica  
76. // ofera intotdeauna raspunsul  
77. // corect (cel oferit si de algoritmul naiv)  
78. void test(ofstream &out)  
79. {  
80.     int A[maxn + 1][maxk + 1];  
81.     pregatire(maxn, maxk, A);  
82.   
83.     int pow10[] = {  
84.         1,  
85.         10,  
86.         100,  
87.         1000,  
88.         10000,  
89.         100000,  
90.         1000000,  
91.         10000000,  
92.         100000000,  
93.         1000000000  
94.     };  
95.     int gresite = 0;  
96.     for (int N = 0; N <= maxn; ++N)  
97.     {  
98.         for (int K = 0; K <= maxk; ++K)  
99.         {  
100.             // rezultat programare dinamica:  
101.             int rezultat_pd = A[N][K];  
102.             // rezultat algoritm naiv:  
103.             int rezultat_naiv = naiv(N, K, pow10);  
104.   
105.             if (rezultat_pd != rezultat_naiv)  
106.             {  
107.                 out << "GRESIT N,K = " << N << ',' << K <<  
108.                     " naiv: " << rezultat_naiv <<  
109.                     " pd: " << rezultat_pd << endl;  
110.                 gresite++;  
111.             }  
112.             else  
113.             {  
114.                 out << "CORECT N,K = " << N << ',' << K <<  
115.                     " pd/naiv: " << rezultat_pd  
116.                     << endl;  
117.             }  
118.         }  
119.     }  
120.   
121.     out << "GRESITE: " << gresite << endl;  
122. }  
123.   
124. int main()  
125. {  
126.     int N, K, A[maxn + 1][maxk + 1];  
127.   
128.     ifstream in("n-cifre-suma-k.in");  
129.     in >> N >> K;  
130.     in.close();  
131.   
132.     pregatire(N, K, A);  
133.   
134.     ofstream out("n-cifre-suma-k.out");  
135.     // afisare matrice-rezultat  
136.     for (int i = 0; i <= N; ++i)  
137.     {  
138.         for (int j = 0; j <= K; ++j)  
139.         {  
140.             out << A[i][j] << ' ';  
141.         }  
142.         out << endl;  
143.     }  
144.     // afisare rezultat  
145.     out << endl << A[N][K] << endl;  
146.     //test(out);  
147.     out.close();  
148.   
149.     return 0;  
150. }