Important information: Google announced that, from September 2026, Android devices will require ALL apps to be signed by Google, effectively leading to an iOS situation. Value your right to a computer that does what you want; do not tolerate this monopolistic practice! Contact me if you don't understand why it is bad. Click to learn more.

 sp_matrice.xhtml

View raw Download
text/xml • 24.43 kiB
XML 1.0 document, Unicode text, UTF-8 text
        
            
1
<?xml version="1.0" encoding="UTF-8"?>
2
<!DOCTYPE html>
3
<html xmlns="http://www.w3.org/1999/xhtml">
4
<head>
5
<meta charset="utf-8"/>
6
<title>Clasele vector&lt;&gt;. Sume parțiale pe matrice.</title>
7
<style>
8
/* <![CDATA[ */
9
body {
10
font-family: "charis sil compact", serif;
11
line-height: 1.25;
12
color: #000000;
13
background: #ffffff;
14
}
15
h1, h2, h3, h4 {
16
font-family: "cantarell", sans-serif;
17
}
18
pre, code, var, samp, kbd {
19
font-family: "inconsolata", monospace;
20
}
21
h1, h2 {
22
color: #009688;
23
}
24
h1 {
25
text-align: center;
26
font-weight: 400;
27
font-size: 2rem;
28
}
29
h2 {
30
font-weight: 700;
31
}
32
.old-information {
33
background-color: #ffff0020;
34
border: 1px solid #ff9800;
35
padding: 1lh;
36
}
37
.definition {
38
background-color: #e91e6320;
39
border: 1px solid #e91e63;
40
padding: 1lh;
41
}
42
p {
43
text-indent: 2em;
44
}
45
h1, h2, h3, h4, h5, h6, p, ul, ol, dl, pre {
46
margin: 0;
47
}
48
.matrix {
49
border-collapse: collapse;
50
:is(td, th) {
51
width: 2em;
52
height: 2em;
53
text-align: right;
54
padding: 0.25lh;
55
}
56
& tr:nth-child(odd) :nth-child(even),
57
& tr:nth-child(even) :nth-child(odd) {
58
background: #303F9F10;
59
}
60
& tr:nth-child(even) :nth-child(even),
61
& tr:nth-child(odd) :nth-child(odd) {
62
background: #303F9F20;
63
}
64
}
65
.sel1 {
66
background-image: linear-gradient(#e91e6380, #e91e6380) !important;
67
}
68
.sel2 {
69
background-image: linear-gradient(#4caf5080, #4caf5080) !important;
70
}
71
.sel3 {
72
background-image: linear-gradient(#ff980080, #ff980080) !important;
73
}
74
.sel4 {
75
background-image: linear-gradient(#303f9f80, #303f9f80) !important;
76
}
77
.txt1 {
78
color: #e91e63;
79
}
80
.txt2 {
81
color: #4caf50;
82
}
83
.txt3 {
84
color: #ff9800;
85
}
86
.txt4 {
87
color: #303f9f;
88
}
89
/* ]]> */
90
</style>
91
</head>
92
<body>
93
<h1>Clasele <code>vector&lt;&gt;</code>. Sume parțiale pe matrice.</h1>
94
<section>
95
<h2><code>vector&lt;&gt;</code></h2>
96
<aside class="definition">
97
<p>
98
<b>Context:</b>
99
<i>Clasa</i> este un tip de date compus care definește
100
operații definite de autorul tipului. Unele operații se
101
folosesc prin operatori și altele sunt funcții interioare
102
clasei (numite și <i>metode</i>) care se accesează cu
103
punct și primesc parametri ca o funcție obișnuită.
104
Momentan nu ne interesează definirea claselor. Clasele
105
pot avea derivate, care moștenesc caracteristicile bazei
106
și le extind, și pot fi șabloane, adică să permită
107
utilizatorului să specifice anumite părți din clasă
108
(tipurile de date din care se compune).
109
</p>
110
<p>
111
Instanțele unei clase se numesc <i>obiecte</i>. Câteva
112
clase pe care poate le știți deja: <code>istream</code>
113
(<code>cin</code> e o instanță a acestei clase),
114
<code>ifstream</code> (care e derivată din istream),
115
<code>string</code>.
116
</p>
117
<p>
118
În C++, clasa este sinonimă cu structura, dar acest
119
lucru nu este valabil pentru toate limbajele de programare
120
care oferă ambele opțiuni.
121
</p>
122
<p>
123
Când se creează un obiect, putem (uneori trebuie) să-i dăm
124
parametri, care vor fi trimiși funcției-constructor.
125
Binecunoscutul exemplu nu de fapt nimic altceva decât o
126
declarare de obiect cu parametru:
127
</p>
128
<pre><code>ifstream fin("numele.in");
129
ofstream fout("numele.out");</code></pre>
130
</aside>
131
<p>
132
Până acum cunoașteți tipurile tradiționale de tablou,
133
care se declară cu sintaxa <code>TipDeBază nume[dimensiune]</code>.
134
Ele funcționează, dar sunt moștenite din limbajul C (1972).
135
Au deci câteva neajunsuri:
136
</p>
137
<ul>
138
<li>
139
nu își memorează dimensiunea, de aceea trebuie să
140
o memorăm separat și să ne amintim pentru fiecare
141
dimensiune care vector o folosește;
142
</li>
143
<li>
144
când sunt trimise în funcții, devin un simplu pointer,
145
și trebuie să fim atenți să nu facem operații fără sens
146
cu acel pointer (se fac foarte ușor);
147
</li>
148
<li>
149
nu pot fi redimensionați (fără alocare dinamică);
150
</li>
151
<li>
152
de fapt, conform standardului, dimensiunea trebuie să
153
fie o constantă determinată la compilare (însă GCC
154
permite și o dimensiune variabilă).
155
</li>
156
</ul>
157
<p>
158
În C++, spre deosebire de C, biblioteca standard ne pune la
159
dispoziție o alternativă, șablonul (template-ul) de tipuri
160
(clase) numit <code>vector</code>. Spre deosebire de tablourile
161
tradiționale:
162
</p>
163
<ul>
164
<li>
165
au dimensiune, care poate fi accesată folosind funcția
166
internă <code>size</code>;
167
</li>
168
<li>
169
această dimensiune se poate schimba oricând;
170
</li>
171
<li>
172
nu se transformă în pointer;
173
</li>
174
<li>
175
îi putem returna din funcții;
176
</li>
177
<li>
178
conținutul nu se alocă pe stivă, deci putem avea tablouri
179
oricât de mari dorim fără a le aloca global sau dinamic.
180
</li>
181
</ul>
182
<p>
183
<code>vector</code> este în antetul
184
<code>&lt;vector&gt;</code> și în spațiul de nume
185
<code>std</code> (dacă avem <code>using namespace std;</code>
186
nu trebuie să scriem asta).
187
</p>
188
<h3>Declararea vectorilor</h3>
189
<div class="gallery">
190
<figure>
191
<pre><code>vector&lt;<b>int</b>&gt; name;</code></pre>
192
<figcaption>Un vector gol care memorează valori de tipul <code>int</code></figcaption>
193
</figure>
194
<figure>
195
<pre><code><b>int</b> N;
196
cin >> N;
197
struct Structure {
198
<b>int</b> a, b;
199
}
200
vector&lt;Structure&gt; p(N);</code></pre>
201
<figcaption>
202
Un vector <code>p</code> care memorează valori de tipul
203
<code>Structure</code>. Inițial are <code>N</code>
204
elemente, care sunt inițializate cu 0.
205
</figcaption>
206
</figure>
207
<figure>
208
<pre><code>vector&lt;<b>short int</b>&gt; alphabet(26, -1);</code></pre>
209
<figcaption>
210
Un vector care memorează inițial 26 de
211
<code>short int</code>, având valoarea inițială
212
de -1.
213
</figcaption>
214
</figure>
215
<figure>
216
<pre><code>vector&lt;<b>int</b>&gt; x = y;</code></pre>
217
<figcaption>
218
Vectorul x este o copie a vectorului y.
219
</figcaption>
220
</figure>
221
<figure>
222
<pre><code>vector&lt;vector&lt;<b>int</b>&gt;&gt; x(N, vector&lt;<b>int</b>&gt;(M));</code></pre>
223
<figcaption>
224
Un vector de vectori e o matrice. Transmitem cu ce
225
parametri va fi inițializat fiecare element.
226
</figcaption>
227
</figure>
228
</div>
229
<h3>Operații de bază</h3>
230
<div class="gallery">
231
<figure>
232
<pre><code>vector&lt;<b>int</b>&gt; a(5);</code></pre>
233
<figcaption>
234
Se declară acest vector.
235
</figcaption>
236
</figure>
237
<figure>
238
<pre><code>a[0]</code></pre>
239
<figcaption>
240
Accesează elementul 0 din vector.
241
</figcaption>
242
</figure>
243
<figure>
244
<pre><code>a[1] = 67</code></pre>
245
<figcaption>
246
Atribuirea se face în modul firesc.
247
</figcaption>
248
</figure>
249
<figure>
250
<pre><code>a.size()</code></pre>
251
<figcaption>
252
Returnează dimensiunea vectorului, adică 5.
253
</figcaption>
254
</figure>
255
<figure>
256
<pre><code>a.capacity()</code></pre>
257
<figcaption>
258
Returnează numărul de elemente disponibile pentru
259
când se lărgește vectorul; dacă vectorul crește peste
260
acest număr de elemente, se va realoca.
261
</figcaption>
262
</figure>
263
</div>
264
<h3>Operații care schimbă dimensiunea</h3>
265
<div class="gallery">
266
<figure>
267
<pre><code>a.resize(9)</code></pre>
268
<figcaption>
269
Vectorul are acum 9 elemente în loc de 5. Cele
270
noi sunt 0.
271
</figcaption>
272
</figure>
273
<figure>
274
<pre><code>a.resize(1)</code></pre>
275
<figcaption>
276
Vectorul are acum un singur element, adică primul.
277
Elementele în afară de acesta se pierd.
278
</figcaption>
279
</figure>
280
<figure>
281
<pre><code>a.reserve(32)</code></pre>
282
<figcaption>
283
Vectorul se va realoca pentru a putea aduna 32 de
284
elemente fără alte realocări. Util când putem afla
285
o dimensiune orientativă (dacă nu chiar pe cea
286
finală).
287
</figcaption>
288
</figure>
289
<figure>
290
<pre><code>a.push_back(8)</code></pre>
291
<figcaption>
292
Adaugă un element la capăt. Vectorul are acum două
293
elemente: 0 și 8.
294
</figcaption>
295
</figure>
296
<figure>
297
<pre><code>a.pop_back()</code></pre>
298
<figcaption>
299
Vectorul pierde ultimul element.
300
</figcaption>
301
</figure>
302
</div>
303
<h3>Iteratori</h3>
304
<p>
305
Iteratorul este un obiect care indică o poziție din vector.
306
Este de tipul <code>vector&lt;TipDeBază&gt;::iterator</code>;
307
putem scrie <code><b>auto</b></code> pentru a nu folosi tot
308
numele.
309
</p>
310
<div class="gallery">
311
<figure>
312
<pre><code>a.begin()</code></pre>
313
<figcaption>
314
Iterator pentru primul element din vector (0).
315
</figcaption>
316
</figure>
317
<figure>
318
<pre><code>a.end()</code></pre>
319
<figcaption>
320
Iterator care se află după sfârșitul vectorului,
321
este folosit ca un indicator că parcurgerea trebuie
322
să se sfârșească.
323
</figcaption>
324
</figure>
325
<figure>
326
<pre><code>a.begin() + 1</code></pre>
327
<figcaption>
328
Adunând iteratorul cu un număr putem obține un iterator
329
pentru alt indice, în acest caz pentru elementul 1.
330
</figcaption>
331
</figure>
332
<figure>
333
<pre><code>a.end() - a.begin()</code></pre>
334
<figcaption>
335
Putem și scădea iteratori și rezultatul este un număr
336
întreg. Cu ce este egal rezultatul acestei expresii?
337
</figcaption>
338
</figure>
339
<figure>
340
<pre><code>++a</code></pre>
341
<figcaption>
342
Mută iteratorul cu o poziție înainte.
343
</figcaption>
344
</figure>
345
</div>
346
<h3>Operații bazate pe iteratori</h3>
347
<div class="gallery">
348
<figure>
349
<pre><code>a.erase(a.begin())</code></pre>
350
<figcaption>
351
Șterge primul element.
352
</figcaption>
353
</figure>
354
<figure>
355
<pre><code>a.insert(a.begin(), 5)</code></pre>
356
<figcaption>
357
Inserează un element în vector.
358
</figcaption>
359
</figure>
360
<figure>
361
<pre><code>a.insert(a.begin(), b.begin(), b.end())</code></pre>
362
<figcaption>
363
Copiază elementele dintre cei doi iteratori (aici cei
364
din b) și le inserează la <code>a.begin()</code>.
365
</figcaption>
366
</figure>
367
</div>
368
</section>
369
<section>
370
<h2>Sume parțiale pe matrice</h2>
371
<p>
372
Definim de acum funcția <code>safe_get</code> care va
373
returna valoarea de la indicele dat dintr-un vector, dacă
374
indicele e valid; în caz contrar, va returna 0. O folosim
375
pentru a nu fi nevoiți să testăm mereu dacă urmează să
376
scădem din poziția -1.
377
</p>
378
<pre><code><b>inline int</b> safe_get(vector&lt;<b>int</b>&gt; <b>const</b> &amp;a, <b>int const</b> i) {
379
<b>if</b> (i &lt; 0 || a.size() &lt;= i) {
380
<b>return</b> 0;
381
}
382
<b>return</b> a[i];
383
}</code></pre>
384
<pre><code><b>inline int</b> safe_get(vector&lt;vector&lt;<b>int</b>&gt;&gt; <b>const</b> &amp;a, <b>int const</b> i, <b>int const</b> j) {
385
<b>if</b> (i &lt; 0 || a.size() &lt;= i || j &lt; 0 || a[0].size() &lt;= j) {
386
<b>return</b> 0;
387
}
388
<b>return</b> a[i];
389
}</code></pre>
390
<aside class="old-information">
391
<h3>Recapitularea sumelor parțiale</h3>
392
<p>
393
Pentru a obține sume parțiale pe un tablou liniar de
394
lungime N, calculăm suma pe fiecare prefix al tabloului,
395
adică suma elementelor de la 0 la i (inclusiv), pentru
396
fiecare i de la 0 la N-1.
397
</p>
398
<p>
399
După aceea, suma pe intervalul [l; r] va fi
400
<code>safe_get(r) - safe_get(l-1)</code>.
401
</p>
402
</aside>
403
<p>
404
Să luăm ca exemplu matricea <code>a</code>:
405
</p>
406
<table class="matrix" contenteditable="true">
407
<tr>
408
<td>12</td>
409
<td>0</td>
410
<td>-4</td>
411
<td>-8</td>
412
<td>3</td>
413
</tr>
414
<tr>
415
<td>-1</td>
416
<td>6</td>
417
<td>7</td>
418
<td>8</td>
419
<td>10</td>
420
</tr>
421
<tr>
422
<td>4</td>
423
<td>-3</td>
424
<td>9</td>
425
<td>1</td>
426
<td>4</td>
427
</tr>
428
<tr>
429
<td>11</td>
430
<td>7</td>
431
<td>9</td>
432
<td>8</td>
433
<td>12</td>
434
</tr>
435
</table>
436
<p>
437
Se calculează, pentru fiecare i și j, suma elementelor aflate
438
pe rânduri până la i și coloane până la j. Matricea
439
<code>ps</code>:
440
</p>
441
<table class="matrix" contenteditable="true">
442
<tr>
443
<td>12</td>
444
<td>12</td>
445
<td>8</td>
446
<td>0</td>
447
<td>3</td>
448
</tr>
449
<tr>
450
<td>11</td>
451
<td>17</td>
452
<td>20</td>
453
<td>20</td>
454
<td>27</td>
455
</tr>
456
<tr>
457
<td>15</td>
458
<td>18</td>
459
<td>30</td>
460
<td>31</td>
461
<td>42</td>
462
</tr>
463
<tr>
464
<td>26</td>
465
<td>36</td>
466
<td>57</td>
467
<td>66</td>
468
<td>89</td>
469
</tr>
470
</table>
471
<p>
472
Cum calculăm această sumă?
473
</p>
474
<table class="matrix" contenteditable="true">
475
<tr>
476
<td class="sel3"></td>
477
<td class="sel3"></td>
478
<td class="sel3"></td>
479
<td class="sel1"></td>
480
<td></td>
481
</tr>
482
<tr>
483
<td class="sel3"></td>
484
<td class="sel3"></td>
485
<td class="sel3">20</td>
486
<td class="sel1">20</td>
487
<td></td>
488
</tr>
489
<tr>
490
<td class="sel2"></td>
491
<td class="sel2"></td>
492
<td class="sel2">30</td>
493
<td class="sel4">31</td>
494
<td></td>
495
</tr>
496
<tr>
497
<td></td>
498
<td></td>
499
<td></td>
500
<td></td>
501
<td></td>
502
</tr>
503
</table>
504
<p>
505
Putem trece la suma pentru o anumită celulă folosind sumele
506
anterioare:
507
</p>
508
<ol>
509
<li>
510
se ia valoarea celulei actuale din matrice;
511
</li>
512
<li>
513
se iau toate celulele cu i mai mic și j mai mic sau egal
514
decât cea actuală (deci suma de deasupra celei actuale);
515
</li>
516
<li>
517
se iau toate celulele cu j mai mic și i mai mic sau egal
518
decât cea actuală (deci suma din stânga celei actuale);
519
</li>
520
<li>
521
acum toate celulele care ne interesează sunt selectate;
522
totuși, unele sunt selectate de două ori, mai precis cele
523
care îndeplinesc ambele condiții 2. și 3.; trebuie, așadar,
524
scăzute acele elemente, adică suma din stânga-sus.
525
</li>
526
</ol>
527
<p>
528
<code>
529
ps[i][j] =
530
<span class="sel4">a[i][j]</span>
531
+ <span class="sel1">safe_get(ps, i - 1, j)</span>
532
+ <span class="sel2">safe_get(ps, i, j - 1)</span>
533
- <span class="sel3">safe_get(ps, i - 1, j - 1)</span>;
534
</code>
535
</p>
536
<p>
537
Mai rămâne să calculăm suma pentru o anumită interogare.
538
De exemplu, de la <code>(1; 1)</code> până la
539
<code>(3; 2)</code>. Notăm <code>(i0; j0; i1; j1)</code>.
540
</p>
541
<table class="matrix" contenteditable="true">
542
<tr>
543
<td class="sel3">12</td>
544
<td class="sel1">12</td>
545
<td class="sel1">8</td>
546
<td>0</td>
547
<td>3</td>
548
</tr>
549
<tr>
550
<td class="sel2">11</td>
551
<td class="sel4">17</td>
552
<td class="sel4">20</td>
553
<td>20</td>
554
<td>27</td>
555
</tr>
556
<tr>
557
<td class="sel2">15</td>
558
<td class="sel4">18</td>
559
<td class="sel4">30</td>
560
<td>31</td>
561
<td>42</td>
562
</tr>
563
<tr>
564
<td class="sel2">26</td>
565
<td class="sel4">36</td>
566
<td class="sel4">57</td>
567
<td>66</td>
568
<td>89</td>
569
</tr>
570
</table>
571
<p>
572
Putem să o calculăm folosind doar sumele calculate deja.
573
</p>
574
<ol>
575
<li>
576
se ia valoarea ultimei celule din interval (în dreapta-jos);
577
aceea va reprezenta evident tot intervalul, dar și alte
578
elemente pe care le vom exclude;
579
</li>
580
<li>
581
se ia valoarea celulei de deasupra colțului dreapta-sus al
582
intervalului, care va conține doar elemente ce trebuie
583
excluse;
584
</li>
585
<li>
586
se ia valoarea celulei din stânga colțului stânga-jos al
587
intervalului, care va conține doar elemente ce trebuie
588
excluse;
589
</li>
590
<li>
591
și acum avem elemente excluse de două ori, și anume celula
592
aflată în stânga-sus față de colțul stânga-sus al
593
intervalului.
594
</li>
595
</ol>
596
<pre><code><b>int</b> get_sum(vector&lt;vector&lt;<b>int</b>&gt;&gt; &amp;ps, <b>int const</b> i0, <b>int const</b> j0) {
597
<b>return</b> <span class="sel4">safe_get(ps, i1, j1)</span>
598
- <span class="sel1">safe_get(ps, i1 - 1, j1)</span>
599
- <span class="sel2">safe_get(ps, i1, j1 - 1)</span>
600
+ <span class="sel3">safe_get(ps, i1 - 1, j1 - 1)</span>;
601
}</code></pre>
602
</section>
603
<section>
604
<h2>Alte sume parțiale (de discutat)</h2>
605
<ul>
606
<li>
607
Sume parțiale pentru indici cu rație (din x în x).
608
</li>
609
<li>
610
Sume parțiale pe diagonală.
611
</li>
612
<li>
613
Sume parțiale pe un trapez dreptunghic delimitat la
614
diagonală.
615
</li>
616
<li>
617
Sume parțiale pe triunghi dreptunghic.
618
</li>
619
<li>
620
Sume parțiale pe linii oblice care nu sunt neapărat
621
diagonale.
622
</li>
623
<li>
624
Sume parțiale pe paralelogram.
625
</li>
626
</ul>
627
</section>
628
</body>
629
</html>
630