Osnovne strukture podataka: niz, string i matrica – zadaci

Lekcija 1 od 11 · Strukture podataka

Pre stekova, redova i stabala dobro je uvežbati rad sa tri osnovne strukture koje se javljaju u skoro svakom zadatku: niz (i vektor), string i matrica. Zadaci na ovoj strani su sa kvalifikacija i školskih takmičenja.

Pre nego što počneš: potrebno predznanje – nizovi, stringovi.
Kako da učiš: svaki primer prekucaj i pokreni, a zadatke na kraju prvo reši sam/a; uputstvo i rešenje otvori tek posle toga. Svi programi su u C++-u.

Kratak pregled

Struktura	Pristup elementu	Tipična upotreba	Lekcija
niz / vector	`a[i]`, O(1)	spisak brojeva, brojači	Nizovi, vektori
string	`s[i]`, O(1)	reči, cifre broja, šifre	Stringovi
matrica	`a[i][j]`, O(1)	tabele, table za igru, mape	Dvodimenzionalni nizovi

Zajedničko im je da elementi stoje jedan do drugog u memoriji, pa je pristup po indeksu trenutan, a umetanje u sredinu sporo (treba pomeriti sve iza).

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

ZADATAK 01Težina: Lako

Palindrom

Ispitati da li je uneti petocifreni broj palindrom (čita se isto sleva i zdesna).

Izlaz: DA ili NE.

Primer 1

Ulaz

Izlaz

DA

Primer 2

Ulaz

Izlaz

NE

Rešenje (C++)

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    bool palindrom = true;
    for (int i = 0; i < n / 2; i++)
        if (s[i] != s[n - 1 - i]) palindrom = false;   // par simetričnih cifara se razlikuje
    cout << (palindrom ? "DA" : "NE") << endl;
    return 0;
}

ZADATAK 02Težina: Srednje

Uzastopna slova

Dat je string od malih slova engleske abecede (dužine do 10 000 000). Pronađi najduži podstring u kome je svako slovo, počev od drugog, sledeće u abecedi u odnosu na prethodno (na primer bcd). Ako ima više najdužih, ispiši onaj čije je prvo slovo najranije u abecedi.

Primer 1

Ulaz

bbcdrtughih

Izlaz

bcd

Primer 2

Ulaz

xyzabc

Izlaz

abc

Rešenje (C++)

#include <iostream>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int n = s.size();
    int najPoc = 0, najDuz = 1;     // najbolji do sada
    int poc = 0;                    // početak tekućeg niza uzastopnih slova
    for (int i = 1; i <= n; i++) {
        if (i < n && s[i] == s[i - 1] + 1) continue;   // tekući niz se nastavlja
        int duz = i - poc;                              // tekući niz se završio na i-1
        if (duz > najDuz || (duz == najDuz && s[poc] < s[najPoc])) {
            najDuz = duz;
            najPoc = poc;
        }
        poc = i;
    }
    cout << s.substr(najPoc, najDuz) << endl;
    return 0;
}

ZADATAK 03Težina: Lako

Trag matrice

Trag kvadratne matrice je zbir elemenata na glavnoj dijagonali (od gornjeg levog do donjeg desnog ugla). Data je matrica n × n (1 ≤ n ≤ 1000, elementi od −10 000 do 10 000). Izračunaj njen trag.

Primer

Ulaz

Izlaz

Rešenje (C++)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long trag = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            int x;
            cin >> x;
            if (i == j) trag += x;      // element na glavnoj dijagonali
        }
    cout << trag << endl;
    return 0;
}

ZADATAK 04Težina: Srednje

Rotacija matrice

Data je matrica n × m. Ispiši je zarotiranu za 90° u smeru kazaljke na satu.

Primer

Ulaz

2 3
1 2 3
4 5 6

Izlaz

4 1
5 2
6 3

Rešenje (C++)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    for (auto &red : a)
        for (int &x : red) cin >> x;
    for (int j = 0; j < m; j++) {               // kolona j postaje red j
        for (int i = n - 1; i >= 0; i--) {      // odozdo nagore
            cout << a[i][j];
            if (i > 0) cout << " ";
        }
        cout << endl;
    }
    return 0;
}

Česte greške i saveti

Kod stringa pazi na indekse: poslednji znak je s[n − 1].
Za ulaz od milion i više znakova koristi ios::sync_with_stdio(false).
Zbir elemenata matrice 1000 × 1000 može da pređe opseg int – koristi long long.

Proveri znanje

Otvori kviz