Pokušajte najpre da samostalno rešite zadatak.
Čak i ako ne dođete do kompletnog rešenja, pokušaj razvijanja ideje
je veoma važan za razvoj algoritamskog razmišljanja.
Uvod
Ovaj primer služi da pokaže razliku između edukativnog (simulacionog) pristupa
i efikasne matematičke formule.
Cilj je da učenici razumeju kako se redovi u trouglu grade i kako se iz toga
izvode prve i poslednje vrednosti reda, pa na kraju i zbir redova.
Prvo je prikazano Rešenje 1 — iterativni, edukativni pristup
koji „gradi“ red po red.
Zadatak
Koliki je zbir brojeva u datom redu sledećeg trougla?
1
2 3 4
5 6 7 8 9
10 11 12 13 14 15 16
...
Ulaz
Sa standardnog ulaza se učitava broj n redova za koje je potrebno izračunati zbir
(celobrojna vrednost, 1 ≤ n ≤ 50 000).
Nakon toga se učitava n rednih brojeva redova k
(1 ≤ k ≤ 5·104) trougla čiji zbir treba izračunati
(brojanje redova počinje od 1).
Izlaz
Zbir vrednosti u svakom zadatom redu trougla
(po jedan red u izlazu za svaki upit).
Primer Ulaz
3
1
2
3
Izlaz
1
9
35
Rešenje 1 — neefikasni (edukativni) pristup — objašnjenje
Ovo rešenje simulira gradnju trougla red po red.
Za traženi red k iterativno se povećava broj elemenata po redovima
(1, 3, 5, ...) dok se ne dođe do traženog reda.
Broj elemenata u redu:
2·k − 1
Prvi i poslednji član reda
određuju se pomoću poslednjeg člana prethodnog reda.
Zbir reda
računa se formulom za zbir aritmetičke progresije:
(prvi + poslednji) * broj_elemenata / 2
Prednost ovog pristupa je jednostavnost i dobra preglednost za učenike,
ali je vremenska složenost O(k) po upitu.
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
// Ucitavanje broja upita
if (!(cin >> n))
return 0;
vector<int> redovi(n);
// Ucitavanje trazenih redova
for (int i = 0; i < n; ++i)
cin >> redovi[i];
// Obrada svakog upita posebno
for (int idx = 0; idx < n; ++idx) {
// Red za koji trazimo zbir
int k = redovi[idx];
// Broj elemenata u trenutnom redu
long long broj_elemenata = 0;
// Prvi broj u redu
long long a_prvi = 0;
// Poslednji broj u redu
long long a_poslednji = 0;
// Zbir trazenog reda
long long zbir_reda = 0;
// Iterativno gradimo trougao do k-tog reda
for (int j = 1; j <= k; ++j) {
// Svaki red ima 2 vise elemenata od prethodnog
if (j == 1)
broj_elemenata = 1;
else
broj_elemenata += 2;
// Prvi element reda je za 1 veci
// od poslednjeg elementa prethodnog reda
a_prvi = a_poslednji + 1;
// Poslednji element reda
a_poslednji = a_prvi + (broj_elemenata - 1);
// Kada dodjemo do trazenog reda
if (j == k) {
// Formula za zbir aritmeticke progresije
zbir_reda =
(a_prvi + a_poslednji)
* broj_elemenata / 2;
cout << zbir_reda << '\n';
}
}
}
return 0;
}
Rešenje 2 — efikasno matematičko rešenje
Za razliku od prethodnog simulacionog pristupa,
ovde pokušavamo da pronađemo matematički obrazac.
Cilj je da direktno izračunamo:
broj elemenata u redu,
prvi broj reda,
poslednji broj reda,
i zbir reda,
bez iterativne gradnje trougla.
Na taj način dobijamo mnogo efikasnije rešenje
sa vremenskom složenošću O(1) po upitu.
Objašnjenje kako dobiti prvi i poslednji broj,
i zbir u r-tom redu trougla
Data je sledeća struktura (prikaz prvih redova):
1
2 3 4
5 6 7 8 9
10 11 12 13 14 15 16
...
Neka je r red za koji želimo zbir
(u kodu to je nr[i]).
Broj elemenata u r-tom redu
Redovi sadrže neparan broj elemenata:
k = 2·r − 1
(npr. za r = 3, k = 5).
Ukupan broj elemenata u prethodna r−1 reda
To je zbir prvih (r−1) neparnih brojeva:
T = 1 + 3 + 5 + ... + (2(r−1)−1)
Kako se dobija ova formula?
Brojevi 1, 3, 5, ... predstavljaju broj elemenata po redovima
i čine aritmetičku progresiju:
a1 = 1 — prvi član,
d = 2 — razlika,
broj članova = r − 1.
Zbir prvih (r−1) članova:
S = (a1 + an) · (r−1) / 2
gde je:
an = a1 + (r−2)·d
Zamenom:
S = (1 + (1 + (r−2)·2)) · (r−1) / 2
S = (1 + (2r − 3)) · (r−1) / 2
S = (2r − 2) · (r−1) / 2
S = (r−1)²
Ova vrednost predstavlja ukupan broj elemenata
u prethodna r−1 reda.
(za r = 3 → T = 4)
Prvi broj u r-tom redu
a1 = T + 1 = (r−1)² + 1
(za r = 3 → a1 = 5)
Poslednji broj u r-tom redu
an = a1 + (k − 1)·d
gde je d = 1.
Jednostavnije:
an = r²
(za r = 3 → an = 9)
Zbir u r-tom redu
S = (a1 + an) · k / 2
odnosno:
S = ((r−1)² + 1 + r²) · (2r−1) / 2
Formula može da se sažme u:
S = (r² − r + 1) · (2r − 1)
Primer (r = 3)
a1 = 5,
an = 9,
k = 5
S = (5 + 9) · 5 / 2 = 35
#include <iostream>
#include <vector>
using namespace std;
/*
Efikasno matematičko rešenje
Promenljive:
- r -> red koji trazimo
- k -> broj elemenata u redu
- T -> broj elemenata u prethodnim redovima
- a1 -> prvi broj reda
- an -> poslednji broj reda
- S -> zbir reda
*/
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
// Broj upita
if (!(cin >> n))
return 0;
vector<int> nr(n);
// Ucitavanje redova
for (int i = 0; i < n; ++i) {
cin >> nr[i];
}
long long a1 = 0;
long long an = 0;
long long S = 0;
long long d = 1;
for (int i = 0; i < n; ++i) {
long long r = nr[i];
// Broj elemenata u redu
long long k = 2 * r - 1;
// Broj elemenata do prethodnog reda
long long T = (r - 1) * (r - 1);
// Prvi broj reda
a1 = T + 1;
// Poslednji broj reda
an = a1 + (k - 1) * d;
// Zbir reda
S = (a1 + an) * k / 2;
cout << S << '\n';
}
return 0;
}
