[C++, programare dinamică] Suma unor dreptunghiuri ale unei matrice

Enunț:

Scrieți un program care răspunde eficient la mai multe interogări privind suma unor dreptunghiuri ale unei matrice.

Se noteaza matricea data cu A, cu indici pornind de la i = 1 pana la H, cu j = 1 pana la W.

Fie dreptunghiul a cărui sumă o căutăm cu atributele w, h, i (sau y), j (sau x), unde w este lățimea, h este înălțimea, i este rândul din matrice în care începe dreptunghiul înspre dreapta-jos, j fiind coloana din matrice în care începe dreptunghiul înspre dreapta-jos.

Figura 1

Pentru date de intrare:

5 5 3 4 2 3
1  2  3  4  5
6  7  8  9  10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

Exista datele de ieșire:

117

Dreptunghiuri de la  X = 4, Y = 3
B[3][4][1][1] = 14    B[3][4][1][2] = 33    B[3][4][1][3] = 57   
B[3][4][2][1] = 29    B[3][4][2][2] = 68    B[3][4][2][3] = 117   

Se observa că i coboară de la 1 (sus, primul rând) și j merge de la 1 la dreapta (de la stânga, prima coloană). La i se adună h și la j se adună w.

În datele de intrare de mai sus, 5×5 este dimensiunea matricei din ultimele 5 randuri, (3, 4) este punctul de pornire al dreptunghiului a carui suma o cautam si (2, 3) sunt dimensiunile dreptunghiului (latime 2, inaltime 3).

Din datele de intrare rezultă că matricea rezultat, notata B, va avea 4 dimensiuni:

B[i][j][w][h] = ?

Cazurile de bază ale recurenței sunt:

  • B[i][j][0][h] = B[i][j][w][0] = 0;
  • B[i][j][1][1] = A[i][j].

Analizăm posibilele cazuri de bază ale recurenței:

  1. i = 1
    1. j = 1
      1. w = 0 sau w = 1 sau w = ?
      2. h = 0 sau h = 1 sau h = ?
    2. j = ?
      1. w = 0 sau w = 1 sau w = ?
      2. h = 0 sau h = 1 sau h = ?
  2. i = ?
    1. j = 1
      1. w = 0 sau w = 1 sau w = ?
      2. h = 0 sau h = 1 sau h = ?
    2. j = ?
      1. w = 0 sau w = 1 sau w = ?
      2. h = 0 sau h = 1 sau h = ?

Combinațiile posibile sunt următoarele (prin ? am notat valori diferite de 0 și 1 și prin „f.g.”, formula generală):

i = 1, j = 1, w = 0, h = 0 => 0
i = 1, j = 1, w = 0, h = 1 => 0
i = 1, j = 1, w = 0, h = ? => 0
i = 1, j = 1, w = 1, h = 0 => 0
i = 1, j = 1, w = 1, h = 1 => A[1][1]
i = 1, j = 1, w = 1, h = ? => f.g. suma submatrice-coloană
i = 1, j = 1, w = ?, h = 0 => 0
i = 1, j = 1, w = ?, h = 1 => f.g. suma submatrice-linie
i = 1, j = 1, w = ?, h = ? => f.g. (formula generală sumă submatrice dreptunghi)

i = 1, j = ?, w = 0, h = 0 => 0
i = 1, j = ?, w = 0, h = 1 => 0
i = 1, j = ?, w = 0, h = ? => 0
i = 1, j = ?, w = 1, h = 0 => 0
i = 1, j = ?, w = 1, h = 1 => A[1][j]
i = 1, j = ?, w = 1, h = ? => f.g. suma submatrice-coloană
i = 1, j = ?, w = ?, h = 0 => 0
i = 1, j = ?, w = ?, h = 1 => f.g. suma submatrice-linie
i = 1, j = ?, w = ?, h = ? => f.g. (formula generală sumă submatrice dreptunghi)

i = ?, j = 1, w = 0, h = 0 => 0
i = ?, j = 1, w = 0, h = 1 => 0
i = ?, j = 1, w = 0, h = ? => 0
i = ?, j = 1, w = 1, h = 0 => 0
i = ?, j = 1, w = 1, h = 1 => A[i][1]
i = ?, j = 1, w = 1, h = ? => f.g. suma submatrice-coloană
i = ?, j = 1, w = ?, h = 0 => 0
i = ?, j = 1, w = ?, h = 1 => f.g. suma submatrice-linie
i = ?, j = 1, w = ?, h = ? => f.g. (formula generală sumă submatrice dreptunghi)

i = ?, j = ?, w = 0, h = 0 => 0
i = ?, j = ?, w = 0, h = 1 => 0
i = ?, j = ?, w = 0, h = ? => 0
i = ?, j = ?, w = 1, h = 0 => 0
i = ?, j = ?, w = 1, h = 1 => A[i][j]
i = ?, j = ?, w = 1, h = ? => f.g. suma submatrice-coloană
i = ?, j = ?, w = ?, h = 0 => 0
i = ?, j = ?, w = ?, h = 1 => f.g. suma submatrice-linie
i = ?, j = ?, w = ?, h = ? => f.g. (formula generală sumă submatrice dreptunghi)

Se observa că pt. w = 0 sau h = 0 suma este mereu 0, deci se ignora aceste cazuri în matricea rezultat, nu se calculeaza.
Rămâne:

i = 1, j = 1, w = 1, h = 1 => A[1][1]
i = 1, j = 1, w = 1, h = ? => f.g. suma submatrice-coloană
i = 1, j = 1, w = ?, h = 1 => f.g. suma submatrice-linie
i = 1, j = 1, w = ?, h = ? => f.g. (formula generală sumă submatrice dreptunghi)

i = 1, j = ?, w = 1, h = 1 => A[1][j]
i = 1, j = ?, w = 1, h = ? => f.g. suma submatrice-coloană
i = 1, j = ?, w = ?, h = 1 => f.g. suma submatrice-linie
i = 1, j = ?, w = ?, h = ? => f.g. (formula generală sumă submatrice dreptunghi)

i = ?, j = 1, w = 1, h = 1 => A[i][1]
i = ?, j = 1, w = 1, h = ? => f.g. suma submatrice-coloană
i = ?, j = 1, w = ?, h = 1 => f.g. suma submatrice-linie
i = ?, j = 1, w = ?, h = ? => f.g. (formula generală sumă submatrice dreptunghi)

i = ?, j = ?, w = 1, h = 1 => A[i][j]
i = ?, j = ?, w = 1, h = ? => f.g. suma submatrice-coloană
i = ?, j = ?, w = ?, h = 1 => f.g. suma submatrice-linie
i = ?, j = ?, w = ?, h = ? => f.g. (formula generală sumă submatrice dreptunghi)

Din toate posibilele cazuri de recurență le-am ales pe cele utile și am extras mai departe din ele cele cu <submatrice-coloană>:

i = 1, j = 1, w = 1, h = ? => f.g. suma submatrice-coloană
i = 1, j = ?, w = 1, h = ? => f.g. suma submatrice-coloană
i = ?, j = 1, w = 1, h = ? => f.g. suma submatrice-coloană
i = ?, j = ?, w = 1, h = ? => f.g. suma submatrice-coloană

Se combina în:
B[i][j][1][h] = A[i + 1 – 1][j] + A[i + 2 – 1][j] + … + A[i + h – 1][j].

Se face analog pentru <submatrice-linie>:

i = 1, j = 1, w = ?, h = 1 => f.g. suma submatrice-linie
i = 1, j = ?, w = ?, h = 1 => f.g. suma submatrice-linie
i = ?, j = 1, w = ?, h = 1 => f.g. suma submatrice-linie
i = ?, j = ?, w = ?, h = 1 => f.g. suma submatrice-linie

Se combina în:
B[i][j][w][1] = A[i][j + 1 – 1] + A[i][j + 2 – 1] + … + A[i][j + w – 1].

Acum avem calculate cazurile:
– B[i][j][1][1];
– B[i][j][w][1];
– B[i][j][1][h];

Mai rămâne de gândit cazul general:
– B[i][j][w][h].

Se ia o submatrice a cărei sumă trebuie calculată (pozițiile se exprimă în funcție de w și h):

B[i][j][w][h] = suma sumelor liniilor sau suma sumelor coloanelor.

1. suma sumelor liniilor (când liniile sunt mai puține decât coloanele sau la fel de multe: h <= w)
B[i][j][w][h] = B[i][j][w][1] + B[i + 1][j][w][1] + B[i + 2][j][w][1] + … + B[i + h – 1][j][w][1];

2. suma sumelor coloanelor (când coloanele sunt mai puține decât liniile: w < h)
B[i][j][w][h] = B[i][j][1][h] + B[i][j + 1][1][h] + B[i][j + 2][1][h] + … + B[i][j + w – 1][1][h]
.

Părțile subliniate din expresiile aldine de mai sus sunt utilizate de mai multe ori în același membru al egalității respective.

Se rezolvă problema cu ce se stie până acum, generând matricea-rezultat de la stânga la dreapta, de sus în jos și se descoperă că ordinea de calculare a valorilor din matrice nu este corectă, se accesează în formula de recurență valori încă necalculate la momentul respectiv.

Mai exact, pentru datele de intrare de mai sus:

5 5 3 4 2 3
1  2  3  4  5
6  7  8  9  10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

unde datele au interpretarea de la începutul acestui articol, adică matricea este 5×5, (3,4) este poziția dreptunghiului și (2,3) este dimensiunea lui.

Exemplu:
Pentru calcularea lui B[1][1][2][2] e ceruta valoarea B[1][2][1][2].

Se modifica programul sa afiseze in functie de ce valori e calculata fiecare valoare (nu se poate face foarte vizual deoarece matricea-rezultat are 4 dimensiuni).

În exemplele de mai jos, ce e subliniat nu se schimba în expresia din care face parte, ca indice al matricei:

– când se iau coloane care alcatuiesc dreptunghiul:
B[1][1][2][2] = B[1][1][1][2] + B[1][2][1][2]
B[1][1][2][3] = B[1][1][1][3] + B[1][2][1][3]

– când se iau rânduri:
B[1][1][3][2] = B[1][1][3][1] + B[2][1][3][1]

Dar înainte de a face decizia în program „care caz din cele 2 de mai sus ale formulei generale să utilizez” trebuie să se aibă valorile necesare calculate, deci să se știe în ce ordine se calculează valorile de la început.

În final, se observă în datele de ieșire că toate valorile care depind de altceva decât de valorile matricei de intrare A au valoare nedefinită.

Se incearca să se calculeze mai întâi valorile matricei B care se pot calcula în funcție doar de A.

După ce am făcut asta, se observă că restul valorilor se calculează în ordine corectă, nemaifiind nici o valoare nedefinită în matricea rezultat.

