SVET PROGRAMIRANJA

PRIPREMA ZA DRŽAVNO TAKMIČENJE IZ INFORMATIKE

Ova stranica je vodič za pripremanje rešavanja zadatka koja se pojavljuju na državnim takmičenjima iz informatike, za osnovne škole. Takođe su pokazani jednostavni primeri koji su sastavni deo većih zadataka.
Ako se prethodno niste pripremili za okržno takmičenje pogledajte stranu Priprema za okružna takmičenja

Državno takmičenje iz 2021

Zadatke sa rešenjima i test primerima možete preuzeti sa sjta društva matematičara srbije: dms.rs/informatika-osnovne-skole/

1. Prašuma

Napomena: Zadatak je preuzet sa sjta društva matematičara srbije: dms.rs/informatika-osnovne-skole/

U prašumi je nađena čudesna tablica sa 3 reda i 3 kolone ispunjena ciframa. Pored tablice je nađen tekst zagonetke. Zagonetka kaže: Formirajte prvi trocifreni broj na osnovu cifara sa glavne dijagonale tablice, počev od vrha i idući ka dnu tablice. Zatim formirajte još jedan trocifreni broj koji se sastoji od cifara u sporednoj dijagonali, takođe počevši od vrha do dna. Rešenje zagonetke je proizvod ova dva trocifrena broja. Napišite program koji učitava cifre napisane na tablici i ispisuje proizvod dva trocifrena broja koji se formiraju na opisani način.
Pojašnjenje: Glavnu dijagonalu tablice obrazuju redom: prva cifra prvog reda, srednja cifra drugog reda i poslednja cifra trećeg reda. Sporednu dijagonalu obrazuju redom: poslednja cifra prvog reda, srednja cifra drugog reda i prva
cifra trećeg reda.
Ulaz
U svakom od tri reda standardnog ulaza date su tri cifre, zapisane bez razmaka.
Izlaz
Na standardnom izlazu, program mora da ispiše jedan ceo broj - proizvod dva
trocifrena broja koji se dobija na gore opisan način.
Primer 1
Ulaz
123
456
789
Izlaz
56763
Pojašnjenje primera: Broj formiran od cifri na glavnoj dijagonali je 159. Broj formiran od cifri na sporednoj dijagonali je 357. Proizvod ta dva broja je 56763


Analiza prvog zadatka

Da bi ste uradili ovaj zadatak jedno od mogućih načina rešavanja je upotrebom matrica i korišćenje ugnježdenih petlji. S obzirom da se ove oblasti pojavljuju na državnom takmičenju preporuka je poznavanje ovih oblasti.
Više o matricama pogledajte na strani: Dvodimenzionalni nizovi - matrice
Više o ugnježdenim petljama pročitajte na strani: Ugnježdene petlje u C/C++
Pre rešavanja zadatka sa državnog takmičenja, preporuka je da se prvo urade sledeći primeri: primer 1 i primer 2

Primer 1:

Učitati 9 brojeva u matricu 3*3. Ispisati vrednosti u glavnoj i sporednoj dijagonali. 
Primer
Ulaz:
1 2 3
4 5 6
7 8 9
Izlaz 
Glavna dijagonala: 1 5 9
Sporedna dijagonala 3 5 7

Rešiti zadatak po sledećem algoritmu:

  • Koristiti dvodimenzioni niz(matricu) za smeštanje podataka u 3 reda i 3 kolone
  • Učitati matricu. Koristiti ugnježdene petlje for. Spoljašnja treba da menja redove, a unutrašnja kolone
  • Koristiti ugnježdene petlje for sa istim kontrolnim izrazima za ispis elemenata matrice
  • Koristiti if naredbu za proveru uslova za glavnu dijagonalu. Uočiti da su za te elemente red i kolona jednaki
  • Koristiti if naredbu za proveru uslova za sporednu dijagonalu. Uočiti da su za te elemente red i kolona jednaki, ako bi kolone menjali od poslednje ka prvoj

