До решења се може доћи коришћењем петљи. У првој петљи одређујемо први елемент \(k\)-тог реда, а уз то одређујемо и број елемената у њему. Први елемент одређујемо тако што саберемо број елемената у претходних \(k-1\) редова, док број елемената сваког реда тако што у сваком кораку број елемената претходног реда увећавамо за два (сваки наредни ред има тачно два елемента више од претходног). Дакле, у петљи одржавамо почетак и број елемената текућег реда (иницијализујемо их на један, јер први ред почиње од један и има тачно један елемент) и \(k-1\) пута почетак реда увећавамо за број елемената текућег реда, а број елемената текућег реда за два.
Пример. Прикажимо ово на примеру одређивања првог елемента реда 5.
k pocetak brojElemenata 1 1 1 2 2 3 3 5 5 4 10 7 5 17 9
Након тога, у другој петљи одређујемо збир елемената у \(k\)-том реду, тако што на збир који иницијализујемо на нулу додајемо један по један елемент тог реда, коришћењем алгоритма сабирања серије бројева – елементи су узастопни природни бројеви, па их је лако набројати.
#include <iostream>
using namespace std;
long long zbirRedaTrougla(long long k) {
// odredjujemo prvi broj u k-tom redu trougla
long long pocetak = 1;
long long brojElemenata = 1;
for (int i = 1; i < k; i++) {
pocetak += brojElemenata;
brojElemenata += 2;
}
// odredjujemo zbir elemenata u k-tom redu trougla
long long zbir = 0;
for (long long i = pocetak; i < pocetak + brojElemenata; i++)
zbir += i;
return zbir;
}
int main() {
int q;
cin >> q;
for (int i = 0; i < q; i++) {
long long k;
cin >> k;
cout << zbirRedaTrougla(k) << endl;
}
return 0;
}Сложеност. У првој петљи обилазимо \(k\) редова којима одређујемо почетак помоћу две операције сабирања. Пажљивом анализом можемо закључити да у реду \(k\) има \(2k-1\) елемената (мада ту чињеницу нисмо употребили у програму), који се у другој фази сабирају. Сложеност обе фазе, па и укупног решења је, дакле, \(O(k)\). Задатак, наравно, може да се реши и у мањој сложености од ове, без коришћења петљи.
Доказ коректности. Докажимо формално коректност овог поступка. Инваријанта петље је да након \(m\) извршавања њеног тела важи да је \(i = m+1\) и \(1 \leq i \leq k\), као и да променљива pocetak садржи први елемент реда \(i = m+1\), а променљива brojElemenata садржи број елемената реда \(i = m+1\).
Пошто се променљива i иницијализује на вредност \(1\), након \(m=0\) корака важи да је \(1 = 0 + 1\) и \(1 \leq 1 \leq k\). Пошто су и обе променљиве иницијализоване на вредност \(1\), након \(m=0\) корака петље, променљиве заиста садрже први елеменат и број елемената реда \(i = m + 1 = 0+1 = 1\).
Претпоставимо да инваријанта важи након \(m\) корака петље и да је услов петље испуњен тј. да је \(i < k\).
Докажимо да тврђење важи и након \(m'=m+1\) извршавања тела и корака петље. Пошто након извршавања корака важи \(i' = i+1\), а пошто је на основу индуктивне хипотезе важило да је \(i = m+1\), важи и да је \(i' = m'+1\). Пошто је услов петље био испуњен, важило је \(i < k\), па уз индуктивну претпоставку \(1 \leq i \leq k\), важи \(1 \leq i' \leq k\).
Означимо са \(p\) и \(b\) вредности променљивих pocetak и brojElemenata на улазу у тело петље, а са \(p'\) и \(b'\) њихове нове вредности, након извршења тела и корака петље. Анализом додела у телу петље, јасно видимо да је \(p' = p + b\) и \(b' = b+2\). На основу претпоставке важи да је \(p\) први елемент реда \(i=m+1\), а да је \(b\) број елемената реда \(i=m+1\). Сабирањем првог елемента било ког реда у троуглу и броја елемената тог реда троугла добија се први елемент наредног реда троугла. Дакле, важи да је \(p+b\) први елемент реда \(i+1 = m+2\) троугла, па, важи да је \(p'=p+b\) први елемент реда \(i' = i+1 = m+2 = m' + 1\). На основу дефиниције троугла важи јасно и да сваки наредни ред има и два елемента више него претходни. Зато, пошто је \(b\) број елемената реда \(m+1\), важи и да је \(b' = b+2\) број елемената реда \(i' = m'+1\).
На крају петље услов није испуњен, па важи да је \(i \geq k\). Уз услов \(1 \leq i \leq k\), мора да важи да је \(i = k\). На основу инваријанте знамо да променљива pocetak садржи број елемената реда \(i = m+1 = k\). Дакле, петља је коректно извршила свој задатак и у променљиву pocetak сместила први елемент реда \(k\).
На сличан начин се може формално доказати и коректност друге петље (инваријанта је да након \(m\) њених корака променљива zbir садржи збир првих \(m\) елемената реда \(k\), а да променљива \(i\) садржи вредност елемента на позицији \(m\) у том реду, ако се позиције броје од 0).
Приметимо да смо у овој петљи увели и нову променљиву којом смо регистровали број елемената у текућем реду троугла. То што смо ту променљиву имали на располагању нам је помоглно да ажурирамо вредност почетног елемента наредног реда, међутим, “кредит” који смо добили на почетку тела петље морали смо да вратимо на крају тако што смо морали да ажурирамо и вредност те променљиве (и тако је припремимо за наредну итерацију). Ова техника је позната под именом ојачавање индуктивне хипотезе и често се користи приликом конструкције алгоритама.
Приметимо да последњи елемент у сваком реду троугла представља потпун квадрат (то су бројеви 1, 4, 9, 16, итд). Дакле, пошто бројање редова почиње од 1, последњи елемент у реду број \(k\) је број \(k^2\). Зато је први број у реду број \(k\) једнак \((k-1)^2 + 1\) (следбеник последњег броја у претходном реду, који је потпун квадрат). У реду број \(k\) има \(n = 2k - 1\) елемент и чланови реда су узастопни природни бројеви, тако да чине аритметички низ, чији је први члан једнак \(a_1 = (k-1)^2 + 1\), а разлика \(d=1\).
Тражени збир можемо израчунати на основу формуле за збир елемената аритметичког низа \(n\cdot a_1 + d\frac{(n-1)n}{2}\). Уврштавањем вредности добијамо
\[(2k-1)((k-1)^2 + 1) + \frac{(2k-2)(2k-1)}{2} =\]
\[(2k-1)\left((k-1)^2 + 1 + (k-1)\right) =\]
\[(2k-1)(k^2-k+1)\]
Нагласимо још и да број елемената у сваком реду троугла чини аритметички низ са првим чланом 1 и разликом 2 (у сваком реду има два реда више него у претходном). То је аритметички низ који чине сви непарни бројеви, његов \(k\)-ти члан је \(1 + 2(k-1) = 2k-1\), док је збир његових \(k\) елемената једнак \(k + 2\frac{k(k-1)}{2} = k^2\), што заправо доказује да у реду \(k\) има \(2k-1\) елемената, а да је последњи елемент у том реду заиста \(k^2\).
Сложеност. Применом изведених формула, решење из израчунава у сложености \(O(1)\).
Читљивости програма ради, уместо финалне формуле можемо употребити функцију за израчунавање збира елемената аритметичког низа.
#include <iostream>
using namespace std;
// zbir niza a1, a1+d, ..., a1+(n-1)d
long long zbirAritmetickogNiza(long long a1, long long d, long long n) {
return n * a1 + d * (n-1) * n / 2;
}
long long zbirRedaTrougla(long long k) {
long long a1 = (k - 1) * (k - 1) + 1;
long long d = 1;
long long n = 2 * k - 1;
return zbirAritmetickogNiza(a1, d, n);
}
int main() {
int q;
cin >> q;
for (int i = 0; i < q; i++) {
long long k;
cin >> k;
cout << zbirRedaTrougla(k) << endl;
}
return 0;
}