Funcția suma calculeaza ce se poate mai intai si de asta in final poate calcula tot (parcurge matricea de mai multe ori, de fiecare data din stanga sus pana in dreapta jos. Functia test afiseaza calculele toate, in ordine naiva, in consola, inclusiv cele cu valori nedefinite, functia test este un pas intermediar de observatie in rezolvarea problemei.

Se afiseaza in consola cu functia test urmatoarele (pentru aflarea ordinei potrivite de calculare a matricei rezultat):

Se calculeaza…..

B[1][1][1][1] = A[1][1] = 1
B[1][1][1][1] = + A[1][1] = 1
B[1][1][1][2] = + A[1][1] + A[2][1] = 7
B[1][1][1][3] = + A[1][1] + A[2][1] + A[3][1] = 18
B[1][1][1][4] = + A[1][1] + A[2][1] + A[3][1] + A[4][1] = 34
B[1][1][1][5] = + A[1][1] + A[2][1] + A[3][1] + A[4][1] + A[5][1] = 55
B[1][1][2][1] = + A[1][1] + A[1][2] = 3
B[1][1][2][2] = + B[1][1][2][1] + B[2][1][2][1] = -858993457
B[1][1][2][3] = + B[1][1][1][3] + B[1][2][1][3] = -858993442
B[1][1][2][4] = + B[1][1][1][4] + B[1][2][1][4] = -858993426
B[1][1][2][5] = + B[1][1][1][5] + B[1][2][1][5] = -858993405
B[1][1][3][1] = + A[1][1] + A[1][2] + A[1][3] = 6
B[1][1][3][2] = + B[1][1][3][1] + B[2][1][3][1] = -858993454
B[1][1][3][3] = + B[1][1][3][1] + B[2][1][3][1] + B[3][1][3][1] = -1717986914
B[1][1][3][4] = + B[1][1][1][4] + B[1][2][1][4] + B[1][3][1][4] = -1717986886
B[1][1][3][5] = + B[1][1][1][5] + B[1][2][1][5] + B[1][3][1][5] = -1717986865
B[1][1][4][1] = + A[1][1] + A[1][2] + A[1][3] + A[1][4] = 10
B[1][1][4][2] = + B[1][1][4][1] + B[2][1][4][1] = -858993450
B[1][1][4][3] = + B[1][1][4][1] + B[2][1][4][1] + B[3][1][4][1] = -1717986910
B[1][1][4][4] = + B[1][1][4][1] + B[2][1][4][1] + B[3][1][4][1] + B[4][1][4][1] = 1717986926
B[1][1][4][5] = + B[1][1][1][5] + B[1][2][1][5] + B[1][3][1][5] + B[1][4][1][5] = 1717986971
B[1][1][5][1] = + A[1][1] + A[1][2] + A[1][3] + A[1][4] + A[1][5] = 15
B[1][1][5][2] = + B[1][1][5][1] + B[2][1][5][1] = -858993445
B[1][1][5][3] = + B[1][1][5][1] + B[2][1][5][1] + B[3][1][5][1] = -1717986905
B[1][1][5][4] = + B[1][1][5][1] + B[2][1][5][1] + B[3][1][5][1] + B[4][1][5][1] = 1717986931
B[1][1][5][5] = + B[1][1][5][1] + B[2][1][5][1] + B[3][1][5][1] + B[4][1][5][1] + B[5][1][5][1] = 858993471
B[1][2][1][1] = A[1][2] = 2
B[1][2][1][1] = + A[1][2] = 2
B[1][2][1][2] = + A[1][2] + A[2][2] = 9
B[1][2][1][3] = + A[1][2] + A[2][2] + A[3][2] = 21
B[1][2][1][4] = + A[1][2] + A[2][2] + A[3][2] + A[4][2] = 38
B[1][2][1][5] = + A[1][2] + A[2][2] + A[3][2] + A[4][2] + A[5][2] = 60
B[1][2][2][1] = + A[1][2] + A[1][3] = 5
B[1][2][2][2] = + B[1][2][2][1] + B[2][2][2][1] = -858993455
B[1][2][2][3] = + B[1][2][1][3] + B[1][3][1][3] = -858993439
B[1][2][2][4] = + B[1][2][1][4] + B[1][3][1][4] = -858993422
B[1][2][2][5] = + B[1][2][1][5] + B[1][3][1][5] = -858993400
B[1][2][3][1] = + A[1][2] + A[1][3] + A[1][4] = 9
B[1][2][3][2] = + B[1][2][3][1] + B[2][2][3][1] = -858993451
B[1][2][3][3] = + B[1][2][3][1] + B[2][2][3][1] + B[3][2][3][1] = -1717986911
B[1][2][3][4] = + B[1][2][1][4] + B[1][3][1][4] + B[1][4][1][4] = -1717986882
B[1][2][3][5] = + B[1][2][1][5] + B[1][3][1][5] + B[1][4][1][5] = -1717986860
B[1][2][4][1] = + A[1][2] + A[1][3] + A[1][4] + A[1][5] = 14
B[1][2][4][2] = + B[1][2][4][1] + B[2][2][4][1] = -858993446
B[1][2][4][3] = + B[1][2][4][1] + B[2][2][4][1] + B[3][2][4][1] = -1717986906
B[1][2][4][4] = + B[1][2][4][1] + B[2][2][4][1] + B[3][2][4][1] + B[4][2][4][1] = 1717986930
B[1][2][4][5] = + B[1][2][1][5] + B[1][3][1][5] + B[1][4][1][5] + B[1][5][1][5] = 1717986976
B[1][3][1][1] = A[1][3] = 3
B[1][3][1][1] = + A[1][3] = 3
B[1][3][1][2] = + A[1][3] + A[2][3] = 11
B[1][3][1][3] = + A[1][3] + A[2][3] + A[3][3] = 24
B[1][3][1][4] = + A[1][3] + A[2][3] + A[3][3] + A[4][3] = 42
B[1][3][1][5] = + A[1][3] + A[2][3] + A[3][3] + A[4][3] + A[5][3] = 65
B[1][3][2][1] = + A[1][3] + A[1][4] = 7
B[1][3][2][2] = + B[1][3][2][1] + B[2][3][2][1] = -858993453
B[1][3][2][3] = + B[1][3][1][3] + B[1][4][1][3] = -858993436
B[1][3][2][4] = + B[1][3][1][4] + B[1][4][1][4] = -858993418
B[1][3][2][5] = + B[1][3][1][5] + B[1][4][1][5] = -858993395
B[1][3][3][1] = + A[1][3] + A[1][4] + A[1][5] = 12
B[1][3][3][2] = + B[1][3][3][1] + B[2][3][3][1] = -858993448
B[1][3][3][3] = + B[1][3][3][1] + B[2][3][3][1] + B[3][3][3][1] = -1717986908
B[1][3][3][4] = + B[1][3][1][4] + B[1][4][1][4] + B[1][5][1][4] = -1717986878
B[1][3][3][5] = + B[1][3][1][5] + B[1][4][1][5] + B[1][5][1][5] = -1717986855
B[1][4][1][1] = A[1][4] = 4
B[1][4][1][1] = + A[1][4] = 4
B[1][4][1][2] = + A[1][4] + A[2][4] = 13
B[1][4][1][3] = + A[1][4] + A[2][4] + A[3][4] = 27
B[1][4][1][4] = + A[1][4] + A[2][4] + A[3][4] + A[4][4] = 46
B[1][4][1][5] = + A[1][4] + A[2][4] + A[3][4] + A[4][4] + A[5][4] = 70
B[1][4][2][1] = + A[1][4] + A[1][5] = 9
B[1][4][2][2] = + B[1][4][2][1] + B[2][4][2][1] = -858993451
B[1][4][2][3] = + B[1][4][1][3] + B[1][5][1][3] = -858993433
B[1][4][2][4] = + B[1][4][1][4] + B[1][5][1][4] = -858993414
B[1][4][2][5] = + B[1][4][1][5] + B[1][5][1][5] = -858993390
B[1][5][1][1] = A[1][5] = 5
B[1][5][1][1] = + A[1][5] = 5
B[1][5][1][2] = + A[1][5] + A[2][5] = 15
B[1][5][1][3] = + A[1][5] + A[2][5] + A[3][5] = 30
B[1][5][1][4] = + A[1][5] + A[2][5] + A[3][5] + A[4][5] = 50
B[1][5][1][5] = + A[1][5] + A[2][5] + A[3][5] + A[4][5] + A[5][5] = 75
B[2][1][1][1] = A[2][1] = 6
B[2][1][1][1] = + A[2][1] = 6
B[2][1][1][2] = + A[2][1] + A[3][1] = 17
B[2][1][1][3] = + A[2][1] + A[3][1] + A[4][1] = 33
B[2][1][1][4] = + A[2][1] + A[3][1] + A[4][1] + A[5][1] = 54
B[2][1][2][1] = + A[2][1] + A[2][2] = 13
B[2][1][2][2] = + B[2][1][2][1] + B[3][1][2][1] = -858993447
B[2][1][2][3] = + B[2][1][1][3] + B[2][2][1][3] = -858993427
B[2][1][2][4] = + B[2][1][1][4] + B[2][2][1][4] = -858993406
B[2][1][3][1] = + A[2][1] + A[2][2] + A[2][3] = 21
B[2][1][3][2] = + B[2][1][3][1] + B[3][1][3][1] = -858993439
B[2][1][3][3] = + B[2][1][3][1] + B[3][1][3][1] + B[4][1][3][1] = -1717986899
B[2][1][3][4] = + B[2][1][1][4] + B[2][2][1][4] + B[2][3][1][4] = -1717986866
B[2][1][4][1] = + A[2][1] + A[2][2] + A[2][3] + A[2][4] = 30
B[2][1][4][2] = + B[2][1][4][1] + B[3][1][4][1] = -858993430
B[2][1][4][3] = + B[2][1][4][1] + B[3][1][4][1] + B[4][1][4][1] = -1717986890
B[2][1][4][4] = + B[2][1][4][1] + B[3][1][4][1] + B[4][1][4][1] + B[5][1][4][1] = 1717986946
B[2][1][5][1] = + A[2][1] + A[2][2] + A[2][3] + A[2][4] + A[2][5] = 40
B[2][1][5][2] = + B[2][1][5][1] + B[3][1][5][1] = -858993420
B[2][1][5][3] = + B[2][1][5][1] + B[3][1][5][1] + B[4][1][5][1] = -1717986880
B[2][1][5][4] = + B[2][1][5][1] + B[3][1][5][1] + B[4][1][5][1] + B[5][1][5][1] = 1717986956
B[2][2][1][1] = A[2][2] = 7
B[2][2][1][1] = + A[2][2] = 7
B[2][2][1][2] = + A[2][2] + A[3][2] = 19
B[2][2][1][3] = + A[2][2] + A[3][2] + A[4][2] = 36
B[2][2][1][4] = + A[2][2] + A[3][2] + A[4][2] + A[5][2] = 58
B[2][2][2][1] = + A[2][2] + A[2][3] = 15
B[2][2][2][2] = + B[2][2][2][1] + B[3][2][2][1] = -858993445
B[2][2][2][3] = + B[2][2][1][3] + B[2][3][1][3] = -858993424
B[2][2][2][4] = + B[2][2][1][4] + B[2][3][1][4] = -858993402
B[2][2][3][1] = + A[2][2] + A[2][3] + A[2][4] = 24
B[2][2][3][2] = + B[2][2][3][1] + B[3][2][3][1] = -858993436
B[2][2][3][3] = + B[2][2][3][1] + B[3][2][3][1] + B[4][2][3][1] = -1717986896
B[2][2][3][4] = + B[2][2][1][4] + B[2][3][1][4] + B[2][4][1][4] = -1717986862
B[2][2][4][1] = + A[2][2] + A[2][3] + A[2][4] + A[2][5] = 34
B[2][2][4][2] = + B[2][2][4][1] + B[3][2][4][1] = -858993426
B[2][2][4][3] = + B[2][2][4][1] + B[3][2][4][1] + B[4][2][4][1] = -1717986886
B[2][2][4][4] = + B[2][2][4][1] + B[3][2][4][1] + B[4][2][4][1] + B[5][2][4][1] = 1717986950
B[2][3][1][1] = A[2][3] = 8
B[2][3][1][1] = + A[2][3] = 8
B[2][3][1][2] = + A[2][3] + A[3][3] = 21
B[2][3][1][3] = + A[2][3] + A[3][3] + A[4][3] = 39
B[2][3][1][4] = + A[2][3] + A[3][3] + A[4][3] + A[5][3] = 62
B[2][3][2][1] = + A[2][3] + A[2][4] = 17
B[2][3][2][2] = + B[2][3][2][1] + B[3][3][2][1] = -858993443
B[2][3][2][3] = + B[2][3][1][3] + B[2][4][1][3] = -858993421
B[2][3][2][4] = + B[2][3][1][4] + B[2][4][1][4] = -858993398
B[2][3][3][1] = + A[2][3] + A[2][4] + A[2][5] = 27
B[2][3][3][2] = + B[2][3][3][1] + B[3][3][3][1] = -858993433
B[2][3][3][3] = + B[2][3][3][1] + B[3][3][3][1] + B[4][3][3][1] = -1717986893
B[2][3][3][4] = + B[2][3][1][4] + B[2][4][1][4] + B[2][5][1][4] = -1717986858
B[2][4][1][1] = A[2][4] = 9
B[2][4][1][1] = + A[2][4] = 9
B[2][4][1][2] = + A[2][4] + A[3][4] = 23
B[2][4][1][3] = + A[2][4] + A[3][4] + A[4][4] = 42
B[2][4][1][4] = + A[2][4] + A[3][4] + A[4][4] + A[5][4] = 66
B[2][4][2][1] = + A[2][4] + A[2][5] = 19
B[2][4][2][2] = + B[2][4][2][1] + B[3][4][2][1] = -858993441
B[2][4][2][3] = + B[2][4][1][3] + B[2][5][1][3] = -858993418
B[2][4][2][4] = + B[2][4][1][4] + B[2][5][1][4] = -858993394
B[2][5][1][1] = A[2][5] = 10
B[2][5][1][1] = + A[2][5] = 10
B[2][5][1][2] = + A[2][5] + A[3][5] = 25
B[2][5][1][3] = + A[2][5] + A[3][5] + A[4][5] = 45
B[2][5][1][4] = + A[2][5] + A[3][5] + A[4][5] + A[5][5] = 70
B[3][1][1][1] = A[3][1] = 11
B[3][1][1][1] = + A[3][1] = 11
B[3][1][1][2] = + A[3][1] + A[4][1] = 27
B[3][1][1][3] = + A[3][1] + A[4][1] + A[5][1] = 48
B[3][1][2][1] = + A[3][1] + A[3][2] = 23
B[3][1][2][2] = + B[3][1][2][1] + B[4][1][2][1] = -858993437
B[3][1][2][3] = + B[3][1][1][3] + B[3][2][1][3] = -858993412
B[3][1][3][1] = + A[3][1] + A[3][2] + A[3][3] = 36
B[3][1][3][2] = + B[3][1][3][1] + B[4][1][3][1] = -858993424
B[3][1][3][3] = + B[3][1][3][1] + B[4][1][3][1] + B[5][1][3][1] = -1717986884
B[3][1][4][1] = + A[3][1] + A[3][2] + A[3][3] + A[3][4] = 50
B[3][1][4][2] = + B[3][1][4][1] + B[4][1][4][1] = -858993410
B[3][1][4][3] = + B[3][1][4][1] + B[4][1][4][1] + B[5][1][4][1] = -1717986870
B[3][1][5][1] = + A[3][1] + A[3][2] + A[3][3] + A[3][4] + A[3][5] = 65
B[3][1][5][2] = + B[3][1][5][1] + B[4][1][5][1] = -858993395
B[3][1][5][3] = + B[3][1][5][1] + B[4][1][5][1] + B[5][1][5][1] = -1717986855
B[3][2][1][1] = A[3][2] = 12
B[3][2][1][1] = + A[3][2] = 12
B[3][2][1][2] = + A[3][2] + A[4][2] = 29
B[3][2][1][3] = + A[3][2] + A[4][2] + A[5][2] = 51
B[3][2][2][1] = + A[3][2] + A[3][3] = 25
B[3][2][2][2] = + B[3][2][2][1] + B[4][2][2][1] = -858993435
B[3][2][2][3] = + B[3][2][1][3] + B[3][3][1][3] = -858993409
B[3][2][3][1] = + A[3][2] + A[3][3] + A[3][4] = 39
B[3][2][3][2] = + B[3][2][3][1] + B[4][2][3][1] = -858993421
B[3][2][3][3] = + B[3][2][3][1] + B[4][2][3][1] + B[5][2][3][1] = -1717986881
B[3][2][4][1] = + A[3][2] + A[3][3] + A[3][4] + A[3][5] = 54
B[3][2][4][2] = + B[3][2][4][1] + B[4][2][4][1] = -858993406
B[3][2][4][3] = + B[3][2][4][1] + B[4][2][4][1] + B[5][2][4][1] = -1717986866
B[3][3][1][1] = A[3][3] = 13
B[3][3][1][1] = + A[3][3] = 13
B[3][3][1][2] = + A[3][3] + A[4][3] = 31
B[3][3][1][3] = + A[3][3] + A[4][3] + A[5][3] = 54
B[3][3][2][1] = + A[3][3] + A[3][4] = 27
B[3][3][2][2] = + B[3][3][2][1] + B[4][3][2][1] = -858993433
B[3][3][2][3] = + B[3][3][1][3] + B[3][4][1][3] = -858993406
B[3][3][3][1] = + A[3][3] + A[3][4] + A[3][5] = 42
B[3][3][3][2] = + B[3][3][3][1] + B[4][3][3][1] = -858993418
B[3][3][3][3] = + B[3][3][3][1] + B[4][3][3][1] + B[5][3][3][1] = -1717986878
B[3][4][1][1] = A[3][4] = 14
B[3][4][1][1] = + A[3][4] = 14
B[3][4][1][2] = + A[3][4] + A[4][4] = 33
B[3][4][1][3] = + A[3][4] + A[4][4] + A[5][4] = 57
B[3][4][2][1] = + A[3][4] + A[3][5] = 29
B[3][4][2][2] = + B[3][4][2][1] + B[4][4][2][1] = -858993431
B[3][4][2][3] = + B[3][4][1][3] + B[3][5][1][3] = -858993403
B[3][5][1][1] = A[3][5] = 15
B[3][5][1][1] = + A[3][5] = 15
B[3][5][1][2] = + A[3][5] + A[4][5] = 35
B[3][5][1][3] = + A[3][5] + A[4][5] + A[5][5] = 60
B[4][1][1][1] = A[4][1] = 16
B[4][1][1][1] = + A[4][1] = 16
B[4][1][1][2] = + A[4][1] + A[5][1] = 37
B[4][1][2][1] = + A[4][1] + A[4][2] = 33
B[4][1][2][2] = + B[4][1][2][1] + B[5][1][2][1] = -858993427
B[4][1][3][1] = + A[4][1] + A[4][2] + A[4][3] = 51
B[4][1][3][2] = + B[4][1][3][1] + B[5][1][3][1] = -858993409
B[4][1][4][1] = + A[4][1] + A[4][2] + A[4][3] + A[4][4] = 70
B[4][1][4][2] = + B[4][1][4][1] + B[5][1][4][1] = -858993390
B[4][1][5][1] = + A[4][1] + A[4][2] + A[4][3] + A[4][4] + A[4][5] = 90
B[4][1][5][2] = + B[4][1][5][1] + B[5][1][5][1] = -858993370
B[4][2][1][1] = A[4][2] = 17
B[4][2][1][1] = + A[4][2] = 17
B[4][2][1][2] = + A[4][2] + A[5][2] = 39
B[4][2][2][1] = + A[4][2] + A[4][3] = 35
B[4][2][2][2] = + B[4][2][2][1] + B[5][2][2][1] = -858993425
B[4][2][3][1] = + A[4][2] + A[4][3] + A[4][4] = 54
B[4][2][3][2] = + B[4][2][3][1] + B[5][2][3][1] = -858993406
B[4][2][4][1] = + A[4][2] + A[4][3] + A[4][4] + A[4][5] = 74
B[4][2][4][2] = + B[4][2][4][1] + B[5][2][4][1] = -858993386
B[4][3][1][1] = A[4][3] = 18
B[4][3][1][1] = + A[4][3] = 18
B[4][3][1][2] = + A[4][3] + A[5][3] = 41
B[4][3][2][1] = + A[4][3] + A[4][4] = 37
B[4][3][2][2] = + B[4][3][2][1] + B[5][3][2][1] = -858993423
B[4][3][3][1] = + A[4][3] + A[4][4] + A[4][5] = 57
B[4][3][3][2] = + B[4][3][3][1] + B[5][3][3][1] = -858993403
B[4][4][1][1] = A[4][4] = 19
B[4][4][1][1] = + A[4][4] = 19
B[4][4][1][2] = + A[4][4] + A[5][4] = 43
B[4][4][2][1] = + A[4][4] + A[4][5] = 39
B[4][4][2][2] = + B[4][4][2][1] + B[5][4][2][1] = -858993421
B[4][5][1][1] = A[4][5] = 20
B[4][5][1][1] = + A[4][5] = 20
B[4][5][1][2] = + A[4][5] + A[5][5] = 45
B[5][1][1][1] = A[5][1] = 21
B[5][1][1][1] = + A[5][1] = 21
B[5][1][2][1] = + A[5][1] + A[5][2] = 43
B[5][1][3][1] = + A[5][1] + A[5][2] + A[5][3] = 66
B[5][1][4][1] = + A[5][1] + A[5][2] + A[5][3] + A[5][4] = 90
B[5][1][5][1] = + A[5][1] + A[5][2] + A[5][3] + A[5][4] + A[5][5] = 115
B[5][2][1][1] = A[5][2] = 22
B[5][2][1][1] = + A[5][2] = 22
B[5][2][2][1] = + A[5][2] + A[5][3] = 45
B[5][2][3][1] = + A[5][2] + A[5][3] + A[5][4] = 69
B[5][2][4][1] = + A[5][2] + A[5][3] + A[5][4] + A[5][5] = 94
B[5][3][1][1] = A[5][3] = 23
B[5][3][1][1] = + A[5][3] = 23
B[5][3][2][1] = + A[5][3] + A[5][4] = 47
B[5][3][3][1] = + A[5][3] + A[5][4] + A[5][5] = 72
B[5][4][1][1] = A[5][4] = 24
B[5][4][1][1] = + A[5][4] = 24
B[5][4][2][1] = + A[5][4] + A[5][5] = 49
B[5][5][1][1] = A[5][5] = 25
B[5][5][1][1] = + A[5][5] = 25

Se observă ușor valori foarte mari în contrast cu cele din jur.

Se remarcă faptul că nu a trebuit să se initializeze matricea B cu 0 înainte de calcularea valorilor din ea, acest lucru fiind nefolositor.

Capturi de ecran 

Codul sursă

  1. #include   
  2. #include   
  3. using namespace std;  
  4.   
  5. const int maxn = 11,  
  6.     maxm = 11;  
  7.   
  8. // calculeaza suma pentru toate dreptunghiurile posibile  
  9. // care se pot lua in matricea A si apoi raspunde la o  
  10. // intrebare de tipul celei din enunt printr-o simpla  
  11. // accesare a unei valori din matricea-rezultat B.  
  12. int suma(int A[maxn][maxm],  
  13.     int B[maxn][maxm][maxm][maxn],  
  14.     int i, int j,  
  15.     int w, int h,  
  16.     int W, int H)  
  17. {  
  18.     // pt fiecare i de la care poate porni un dreptunghi..  
  19.     for (int k = 1; k <= H; ++k) // ca i  
  20.     {  
  21.         // pt fiecare j de la care poate porni un dreptunghi..  
  22.         for (int l = 1; l <= W; ++l) // ca j  
  23.         {  
  24.             B[k][l][1][1] = A[k][l];  
  25.   
  26.             // pt fiecare latime posibila a unui dreptunghi  
  27.             // care incepe de la punctul (i, j) curent adica  
  28.             // de la (k, l)..  
  29.             for (int m = 1; m <= W – l + 1; ++m) // ca w  
  30.             {  
  31.                 int val = 0;  
  32.                 for (int n = l + 1 – 1; n <= l + m – 1;  
  33.                     ++n) // n ca h  
  34.                 {  
  35.                     val += A[k][n];  
  36.                 }  
  37.                 B[k][l][m][1] = val;  
  38.   
  39.                 // pt fiecare inaltime posibila a unui dreptunghi  
  40.                 // care incepe de la punctul (i, j) curent adica  
  41.                 // de la (k, l)..  
  42.                 for (int n = 1; n <= H – k + 1; ++n) // ca h  
  43.                 {  
  44.                     // cazurile din acest if sunt calculate deja  
  45.                     if (n == 1 || (m == n && m == 1))  
  46.                     {  
  47.                         continue;  
  48.                     }  
  49.                       
  50.                     if (m == 1) // w  
  51.                     {  
  52.                         int val = 0;  
  53.                         for (int o = k + 1 – 1; o <= k + n – 1; // o ca i  
  54.                             ++o)  
  55.                         {  
  56.                             val += A[o][l];  
  57.                         }  
  58.                         B[k][l][1][n] = val;  
  59.                     }  
  60.                 }  
  61.             }  
  62.         }  
  63.     }  
  64.   
  65.     // pt fiecare i de la care poate porni un dreptunghi..  
  66.     for (int k = 1; k <= H; ++k) // ca i  
  67.     {  
  68.         // pt fiecare j de la care poate porni un dreptunghi..  
  69.         for (int l = 1; l <= W; ++l) // ca j  
  70.         {  
  71.             // pt fiecare latime posibila a unui dreptunghi  
  72.             // care incepe de la punctul (i, j) curent adica  
  73.             // de la (k, l)..  
  74.             for (int m = 1; m <= W – l + 1; ++m) // ca w  
  75.             {  
  76.                 // pt fiecare inaltime posibila a unui dreptunghi  
  77.                 // care incepe de la punctul (i, j) curent adica  
  78.                 // de la (k, l)..  
  79.                 for (int n = 1; n <= H – k + 1; ++n) // ca h  
  80.                 {  
  81.                     // cazurile din acest if sunt calculate deja  
  82.                     if (n == 1 || (m == n && m == 1))  
  83.                     {  
  84.                         continue;  
  85.                     }  
  86.   
  87.                     // inaltimea mai mica (sau egala) cu latimea,  
  88.                     // rezulta ca pt optimizare se insumeaza randuri  
  89.                     if (n <= m) // h <= w  
  90.                     {  
  91.                         int val = 0;  
  92.                         for (int p = k; p <= k + n – 1; ++p) // p ca i  
  93.                         {  
  94.                             val += B[p][l][m][1];  
  95.                         }  
  96.                         B[k][l][m][n] = val;  
  97.                     }  
  98.                     else // altfel se insumeaza coloane  
  99.                     {  
  100.                         int val = 0;  
  101.                         for (int p = l; p <= l + m – 1; ++p) // p ca j  
  102.                         {  
  103.                             val += B[k][p][1][n];  
  104.                         }  
  105.                         B[k][l][m][n] = val;  
  106.                     }  
  107.                 }  
  108.             }  
  109.         }  
  110.     }  
  111.   
  112.     return B[i][j][w][h];  
  113. }  
  114.   
  115. int test(int A[maxn][maxm],  
  116.     int B[maxn][maxm][maxm][maxn],  
  117.     int i, int j,  
  118.     int w, int h,  
  119.     int W, int H)  
  120. {  
  121.     cout << „Se calculeaza…..” << endl << endl;  
  122.   
  123.     // pt fiecare i de la care poate porni un dreptunghi..  
  124.     for (int k = 1; k <= H; ++k) // ca i  
  125.     {  
  126.         // pt fiecare j de la care poate porni un dreptunghi..  
  127.         for (int l = 1; l <= W; ++l) // ca j  
  128.         {  
  129.             B[k][l][1][1] = A[k][l];  
  130.             cout << „B[„ << k << „][„ << l << „]” <<  
  131.                 „[„ << 1 << „][„ << 1 << „] = A[„ <<  
  132.                 k << „][„ << l << „] = „ <<  
  133.                 B[k][l][1][1] << endl;  
  134.   
  135.             // pt fiecare latime posibila a unui dreptunghi  
  136.             // care incepe de la punctul (i, j) curent adica  
  137.             // de la (k, l)..  
  138.             for (int m = 1; m <= W – l + 1; ++m) // ca w  
  139.             {  
  140.                 // (n == 1) // n ca h  
  141.                 cout << „B[„ << k << „][„ << l << „]” <<  
  142.                     „[„ << m << „][„ << 1 << „] =”;  
  143.                 int val = 0;  
  144.                 for (int n = l + 1 – 1; n <= l + m – 1;  
  145.                     ++n) // n ca h  
  146.                 {  
  147.                     cout << ” + A[„ << k << „][„ << n << „]”;  
  148.                     val += A[k][n];  
  149.                 }  
  150.                 B[k][l][m][1] = val;  
  151.                 cout << ” = „ <<  
  152.                     B[k][l][m][1] << endl;  
  153.   
  154.                 // pt fiecare inaltime posibila a unui dreptunghi  
  155.                 // care incepe de la punctul (i, j) curent adica  
  156.                 // de la (k, l)..  
  157.                 for (int n = 1; n <= H – k + 1; ++n) // ca h  
  158.                 {  
  159.                     // cazurile din acest if sunt calculate deja  
  160.                     if (n == 1 || (m == n && m == 1))  
  161.                     {  
  162.                         continue;  
  163.                     }  
  164.   
  165.                     if (m == 1) // w  
  166.                     {  
  167.                         cout << „B[„ << k << „][„ << l << „]” <<  
  168.                             „[„ << 1 << „][„ << n << „] =”;  
  169.                         int val = 0;  
  170.                         for (int o = k + 1 – 1; // o ca i  
  171.                             o <= k + n – 1;  
  172.                             ++o)  
  173.                         {  
  174.                             cout << ” + A[„ << o << „][„ << l << „]”;  
  175.                             val += A[o][l];  
  176.                         }  
  177.                         B[k][l][1][n] = val;  
  178.                         cout << ” = „ << B[k][l][1][n] << endl;  
  179.                         continue;  
  180.                     }  
  181.   
  182.                     // inaltimea mai mica (sau egala) cu latimea,  
  183.                     // rezulta ca pt optimizare se insumeaza randuri  
  184.                     if (n <= m) // h <= w  
  185.                     {  
  186.                         cout << „B[„ << k << „][„ << l << „]” <<  
  187.                             „[„ << m << „][„ << n << „] =”;  
  188.                         int val = 0;  
  189.                         for (int p = k; p <= k + n – 1; ++p) // p ca i  
  190.                         {  
  191.                             cout << ” + B[„ << p << „][„ << l << „][„ <<  
  192.                                 m << „][„ << 1 << „]”;  
  193.                             val += B[p][l][m][1];  
  194.                         }  
  195.                         B[k][l][m][n] = val;  
  196.                         cout << ” = „ <<  
  197.                             B[k][l][m][n] << endl;  
  198.                     }  
  199.                     else // altfel se insumeaza coloane  
  200.                     {  
  201.                         cout << „B[„ << k << „][„ << l << „]” <<  
  202.                             „[„ << m << „][„ << n << „] =”;  
  203.                         int val = 0;  
  204.                         for (int p = l; p <= l + m – 1; ++p) // p ca j  
  205.                         {  
  206.                             cout << ” + B[„ << k << „][„ << p << „][„ <<  
  207.                                 1 << „][„ << n << „]”;  
  208.                             val += B[k][p][1][n];  
  209.                         }  
  210.                         B[k][l][m][n] = val;  
  211.                         cout << ” = „ <<  
  212.                             B[k][l][m][n] << endl;  
  213.                     }  
  214.                 }  
  215.             }  
  216.         }  
  217.     }  
  218.   
  219.     return B[i][j][w][h];  
  220. }  
  221.   
  222. int main()  
  223. {  
  224.     int A[maxn][maxm],  
  225.         B[maxn][maxm][maxm][maxn],  
  226.         H, W, y, x, w, h;  
  227.   
  228.     ifstream in(„suma.in”);  
  229.     in >> W >> H >> x >> y >> w >> h;  
  230.     for (int i = 1; i <= H; ++i)  
  231.     {  
  232.         for (int j = 1; j <= W; ++j)  
  233.         {  
  234.             in >> A[i][j];  
  235.         }  
  236.     }  
  237.     in.close();  
  238.   
  239.     ofstream out(„suma.out”);  
  240.     out << suma(A, B, y, x, w, h, W, H) <<  
  241.         endl << endl;  
  242.   
  243.     out << „Dreptunghiuri de la  X = „ << x <<  
  244.         „, Y = „ << y << „:” << endl;  
  245.     for (int m = 1; m <= W – x + 1; ++m) // ca w  
  246.     {  
  247.         for (int n = 1; n <= H – y + 1; ++n) // ca h  
  248.         {  
  249.             out << „B[„ << y << „][„ << x << „][„ << m << „][„ <<  
  250.                 n << „] = „ << B[y][x][m][n] << ‘\t’;  
  251.         }  
  252.         out << endl;  
  253.     }  
  254.   
  255.     out.close();  
  256.   
  257.     return 0;  
  258. }

[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 Ncifre 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 = 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   
  2. #include   
  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 = 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. }  

[C++, algoritmică] Numărarea parantezărilor booleane

Teoria este din cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo.

Teorie

Fişierul paran.in conţine pe prima linie un număr natural N. Pe a doua linie se află N valori booleane (0 sau 1), iar a treia linie conţine N – 1 valori din mulţimea {-1, -2, -3}, reprezentând operatorii and, or, respectiv xor. Aceştia au priorităţi egale şi se consideră dispuşi între operanzii daţi.

Se cere numărul de parantezări valide existente astfel încât expresia rezultată să aibă rezultatul true.

Exemplu:
paran.in

3
1 0 0
-2 -1

paran.out:
1

Explicaţie: expresia dată este T or F and F. Există două parantezări valide: ((T or F) and F) şi (T or (F and F)). Se poate observa că, dintre acestea, doar a doua are valoarea true.

Spre deosebire de majoritatea problemelor prezentate până acum, aceasta este o problemă de numărare, nu de determinare a unui optim. Rezolvarea acestei probleme este similară cu problema numărării partiţiilor unui număr: va trebui să găsim subprobleme a căror rezultat să îl putem aduna pentru a obţine rezultatul unei probleme mai mari.

Este evident că abordările backtracking ies din discuţie, întrucât am fi astfel limitaţi la expresii de lungime nu mai mare de ~10.

Să punem la punct modul în care vom reţine datele. Vom considera valorile 1 / 0 date ca fiind nişte simboluri şi le vom reţine într-un vector boolean S. Operatorii daţi îi vom reţine într-un vector de numere întregi op, cu semnificaţie op[i] = operatorul dintre simbolurile i şi i + 1. Acesta va juca un rol foarte important în formula de recurenţă pe care o vom deduce.

Fie acum T[i][j] = câte posibilităţi există de a paranteza expresia formată din simbolurile [i, j] astfel încât rezultatul acesteia să fie true. Mai mult, vom calcula în paralel şi F[i][j] = câte posibilităţi există de a paranteza expresia formată din simbolurile [i, j] astfel încât rezultatul acesteia să fie false. Aceste două matrici se vor calcula similar cu modul de calcul al matricii de la problema înmulţirii optime a matricelor. T şi F vor depinde una de cealaltă, dar dependeţele nu vor fi circulare, deci le vom putea calcula pe amândouă în paralel.

Am identificat deja elemente descoperite prima dată în cadrul a două probleme distincte. Tocmai acest lucru face ca programarea dinamică să fie o tehnică greu de stăpânit: inexistenţa unui şablon de rezolvare a problemelor. De multe ori avem nevoie de tehnici pe care nu le-am mai întâlnit, sau de combinarea mai multor idei de rezolvare a altor probleme.

În primul rând ne punem problema cazurilor de bază: T[i][i] şi F[i][i] ar trebui să fie evident cum se calculează, aşa că nu vom insista asupra acestui aspect.

Să presupunem acum că vrem să aflăm numărul de parantezări valide şi adevărate (a căror rezultat este true) ale unei subexpresii formate din simbolurile [i, j]. Mai mult, presupunem că ştim care este numărul de parantezări valide şi adevărate (şi false) ale subexpresiilor [i, k] şi [k + 1, j], pentru orice 1 ≤ i ≤ k < j ≤ N. Dacă ştim să calculăm T[i][j] şi F[i][j] pe baza acestor informaţii, atunci putem aplica acelaşi procedeu pentru toate elementele de deasupra diagonalei principale, iar în final răspunsul problemei va fi dat de T[1][N].

Avem trei cazuri pentru un k fixat:

  1. Dacă op[k] = -1 (and), atunci adunăm la T[i][j] valoarea T[i][k] * T[k + 1][j], deoarece avem nevoie ca ambele subexpresii să fie adevărate, deci putem combina orice parantezare adevărată a acestora.
  2. Dacă op[k] = -2 (or), atunci este de ajuns ca doar una dintre subexpresii să fie adevărată. Vom aduna aşadar la T[i][j] valoarea A[i][k] * A[k + 1][j] – F[i][k] * F[k + 1][j], unde A[x][y] = T[x][y] + F[x][y]. Practic, se scad din totalul parantezărilor cele false, rămânând cele adevărate.
  3. Dacă op[k] = -3 (xor), atunci cele două subexpresii trebuie să aibă valori diferite (una adevărată, iar cealaltă falsă). Adunăm aşadar la T[i][j] valoarea:
    T[i][k] * F[k + 1][j] + F[i][k] * T[k + 1][j]

Valorile matricei F se calculează similar. Avem aşadar recurenţele:

Menţionăm că suma T[1][N] + F[1][N] este al N-lea număr Catalan. Acestea reprezintă, printre altele, numărul de parantezări valide formate din N paranteze.

Avem aşadar un algoritm cu timpul de execuţie O(N3), a cărui implementare nu ar trebui să fie o noutate.

Adăugirile mele

În figura de mai sus, cu cele 2 sume cu 3 ramuri fiecare:

  1. op[k] == -1 înseamnă că al k-lea operator (unde k începe de la 1 și crește) este ȘI.
  2. op[k] == -2 înseamnă similar SAU.
  3. op[k] == -3 înseamnă similar XOR (SAU EXCLUSIV).

A II-a ramură a sumei de la T este scrisă astfel:

op[k] == -2 înseamnă că această ramură se folosește doar când operatorul de pe poziția k este SAU.

Ea poate fi scrisă și astfel:
    ce e la această sumă în cazul când op[k] == -1 (când operatorul este ȘI), +(plus) T[i][k] * F[k+1][j] + F[i][k] * T[k+1][j].

Altfel scris:
T[i][j] = T[i][k] * T[k+1][j] + T[i][k] * F[k+1][j] + F[i][k] * T[k+1][j].

T[i][j] reprezintă numărul maxim de parantezări care se evaluează la true (spre deosebire de false) care se pot construi din elementele booleane (true sau false) din subsecvența S[i, j].
F[i][j] are valoare complementară lui T[i][j], și pentru oricare i și j date, A[i][j] = T[i][j] + F[i][j], în această relație putându-se muta elemente din membrul stâng în cel drept și invers.

Deci expresia de mai sus „T[i][k] * T[k+1][j] + T[i][k] * F[k+1][j] + F[i][k] * T[k+1][j]”  poate fi scrisă în cuvinte astfel:

parantezari true de la i la j =
    parantezari true de la i la k ORI parantezari true de la k+1 la j PLUS
    parantezari true de la i la k ORI parantezari false de la k+1 la j PLUS
    parantezari false de la i la k ORI parantezari true de la k+1 la j.

Mai sus, prin parantezari intelegem parantezari booleane, eventual complexe – exemple: T; T or F, ((T or F) and T) etc. Practic, se însumează produse care reprezintă combinații din tabelele de adevăr ale funcțiilor.
Factorul din stânga/dreapta reprezintă expresia din stânga/dreapta a unei perechi de expresii care împreună formează o nouă parantezare (combinație de paranteze).

O formulă generală de calcul al lui A[i][j] care se obține din posibilele combinații din tabelele de adevăr de mai jos este:
A[i][j] = T[i][j] + F[i][j] = T[i][k] * T[k+1][j] + T[i][k] * F[k+1][j] + F[i][k] * T[k+1][j] + F[i][k] * F[k+1][j].

Dacă i == j, A[i][j] este răspunsul la întrebarea „Câte parantezări sunt posibile dintr-o singură valoare booleană?”, dacă i != j, se aplică formulele de recurență.

Tabelele de adevăr ale operațiilor logice folosite:

AND (ȘI)
0
1
0
0
0
1
0
1

OR (SAU)
0
1
0
0
1
1
1
1

XOR (SAU EXCLUSIV)
0
1
0
0
1
1
1
0

Pentru exemplul dat (paran.in & paran.out), cele 3 matrice rezultat sunt (se afișează doar diagonalele principale și elementele care sunt deasupra ei):

T

  1 1 1
    0 0
      0

F

  0 0 1
    1 1
      1

A

  1 1 2
    1 1
      1

După cum se vede, valorile matricei T și cele ale matricei F sunt complementare una alteia.

Execuția pas cu pas

La citirea datelor,
N devine 3,
S devine [1, 0, 0] și
op devine [-2, -1] (lungimea lui op este lungimea lui S, – 1).

Se creează 2 matrice, T (numele vine de la True) și F (numele vine de la False), de dimensiuni N ori N, care se completează astfel:

1. toate celulele matricelor (eventual doar cele din diag. princip. și de deasupra) se inițializează cu 0.
2. toate celulele din diagonala principala a lui T se initializeaza cu S[i] si cele din diagonala principala a lui F se initializeaza cu 1 – S[i] (echivalent cu 1 – T[i][i]).
3. ultimul pas este parcurgerea celulelor în felul de mai jos și aplicarea formulelor de recurență din figura întâi:

i = N – 1 = 3 – 1 = 2

> j = 1
    pt. fiecare k de la i = 2 la j – 1 = 0, crescator
       [nu se execută] 

> j = 2
    pt. fiecare k de la i = 2 la j – 1 = 1
       [nu se execută]
> j = 3
    pt. fiecare k de la i = 2 la j – 1 = 2 [1 pas]
       > k = 2
           op[k] = -1 (AND)
           => T[i][j] (T[2][3]) = T[2][2] * T[3][3] = 0 * 0 = 0
              F[i][j] = A[2][2] * A[3][3] – T[2][3] = 1 * 1 – 0 = 1

i = 2 – 1 = 1

> j = 1
    pt. fiecare k de la i = 1 la j – 1 = 0
        [nu se executa]

> j = 2
    pt. fiecare k de la i = 1 la j – 1 = 1 [1 pas]
        > k = 1
           op[k] = -2 (OR)
           => T[1][2] = T[1][1] * T[2][2] = 1
              F[1][2] = F[1][1] * F[2][2] = 0 * 1 = 0

> j = 3
    pt. fiecare k de la i = 1 la j – 1 = 2
        > k = 1
           op[k] = -2 (OR)
           => T[1][3] = A[1][1] * A[2][3] – F[1][1] * F[2][3] = 1 * 1 – 0 * 1 = 1
              F[1][3] = F[1][1] * F[2][3] = 0 * 1 = 0
        > k = 2
           op[k] = -1 (AND)
           => T[1][3] = T[1][2] * T[3][3] = 1 * 0 = 0
              F[1][3] = A[1][2] * A[3][3] – T[1][2] * T[3][3] = 1 * 1 – 1 * 0

i = 1 – 1 = 0 < 1, sfarsit.

Matricile T și F se calculează doar pentru valorile de deasupra diagonalei principale, din colțul din dreapta jos a matricei, în zig-zag până sus.

Eu nu am găsit problema aceasta pe infoarena.ro.

Codul meu sursă

#include
using namespace std;

const int maxn = 101;

void citire(int &N, int S[maxn],
       int op[maxn], ifstream &in)
{
       in >> N;
       for (int i = 1; i <= N; ++i)
       {
              in >> S[i];
       }
       // op[i] = operatorul dintre simbolul i si i + 1
       for (int i = 1; i <= N – 1; ++i)
       {
              in >> op[i];
       }
}

void paran(int N, int S[], int op[],
       int T[][maxn], int F[][maxn])
{
       for (int i = 1; i <= N; ++i)
       {
              for (int j = 1; j <= N; ++j)
              {
                     T[i][j] = F[i][j] = 0;
              }
       }

       for (int i = 1; i <= N; ++i)
       {
              T[i][i] = S[i];
              F[i][i] = 1 – T[i][i];
       }

       // atentie la sensul parcurgerii
       for (int i = N – 1; i >= 1; –i)
       {
              for (int j = 1; j <= N; ++j)
              {
                     for (int k = i; k < j; ++k) // exclus j
                     {
                           int aik = T[i][k] + F[i][k],
                                  akp1j = T[k + 1][j] +
                                  F[k + 1][j];
                           if (op[k] == -1) // and
                           {
                                  T[i][j] += T[i][k] * T[k + 1][j];
                                  F[i][j] += aik * akp1j – T[i][k] *
                                         T[k + 1][j];
                           }
                           else if (op[k] == -2) // or
                           {
                                  T[i][j] += aik * akp1j –
                                         F[i][k] * F[k + 1][j];
                                  F[i][j] += F[i][k] * F[k + 1][j];
                           }
                           else // xor
                           {
                                  T[i][j] += T[i][k] * F[k + 1][j] +
                                         F[i][k] * T[k + 1][j];
                                  F[i][j] += F[i][k] * F[k + 1][j] +
                                         T[i][k] * T[k + 1][j];
                           }
                     }
              }
       }
}

int main()
{
       int N, S[maxn], op[maxn];
       int T[maxn][maxn], F[maxn][maxn];

       ifstream in(„paran.in”);
       citire(N, S, op, in);
       in.close();

       ofstream out(„paran.out”);
       paran(N, S, op, T, F);
       out << T[1][N] << endl;
       out.close();

       return 0;
}

Dacă se înlocuiește acest rând de mai sus din funcția main:

out << T[1][N] << endl;
cu următorul fragment de cod, programul afișează ce este deasupra diagonalelor principale și pe diagonalele principale din matricele T, F și A (se afișează frumos doar când numărul de parantezări este de o singură cifră).

out << ‘T’ << endl;
for (int i = 1; i <= N; ++i)
{
       for (int j = 1; j <= i; ++j)
       {
              out << ‘ ‘ << ‘ ‘;
       }
       for (int j = i; j <= N; ++j)
       {
              out << T[i][j] << ‘ ‘;
       }
       out << endl;
}

out << ‘F’ << endl;
for (int i = 1; i <= N; ++i)
{
       for (int j = 1; j <= i; ++j)
       {
              out << ‘ ‘ << ‘ ‘;
       }
       for (int j = i; j <= N; ++j)
       {
              out << F[i][j] << ‘ ‘;
       }
       out << endl;
}

out << ‘A’ << endl;
for (int i = 1; i <= N; ++i)
{
       for (int j = 1; j <= i; ++j)
       {
              out << ‘ ‘ << ‘ ‘;
       }
       for (int j = i; j <= N; ++j)
       {
              out << (T[i][j] + F[i][j]) << ‘ ‘;
       }
       out << endl;
}

Capturi de ecran

[C# WinForms] TableLayoutPanel (via Dot Net Perls, cu adăugiri)

TableLayoutPanel (panou de așezare în formă de tabel) poziționează controale. Cerem o interfață grafică pentru utilizator atractivă și funcțională care se redimensionează corect când utilizatorii schimbă dimensiunea ferestrei.

Mai întâi, pentru a face un TableLayoutPanel, extindeți cutia cu unelte (en. toolbox) din stânga. Faceți dublu-clic pe pictograma TableLayoutPanel din stânga, și apoi deschideți panoul Properties (tradus „Proprietăți”) din dreapta [jos].

Panou din 4 secțiuni. Ar trebui să vedeți un panou din 4 celule. Va trebui să modificați numărul de coloane și de rânduri. Și apoi veți putea schimba întinderile pe rânduri și întinderile pe coloane [proprietățile RowSpan și respectiv ColumnSpan].

Proprietăți. Anchor [proprietate, în acest caz, a controalelor din TableLayoutPanel, în română: ancore] este folosit pentru a alinia, a extinde, sau a umple un control. ColumnCount este folosit pentru a specifica numărul de coloane. RowCount este folosit pentru a specifica numărul de rânduri – adăugați unul pentru a obține un nou rând în partea de jos [a tabelului].

Anchor. Când faceți clic pe spațiul din dreapta lui Anchor în panoul de proprietăți din dreapta [când un control din TableLayoutPanel este selectat], veți vedea o cutie care seamănă cu un +. Faceți clic pe dreptunghiuri pentru a ancora de marginea respectivă [a celulei].

TextBox. Pentru a crea un TextBox multilinie care umple întreaga celulă, setați TextBox-ul ca multilinie. Adăugați Top (Sus) și Bottom (Jos) în meniul Anchor făcând clic pe partea de sus și pe partea de jos a +ului.
TextBox [EN]

Rezolvarea problemelor de schemă (en. layout). TableLayoutPanel poate rezolva multe dintre problemele dvs. de aliniere ale controalelor. TableLayoutPanel este flexibil și poate îmbunătăți cu foarte mult interfețele.

Cu toate acestea, el cere o etapă de planificare înainte de a trage controale în formularul (en. form) dvs. TableLayoutPanel este mai ușor de menținut. Această etapă de planificare merită făcută.

O schemă rigidă face viața grea pentru dvs., ca designer, și pentru utilizator care încearcă să folosească programul într-o puțin diferită configurație. TableLayoutPanel elimină aceste probleme.


Conținutul de mai sus este tradus de pe https://www.dotnetperls.com/tablelayoutpanel, cu adăugiri între paranteze drepte. Acesta este un link la documentația oficială a Microsoft pentru controlul container TableLayoutPanel. Am adăugat și capturi de ecran Visual Studio de-a lungul articolului și câteva mai jos.

Dacă faceți clic-dreapta pe spațiu neumplut al TableLayoutManager, puteți alege din meniul contextual opțiunea „Edit Rows and Columns…” (tradus „Editați Rânduri și Coloane…”) și vi se va deschide o fereastră de editare a unor proprietăți importante ale fiecărui rând/fiecărei coloană. Aceeași fereastră se deschide dacă dați clic pe butoanele din dreapta proprietății Columns sau Rows în panoul Properties după selectarea TableLayoutManager-ului.

Iată fereastra:


În această fereastră, în dreapta lui „Show:”, se poate selecta ce se afișează în ListBox-ul de sub „Show:”: Columns (coloanele) sau Rows (rândurile). Cu butoanele de sub ListBox se pot adăuga (Add), șterge (Delete) sau insera (Insert) coloane sau rânduri: Add adaugă un element (rând sau coloană) după toate elementele existente (ca ultim element al ListBox-ului), Insert inserează un element deasupra elementelor selectate (în total inserează unul) și Delete șterge elementele selectate. Se pot selecta mai multe elemente din ListBox folosind Ctrl + clic stânga. Butoanele Delete și Insert nu funcționează fără cel puțin un element selectat, spre deosebire de Add. Când nr. de coloane sau rânduri scade sub nr. necesar pt. afișarea controalelor deja inserate în TableLayoutManager, el revine automat la o valoare acceptabilă. În dreapta, se poate selecta cum se afișează în designer (și programul final) ce e selectat în ListBox: dacă Absolute este selectat, se specifică exact cât de lată să fie coloana (sau înalt, dacă e vorba de rând) printr-un nr. fix de pixeli. Dacă Percent este selectat, coloana va ocupa procentul introdus din lățimea totală a TableLayoutManager-ului (sau înălțimea, dacă e vorba de rând). Dacă AutoSize este selectat, TableLayoutManager-ul va cere fiecărui control, dintre celulele conținute de rândul selectat sau de coloana selectată, dimensiunile de care au nevoie și le va acorda acest spațiu dacă este posibil, și dacă nu, le va decupa.

În exemplul de mai sus, am setat Anchor la TableLayoutPanel (nu la unul din controalele din el) la „Top, Bottom, Left, Right” ceea ce înseamnă că se va redimensiona odată cu fereastra, păstrând aceeași distanță a laturilor sale față de laturile ferestrei ce-l conține.

La execuția programului, arată astfel:

După redimensionarea ferestrei, arată astfel:

Se observă cum TextBox-ul multilinie se întinde pe toată înălțimea celulei în care este pus.

[C++, algoritmică] Distanța Levenshtein cu reconstrucția pașilor de editare

Enunțul problemei:

Se dau 2 șiruri de caractere A și B, formate din litere mici ale alfabetului englez. Asupra șirului A putem face trei operații: 1. inserăm, 2. ștergem, 3. înlocuim un caracter. Se cere determinarea numărului minim de operații necesare transformării șirului de caractere A în șirul de caractere B.

Ca inspirație, cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo.

Programul de mai jos, scurtat și modificat, obține 30 de puncte pe infoarena.ro (la 3 teste obține 10 puncte la fiecare, la restul eroarea „Killed by signal 11(SIGSEGV).”, și nu din cauza utilizării de prea multă memorie).

Fișierul de intrare

Lungimile celor 2 șiruri de caractere vor fi determinate automat.

lev.in:
kitten
sitting

Fișierul de ieșire

Conține matricea creată prin programare dinamică, D, apoi numărul minim de pași de editare necesari, apoi pe fiecare rând câte un pas de editare sub forma „Inlocuire X cu Y”, „Inserare X” sau „Stergere X”, unde X si Y sunt caractere ale alfabetului englez.

lev.out:
1 2 3 4 5 6 7
2 1 2 3 4 5 6
3 2 1 2 3 4 5
4 3 2 1 2 3 4
5 4 3 2 2 3 4
6 5 4 3 3 2 3
3
Inlocuire k cu s
Inlocuire e cu i
Inserare g

Codul sursă

Source.cpp:
#include
#include
#include
using namespace std;

const int maxn = 101;

int min(int a, int b)
{
    return a < b ? a : b;
}

void levenshtein(const string &A, const string &B,
    int D[maxn][maxn], ofstream &out)
{
    for (int i = 0; i <= A.length(); ++i)
        D[i][0] = i;
    for (int j = 0; j <= B.length(); ++j)
        D[0][j] = j;
    for (int i = 1; i <= A.length(); ++i)
    {
        for (int j = 1; j <= B.length(); ++j)
        {
            if (A[i – 1] == B[j – 1])
                D[i][j] = D[i – 1][j – 1];
            else
                D[i][j] = 1 + min(
                    min(D[i][j – 1],
                        D[i – 1][j]),
                        D[i – 1][j – 1]
                );
            out << D[i][j] << ' ';
        }
        out << endl;
    }

    out << D[A.length()][B.length()] << endl;
}

void reconst(const string &A, const string &B,
    int D[maxn][maxn], ofstream &out)
{
    stack st;

    int i = A.length(), j = B.length();
    while (true)
    {
        string o;
        if (i – 1 < 0 && j – 1 < 0)
        {
            // inceputurile sirurilor
            // coincid
            break;
        }
        else if (i – 1 < 0)
        {
            o = „Inserare „;
            o += B[j – 1];
            st.push(o);
            break;
        }
        else if (j – 1 < 0)
        {
            o = „Stergere „;
            o += A[i – 1];
            st.push(o);
            break;
        }
        else
        {
            if (A[i – 1] == B[j – 1])
            {
                i = i – 1;
                j = j – 1;
                // caractere identice
            }
            else
            {
                if (D[i][j] – 1 == D[i][j – 1])
                {
                    j = j – 1;
                    o = „Inserare „;
                    o += B[j];
                }
                else if (D[i][j] – 1 == D[i – 1][j])
                {
                    i = i – 1;
                    o = „Stergere „;
                    o += B[j];
                }
                else // if (D[i][j] – 1 == D[i – 1][j – 1])
                {
                    i = i – 1;
                    j = j – 1;

                    o = „Inlocuire „;
                    o += A[i];
                    o += ” cu „;
                    o += B[j];
                }
                st.push(o);
            }

            if (i < 0 || j < 0) break;
        }
    }

    while (!st.empty())
    {
        out << st.top() << endl;
        st.pop();
    }
}

int main()
{
    string A, B;
    int D[maxn][maxn];

    ifstream in(„lev.in”);
    in >> A >> B;
    in.close();

    ofstream out(„lev.out”);
    levenshtein(A, B, D, out);
    reconst(A, B, D, out);
    out.close();

    return 0;

Capturi de ecran

Fișier de intrare

 Fișier de ieșire

 Codul sursă

[C#] Validarea și procesarea CNP-urilor

CNP = cod numeric personal. (la acest Link e descris și formatul)

Cea mai ușoară metodă este să verific că:
1. șirul de caractere are lungimea exactă de 13;
2. fiecare caracter este o cifră;
3. cifra de control este corectă (secțiunea C);
4. secțiunea S este validă;
5. secțiunea AA;
6. secțiunea LL;
7. secțiunea ZZ;
8. secțiunea JJ;
9. secțiunea NNN (e mai puțin probabil să fie invalidă, deci este verificată la sfârșit).

Sumar

În designer realizez un simplu Form cu un TextBox numit tbCNP și un buton numit btnAnalizeaza. Codul din spate este modularizat: o clasă AnalizaCNP cu câmpurile publice
int S, AA, AAAA, LL, ZZ, JJ, NNN, CDat, CRecalculat (până aici au numele similare titlurilor de secțiune din articolul Wikipedia); string CNP, string Sex, Nascut, Luna, Judet; bool CEsteCorect, CNPValid. Clasa conține și metodele NumeLunaDinNumar, NumeJudetDinCodJudet și ToString (cea din urmă e supraîncărcată). Pentru validarea unui CNP sau afișarea informațiilor despre el, sunt necesare la final doar 2 rânduri de cod. Codul din spate mai conține rânduri care fac butonul acționabil cu tasta Enter/Return și focalizarea inițială a TextBox-ului la pornire (cursorul de introducere de text să fie inițial în TextBox).

Sub cod sunt capturi de ecran.

Codul

using System;
using System.Windows.Forms;

namespace cs_validare_cnp
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        ///

        /// Campurile CDat, CRecalculat si CEsteCorect se refera
        /// la cifra de control.
        ///

        public class AnalizaCNP
        {
            public string CNP;
            public int S, AA, AAAA, LL, ZZ, JJ, NNN, CDat, CRecalculat;
            public string Sex, Nascut, Luna, Judet;
            public bool CEsteCorect, CNPValid;

            public string NumeLunaDinNumar(int luna)
            {
                string s;
                switch (luna)
                {
                    case 1:
                        s = „ianuarie”;
                        break;
                    case 2:
                        s = „februarie”;
                        break;
                    case 3:
                        s = „martie”;
                        break;
                    case 4:
                        s = „aprilie”;
                        break;
                    case 5:
                        s = „mai”;
                        break;
                    case 6:
                        s = „iunie”;
                        break;
                    case 7:
                        s = „iulie”;
                        break;
                    case 8:
                        s = „august”;
                        break;
                    case 9:
                        s = „septembrie”;
                        break;
                    case 10:
                        s = „octombrie”;
                        break;
                    case 11:
                        s = „noiembrie”;
                        break;
                    case 12:
                        s = „decembrie”;
                        break;
                    default:
                        s = „luna necunoscuta”;
                        break;
                }
                return s;
            }

            public string NumeJudetDinCodJudet(int codInt)
            {
                string cod = codInt >= 10 ?
                    codInt.ToString() :
                    $”0{codInt}”;
                // Copy-Paste la tabelul din pagina Wikipedia CNP
                string coduri = @”01  Alba
02  Arad
03  Argeș
04  Bacău
05  Bihor
06  Bistrița – Năsăud
07  Botoșani
08  Brașov
09  Brăila
10  Buzău
11  Caraș – Severin
12  Cluj
13  Constanța
14  Covasna
15  Dâmbovița
16  Dolj
17  Galați
18  Gorj
19  Harghita
20  Hunedoara
21  Ialomița
22  Iași
23  Ilfov
24  Maramureș
25  Mehedinți
26  Mureș
27  Neamț
28  Olt
29  Prahova
30  Satu Mare
31  Sălaj
32  Sibiu
33  Suceava
34  Teleorman
35  Timiș
36  Tulcea
37  Vaslui
38  Vâlcea
39  Vrancea
40  București
41  București – Sector 1
42  București – Sector 2
43  București – Sector 3
44  București – Sector 4
45  București – Sector 5
46  București – Sector 6
51  Călărași
52  Giurgiu”;
                try
                {
                    string judet = coduri.Split(‘\n’)[codInt – 1]
                        .Split(new string[] { ”  ” },
                            StringSplitOptions.RemoveEmptyEntries)[1].Trim();
                    return judet;
                }
                catch (Exception)
                {
                    return „”;
                }
            }

            public override string ToString()
            {
                AnalizaCNP a = this;

                return a.CNPValid ?
                    $@”CNP: {a.CNP}
S: {a.S} AA/AAAA: {a.AA}/{a.AAAA} LL: {a.LL} ZZ: {a.ZZ} JJ: {a.JJ} NNN: {a.NNN} C dat: {a.CDat}, C recalculat: {a.CRecalculat}
Sex: {a.Sex}
Nascut: {a.Nascut}
Luna: {a.Luna}
Judet: {a.Judet}
C este corect: {a.CEsteCorect}” :
„CNP invalid.”;
            }

            ///

            /// CNP-ul dat poate fi inconjurat de spatii,
            /// acestea vor fi sterse.
            ///

            ///
            public AnalizaCNP(string cnp)
            {
                CNP = cnp.Trim();

                // lungime corecta
                CNPValid = CNP.Length == 13;
                if (!CNPValid)
                {
                    return;
                }

                try
                {
                    CDat = Convert.ToInt32(cnp.Substring(12), 10);

                    string ctrl = „279146358279”;
                    int suma = 0;
                    for (int i = 0; i < 12; ++i)
                    {
                        int cifra1 = cnp[i] – ‘0’;
                        int cifra2 = ctrl[i] – ‘0’;
                        int produs = cifra1 * cifra2;
                        suma += produs;
                    }
                    if (suma % 11 == 10)
                    {
                        CRecalculat = 1;
                    }
                    else
                    {
                        CRecalculat = suma % 11;
                    }

                    CEsteCorect = CRecalculat == CDat;
                    if (!CEsteCorect)
                    {
                        CNPValid = false;
                        return;
                    }

                    S = int.Parse(cnp.Substring(0, 1));

                    if (S == 1 || S == 3 ||
                        S == 5 || S == 7)
                    {
                        Sex = „masculin”;
                    }
                    else
                    {
                        Sex = „feminin”;
                    }

                    if (S == 1 || S == 2)
                    {
                        Nascut = „intre 1 ianuarie 1900 si 31 decembrie 1999”;
                    }
                    else if (S == 3 || S == 4)
                    {
                        Nascut = „intre 1 ianuarie 1800 si 31 decembrie 1899”;
                    }
                    else if (S == 5 || S == 6)
                    {
                        Nascut = „intre 1 ianuarie 2000 si 31 decembrie 2099”;
                    }
                    else if (S == 7 || S == 8)
                    {
                        Nascut = „persoana straina rezidenta in Romania”;
                    }
                    else
                    {
                        CNPValid = false;
                        return;
                    }

                    AA = int.Parse(cnp.Substring(1, 2));
                    AAAA = AA;

                    if (S == 1 || S == 2)
                        AAAA += 1900;
                    else if (S == 3 || S == 4)
                        AAAA += 1800;
                    else // 5 sau 6 sau rezidenti (7 sau 8)
                        AAAA += 2000;

                    LL = Convert.ToInt32(cnp.Substring(3, 2));
                    if (LL > 12 || LL < 1)
                    {
                        CNPValid = false;
                        return;
                    }
                    Luna = NumeLunaDinNumar(LL);

                    ZZ = Convert.ToInt32(cnp.Substring(5, 2), 10);
                    if (DateTime.DaysInMonth(AAAA, LL) < ZZ)
                    {
                        CNPValid = false;
                        return;
                    }

                    JJ = Convert.ToInt32(cnp.Substring(7, 2), 10);
                    Judet = NumeJudetDinCodJudet(JJ);

                    NNN = Convert.ToInt32(cnp.Substring(9, 3), 10);
                }
                catch (Exception)
                {
                    CNPValid = false;
                }
            }
        }

        private void btnAnalizeaza_Click(object sender, EventArgs e)
        {
            AnalizaCNP a = new AnalizaCNP(tbCNP.Text);
            MessageBox.Show(a.ToString());
        }

        private void Form1_Load(object sender, EventArgs e)
        {
            ActiveControl = tbCNP;
        }

        private void tbCNP_KeyPress(object sender, KeyPressEventArgs e)
        {
            if (e.KeyChar == (char)Keys.Return)
            {
                btnAnalizeaza.PerformClick();
            }
        }
    }
}

Capturi de ecran

 O parte din codul din spate:



 La rularea programului (CNP aleator: 6750821105927):

Documentație oficială

Dau link-uri la documentația oficială Microsoft pentru metodele folosite:

– clasa controlului TextBox;
– clasa controlului Form;
– metoda supraîncărcată Object.ToString;
– metoda String.Split și enumerarea StringSplitOptions;
string-uri textuale (cu @, en. „verbatim”);
string-uri interpolate (cu $);
– metoda int.Parse;
– metoda Convert.ToInt32;
– proprietatea ContainerControl.ActiveControl;
– metoda MessageBox.Show;
– metoda Button.PerformClick;
– metoda DateTime.DaysInMonth.

[C#] Cum să redai un fișier audio WAV incorporat într-o resursă?

Metoda prezentată în acest articol este funcțională și în proiecte WinForms dar și în cele WPF.

// la începutul fișierului de cod-din-spate
// trebuie pus acest rând dacă nu există deja:
using System.Media;

Putem folosi metoda Load sau LoadAsync pentru a încărca fișierul wav înainte de redarea lui și intercepta evenimentul LoadCompleted pentru a acționa după încărcarea fișierului audio (din testele mele, acest eveniment este apelat doar când se oferă un Stream, nu un nume de fișier, și nu este apelat când încărcarea dă eroare), dar metodele Play, PlaySync și PlayLooping fac asta automat înainte de redare.

Dorim ca fișierul audio să fie preluat din dosarul executabilului

Adăugăm fișierul WAV la proiect prin meniul Project > Add Existing Item… apoi îl selectăm în Solution Explorer și în panoul Properties atribuim proprietății cu numele Copy to Output Directory valoarea Copy if newer.

// în metoda handler la clic pe un buton se pun următoarele rânduri
SoundPlayer p = new SoundPlayer(„nume_fisier.wav”);
p.PlayLooping(); // repetă la infinit sunetul; alternativ: p.Play() care nu redă repetat sau p.PlaySync() care blochează firul de execuție până la finalizarea redării

În cazul încărcării asincrone prin LoadAsync (care ajută la fișiere mari, dar am adăugat un fișier WAV de aprox 700MB la proiect și s-a blocat, la repornire nu era fișierul în proiect), poate fi folositor să declarăm variabila p (de tip SoundPlayer) la nivelul clasei (de ex. Form1).

Sau dorim fișierul audio incorporat în fișierul executabil

Adăugăm fișierul WAV la proiect prin meniul Project > Add Existing Item… apoi îl selectăm în Solution Explorer și în panoul Properties atribuim proprietății cu numele Build Action (ro. Acțiunea la construire) valoarea Embedded Resource (ro. Resursă incorporată). Proprietatea cu numele Copy to Output Directory nu mai are relevanță în acest exemplu.

Dacă setăm Copy to Output Directory la valoarea Do not copy, la următoarea compilare (construcție sau en. build), fișierul audio nu va mai fi în directorul bin/Debug (unde se află executabilul generat de obicei), dar datorită proprietății Build Action va fi conținut de executabil.

În exemplul acesta numele fișierului audio este chimes.wav, fișier preluat din link-ul de mai jos. În fereastra de proprietăți ale proiectului (clic-dreapta pe proiect în panoul Solution Explorer, apoi în meniul apărut se selectează Properties) se caută în secțiunea Application setarea „Default namespace” (spațiul de nume implicit al proiectului). În cazul exemplului, aceasta are valoarea „cs_soundplayer_test”.

System.Reflection.Assembly a =
    System.Reflection.Assembly.GetExecutingAssembly();
System.IO.Stream s =

    a.GetManifestResourceStream(„cs_soundplayer_test.chimes.wav”);
SoundPlayer p = new SoundPlayer(s); // nu c-torul încarcă fluxul WAV în memorie ci apelul de mai jos:
p.PlayLooping();

Capturi de ecran


Secvențele de cod din acest articol au fost testate pe Windows 10 cu .NET Framework 4.6.1.

Inspirație [EN]:

Sunetele implicite din Windows 7 pot fi descărcate de aici: https://winsounds.com/windows-7-default-sounds/.

Documentație oficială [EN]: https://msdn.microsoft.com/en-us/library/system.media.soundplayer(v=vs.110).aspx.

[C# WinForms] ComboBox (via Dot Net Perls)

ComboBox este o cominație de TextBox cu un meniu drop-down. Lista sa drop-down preintă variante prealese. Utilizatorul poate tasta orice în ComboBox. Alternativ, el sau ea poate selecta ceva din listă.

Pentru a începe, creează o nouă aplicație Windows Forms și adaugă-i un ComboBox. Poți apoi face clic-dreapta pe ComboBox și adăuga handlere la evenimentele SelectedIndexChanged și TextChanged în panoul Properties (Proprietăți).

Program:
Când schimbi textul tastând în ComboBox sau făcând clic pe lista de elemente (Items), handlerele de evenimente sunt declanșate

Items:
Vezi secțiunea despre proprietatea Items înainte de a rula programul. Cu Items noi adăugăm șiruri de caractere (string-uri) la ComboBox.

Bazat pe: .NET (2018)

Program C# care demonstrează handlerele de evenimente ale ComboBox
 
using System;
using System.Windows.Forms;

namespace cs_winforms_combobox
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}

int _selectedIndex;
string _text;

private void comboBox1_SelectedIndexChanged(object sender, EventArgs e)
{
// Apelat când un nou indice este selectat.
_selectedIndex = comboBox1.SelectedIndex;
Display();
}

private void comboBox1_TextChanged(object sender, EventArgs e)
{
// Apelat oricând textul se schimbă.
_text = comboBox1.Text;
Display();
}

void Display()
{
this.Text = string.Format("Text: {0}; SelectedIndex: {1}",
_text,
_selectedIndex);
}
}
}
 

Text. Proprietatea Text a ComboBox funcționează în mare parte ca proprietatea Text a unui TextBox. Dacă atribui proprietății Text, valoarea ccurentă din ComboBox se va schimba. Tu poți de asemenea citi proprietatea Text și să atribui variabile ei.

Tip:
Pentru a-l goli, poți să îi atribui un șir de caractere literal gol. Aceasta este o cale efectivă de a goli multe proprietăți.
Empty String [EN]
String Literal [RO]

Items. Proprietatea Items conține șiruri de caractere care sunt situate în partea drop-down a ComboBox-ului. Poți tasta Item-urile rând cu rând în Visual Studio prin fereastra de dialog Items, sau poți să le adaugi dinamic în timpul execuției.

Tip:
Pentru a adăuga Item-uri, apelez metoda Add: folosește sintaxa comboBox1.Add(„Valoare”). Poți de asemenea goli („Clear”) ComboBox-ul cu Clear().

Utilizarea dialogului. Conceptual, ComboBox-ul este folosit pentru a reprezenta introducere de text cu un set de valori asociate predefinite care sunt ușor de selectat. Pentru acest motiv, este o alegere bună pentru dialoguri de preferințe.

Poți folosi controale ComboBox și avea valori presetate care sunt prezente în meniurile drop-down, dar să permiți utilizatorilor să selecteze orice valoare tastând-o direct înăuntru. Asta evită nevoia pentru mai mult de un control.

AutoComplete. Există 3 proprietăți pentru AutoComplete în ComboBox: AutoCompleteCustomSource, AutoCompleteMode, și AutoCompleteSource. Proprietatea AutoCompleteMode poate fi setată să sugereze, să adauge sau ambele.

Și:
Proprietățile Source îți permit să specifici setul de șiruri de caractere care sunt folosite ca sugestii.

Stiluri DropDown. Există 3 proprietăți de stil DropDown. Ele sunt DropDownHeight, DropDownStyle și DropDownWidth. Proprietățile DropDownHeight și DropDownWidth par a nu afecta aspectul vizual. Windows își folosește widget-urile implicite.

De asemenea:
Poți elimina drop-down-ul în întregime (cu Simple), sau să-l faci ca textul să nu fie editabil (cu DropDownList).

MaxDropDownItems. Această proprietate setează nr. maxim de elemente vizibile în drop-down. Nu are efect când IntegralHeight este setată la true. Dar dacă IntegralHeight este false, limitează nr. de elemente vizibile (o bară de glisare poate apărea).

Notă:
Mulțumiri lui Clarence Ravel pentru a arăta că MaxDropDownItems are un efect pentru un fals IntegralHeight.

Sumar:
Controlul ComboBox combină TextBox și un meniu listă drop-down. Reprezintă un widget hibrid folositor în Windows Forms. Este ideal pentru dialoguri unde unele sugestii pentru o intrare ar putea fi știute, dar orice valoare trebuie acceptată.

Recenzie:
ComboBox poate simplifica interfața ta prin unirea controalelor de interfață pentru utilizator.

Tradus de pe https://www.dotnetperls.com/combobox. Link la documentația oficială Microsoft a controlului ComboBox. Am adăugat și câteva capturi de ecran din Visual Studio:

Evenimentele ComboBox:




Proprietatea Items:




Programul în execuție:



[C#] Șir de caractere literal: linie-nouă și ghilimele (via Dot Net Perls)

Șir de caractere literal (en. String literal). Acesta constă în date constante sub forma unui șir de caractere. Datele șir de caractere sunt create în moduri diferite. Noi folosim literalele ca argumente la metode, sau oriunde un șir de caractere este cerut.

Cu un șir de caracter literal, caracterele sunt stocate direct în metadate. Mai puține ocoluri (care reduc performanța) sunt necesare.

Acest program conține șiruri de caractere literale. Șirurile de caractere literale la nivel de clasă sunt reprezentate ca referințe static sau const. Cele la nivel de metodă sunt tratate separat în metadate.
Static [EN]

Apoi:
Programele demonstrează literalele. Are caractere linie-nouă, tab-uri și ghilimele în literali.

Linii noi:
Acestea sunt specificate fie cu „\r\n” sau doar „\n”. Și tab-urile sunt specificate cu „\t”.

Ghilimelele:
Pentru ghilimele, noi folosim deseori un „backslash” (bară oblică înclinată spre stânga: „\”), dar pentru un literal textual (en. „verbatim”) (prefixat cu @), noi folosim două ghilimele pentru a ne referi la o ghilimea.

Program bazat pe .NET 2018:
Program C# care folosește șiruri de caractere literale

using System;

class Program
{
static string _value1 = "String literal";
const string _value2 = "String literal 2";
const string _value3 = "String literal 3\r\nAnother line";
const string _value4 = @"String literal 4
Another line";

const string _value5 = "String literal\ttab";
const string _value6 = @"String literal\ttab";

static void Main()
{
//
// Motorul de execuție începe aici.
//
string test1 = "String literal \"1\"";
const string test2 = "String literal 2";
string test3 = @"String literal ""3""";
const string test4 = @"String literal 4";
//
// Afișează șirurile de caractere literale.
//
Console.WriteLine(
"{0}\n{1}\n{2}\n{3}\n{4}\n{5}\n{6}\n{7}\n{8}\n{9}",
_value1, _value2, _value3, _value4, _value5, _value6,
test1, test2, test3, test4);
}
}
 
Ieșire

String literal
String literal 2
String literal 3
Another line
String literal 4
Another line
String literal tab
String literal\ttab
String literal "1"
String literal 2
String literal "3"
String literal 4
 

Notă la programul de mai sus. Prima referință către șir literal este o variabilă statică, ceea ce înseamnă că va fi referită, în limbajul intermediar generat, în corpul metodelor unde este folosită.

Notă:
Folosind șirul de caractere static va cere motorului de execuție să rezolve simbolul _value1 în metadate.
Static String [EN]

Cu toate acestea:
Poți să reatribui variabilei _value1 oriunde în programul tău unde este accesibilă, cum ar fi în metoda Main.

Simbolul Arond. Patru dintre șirurile literale sunt prefixate cu simbolul @ înainte de semnele de citare. Acest simbol indică faptul că tu folosești sinaxa de șir literal textual.

Sfat:
Poți vedea că backslash-ul este tratat ca un caracter și nu o secvență de șir de evacuare când @ este folosit.

De asemenea:
Compilatorul C# îți permite să folosești linii noi reale în literalii textuali. Trebuie să codifici semnele de citare cu ghilimele duble.

Concat. Concatenarea variabilelor șiruri de caractere este făcută în timpul execuției („runtime”). Dar dacă o variabilă șir de caractere este constantă, compilatorul va genera limbaj intermediar cu concatenările eliminate.

Apoi:
Acest program pare a concatena 3 șiruri de caractere. Când este compilat IL arată că doar un singur șir este folosit.
string.Concat [EN]

Program C# care concatenează șiruri de caractere literale
using System;

class Program
{
static void Main()
{
const string a = "Dot ";
const string b = "Net ";
const string c = "Perls";
Console.WriteLine(a + b + c);
}
}
 
Ieșire
Dot Net Perls

Limbaj intermediar: IL
.method private hidebysig static void  Main() cil managed
{
.entrypoint
// Code size 11 (0xb)
.maxstack 8
IL_0000: ldstr "Dot Net Perls"
IL_0005: call void [mscorlib]System.Console::WriteLine(string)
IL_000a: ret
} // end of method Program::Main

Metadate. Șirurile de caractere literale sunt stocate în format metadate. Acesta este definit în Specificația Limbajului Comun. El include o baza de date cu tabele cu antete și rânduri în toate fișierele exe.

Sfat:
Există câteva fluxuri predefinite în fișierele cu metadate , inclusiv #Strings și #US („user strings” – șiruri ale utilizatorului).

Fluxul #US este folosit pentru a stoca literali definiți de programator. Tabelele de metadate conțin ofseturi către acest flux. Fluxul însuși este o serie concatenată de caractere.

Notă:
Motorul de execuție reține ofseturile și tabelele în memorie și apoi citește un interval în fluxul #US.

Performanța. Înainte ca literalii șiruri de caractere să ajungă în metadate sau în instrucțiunile limbajului intermediar, compilatorul C# aplică o optimizare numită împăturirea constantelor („constant folding”).

Aici:
Constantele de tip șir de caractere literal sunt separate și partajate. Aplicarea împăturirii constantelor manual nu este cerută pentru eficiență.

Stocare:
Dacă folosești un anumit șir de caractere literal într-un program, el este stocat doar o singură dată în fluxul de șiruri de caractere ale utilizatorului („user strings stream”).

În concluzie:
Vedem tehnica compilatorului numită împăturirea constantelor aplicată la șiruri de caractere literale în programe C#.

Pe scurt. Literalii șiruri de caractere sunt specificați cu sintaxa șirurilor textuale („verbatim”). Noi folosm „backslash” (‘\‘) pentru a „evacua” anumite secvențe. Șirurile de caractere literale sunt constante – ele nu pot fi schimbate.

Tradus de pe https://www.dotnetperls.com/string-literal. Am adăugat și 2 capturi de ecran Visual Studio.

[C#] Despre boxing și unboxing

Ce sunt boxing și unboxing?

string s = „test”;

object obj = s; // boxing, nu trebuie folosit cast-ul

string str = (string)obj; // unboxing, trebuie folosit cast-ul

De ce se folosesc?

object este un tip-referință, string este un tip-valoare. În unele locuri e nevoie de folosirea unui tip-referință și nu a unui tip-valoare (când trebuie să apelezi o metodă care folosește metoda ToString a unui parametru de tip object sau o subclasă a object). Atunci e posibilă introducerea unei variabile de tip-valoare într-o variabilă de tip-referință. Și variabilele de tipuri-referință, și cele de tipuri-valoare se pot inițializa cu operatorul new când tipul respectiv are un constructor accesibil.

Ce este un tip-valoare?

int x = 5;
int y = 5;
Console.WriteLine(x == y); // Adevărat (True) pentru că valoarea lui y este o copie a valorii lui x, și se testează doar egalitatea valorilor, nu a adreselor de memorie ale variabilelor.

Tipurile-valoare se creează cu cuv. cheie struct. Documentație oficială în acest link [EN].

Ce este un tip-referință?

object a = 5;
object b = 5;
Console.WriteLine(a == b); // Fals (False) pentru că a și b sunt indicatori ai unei singure valori, 5, dar a face trimitere la a, și b face trimitere la b. Se compară adresele din memorie ale variabilelor.

Tipurile-referință se creează cu cuv. cheie class. Documentație oficială în acest link [EN].

Exemplu

using System;
using System.Windows.Forms;

namespace cs_boxing_unboxing
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void Form1_Load(object sender, EventArgs e)
        {
            string s = „test”;
            object obj = s; // boxing, nu trebuie folosit cast-ul
            string str = (string)obj; // unboxing, trebuie folosit cast-ul
            Console.WriteLine(str);

            int x = 5;
            int y = 5;
            Console.WriteLine(x == y); // Adevărat (True) pentru că valoarea lui y este o copie a valorii lui x, și se testează doar egalitatea valorilor, nu a adreselor de memorie ale variabilelor.

            object a = 5;
            object b = 5;
            Console.WriteLine(a == b); // Fals (False) pentru că a și b sunt indicatori ai unei singure valori, 5, dar a face trimitere la a, și b face trimitere la b. Se compară adresele din memorie ale variabilelor.
        }
    }
}

Capturi de ecran

La rularea programului, se afișează: