Zadatak Aritmetički trougao-rešenje

Aritmetički trougao — rešenje

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·10⁴) 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 (u kodu k = redovi[idx]) iterativno se povećava broj elemenata po redovima (1, 3, 5, ...) dok se ne dođe do traženog reda. Kada dođemo do reda k, određujemo prvi i poslednji broj reda i računamo zbir aritmetičke progresije.

Broj elemenata u traženom redu (neparan): broj_elemenata = 2·k − 1. U kodu to dobijamo postupnim povećanjem: 1, pa +2, pa +2...
Prvi i poslednji broj reda nalaze se prateći poslednji broj prethodnog reda: prvi = prethodni_poslednji + 1; poslednji = prvi + (broj_elemenata − 1).
Zbir reda se računa formulom za sumu aritmetičke progresije: (prvi + poslednji) * broj_elemenata / 2.

Prednost: jednostavno za razumevanje i prikladno za nastavu. Mana: u najgorem slučaju radi O(k) koraka po upitu — za veliki broj i/ili velike upite to je neefikasno. Efikasnija (i preporučena) formula je navedena u komentarima koda.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    vector<int> redovi(n);
    for (int i = 0; i < n; ++i) cin >> redovi[i];

    for (int idx = 0; idx < n; ++idx) {
        int k = redovi[idx];                 // red koji trazimo (1 ≤ k ≤ 5·10^4)
        long long broj_elemenata = 0;        // 1, 3, 5, ... (u iterativnom pristupu)
        long long a_prvi = 0;                // prvi broj u tekućem redu
        long long a_poslednji = 0;           // poslednji broj u tekućem redu
        long long zbir_reda = 0;

        // Iterativno "gradimo" do k-tog reda (edukativni pristup)
        for (int j = 1; j <= k; ++j) {
            if (j == 1) broj_elemenata = 1;
            else broj_elemenata += 2;          // svaki naredni red ima +2 elemenata

            a_prvi = a_poslednji + 1;          // prvi je uvek za 1 veci od poslednjeg prethodnog reda
            a_poslednji = a_prvi + (broj_elemenata - 1); // poslednji = prvi + (n-1)

            if (j == k) {
                // zbir aritmeticke progresije: (prvi + poslednji) * broj_elemenata / 2
                zbir_reda = (a_prvi + a_poslednji) * broj_elemenata / 2;
                cout << zbir_reda << '\n';
            }
        }
    }

    return 0;
}

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 prve (r−1) neparne vrednosti:
T = 1 + 3 + 5 + ... + (2(r−1)−1)
Kako se dobija ova formula?
Brojevi 1, 3, 5, ... koji predstavljaju broj elemenata po redovima čine aritmetičku progresiju sa:
- a1 = 1 (prvi član),
- d = 2 (razlika),
- broj članova = r − 1.
Zbir prvih (r−1) članova je:
S = (a1 + an) · (r−1) / 2, gde je an = a1 + (r−2)·d.
Zamenom dobijamo:
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 je 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 se dobija: 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;

/*
Ispravljeno resenje:
- nr[i]  - red koji trazimo (r)
- k      - broj elemenata u trazenom redu (2*r - 1)
- a1     - prvi broj u trazenom redu
- an     - poslednji broj u trazenom redu
- S      - zbir trazenog reda
- d      - razlika izmedju clanova (d = 1)

Napomena: postoji i skracena formula
S = (r^2 - r + 1) * (2r - 1),
ali ovde zadrzavamo sve korake.
*/

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    vector<int> nr(n);
    for (int i = 0; i < n; ++i) {
        cin >> nr[i];
    }

    long long a1 = 0, an = 0, S = 0;
    long long d = 1; // razlika u trouglu je 1

    for (int i = 0; i < n; ++i) {
        long long r = nr[i];

        // broj elemenata u redu
        long long k = 2 * r - 1;

        // ukupan 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;
}