#include < iostream >
using namespace std;
int main()
{
int A[3][3];
int X=0,Y=0;
//Menja redove
for(int i=0; i<3; i++)
{
//menja kolone
for(int j=0; j<3; j++)
{
cin >> A[i][j];
}
}
int d=1000,d1=1000;
for(int i=0; i < 3; i++)
{
//menja kolone
for(int j=0; j < 3; j++)
{
int c=A[i][j];// cifra izvađena iz matrice u i-tom redu i j-toj koloni. U ciklusima 1,5,9
if(i==j)
{
d=d/10;////100,10,1 u ciklusima redom
X=X+c*d;//vrednosti 100,150,159 u ciklusima redom
}
if(2-i==j)
{
d1=d1/10;//100,10,1 u ciklusima redom
Y=Y+c*d1;//vrednosti 300,350,357 u ciklusima redom
}
}
cout << endl;
}
cout << (X*Y) << endl; // rezultat
return 0;
}

Sastaviti broj od poznatih cifara

Primer 2:

Uneti 4 cela broja koji predstavljaju cifre četvorocifrenog broja. Sastaviti novi broj čije su cifre u obrnutom redosledu.
Primer:
Ulaz:
4
5
6
7
​Izlaz: 7654

Poslednja uneta cifra je cifra 1000 pa nju treba pomnožiti sa 1000, pretposlednju cifru sa 100, treću od nazad sa 10 itd. Dobijen broj je zbir pomenutih proizvoda

#include < iostream >
using namespace std;
int main()
{
int a,b,c,d,broj;
cin >> a >> b >> c >> d;
broj=1000*d + 100*c + 10*b + a;
cout << broj< return 0;
}

2. Zbir kvadrata neparnih cifara

Napomena: Zadatak je preuzet sa sjta društva matematičara srbije: dms.rs/informatika-osnovne-skole/

​Lenka želi da izračuna zbirove kvadrata neparnih cifara nekoliko brojeva. Pomozi Lenki i napiši program koji sa standardnog ulaza učitava jedan prirodan broj manji od milijardu i na standardni izlaz ispisuje zbir kvadrata njegovih neparnih cifara (ako takvih cifara nema, računamo da je zbir nula). Kvadrat neke cifre je jednak proizvodu te cifre sa samom sobom. Na primer, kvadrat cifre 3 je
3, jer 3×3=9
Primer 1
Ulaz
1234560
Izlaz
35
Primer 2
Ulaz
11
Izlaz
2
Primer 3
Ulaz
888
Izlaz
0

Analiza drugog zadatka

Da bi se izdvojile cifre iz broja potrebno je koristiti operatore % i /, tj. deljenje sa nekim od stepena sa osnovom 10 ili ostatka deljenja sa ovim brojevima. Sličan primer je obrađen u zadatku 4 sa web strane Podaci i tipovi podataka-dodatni primeri
Takođe je potrebno znanje iz  petlji i to kako sabrati brojeve koristeći petlju. Sličan primer je objašnjen na web strani Priprema za kontrolni zadatak iz petlji (Zadatak 3)

Rešiti zadatak po sledećem algoritmu:

  • Učitati ceo broj
  • Koristeći petlju(while) vršiti izdvajanje poslednje cifre sa desne strane iz ostatka broja
  • Ostatak broja je taj broj na pre početka petlje, a unutar petlje se transformiše tako što se deljenjem sa 10 uklanja jedna cifra
  • Postupak se ponavlja dok je ostatak broja veći od nule
  • Dodavati kvadrat izdvojene cifre u trenutni zbir, povećavajući ga kroz petlju postupno
  • Ne zaboraviti da se zbir inicijalizuje na vrednost nula pre početka petlje

#include < iostream >
using namespace std;
int main()
{
int broj,x;
int zb=0;//zbir, koji je u početku jedna nuli
cin >> broj;
x=broj;
while( x > 0 ){
int c=x % 10;//cifra na desnom kraju
x=x/10;//uklanja cifru na desnom kraju
if((c % 2) != 0){//da li je neparna
zb += c*c;//formira zbir kvadrata
}
}
cout << zb << endl;
return 0;
}

3. Čarobni niz

Napomena: Zadatak je preuzet sa sjta društva matematičara srbije: dms.rs/informatika-osnovne-skole/

