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 pokazuje razliku između edukativnog (simulacionog) pristupa i efikasne matematičke formule. Cilj je da razumete kako se redovi u trouglu grade, kako se iz toga izvode prvi i poslednji broj reda i, na kraju, zbir reda. Prvo je prikazano Rešenje 1, koje „gradi” trougao red po red, a zatim Rešenje 2, koje do rezultata dolazi direktno, formulom.

Tekst zadatka

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 (1 ≤ n ≤ 50 000). Nakon toga se učitava n rednih brojeva redova k (1 ≤ k ≤ 5·104) čiji zbir treba izračunati. Brojanje redova počinje od 1.

Izlaz

Za svaki upit, u posebnom redu, ispisati zbir brojeva u zadatom redu trougla.

Primer

Ulaz:
3
1
2
3

Izlaz:
1
9
35

Prvi red sadrži samo broj 1, drugi red 2 + 3 + 4 = 9, a treći red 5 + 6 + 7 + 8 + 9 = 35.

Rešenje 1 — simulacioni (edukativni) pristup

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.

Prednost ovog pristupa je jednostavnost i dobra preglednost, ali je vremenska složenost O(k) po upitu.

Prikaži / sakrij rešenje 1 
#include <iostream>
#include <vector>

using namespace std;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;

    // Učitavanje broja upita
    if (!(cin >> n))
        return 0;

    vector<int> redovi(n);

    // Učitavanje traženih 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 tražimo 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 traženog reda
        long long zbir_reda = 0;

        // Iterativno gradimo trougao do k-tog reda
        for (int j = 1; j <= k; ++j) {

            // Svaki red ima 2 elementa više od prethodnog
            if (j == 1)
                broj_elemenata = 1;
            else
                broj_elemenata += 2;

            // Prvi element reda je za 1 veći
            // od poslednjeg elementa prethodnog reda
            a_prvi = a_poslednji + 1;

            // Poslednji element reda
            a_poslednji = a_prvi + (broj_elemenata - 1);

            // Kada dođemo do traženog reda
            if (j == k) {

                // Formula za zbir aritmetičke progresije
                zbir_reda = (a_prvi + a_poslednji) * broj_elemenata / 2;

                cout << zbir_reda << '\n';
            }
        }
    }

    return 0;
}

Nedostaci rešenja 1 i šta treba popraviti

Rešenje 2 — efikasno matematičko rešenje

Za razliku od simulacije, ovde tražimo matematički obrazac, da bismo direktno izračunali broj elemenata u redu, prvi broj, poslednji broj i zbir reda, bez gradnje trougla. Tako dobijamo rešenje sa vremenskom složenošću O(1) po upitu.

Neka je r red za koji želimo zbir (u kodu je to nr[i]).

1. Broj elemenata u r-tom redu

Redovi sadrže neparan broj elemenata, pa je:

k = 2r − 1

Na primer, za r = 3 dobijamo k = 5.

2. Ukupan broj elemenata u prethodnih r − 1 redova

To je zbir prvih r − 1 neparnih brojeva:

T = 1 + 3 + 5 + ... + (2(r − 1) − 1)

Brojevi 1, 3, 5, ... čine aritmetičku progresiju sa prvim članom a1 = 1, razlikom d = 2 i r − 1 članova. Poslednji član je 1 + (r − 2)·2 = 2r − 3, pa je zbir:

T = (1 + (2r − 3)) · (r − 1) / 2 = (2r − 2) · (r − 1) / 2 = (r − 1)²

Za r = 3 dobijamo T = 4: pre trećeg reda nalaze se četiri broja (1, 2, 3, 4).

3. Prvi broj u r-tom redu

a1 = T + 1 = (r − 1)² + 1

Za r = 3 dobijamo a1 = 5.

4. Poslednji broj u r-tom redu

Brojevi u redu rastu za 1, pa je an = a1 + (k − 1). Jednostavnije, poslednji broj r-tog reda jednak je ukupnom broju elemenata u prvih r redova:

an = r²

Za r = 3 dobijamo an = 9.

5. Zbir u r-tom redu

S = (a1 + an) · k / 2 = ((r − 1)² + 1 + r²) · (2r − 1) / 2

Pošto je (r − 1)² + 1 + r² = 2r² − 2r + 2, izraz se skraćuje na:

S = (r² − r + 1) · (2r − 1)

Provera na primeru (r = 3)

a1 = 5, an = 9, k = 5, pa je S = (5 + 9) · 5 / 2 = 35. Iz skraćene formule: (9 − 3 + 1) · 5 = 7 · 5 = 35.

Prikaži / sakrij rešenje 2 
#include <iostream>
#include <vector>

using namespace std;

/*
Efikasno matematičko rešenje

Promenljive:
- r   -> red koji tražimo
- 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);

    // Učitavanje 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;  // razlika susednih brojeva u redu

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

Objašnjenje važnih delova programa

Složenost rešenja

Zaključak

Zadatak pokazuje kako se iz posmatranja nekoliko prvih redova dolazi do opšte formule. Ključni koraci su zbir prvih neparnih brojeva, (r − 1)², i formula za zbir aritmetičke progresije. Kada se problem rešava za veliki broj upita, matematičko rešenje u O(1) je ono koje prolazi sve testove.