PRIPREMA ZA OKRUŽNA TAKMIČENJA: 7 i 8. RAZRED
Sadržaj stranice
Dobrodošli na stranicu posvećenu pripremi za okružna takmičenja iz informatike za 5. i 6. razred. Ova stranica je deo sveobuhvatnog programa pripreme koji pretpostavlja osnovno znanje iz oblasti, a ovde se to znanje dopunjuje specifičnostima takmičarskog programa. Na ovoj stranici možete pronaći ključne teme, primere zadataka, objašnjenja i interaktivne alate koji će vam pomoći da se bolje pripremite za takmičenja.
Uvod
Ova stranica predstavlja vodič za pripremu rešavanja zadataka koji se pojavljuju na okružnim takmičenjima iz informatike, namenjen regionalnom nivou za učenike 7. i 8. razreda. Materijal ovde predstavlja dopunu osnovnog gradiva, a detaljnije osnove i dodatne primere možete pronaći putem priloženih linkova.
Takođe, dodatna priprema i vežbanje mogu se obavljati i na sajtu: https://takprog.petlja.org/osnovnaskola/posts/27.
Ovaj vodič sadrži jednostavne primere koji su sastavni deo većih zadataka, a služe kao osnova za dalju razradu i usavršavanje u rešavanju kombinatoričkih, geometrijskih i algoritamskih problema.
Analiza podserija
U ovom odeljku razmatramo kako se ulazna serija može razložiti na manje podserije. Primeri uključuju:
- Podserije fiksne dužine – na primer, grupisanje dnevnih vrednosti u sedmice (podserije od 7 uzastopnih elemenata).
- Podserije sa separatorom – na primer, niz brojeva razdvojenih nulom, gde se nula koristi kao separator između podserija.
Slede dva primera sa objašnjenjima i kodom:
Primer 1: Podserije fiksne dužine (sedmice)
Pretpostavimo da imamo niz dnevnih vrednosti i želimo da ih podelimo u podserije od 7 uzastopnih elemenata, što odgovara sedmici u jednoj godini. U ovom primeru, program učitava broj dnevnih vrednosti, zatim učitava vrednosti i na kraju ispisuje sedmične grupe.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cout << "Unesite broj dnevnih vrednosti: ";
cin >> n; // Učitavanje broja elemenata
vector<int> dnevne(n);
cout << "Unesite dnevne vrednosti: " << endl;
for (int i = 0; i < n; i++) {
cin >> dnevne[i]; // Učitavanje pojedinačne vrednosti
}
cout << "Podserije (sedmice):" << endl;
for (int i = 0; i < n; i++) {
cout << dnevne[i] << " ";
if ((i + 1) % 7 == 0)
cout << endl; // Prelazak u novi red nakon svakih 7 elemenata
}
return 0;
}
Primer 2: Podserije sa separatorom
U ovom primeru, ulazni niz brojeva sadrži podserije koje su razdvojene nulom kao separatorom. Na primer, ako je ulaz: 5 3 7 0 8 9 2 0 4 1, onda se niz deli na tri podserije:
- 5 3 7 – elementi pre prve nule,
- 8 9 2 – elementi između prve i druge nule,
- 4 1 – elementi posle druge nule.
Program prepoznaje nulu kao separator i izdvaja sve podserije za dalju obradu.
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> brojevi;
int x;
cout << "Unesite brojeve (0 kao separator): " << endl;
while (cin >> x) {
brojevi.push_back(x); // Čuvanje unetih brojeva u vektor
}
cout << "Podserije:" << endl;
vector<int> segment;
for (int i = 0; i < brojevi.size(); i++) {
if (brojevi[i] == 0) {
for (int j = 0; j < segment.size(); j++) {
cout << segment[j] << " ";
}
cout << endl;
segment.clear(); // Čišćenje segmenta nakon ispisivanja
} else {
segment.push_back(brojevi[i]); // Dodavanje broja u tekući segment
}
}
if (!segment.empty()) {
for (int j = 0; j < segment.size(); j++) {
cout << segment[j] << " ";
}
cout << endl;
}
return 0;
}
Ovi primeri pokazuju kako se ulazna serija može razložiti na manje segmente (podserije) u zavisnosti od zadatog kriterijuma (fiksna dužina ili separator). Ova tehnika je korisna u analizi podataka i pripremi za takmičenja iz informatike.
Za dodatne informacije i primere, pogledajte resurse na stranici: Stringovi u C++ jeziku.
Za dodatne informacije o vektorima u c++, pogledajte resurse na stranici: Vektori u C++ jeziku.
Testirajte svoj kod ovde
Transformacije sa nizovima
Formiranje novog niza na osnovu postojećeg
U ovom primeru ćemo formirati novi niz koji sadrži samo parne brojeve iz postojećeg niza. Na ovaj način se demonstrira kako možemo izvući određene elemente iz originalnog niza i smestiti ih u novi niz. Rezultujući niz može imati manji broj elemenata nego početni.
Program učitava postojeći niz, proverava uslov za svaki element, a zatim elemente koji zadovoljavaju uslov (parni brojevi) dodaje u novi niz.
#include <iostream>
using namespace std;
int main() {
const int size = 8; // Veličina originalnog niza
int original[size] = {1, 2, 3, 4, 5, 6, 7, 8}; // Originalni niz
int novi[size]; // Niz za parne brojeve (maksimalne dužine size)
int count = 0; // Brojač za nove elemente
for (int i = 0; i < size; i++) {
if (original[i] % 2 == 0) {
novi[count] = original[i]; // Dodavanje parnog broja u novi niz
count++; // Povećanje brojača
}
}
cout << "Novi niz (samo parni brojevi): " << endl;
for (int i = 0; i < count; i++) {
cout << novi[i] << " ";
}
cout << endl;
return 0;
}
Premeštanje elemenata u okviru niza (ciklični pomeraj)
U ovom primeru prikazujemo kako se elementi niza mogu ciklično pomeriti udesno za određeni broj mesta. Program koristi privremeni niz za čuvanje poslednjih k elemenata, zatim pomera preostale elemente udesno, a na kraju vraća privremene elemente na početak.
Ovo je korisno kada je potrebno izvršiti rotaciju elemenata niza, na primer, kod problema iz takmičenja.
#include <iostream>
using namespace std;
int main() {
const int size = 8;
int arr[size] = {1, 2, 3, 4, 5, 6, 7, 8};
int k; // Broj mesta za ciklični pomeraj
cout << "Unesite broj mesta za ciklični pomeraj: ";
cin >> k;
// Normalizacija k (ako je k veći od veličine niza)
k = k % size;
if (k == 0) {
cout << "Niz ostaje nepromenjen." << endl;
return 0;
}
int temp[k]; // Privremeni niz za čuvanje poslednjih k elemenata
// Čuvanje poslednjih k elemenata u privremeni niz
for (int i = 0; i < k; i++) {
temp[i] = arr[size - k + i];
}
// Pomeranje preostalih elemenata udesno
for (int i = size - 1; i >= k; i--) {
arr[i] = arr[i - k];
}
// Vraćanje elemenata iz privremenog niza na početak
for (int i = 0; i < k; i++) {
arr[i] = temp[i];
}
cout << "Niz nakon cikličnog pomeraja: ";
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
Ovi primeri pokazuju kako se, pomoću ugnežđenih petlji, može formirati novi niz na osnovu postojećeg i kako se elementi niza mogu ciklično premeštati. Ove tehnike su od velikog značaja u rešavanju problema sa manipulacijom podataka na takmičenjima iz informatike.
Za dodatne informacije, pogledajte resurse na stranici: Nizovi u jeziku C++.
Uvod u matrice
Matrice (dvodimenzionalni nizovi) predstavljaju ključnu strukturu za organizaciju i obradu podataka u programiranju. One omogućavaju da se podaci rasporede u redove i kolone, što je od velikog značaja za rešavanje različitih problema – od jednostavnih tabela do kompleksnih matematičkih i statističkih analiza.
Za više informacija o osnovama rada sa matricama u C++, posetite stranicu Dvodimenzioni nizovi u programskom jeziku C++. Ukoliko vas zanima dinamički pristup i rad sa matricama, pogledajte i stranicu Dvodimenzioni dinamički nizovi i matrice u C++.
Primer 3: Prebrojavanje statistika nad matricom
U ovom primeru, imamo matricu i potrebno je izračunati osnovne statistike: zbir, proizvod, minimum i maksimum svih elemenata. Takođe, vrši se linearno pretraživanje za određeni element, preslikavanje (transformacija svakog elementa) i filtriranje (izdvajanje elemenata koji zadovoljavaju uslov).
#include <iostream>
using namespace std;
int main() {
const int rows = 3, cols = 4;
int matrix[rows][cols] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}
};
int sum = 0, prod = 1, minVal = matrix[0][0], maxVal = matrix[0][0];
bool found = false;
int searchValue = 7;
int mapped[rows][cols]; // Novi niz sa transformisanim elementima
int filtered[rows * cols]; // Niz za filtrirane elemente
int countFiltered = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
int val = matrix[i][j];
sum += val;
prod *= val;
if (val < minVal) minVal = val;
if (val > maxVal) maxVal = val;
if (val == searchValue) found = true;
mapped[i][j] = val * 2; // Preslikavanje: svaki element se udvostruči
if (val % 2 == 0) {
filtered[countFiltered] = val;
countFiltered++;
}
}
}
cout << "Sum: " << sum << endl;
cout << "Product: " << prod << endl;
cout << "Min: " << minVal << endl;
cout << "Max: " << maxVal << endl;
cout << "Element " << searchValue << " "
<< (found ? "je pronadjen." : "nije pronadjen." ) << endl;
cout << "Mapped matrix:" << endl;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
cout << mapped[i][j] << " ";
}
cout << endl;
}
cout << "Filtered even numbers:" << endl;
for (int i = 0; i < countFiltered; i++) {
cout << filtered[i] << " ";
}
cout << endl;
return 0;
}
Primer 4: Statistika nad vrstama, kolonama i dijagonalama
U ovom primeru, imamo kvadratnu matricu i računamo statistike za svaku vrstu, kolonu i glavne dijagonale. Na primer, može se izračunati maksimum u svakoj vrsti, a zatim se iz tih maksimuma bira najmanji – što predstavlja kombinaciju "najmanji od maksimuma".
#include <iostream>
using namespace std;
int main() {
const int size = 3;
int matrix[size][size] = {
{5, 7, 3},
{9, 2, 8},
{4, 6, 1}
};
// Računanje maksimuma u svakoj vrsti
int rowMax[size];
for (int i = 0; i < size; i++) {
int maxVal = matrix[i][0];
for (int j = 0; j < size; j++) {
if (matrix[i][j] > maxVal)
maxVal = matrix[i][j];
}
rowMax[i] = maxVal;
}
// Određivanje najmanjeg maksimuma iz svih vrsta
int minOfRowMax = rowMax[0];
for (int i = 1; i < size; i++) {
if (rowMax[i] < minOfRowMax)
minOfRowMax = rowMax[i];
}
cout << "Najmanji od maksimuma po vrstama: " << minOfRowMax << endl;
return 0;
}
Primer 5: Pristupanje pravougaonim i trougaonim delovima matrice
U ovom primeru, prikazuje se kako se pristupa elementima pravougaonog dela matrice kao i trougaonom delu. Na primer, iz matrice se može izdvojiti pravougaoni podniz ili donji trougaoni deo.
#include <iostream>
using namespace std;
int main() {
const int rows = 4, cols = 4;
int matrix[rows][cols] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}
};
// Pravougaoni podniz: izdvajanje elemenata iz redova 1-2 i kolona 2-3
cout << "Pravougaoni podniz:" << endl;
for (int i = 1; i <= 2; i++) {
for (int j = 2; j <= 3; j++) {
cout << matrix[i][j] << " ";
}
cout << endl;
}
// Trougaoni podniz: donji trougaoni deo matrice
cout << "Donji trougaoni deo matrice:" << endl;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < rows; j++) {
if (j <= i)
cout << matrix[i][j] << " ";
else
cout << "0 ";
}
cout << endl;
}
return 0;
}
Ovi primeri pokazuju kako se matrica može analizirati na više načina: izračunavanjem statistika, pretraživanjem, preslikavanjem, filtriranjem, kao i pristupanjem posebnim segmentima matrice.
Za više informacija, pogledajte resurse na stranici: Nizovi u jeziku C++.
Analiza podserija: Pristupanje elementima pravougaonih i trougaonih delova matrice
U ovom odeljku prikazujemo kako se, koristeći ugneždene petlje, može pristupiti određenom delu matrice. Na primer, iz kvadratne matrice možemo izdvojiti pravougaoni podniz ili trougaoni deo.
Primer 1: Pristupanje elementima pravougaonog dela matrice
U sledećem primeru imamo matricu dimenzija 4x4. Program izdvaja elemente iz reda 1 i 2 i kolona 2 i 3, čime se formira pravougaoni podniz.
#include <iostream>
using namespace std;
int main() {
const int rows = 4, cols = 4;
int matrix[rows][cols] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}
};
// Izdvajanje pravougaonog dela: redovi 1 i 2 (indeksi 1 i 2) i kolone 2 i 3 (indeksi 2 i 3)
cout << "Pravougaoni podniz:" << endl;
for (int i = 1; i <= 2; i++) {
for (int j = 2; j <= 3; j++) {
cout << matrix[i][j] << " ";
}
cout << endl;
}
return 0;
}
Primer 2: Premeštanje pravougaonog dela u okviru matrice
U ovom primeru prikazujemo kako se premešta određeni pravougaoni deo matrice na novu poziciju unutar iste matrice. Pretpostavimo da želimo da pomerimo podniz definisan redovima 1 i 2 i kolonama 1 i 2 na poziciju gde počinje na redu 2 i koloni 2.
#include <iostream>
using namespace std;
int main() {
const int rows = 4, cols = 4;
int matrix[rows][cols] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}
};
// Definisanje pravougaonog dela za premeštanje: redovi 1 i 2, kolone 1 i 2
int temp[2][2];
// Kopiranje podniza u privremeni niz
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
temp[i][j] = matrix[i+1][j+1];
}
}
// Premeštanje kopiranog dela na novu poziciju: počevši od reda 2, kolone 2
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
matrix[i+2][j+2] = temp[i][j];
}
}
// Ispis matrice nakon premeštanja
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
cout << matrix[i][j] << "\t";
}
cout << endl;
}
return 0;
}
Ovi primeri demonstriraju dve tehnike: formiranje novog niza (filtriranjem ili transformacijom elemenata) i premeštanje pravougaonih delova unutar matrice. Ove tehnike su ključne za analizu i obradu podataka u zadacima sa matricama, a posebno su korisne na takmičenjima iz informatike.
Za dodatne informacije, posetite: Nizovi u jeziku C++.
Metode efikasnosti algoritama 1
Efikasno sortiranje niza
U mnogim zadacima, naročito na takmičenjima, efikasno sortiranje niza je ključno za optimizaciju algoritama. Umesto kvadratnog vremena (O(n²)) za jednostavne metode sortiranja, bibliotečka funkcija sort (iz <algorithm>) omogućava sortiranje u prosečnom vremenu od O(n log n). Ovim se postiže brže prebrojavanje različitih elemenata ili određivanje preseka dva niza.
Za detaljnija objašnjenja o efikasnom sortiranju nizova i binarnoj pretrazi, posetite stranicu: Sortiranje nizova. Binarna pretraga.
U sledećem primeru, niz se sortira, a zatim se koriste funkcije unique i aritmetičke operacije za prebrojavanje različitih elemenata:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
vector<int> arr = {5, 3, 8, 5, 2, 8, 1};
// Sortiranje niza u rastućem redosledu
sort(arr.begin(), arr.end());
cout << "Sortirani niz: " << endl;
for (int x : arr) {
cout << x << " ";
}
// Prebrojavanje različitih elemenata
int distinct = unique(arr.begin(), arr.end()) - arr.begin();
cout << "\nBroj različitih elemenata: " << distinct << endl;
return 0;
}
Binarna pretraga sortiranog niza
Kada je niz sortiran, korišćenjem funkcije binary_search (iz <algorithm>) može se brzo pronaći da li određeni element postoji u nizu. Ova metoda ima vremensku složenost O(log n) u odnosu na linearno pretraživanje koje traje O(n). Takođe, koristeći lower_bound i upper_bound moguće je odrediti broj pojavljivanja određenog elementa.
Sledeći primer prikazuje kako se vrši binarna pretraga i prebrojavanje pojavljivanja elementa 5 u sortiranom nizu:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
vector<int> arr = {1, 2, 3, 4, 5, 5, 5, 6, 7};
// Niz je već sortiran, ali ukoliko nije, pozvati: sort(arr.begin(), arr.end());
bool found = binary_search(arr.begin(), arr.end(), 5);
cout << "Element 5 " << (found ? "je pronadjen." : "nije pronadjen.") << endl;
// Prebrojavanje pojavljivanja elementa 5
int count = upper_bound(arr.begin(), arr.end(), 5) - lower_bound(arr.begin(), arr.end(), 5);
cout << "Broj pojavljivanja elementa 5: " << count << endl;
return 0;
}
Elementi teorije brojeva 1
Ova tema pokriva osnovne koncepte teorije brojeva, uključujući izračunavanje broja i zbira delioca prirodnog broja, utvrđivanje da li je broj prost, kao i nalaženje prostih brojeva. Razumevanje ovih osnova je ključno za rešavanje mnogih zadataka, posebno na takmičenjima.
1. Broj i zbir delioca prirodnog broja
Za dati prirodan broj, potrebno je pronaći sve njegove delioca i izračunati koliko ih ima i koliki je njihov zbir. Na primer, za broj 12, delioci su 1, 2, 3, 4, 6 i 12, a zbir im je 28.
#include <iostream>
using namespace std;
int main() {
int n;
cout << "Unesite prirodan broj: ";
cin >> n;
int count = 0, sum = 0;
for (int i = 1; i <= n; i++) {
if (n % i == 0) {
count++; // Povećaj broj delioca
sum += i; // Saberi delioca
}
}
cout << "Broj delioca: " << count << endl;
cout << "Zbir delioca: " << sum << endl;
return 0;
}
2. Utvrđivanje da li je broj prost
Broj je prost ako ima tačno dva delioca, 1 i sam broj. Sledeći primer proverava da li je uneti broj prost korišćenjem jednostavne petlje.
#include <iostream>
using namespace std;
int main() {
int n;
cout << "Unesite broj: ";
cin >> n;
bool isPrime = true;
if (n < 2) {
isPrime = false;
} else {
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
isPrime = false;
break; // Ako je pronađen delilac, broj nije prost
}
}
}
cout << n << " je "
<< (isPrime ? "prost." : "nije prost." )
<< endl;
return 0;
}
Za dodatne resurse i primere o prostim brojevima i faktorizaciji , pogledajte stranicu: Prosti brojevi i faktorizacija.
Analiza podserija: Rastavljanje broja na proste činioce i primene
U ovoj temi razmatramo kako se broj može rastaviti na svoje proste činioce korišćenjem jednostavnih algoritama sa kompleksnošću O(√n). Na osnovu dobijene faktorizacije, moguće je izračunati najmanji prirodni broj kojim treba pomnožiti dati broj da bi se dobio potpuni kvadrat ili kub. Ovaj pristup je od velikog značaja u takmičarskim zadacima gde se traže optimizovana rešenja.
#include <iostream>
using namespace std;
int main() {
int n;
cout << "Unesite broj: ";
cin >> n;
// Rastavljanje broja na proste činioce
cout << "Prosti činioci broja: ";
int original = n;
for (int i = 2; i * i <= n; i++) {
while (n % i == 0) {
cout << i << " ";
n /= i;
}
}
if (n > 1)
cout << n;
cout << endl;
// Primenjena metoda: nalaženje najmanjeg prirodnog broja kojim se daje broj udvostručuje (potpuni kvadrat)
int multiplier = 1;
n = original;
for (int i = 2; i * i <= n; i++) {
int count = 0;
while (n % i == 0) {
count++; // Broji eksponente
n /= i;
}
if (count % 2 == 1)
multiplier *= i; // Ako je eksponent neparan, uključujemo i u multiplier
}
if (n > 1) multiplier *= n;
cout << "Najmanji množioc za potpuni kvadrat: " << multiplier << endl;
return 0;
}
Analiza NZD i NZS korišćenjem Euklidovog algoritma
Euklidov algoritam omogućava brzo izračunavanje najvećeg zajedničkog delioca (NZD) dva broja. Na osnovu NZD, lako se može izračunati najmanji zajednički sadržalac (NZS). Ove tehnike se često koriste u problemima kao što su skraćivanje razlomaka ili optimizacija zadataka u takmičenjima.
#include <iostream>
using namespace std;
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int main() {
int a, b;
cout << "Unesite dva broja: ";
cin >> a >> b;
int nzd = gcd(a, b);
int nzs = (a / nzd) * b; // NZS se računa korišćenjem NZD
cout << "NZD: " << nzd << endl;
cout << "NZS: " << nzs << endl;
cout << "Skraćeni razlomak: " << (a / nzd) << "/" << (b / nzd) << endl;
return 0;
}
Ove primere možete detaljnije proučiti na stranici: Prosti brojevi i faktorizacija. Euklidov algoritam.
Elementi efikasnosti algoritama 2
Takmičar treba da ume da oceni vremensku složenost algoritma koji primenjuje. To znači da je važno razumeti osnovne principe analize algoritama, kako bi se moglo predvideti koliko brzo će program izvršavati određene operacije. Za osnovni uvod u efikasnost algoritama, pogledajte informacije na portalu petlja.org.
Mnogi problemi se mogu efikasnije rešiti u odnosu na naivno rešenje primenom jedne ili više tehnika. Primeri ovih tehnika uključuju:
- Optimizaciju petlji (smanjenje broja iteracija ili zamena ugnežđenih petlji jednim, kada je to moguće),
- Korišćenje dinamičkog programiranja za eliminisanje ponovljenih proračuna,
- Tehniku "podeli i osvoji" (divide and conquer) za brže rešenje kompleksnih problema,
- Upotrebu efikasnijih struktura podataka, kao što su hash tabele ili prioritetni redovi,
- Korišćenje sortiranja i binarne pretrage umesto linearne pretrage,
- Primenu memorisanja (memoization) u rekurzivnim algoritmima.
Razumevanje ovih tehnika omogućava takmičarima da prepoznaju kada je moguće unaprediti naivno rešenje i da izaberu najefikasniji pristup za rešavanje datog problema.
Elementi efikasnosti algoritama 2 – Transformisanje nizova
U ovoj temi razmatramo dve tehnike koje poboljšavaju efikasnost algoritama:
- Primena matematičkih formula: Umesto da se prolazi kroz sve elemente niza (što traje linearno vreme), možemo izračunati zbir ili druge operacije korišćenjem poznatih formula u konstantnom vremenu. Na primer, zbir prvih n članova aritmetičkog niza se računa pomoću formule: S = n/2 * (2a + (n - 1)*d), gde je a prvi član, d je razlika, a n broj članova.
- Inkrementalno računanje: Umesto da se svaki put iznova računa vrednost od početka (što može biti kvadratno vreme), prethodni rezultat se koristi za brzo izračunavanje sledećeg. Primeri ovoga su izračunavanje svih prefiksnih suma ili faktorijela brojeva od 1 do n.
Slede konkretni primeri sa objašnjenjima i komentarima u kodu:
Primer 1: Zbir prvih n članova aritmetičkog niza
Program učitava početni član a, razliku d i broj članova n i zatim izračunava zbir koristeći formulu: S = n/2 * (2a + (n - 1)*d). Ovaj proračun se vrši u konstantnom vremenu.
#include <iostream>
using namespace std;
int main() {
double a, d; // a: prvi član, d: razlika
int n; // Broj članova niza
cout << "Unesite a, d i n: ";
cin >> a >> d >> n;
double S = n / 2.0 * ( 2 * a + (n - 1) * d ); // Izračunavanje zbira pomoću formule
cout << "Zbir prvih n članova: " << S << endl;
return 0;
}
Primer 2: Izračunavanje prefiksnih suma
U ovom primeru se učitava niz celih brojeva i zatim se za svaki element niza izračunava prefiksna suma – zbir svih elemenata od početka niza do tekućeg elementa. Ovaj pristup je efikasan jer se svaka suma izračunava inkrementalno, koristeći prethodni rezultat, što traje linearno vreme.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cout << "Unesite broj elemenata niza: ";
cin >> n;
vector<int> arr(n);
cout << "Unesite elemente niza: " << endl;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
vector<int> prefixSums(n);
prefixSums[0] = arr[0]; // Prva prefiksna suma je prvi element
for (int i = 1; i < n; i++) {
prefixSums[i] = prefixSums[i - 1] + arr[i]; // Inkrementalno računanje prefiksnih suma
}
cout << "Prefiksne sume: " << endl;
for (int i = 0; i < n; i++) {
cout << prefixSums[i] << " ";
}
cout << endl;
return 0;
}
Za dodatne informacije o tehnikama transformisanja i generisanja nizova, kao i efikasnom pristupu u algoritamskoj analizi, pogledajte resurse na stranici: Nizovi u jeziku C++.
Tehnika dva pokazivača (Two Pointer Technique)
Tehnika dva pokazivača je optimizovana metoda za rešavanje problema koji uključuju iteraciju kroz nizove ili liste. Koristi se kada je potrebno efikasno pronaći određene parove elemenata, segmentirati podatke ili obraditi niz u jednom prolazu.
Princip rada
Dva pokazivača (indeksa) postavljaju se na različite pozicije unutar niza, obično na:
- Početak i kraj (za probleme sa sumama, pretragom parova).
- Dva uzastopna elementa (za probleme sa spajanjem, pomeranjem podataka).
- Različite delove niza (za specifične zadatke poput sortiranja ili particionisanja).
Primer: Pronalaženje dva broja u sortiranom nizu koji daju određeni zbir
Imamo sortiran niz i želimo da pronađemo dva broja čiji zbir daje određenu vrednost target. Umesto da koristimo dva ugnježdena for petlje (O(n2)), koristimo dva pokazivača za rešenje u O(n) vremenskoj složenosti.
Pokazivači u početku pokazuju na početak i na kraj niza. Proverava se da li zbir elemenata na koji pokazuju jednak traženom (target). Ako jeste petlja se prekida, a ako nije razmatramo dva slučaja:
1) zbir je manji od traženog i treba ga povećati i u tom slučaju pomera se pokazivač levog elementa na desno, s obzirom da je niz sortiran rastuće pa će se na taj način dobiti povećanje zbira.
2) zbir je veći od traženog pa ga treba snanjivati. To će se postići pomeranjem desnog pokazivača ulevo, ka manjim vrednostima.
#include <iostream>
using namespace std;
bool twoSum(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
cout << "Brojevi su: " << arr[left] << " i " << arr[right] << endl;
return true;
} else if (sum < target) {
left++; // Povećavamo levog pokazivača (treba veći zbir)
} else {
right--; // Smanjujemo desnog pokazivača (treba manji zbir)
}
}
return false;
}
int main() {
int arr[] = {1, 2, 4, 7, 11, 15};
int target = 9;
int n = sizeof(arr) / sizeof(arr[0]);
if (!twoSum(arr, n, target)) {
cout << "Nema takvih brojeva!" << endl;
}
return 0;
}
Objašnjenje koda:
- Postavljamo dva pokazivača: left na početak niza i right na kraj niza.
- Računamo zbir elemenata: arr[left] + arr[right].
- Ako je zbir manji od target-a, povećavamo left (potreban nam je veći broj).
- Ako je zbir veći, smanjujemo right (potreban nam je manji broj).
- Ako je zbir jednak target-u, ispisujemo brojeve i završavamo pretragu.
- Petlja se ponavlja dok se pokazivači ne sretnu.
Gde se koristi ova tehnika?
- Pretraga u sortiranom nizu (kao u primeru iznad).
- Određivanje najveće dužine podniza sa određenim svojstvima.
- Preuređivanje niza bez dodatne memorije (npr. premještanje svih nula na kraj).
- Određivanje trougaonih tripleta u sortiranom nizu.
Napredne strukture podataka u rešavanju problema
Napredne strukture podataka, kao što su torke (tuples), rečnici (dictionaries), mape (maps) i skupovi (sets), omogućavaju efikasnije rešavanje problema u programiranju. One pomažu u organizaciji podataka na način koji omogućava bržu pretragu, sortiranje i pristup, čime se optimizuju algoritmi i smanjuje ukupno vreme izvršavanja.
Na primer, korišćenje rečnika ili mapa omogućava brzo pronalaženje parova elemenata sa određenim svojstvima (kao što je pronalaženje svih parova čiji zbir odgovara datoj vrednosti) jer se pretraga vrši u vremenu O(log n) ili čak O(1) u slučaju hash mapa. S druge strane, skupovi se koriste za brzo testiranje pripadnosti i eliminisanje duplikata, dok torke omogućavaju čuvanje heterogenih podataka u fiksnom redosledu.
Kombinovanjem ovih struktura sa efikasnim algoritmima, kao što su sortiranje i binarna pretraga, možete postići znatno bolje performanse u rešavanju kompleksnih problema. Ovo je naročito važno u takmičarskim zadacima gde je efikasnost algoritma ključna.
Za dodatne informacije i primere upotrebe ovih naprednih struktura podataka, posetite stranicu: Rečnici, mape i skupovi u C++.
Upotreba torki/struktura, rečnika/mapa i skupova u C++ za efikasne algoritme
Napredne strukture podataka kao što su torke (tuples), rečnici (dictionaries), mape (maps) i skupovi (sets) omogućavaju brzo i efikasno rešavanje problema. U nastavku je prikazan primer za nalaženje parova elemenata niza koji daju zadati zbir S. Ovaj primer koristi unordered_map za evidentiranje brojeva iz niza, što omogućava pretragu u prosečnom vremenu O(1).
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
void pronadjiParoveHashMap(vector<int>& niz, int S) {
unordered_map<int, int> mapa; // Kreiramo mapu za evidentiranje brojeva
for (int broj : niz) { // Iteriramo kroz sve brojeve u nizu
int potreban = S - broj; // Izračunavamo komplementarni broj
if (mapa.find(broj) == mapa.end()) {
// Ako broj nije ranije viđen, ne radimo ništa
}
if (mapa.find(potreban) != mapa.end()) { // Ako je komplementarni broj pronađen
cout << "Par: (" << potreban << ", " << broj << ")\n";
}
mapa[broj]++; // Evidentiramo trenutni broj u mapi
}
}
int main() {
vector<int> niz = {1, 4, 7, 3, 2, 5, 8};
int S = 9; // Zadati zbir
pronadjiParoveHashMap(niz, S); // Poziv funkcije za pronalaženje parova
return 0; // Završetak programa
}
Objašnjenje rešenja
U ovom rešenju, za svaki element x iz niza se računa komplementarni broj (S - x). Ako je komplementarni broj već evidentiran u mapi, to znači da postoji par čiji zbir iznosi S i taj par se ispisuje. Koristeći unordered_map omogućeno je brzo pretraživanje, što čini ovaj algoritam efikasnim sa vremenskom složenošću O(n).
Za dodatne informacije o mapama i rečnicima, pogledajte resurse na stranici: Rečnici i mape u C++.
Upotreba prefiksnih i sufiksnih suma i kombinacija prethodnih tehnika
U ovoj temi, pokazaćemo kako se mogu koristiti tehnike koje smanjuju vremensku složenost algoritama:
- Primena matematičkih formula: Umesto iterativnog računanja, neke operacije (npr. zbir aritmetičkog niza) mogu se izračunati u konstantnom vremenu koristeći poznate formule.
- Inkrementalno računanje: Izračunavanje prefiksnih ili sufiksnih suma omogućava brzo dobijanje zbira bilo kog segmenta niza, što je linearno u odnosu na veličinu niza, a znatno brže od kvadratnog rešenja.
- Kombinacija prethodnih tehnika: Kombinovanjem sortiranja, upotrebe mapa/skupova i inkrementalnog računanja moguće je rešavati složenije zadatke, kao što su broj pojavljivanja određenog elementa u nesortiranom nizu ili pronalaženje trojki čiji zbir odgovara zadatoj vrednosti.
Slede primeri sa objašnjenjima i komentarima u kodu:
Primer 1: Izračunavanje prefiksnih suma
Ovim primerom se demonstrira kako se, uz jedan prolaz kroz niz, mogu izračunati prefiksne sume, tj. zbir svih elemenata od početka do svakog indeksa. Ovo omogućava da se kasnije brzo odgovori na upit o sumi bilo kog segmenta niza, smanjujući vremensku složenost sa O(n²) na O(n).
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cout << "Unesite broj elemenata niza: ";
cin >> n;
vector<int> arr(n);
cout << "Unesite elemente niza: " << endl;
for (int i = 0; i < n; i++) {
cin >> arr[i]; // Učitavanje elemenata niza
}
vector<int> prefix(n);
prefix[0] = arr[0]; // Prvi element je početna suma
for (int i = 1; i < n; i++) {
prefix[i] = prefix[i - 1] + arr[i]; // Inkrementalno računanje prefiksnih suma
}
cout << "Prefiksne sume: " << endl;
for (int i = 0; i < n; i++) {
cout << prefix[i] << " ";
}
cout << endl;
return 0;
}
Primer 2: Trojke elemenata niza sa zadatim zbirom
U ovom primeru, iz nesortiranog niza se pronalaze sve trojke elemenata čiji zbir odgovara zadatoj vrednosti. Iako naivno rešenje koristi tri ugneždene petlje sa vremenskom složenošću O(n³), ova tehnika pokazuje kako se kombinacijom prethodnih metoda mogu rešavati kompleksniji problemi.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, target;
cout << "Unesite broj elemenata niza: ";
cin >> n;
vector<int> arr(n);
cout << "Unesite elemente niza: " << endl;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "Unesite ciljnu vrednost: ";
cin >> target;
// Pronalaženje svih trojki čiji zbir je jednak target
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
if (arr[i] + arr[j] + arr[k] == target) {
cout << "Trojka: (" << arr[i]
<< ", " << arr[j]
<< ", " << arr[k]
<< ")" << endl;
}
}
}
}
return 0;
}
Ovi primeri pokazuju kako se različite tehnike mogu kombinovati kako bi se optimizovalo rešavanje problema. Za dodatne informacije o transformisanju i generisanju nizova, kao i efikasnim algoritmima, posetite resurs: Nizovi u jeziku C++.
Problem prekoračenja i memorijska složenost algoritma
U ovom primeru prikazujemo dva važna aspekta:
- Prekoračenje (overflow): Kada se sabiraju veliki brojevi u nizu koristeći tip int, može doći do prekoračenja ukoliko zbir prevaziđe maksimalnu vrednost koju taj tip može da drži. Ovo može dovesti do netačnih rezultata.
- Memorijska složenost: Algoritam sabiranja niza zahteva memoriju proporcionalnu broju elemenata u nizu, tj. O(n). Odabir odgovarajućeg tipa podataka pomaže u optimizaciji memorijske upotrebe.
Sledeći primer demonstrira sabiranje elemenata niza korišćenjem tipa int i ukazuje na mogućnost prekoračenja, kao i na linearnu memorijsku složenost algoritma.
#include <iostream>
using namespace std;
int main() {
int n;
cout << "Unesite broj elemenata niza: "; // Učitavanje broja elemenata
cin >> n;
// Alokacija niza – memorijska složenost O(n)
int arr[1000]; // Pretpostavimo da n ne prelazi 1000
for (int i = 0; i < n; i++) {
cin >> arr[i]; // Učitavanje elemenata niza
}
int sum = 0;
// Sabiranje elemenata niza
for (int i = 0; i < n; i++) {
sum += arr[i]; // Moguće prekoračenje ako je zbir prevelik
}
cout << "Zbir elemenata niza: " << sum << endl;
// Ovaj algoritam ima vremensku složenost O(n) i memorijsku složenost O(n)
return 0;
}
Uvod u rekurziju
Rekurzija je tehnika u kojoj funkcija poziva samu sebe kako bi rešila manji deo problema, a zatim kombinuje rezultate da bi se dobilo rešenje celokupnog problema. Ova metoda je posebno korisna kada se problem može podeliti na slične podprobleme. Za detaljnije objašnjenje rekurzivnih algoritama, posetite stranicu: Rekurzivni algoritmi.
Primer: Izračunavanje faktorijela (n!) rekurzivno
U sledećem primeru, rekurzivna funkcija factorial računa faktorijel broja n. Ako je n manji ili jednak 1, funkcija vraća 1 (osnovni slučaj). U suprotnom, funkcija vraća proizvod broja n i faktorijela od n-1 (rekurzivni slučaj).
#include <iostream>
using namespace std;
int factorial(int n) {
if (n <= 1) {
// Osnovni slučaj: 0! i 1! su jednaki 1
return 1;
} else {
// Rekurzivni slučaj: n! = n * (n-1)!
return n * factorial(n - 1);
}
}
int main() {
int n;
cout << "Unesite broj: ";
cin >> n;
cout << "Faktorijel od " << n << " je "
<< factorial(n) << endl;
return 0;
}
Primena rekurzije u kombinatoričkim problemima
Rekurzija je tehnika u kojoj funkcija poziva samu sebe kako bi rešila manji deo problema, a zatim kombinuje rezultate da bi se dobilo rešenje celokupnog problema. Ova metoda je posebno korisna u kombinatoričkim zadacima, gde se generišu sve moguće n-torke, permutacije, kombinacije i varijacije. Iako rekurzivna rešenja često imaju eksponencijalnu vremensku složenost, ona su elegantna i lako se implementiraju kada su ulazni podaci mali.
U nastavku su prikazani primeri za dve podteme:
- Generisanje n-torki pomoću rekurzije (npr. binarne n-torke bez susednih istih elemenata),
- Generisanje permutacija niza pomoću rekurzije.
Za dodatne informacije o rekurziji i kombinatorici, posetite resurse na relevantnim stranicama.
Primer 1: Generisanje binarnih n-torki bez susednih istih elemenata
Ovaj primer koristi rekurziju za generisanje svih binarnih n-torki (stringova dužine n sastavljenih od '0' i '1') sa uslovom da nema dve uzastopne '1'. Funkcija poziva samu sebe i dodaje '0' ili '1' u trenutni string, a uslov osigurava da, ukoliko je poslednji karakter '1', sledeći mora biti '0'.
#include <iostream>
#include <string>
using namespace std;
void generateBinaryTuples(string curr, int n) {
if (curr.size() == n) {
cout << curr << endl; // Ako je n-torka kompletna, ispisujemo je
return;
}
if (curr.empty() || curr.back() == '0') {
generateBinaryTuples(curr + '0', n); // Može se dodati '0'
generateBinaryTuples(curr + '1', n); // Može se dodati i '1'
} else {
generateBinaryTuples(curr + '0', n); // Ako je poslednji karakter '1', sledeći mora biti '0'
}
}
int main() {
int n;
cout << "Unesite dužinu n-torke: ";
cin >> n;
generateBinaryTuples("", n);
return 0;
}
Primer 2: Generisanje permutacija niza
U ovom primeru rekurzivno generišemo sve permutacije niza celih brojeva. Funkcija permute koristi tehniku backtrackinga kako bi razmenjivala elemente niza i ispisivala svaki jedinstveni raspored.
#include <iostream>
#include <vector>
using namespace std;
void permute(vector<int>& arr, int start) {
if (start == arr.size() - 1) {
for (int x : arr)
cout << x << " ";
cout << endl;
return;
}
for (int i = start; i < arr.size(); i++) {
swap(arr[start], arr[i]); // Razmena elemenata
permute(arr, start + 1);
swap(arr[start], arr[i]); // Vraćanje elemenata na mesto (backtracking)
}
}
int main() {
vector<int> arr = {1, 2, 3};
permute(arr, 0);
return 0;
}
Za dodatne informacije o rekurziji i generisanju kombinatoričkih objekata, pogledajte resurse na relevantnim stranicama.
|
Sledeće
Kvalifikacije za okružna takmičenja >| |