​Laza je odlučio da napravi čarobni niz brojeva na sledeći način: Laza je počeo da pravi niz od nekog zadatog broja i svaki naredni član niza se dobija tako što se prethodnom broju doda broj svih njegovih delilaca. Na primer, ako je neki član niza jednak 6, onda je sledeći član niza jednak 6 + 4 tj. 10, jer postoje tačno 4 delioca broja 6 (to su redom brojevi 1, 2, 3, 6).
Napišite program koji učitava sa standardnog ulaza u prvom redu prvi član niza (0<a1≤10000) i u drugom redu prirodan broj N (0<N≤100), a štampa na standardni izlaz N-ti član Lazinog niza.
Primer 1
Ulaz
2
4
Izlaz
9
Pojašnjenje: a1=2, a2=4, a3=7, a4=9
Primer 2
Ulaz
3882
93
Izlaz
4878

Analiza trećeg zadatka

Zadak se može odraditi tako što se u posebnu metodu izdvoji postupak određivanje broja delilaca za unet broj. 
Za rešavanje zadatka potrebno je poznavanje:
  1. Petlje u programskom jeziku C/C++
  2. metode(opciono)

Zadak se može odraditi tako što se u posebnu metodu izdvoji postupak određivanje broja delilaca za unet broj. U glavnoj metodi bi se onda posle unošenja prvog člana niza formirala petlja od k ponavljanja, gde je k broj elemenata niza i taj broj se takođe unosi. U svakom ciklusu petlje bi se određivao broj delioca tekućeg člana niza pozivanjem dodatne metode (može se uraditi i bez upotrebe metoda pisanjem celog postupka određivanja broja delilaca unutar petlje). Dobijeni broj delilaca bi se iskoristio za izračunavanje sledećeg elementa u nizu.

#include < iostream >
using namespace std;

