Choose your language!

---

|

Aritmetički trougao — rešenje

⚠️ Pre nego što pogledate rešenje

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·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 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.

□ Prikaži / Sakrij rešenje

#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.

□ Prikaži / Sakrij objašnjenje i kod

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]).

1. Broj elemenata u r-tom redu
   Redovi sadrže neparan broj elemenata:
   k = 2·r − 1
   (npr. za r = 3, k = 5).


2. 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)


3. Prvi broj u r-tom redu
   a1 = T + 1 = (r−1)² + 1
   (za r = 3 → a1 = 5)


4. Poslednji broj u r-tom redu
   an = a1 + (k − 1)·d
   gde je d = 1.
   
   Jednostavnije:
   an = r²
   (za r = 3 → an = 9)


5. 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;
}

---

Prethodno
​|< Priprema za drzavno takmičenje i SIO

---