/*Metoda koja za unet broj n, određuje kolko ima delilaca*/
int brojDelioca(int n)
{
int br=0;//broj delilaca
for(int i=1;i<=n;i++)
{
if(n%i == 0)//ispituje deljivost sa trenutnom vrednošću promenljive "i"
{
br++;//ako je deljiv sa "i" povećava broj delilaca za 1
cout << i << " ";
}
}
cout << endl;
return br;
}
int main()
{
int a1,brDel=0,n;
cin >> a1 >> n;
int x=a1;//tekuci element niza
for(int i=1; i {
brDel=brojDelioca(x);
x=x+brDel;
cout << x << endl;
brDel=0;
}
cout << x << endl;
return 0;
}

4. Mesto K-tog pojavljivanja broja

Napomena: Zadatak je preuzet sa sjta društva matematičara srbije: dms.rs/informatika-osnovne-skole/

​Pogledajmo sledeće redove:
1
121
​12321
1234321
123454321
............................
Red čiji je redni broj M (M=1, 2, 3, ...) se formira zapisivanjem redom prirodnih brojeva od 1 do M, a zatim zapisivanjem brojeva u obratnom smeru od M-1 do 1. Sada formiramo beskonačni red uzimajući prvi od gore navedenih redova i dodajući mu
drugi red, zatim dodajemo treći red i tako dalje.
Početak formirane beskonačne serije brojeva izgleda ovako: 1 1 2 1 1 2 3 2 1 1 2 3 4 3 2 1 1 2 3 4 5 4 3 2 1 ...
Članovi ove serije su numerisani počev od jedan. Napišite program koji pronalazi na kom mestu se dati broj n javlja po k-ti put.
Ulaz
U jedinom redu standardnog ulaza data su dva cela broja n i k, odvojena jednim
znakom razmaka (0<n≤1000000, 0<k≤1000000).
Izlaz
Na standardnom izlazu, program mora da ispiše ceo broj - pozicija k-te pojave
broja n u nizu.
Primer 1
Ulaz
1 1
Izlaz
1
Primer 2
Ulaz
2 2
Izlaz
6
Primer 3
Ulaz
3 3
Izlaz
14

Analiza četvrtog zadatka 

Za rešavanje zadatka potrebno je prethodno poznavanje sledećih oblasti:
Grananje u programu
Petlje
Uočimo sledeće pravilo. Analizirajmo broj, podniz gde je taj broj u sredini podniza, dužinu podniza i poziciju poslednjeg elementa na kraju tekućeg podniza.
Broj Novi član se dodaje nizu Dužina podniza Pozicija na kraju
1 1 1 1
2 1 2 1 3 4
3 1 2 3 2 1 5 9
4 1 2 3 4 3 2 1 7 7
5 1 2 3 4 5 4 3 2 1 9 9
6 1 2 3 4 5 6 5 4 3 2 1 11 20

Uneti broj "n" i broj potrebnih pojavljivanja "k". Zatim kroz petlju uraditi sledeće:

  • Povećavati vrednost broja(1. kolona u tabeli)
  • Dok broj ne dostigne vrednost n pomerati samo dužinu i poziciju( 3. i 4. kolona). Do tada sigurno nema još ni jednog pojavljivanja broja n.
  • U redu (ciklusu) u kojem je brojač dostigao vrednost n, dostignuto je prvo pojavljivanje koje se u podnizu nalazi tačno na sredini.
  • U narednim redovima ukoliko je više od dva pojavljivanja do dostizanja k-tog pojavljivanja, pored promena pozicije i dužine po utvrđenom pravilu, treba povećavati broj pojavljivanja za 2
  • U narednim redovima ukoliko je manje ili jednako od dva pojavljivanja do dostizanja k-tog pojavljivanja, imamo 2 slučaja
  • Prvi slučaj da je ostalo samo još 1 pojavljivanje, onda je tražena pozicija za n mesta udaljena od poslednje zapamćene(4. kolona)
  • Drugi slučaj da je ostalo samo još 2 pojavljivanje, onda je tražena pozicija za (duzinaPodniza + 1 -n) mesta udaljena od poslednje zapamćene(4. kolona), a to se može zaključiti posmatranjem druge kolone
#include < iostream >
using namespace std;

int main()
{
int n,k,poz,pom=0,broj=0,poj=0;
cin>>n>>k;//n- broj, k- broj pojavljivanja broja n
poz=0;
do
{
broj++;
// dok broj ne dodje do n nema pojavljivanja
/*pom je u stvari duzina podniza. Npr za broj 3, podniz
je 12321, pa je duzina 5*/
if(broj {
if(broj==1)
{
pom+=1;//sledece pomeranje
}
else
{
pom+=2;
}
poz=poz+pom;//pozicija na kraju niza
}
else if(broj==n) //Pocinje da broji
{
poj=1;//Prvo pojavljivanje
if(poj==k) //slucaj za n=1
{
poz=poz+n;
break;
}
pom+=2;//Dužina podniza u tekucem ciklusu
poz=poz+pom;//Nova pozicija
}
else
{
if(poj {
poj+=2;
pom+=2;//dužina podniza je za 2 veća od prethodne
poz=poz+pom;//pozicija poslednje cifre se pomera za dužinu podniza
}
else if(poj == k-2)//ostaju još dva pojavljivanja
{
pom+=2;
poz=poz+pom;//pozicija koja bi bila na kraju
poz=poz+1-n;//drugo pojavljivanje od poslednjeg je udaljeno za n-1
break;
}
else//ostaje još jedno pojavljivanje
{
poz=poz+n;
break;
}
}
}
while(poj < k);
cout << poz << endl;
return 0;
}

Državno takmičenje iz 2019

5. Visoki učenici

Napomena: Zadatak(6. razred) je preuzet sa sjta društva matematičara srbije: dms.rs/informatika-osnovne-skole/

​Poznate su visine svih učenika jedne škole. Napiši program koji određuje najvišeg dečaka i najvišu devojčicu u toj školi, određuje ko je od njih viši i ispisuje razliku njihovih visina.
Ulaz
Sa standardnog ulaza se unosi broj učenika (5 ≤ 𝑛 ≤ 100), a zatim u svakom od 𝑛 narednih redova podaci za po jednog učenika. Za svakog učenika se unosi visina (ceo broj između 120 i 200) i oznaka pola (m za muški pol i z za ženski), razdvojeni
jednim razmakom. Pretpostaviti da postoji bar jedan dečak i bar jedna devojčica.
Izlaz
Ako je najviša devojčica viša od najvišeg dečaka, na standardni izlaz ispisati z, razmak i zatim za koliko je viša. Ako je najviši dečak viši od najviše devojčice, na standardni izlaz ispisati m, razmak i zatim za koliko je viši. Ako su iste visine, ispisati samo "=".
Primer
Ulaz
5
152 z
174 m
165 z
172 m
170 z
Izlaz
m 4

Uneti broj "n" i napraviti petlju koja ima n ponavljanja. Zatim kroz petlju uraditi sledeće:

  • Uneti podatke iz jednog reda unosa, visinu i pol. Za pol koristiti char promenljivu
  • Ispitati da li je pol muški ili ženski. Odrediti posebno maksimum visine za muški, a posebno za ženski pol.

Uporediti maksimume visina koji su određeni prethodno i ispisati traženu poruku

#include < iostream >
using namespace std;

int main()
{
int n,m=0,z=0;
cin >> n;
for(int i=0; i {
int v;
char p;
cin >> v;
cin >> p;
if(p=='m')//ispituje se da li je pol muski
{
/*Određuje se maksimalna visina za muskarce*/
if(v > m)
{
m=v;
}
}
else if(p == 'z')//ako je pol jednak ženskom
{
/*Određuje se maksimalna visina za žene*/
if(v > z)
{
z=v;
}
}
}
/*poredi najvecu musku i najvecu zensku visinu*/
if(m>z)
{
cout << "m " << (m-z) << endl;
}
else if(m == z)
{
cout << "=" << endl;
}
else
{
cout << "z " << (z-m) << endl;
}
return 0;
}

6. Knjiga

Napomena: Zadatak(6. razred) je preuzet sa sjta društva matematičara srbije: dms.rs/informatika-osnovne-skole/

​Nizom 𝑎 date su dužine 𝑛 poglavlja jedne knjige. Elementom 𝑎0 je dat broj stranica za prvo poglavlje, elementom 𝑎1 za drugo i tako redom. Potrebno je knjigu podeliti na dva dela, tako da se ukupni brojevi strana u ta dva dela najmanje razlikuju. Podela
se vrši iza nekog od poglavlja. Ako postoje dve moguće podele sa istom najmanjom razlikom, podela se vrši nakon ranijeg od dva poglavlja (tako da prvi deo bude kraći). Napiši program koji određuje nakon kog poglavlja treba izvršiti podelu.

Ulaz
U prvoj liniji standardnog ulaza nalazi se prirodan broj 𝑛 (1 < 𝑛 ≤ 50000). U sledećih 𝑛 linija nalaze se po jedan prirodan broj (između 1 i 1000), brojevi predstavljaju brojeve stranica svakog poglavlja.

Izlaz
Na standarnom izlazu prikazati u jednoj liniji redni broj poglavlja (poglavlja se broje od nule) posle kog treba izvršiti podelu knjige.
Primer
Ulaz
5
100
120
50
150
70
Izlaz
1
Kada se podela izvrši posle poglavlja broj 1 (to je drugo poglavlje), tada prvi deo knjige sadrži 220, a drugi 270 strana, što daje najmanju moguću razliku od 50 strana.
Ako bi se podela izvršila nakon poglavlja broj 2 (to je treće poglavlje), prvi deo bi sadržao 270 strana, a drugi 220, što bi takođe bila razlika 50, međutim, po uslovima zadatka u tom slučaju podela se vrši tako da prvi deo knjige bude kraći,
pa je rešenje 1 (podela se vrši posle poglavlja broj 1).

Analiza zadatka

Ako bi poglavlja označili indeksima od 0 do n, onda bi mogli da uočimo 4 niza. Prvi je broj knjiga po svakom poglavlju. To je inače niz koji se unosi. Drugi niz je broj strana koji se dobija sabiranjem broja strana svih poglavlja, do posmatranog, sa leve strane. Treći niz predstavlja zbir strana svih preostalih poglavlja, od tekućeg poglavlja pa do kraja knjige, tj. desno od tekućeg poglavlja. Četvrti niz dobijemo ako od 3. oduzmemo elemente 2. niza.Posmatrajmo to u sledećoj tabeli:
0 1 2 3 4
100 120 50 150 70
100 220 270 420 490
390 270 220 70 0
290 50 -50 -350 -490
Potrebno je naći dakle, najmanju razliku broja knjiga desno i levo od kraja tekućeg poglavlja, što praktično znači najmanji broj po apsolutnoj vrednosti u 4. nizu. Treba takođe uočiti da najmanja vrednost može biti samo prva levo od prelaza od pozitivnih ka negativnim vrednostima, ili prva desno. kasnije se te vrednosti povećavaju po absolutnoj vrednosti. Dakle to je vrednost u koloni sa indeksom 1 i 2. Pošto su one jednake po apsolutnoj vrednosti uzima se vrednost levo.

Rešiti zadatak po sledećem algoritmu:

  • Učitati broj poglavlja
  • Koristeći petlju(for) učitati niz broja strana po poglavlju, u primeru datom u tabeli, to su brojevi u prvom redu.
  • Formirati niz formiran od zbira učitanih elemenata prethodnog niza sa leve strane
  • Formirati niz formiran od zbira učitanih elemenata prethodnog niza sa desne strane. Indeks kolone menjati od poslednje ka početnoj. To su brojevi u 3. redu.
  • Kreirati 4. niz, kao razlika elemenata 3. i 2. reda
  • U istom ciklusu tražiti minimalnu vrednost razlike
  • Kada se dođe do elementa koji ima negativnu razliku prekinuti ciklus

#include < iostream >
using namespace std;
int main()
{
int n,z=0,minR;
cin >> n;
int a[n],l[n],r[n];
for(int i = 0; i < n; i++)
{
cin >> a[i];
z=z+a[i];
l[i]=z;
}
minR=z;//Najveća moguća razlika je jednaka zbiru svih elemenata
z=0;
for(int i=n-1; i>=0; i--)
{
r[i]=z;
z=z+a[i];
}
int raz;
int ind=0;
for(int i=0; i < n; i++)
{
raz=r[i]-l[i];//razlika između levog i desnog dela knjige u odnosu na kraj tekućeg poglavlja

//svaka sledeca razlika ce biti veca
if(raz < 0)
{
minR=(abs(raz) < minR) ? abs(raz):minR;
ind=(abs(raz) break;
}
//ako se naiđe na manju razliku, ona se pamti kao minimalna
if(raz < minR)
{
minR=raz;
}
}
cout << ind << endl;
return 0;
}

7. Rastuće cifre

Napomena: Zadatak(6. razred) je preuzet sa sjta društva matematičara srbije: dms.rs/informatika-osnovne-skole/

​Napiši program koji među unetim brojevima pronalazi one kojima su cifre strogo rastuće, gledajući od cifre najveće težine (prve cifre sleva).


Ulaz Sa standardnog ulaza se učitava broj □ (1 ≤ □ ≤ 5000), a zatim i □ prirodnih brojeva većih ili jednakih od 10 i manjih ili jednakih od 109 , svaki u posebnom redu.

Izlaz
Na standardni izlaz ispisati tražene brojeve sa rastućim ciframa, svaki u posebnom redu.

Primer
Ulaz
3
123
222
321
Izlaz
123
​

Rešiti zadatak po sledećem algoritmu:

  • Uneti ceo broj
  • Odrediti koliko ima cifara. To se može uraditi ili while petljom ili korišćenjem funkcije log10 iz zaglavlja cmath. Videti detaljnije objašnjenje na strani Priprema za okružna takmičenja
  • Otvoriti petlju, najbolje do-while
  • Unutar petlje:
    1. Izdvajati cifru sa leve strane
    2. Skratiti broj za tu cifru deljenjem sa stepenom broja 10 čiji je izložilac za 1 manji od broja cifara ostatka broja. Npr. Ako je broj 12345, treba izdvojiti cifru 1, pa podeliti broj sa 104, tako da broj u sledećem ciklusu bude 2345
    3. Proveriti da li je tekuca cifra u rastućem poretku sa prethodnom cifrom
    4. Tekuća cifra biće prethodna u sledećem ciklusu
    5. Ako je prvi ciklus zapamptiti tekuću cifru kao prethodnu za sledeći ciklus i odmah preći u naredni ciklus
    6. Ako prethodna i tekuća cifra nisu u rastućem poretku konstatovati da poredak nije rastući postavljanjem logičke promenljive na false i prekinuti cikluse
  • Ako je logička promenljiva koja ispituje da li je redosled rastući ostala na true ispisati broj
  • Za promenu broja koji se ispituje koristiti petlju tako da druga petlja koja razdvaja cifre bude ugnježdena

#include < iostream >
#include< cmath >
using namespace std;
int main()
{
int n,brCif=0;
cin >> n;
int broj[n];
//ucitavanje
for(int i=0; i < n; i++)
{
cin >> broj[i];
}
//analiza
for(int i=0; i < n; i++)
{
brCif=(int)log10(broj[i])+1;//Određuje broj cifara
//ispituje da li je rastuci poredak
bool rastuci=true;//pretpostavi se da je rastući redosled
int d=(int)pow(10,brCif-1);//pocetni delilac
int p,j=0;//prethodna cifra, kontrolna promenljiva za do-while ciklus(pomeranje po ciframa)
int a=broj[i];//broj kome ce se skidati cifre levo, u pocetku jednak unetom broju
do
{
int c=a/d; //cifra sa leve strane
a=a % d; //skida cifru sa leve strane tekucem broju a. Npr Od 123, broj postaje 23
d /= 10; //d=d/10
if(j==0)//prvi ciklus
{
p=c;
j++;
continue;//prelazak u sledeći ciklus
}
//proverava rastuci poredak
if(c <= p)
{
rastuci=false;
break;
}
p=c;//tekuca cifra postaje prehodna za sledeci ciklus
j++;//povecava broj ciklusa za 1
} while(d>=1);
if(rastuci)
{
cout << broj[i] << endl;
}
}
return 0;
}

8. Razlika visina

Napomena: Zadatak(6. razred) je preuzet sa sjta društva matematičara srbije: dms.rs/informatika-osnovne-skole/

​U jednoj školi biraju se glumci za školsku predstavu u kojoj likovi koje tumače imaju veliku razliku u visini. Napiši program koji određuje na koliko načina možemo da odaberemo dva glumca iz odeljenja tako da im je razlika visina jednaka datom broju 𝑟.
Ulaz
Sa standardnog ulaza se unosi prvo pozitivan prirodan broj 𝑟 (1 ≤ 𝑟 ≤ 1000), u
narednom redu broj učenika 𝑛 (1 ≤ 𝑛 ≤ 50000), a nakon toga u narednih 𝑛 redova
visina svakog učenika (broj između 1 i 100000).
Izlaz
Na standardni izlaz ispiši broj parova koje je moguće formirati.
Primer 1
Ulaz
10
5
150
160
165
170
175
Izlaz
3
Moguće je napraviti parove od prvog i drugog deteta (150, 160), od drugog i četvrtog deteta (160, 170) i trećeg i petog deteta (165, 175).

Primer 2
Ulaz
23
5
157
180
157
162
134
Izlaz
4
Moguće je napraviti parove od prvog i drugog deteta (157, 180), od petog i prvog (134, 157), od drugog i trećeg (157, 180) i od petog i trećeg deteta (134, 157).
Napomena
U 20 od 25 test­primera sva deca će biti različite visine.

Analiza zadatka

Ako se visine učitaju kao niz, trebalo bi ga prvo sortirati. Da bi se napravile sve kombinacije parova i razlika visina tih parova uporediti sa zadatom treba s jedne strane menjati prvi element niza , odnosno visinu prvog deteta u okviru para  a sa druge strane za fiksiranu vrednost prve visine menjati drugu vrednost u paru. Za ovo se mogu koristiti dve petlje u kojoj je jedna ugnježdena u drugoj. Obe petlje mogu da menjaju vrednosti linearno, od početka do kraja ili, jedna linearno, dok druga po principu Binarne pretrage, što bi bilo efikasnije.

Rešiti zadatak po sledećem algoritmu:

  • Uneti dva cela broja, traženu razliku i broj dece.
  • Učitati niz visina dece
  • Otvoriti dve petlju, jednu ugnježdenu u drugoj
  • Sortirati niz po rastućem redosledu.
  • U petlji formirati razliku visina i uporediti sa zadatom.
  • Ako je razlika jednaka zadatoj povećati traženi broj parova za 1
  • Iterativno kroz unutrašnju petlju menjati drugu visinu unutar parova visina sve dok razlika visina ili ne bude pronađena ili dok se ne dođe do veće razlike od zadate i tad prekinuti unutrašnju petlju, jer bi svaka sledeća razlika bila još veća
  • Po izlasku iz petlje štampati traženi broj parova

#include < iostream >
#include< algorithm >
using namespace std;
int main()
{
int r,n,b=0;
cin >> r >> n;
int v[n]; //niz visina
//ucitavanje
for(int i=0; i < n; i++)
{
cin >> v[i];
}
/*Sortiranje niza visina*/
sort(v,v+n);
/*Formiranje različitih parova visina i ispitivanje */
for(int i=0; i < n-1; i++)
{
for(int j=i+1; j < n; j++)
{
int raz=v[j]-v[i];//razlika visina
if(raz==r)//Ako je razlika visina jednaka zadatoj
{
b++;//Povećava broj nađenih parova za 1
}
else if(raz > r )/*Ako je razlika veća od zadate prekidaju se promene druge
visine u paru, jer svaka sledeća razlika je sve veća*/
{
break;
}
}
}
cout << b << endl;
return 0;
}

Efikasnije rešenje sa binarnom pretragom

Rešiti zadatak po sledećem algoritmu:

  • Uneti dva cela broja, traženu razliku i broj dece.
  • Učitati niz visina dece
  • Otvoriti dve petlju, jednu ugnježdenu u drugoj
  • Sortirati niz po rastućem redosledu.
  • U petlji formirati razliku visina i uporediti sa zadatom.
  • Ako je razlika jednaka zadatoj povećati traženi broj parova za 1
  • Unutrašnja petlja menja drugu visinu tražeći onu čija je razlika sa prvom visinom jednaka zadatoj. Pretraživanje vršiti koristeći algoritam binarne pretrage. Dakle menjati krajnje levu i krajnje desnu poziciju posmatranog podniza.
    Ovaj podniz je u početku jednak celom nizu, što znači da su krajnja leva i krajnja desna pozicija u početku krjnje pozicije celog niza.
    Unutar ciklusa se najpre određuje srednja pozicija.Zatim se pronalazi razlika elementa niza na toj, srednjoj poziciji i visine prvog deteta unutar tekućeg para. Ako je ta razlika baš ona zadata, povećava se broj pronađenih parova za 1.
    Treba proveriti da li ima jos vrednosti sa jednakom razlikom, npr. ako postoji vise dece sa istim visinama.
    Ako ne, onda dalje proveriti da li je trazena razlika u levoj ili desnoj polovini tekuceg podniza i u skladu sa tim pomeriti krajnje desnu ili krajnje levu poziciju podniza u sledecem ciklusu.
  • Po izlasku iz petlje štampati traženi broj parova

#include < iostream >
#include< algorithm >
using namespace std;
int main()
{
int dif,n,b=0;
cin >> dif >> n;//dif-trazena razlika,n-broj dece
int v[n]; //niz visina
//ucitavanje
for(int i=0; i < n; i++)
{
cin >> v[i];
}
/*Sortiranje niza visina*/
sort(v,v+n);
/*Formiranje različitih parova visina i ispitivanje */
for(int i=0; i < n-1; i++)
{
int l=i+1,r=n-1;//niz za pretragu je od pozicije i+1 pa do n-1, l-left,r-right
while(l <= r)//ciklus traje sve dok je leva pozicija manja ili jednaka desnoj
{
int mid=(l+r)/2;;//srednja pozicija intervala[l,r]
int raz=v[mid]-v[i];//razlika visina
//Ako je razlika jednaka dif pronadjen je novi par cija je razlika visina jednaka zadatoj
if(raz==dif)
{
b++;//broj parova se uvecava za 1
int k=mid+1;
while(v[k]==v[mid])
{
b++;
k++;
}
k=mid-1;
while(v[k]==v[mid])
{
b++;
k--;
}
break;
}
else if(dif {
r=mid-1; //desna granica za novu pretragu je prva pozicija levo u odnosu na srednju vrednost
}
else if(dif > raz)//Ako je ocekivana razlika veca od stvarne, ocekivana vrednost je u desnoj polovini
{
l=mid+1;//leva granica za novu pretragu je prva pozicija desno u odnosu na srednju vrednost
}
}
}
cout << b << endl;
return 0;
}
SVET PROGRAMIRANJA