Nizovi - Zadaci iz programiranja

Ovo su funkcije koje se bave nekim operacijama koje se često ponavljaju. To su:

• unosNiza(a, n) - unos niza a za zadati broj elemenata n
• popunaNiza(a,n, kor) - automatsko popunjavanje niza a sa n slučajnih brojeva od 0 do 99, povećanih za korektivni faktor kor
• ispisNiza(a, n) - ispis niza a od n elemenata

function unosNiza(a, n) {for (i=1..n) { read(a[i]); } } function popunaNiza(a,n, kor) {for (i=1..n) { a[i] = trunc(rand()*100) + kor; } } function ispisNiza(a, n) { write("Elementi niza:"); r=""; for (i=1..n) { r += a[i] + " "; } write(r); }

Ovde uspostavljamo osnove rada sa nizovima - unos elemenata niza i formiranje niza slučajnih brojeva pomoću pripremljene funkcije iz biblioteke. Takođe, vežbamo prolazak kroz niz putem brojačkog ciklusa i to radi ispisa ili računanja neke vrednosti.

Zadatak 1
Napisati program kojim se unosi niz od N elemenata i potom ispisuju elementi niza.

Zadatak 2
Napisati program kojim se unosi niz od N elemenata i potom ispisuju elementi niza, uz korišćenje unapred pripremljenih funkcija iz biblioteke.

Zadatak 3
Formira se niz od N članova. Izračunati zbir elemenata niza.

Zadatak 4
Izračunati prosek (aritmetičku sredinu) svih elemenata niza od N numeričkih elemenata.

Filtriranje elemenata niza

Sledeća grupa zadataka takođe spada u osnovne. Obično je potrebno nešto izračunati, prebrojati ili ispisati na osnovu elemenata niza, ali ne svih, već samo onih koji zadovoljavaju određeni uslov. Ovi zadaci se obično rešavaju prolaskom kroz niz, dok se unutar ciklusa vrši ispitivanje svakog elementa niza.

Zadatak A.1
Napisati program kojim se pronalazi broj nula u unetom nizu brojeva.

Zadatak A.2
Kreira se niz od N celih brojeva. Treba ispisati sve one članove čija je vrednost manja od njihovog rednog broja (indeksa) u nizu.

Zadatak A.3
Izračunati zbir elemenata niza koji su veći od svog indeksa.

Zadatak A.4
Kreira se niz od N članova i unosi broj X. Treba ispisati indekse onih članova niza koji su jednaki broju X.

Zadatak A.5
Prebrojati koliko ima negativnih brojeva u nizu, u intervalu od indeksa I1 do indeksa I2.

Zadatak A.6
U unetom nizu celih brojeva, treba naći broj parnih i broj neparnih elemenata niza.

Zadatak A.7
Proveriti da li u nizu ima više pozitivnih ili negativnih brojeva.

Zadatak A.8
Izračunati aritmetičku sredinu svih pozitivnih elemenata niza celih brojeva.

Zadatak A.9
Izračunati proizvod svih elemenata koji se nalaze na parnim pozicijama (indeksima).

Zadatak A.10
Kreiraju se nizovi A i B od po N celih brojeva, s tim što elementi niza B mogu biti samo brojevi 0 i 1. Potrebno je izračunati ispisati sve elemente niza A za koje je odgovarajući elemenat niza B jednak 1 i izračunati njihov zbir.

Zadatak A.11
Za unete nizove A od N i B od M celih brojeva, treba ispisati M elemenata niza A onim redosledom kako je navedeno u nizu B. Podrazumeva se da ni jedan elemenat niza B nije veći od N.
Npr. A=[23,52,38,44} i B=[3,1,1,2], ispisuje se 38, 23, 23, 52.

Zadatak A.12
Za uneti niz od N numeričkih vrednosti, prebrojati koliko ima elemenata koji su duplo veći od prethodnog i za 10 manji od sledećeg elementa u nizu.

Zadatak A.13
Proveriti da li je niz uređen po neopadajućem redosledu (svaki sledeći el. je veći ili jednak prethodnom).

Zadatak A.14
U nizu brojeva A od N elemenata, pronaći najduži podniz pozitivnih brojeva.

Zadatak A.15
U nizu brojeva A, pronaći najduži neopadajući podniz.
Zadatak je sličan pronalaženju najdužeg pozitivnog podniza, uz par manjih izmena

Zadatak A.16
Proveriti da li među elementima niza nema duplikata.

U rešenju se oba ciklusa nepotrebno izvršavaju od početka do kraja čak iako se duplikat nađe odmah na početku. Razmislite o verziji rešenja koja bi bila efikasnija i prekidala cikluse čim se pronađe prvi duplikat.

Pretraga niza

U ovim zadacima pokušavamo da pronađemo specifičan element. U nekim situacijama se pretraga može zaustaviti čim se pronađe elemenat koji zadovoljava traženi uslov, ali u nekim situacijama moramo proći kroz ceo niz u potrazi za "boljim" elementom.

Suštinski, ovo nisu zaista zadaci koji se bave algoritmima za pretraživanje, već samo zadaci koji pod pojmom "pretraga" maskiraju već rađene zadatke u kojima je potrebno proći kroz niz i nešto izračunati ili prebrojati odgovarajuće elemente. Jedina razlika je što se ovde pronađeni element ne "uračunava" već pamti kao "pronađen".

Inače, jedini tip pretrage koji za sada znamo je sekvencijalno pretraživanje, koje se svodi na prolazak kroz jedan-po-jedan elemenat niza.

Zadatak B.1
Pronaći najveći elemenat niza.

Zadatak B.2
Pronaći indeks najmanjeg elementa niza.

Zadatak B.3
Pronaći prvi negativni elemenat u nizu od N celih brojeva, ako postoji.

Zadatak B.4
Ispitati da li je veći maksimum elemenata na parnim ili elemenata na neparnim pozicijama niza.

Zadatak B.5
Pronaći elemenat koji je najbliži proseku niza.

Zadatak B.6
Kreira se niz pozitivnih i negativnih brojeva. Treba ispisati indekse prvog i poslednjeg pozitivnog elementa u nizu.

Zadatak B.7
Pronaći drugi najveći elemenat niza. Podrazumeva se da niz ima bar dva elementa.

Zadatak B.8
Za niz od N elemenata i unet celi pozitivan broj M i vrednost X, naći indeks M-te pojave elementa X u nizu, ako postoji.

Generisanje niza

U ovim zadacima stvaramo novi niz bilo na osnovu nekih početnih vrednosti i "formule", bilo na osnovu postojećeg niza ili više njih.

Zadatak C.1
Za unete nizove A i B formirati niz C koji se dobija sabiranjem elemenata nizova A i B.

Zadatak C.2
Unose se nizovi A i B od po N elemenata. Kreirati niz C čiji je svaki elemenat jednak manjem od odgovarajućih elemenata nizova A i B.
Ako bismo želeli preciznije da se izrazimo: Ci = min(Ai, Bi).

Zadatak C.3
Za uneto X i N, kreirati niz od N elemenata kome je A1 = X, a svaki sledeći elemenat se dobija dupliranjem prethodnog.
Npr. za uneto N=5 i X=3, dobija se niz [3, 6, 12, 24, 48].

Zadatak C.4
Kreirati Fibonačijev niz od N elemenata. A1 = 1, A2 = 1, a svaki sledeći se dobija kao zbir prethodna dva elementa.

Zadatak C.5
Za generisani niz A od N članova, kreirati niz B koji se dobija obrtanjem elemenata niza A.
Dakle ako je niz A [4,9,2,7], niz B treba da bude [7,2,9,4].
Znači, B₁=A_N, B₂=A_N-1, ... B_N=A₁

Zadatak C.6
Za zadati niz od N celih brojeva krirati i ispisati novi niz čiji se elementi dobijaju kao zbirovi prvog i poslednjeg elementa unetog niza, zatim drugog i pretposlednjeg, trećeg i trećeg s kraja... Podrazumeva se da je N parno.
Ako je zadat niz [4,8,6,2,1,9], treba da se dobije [13,9,8].

Zadatak C.7
Za uneti niz A od N brojeva, kreirati niz B od N-1 elemenata koji se dobijaju sabiranjem elemenata niza A, gde se i-ti element dobija kao zbir i-tog i i+1 elementa.
b₁=a₁+a₂, b₂=a₂+a₃, b₃=a₃+a₄...

Zadatak C.8
Za uneti niz A od N elemenata, kreirati niz B koji se dobija kumuliranjem elemenata niza A. To znači da se i-ti element dobija kao zbir od prvog do i-tog elementa niza A. I da još pojasnimo: b₁=a₁, b₂ = a₁+a₂, b₁=a₁+a₂+a₃...

Zadatak C.9
Za uneti niz A od N celih brojeva, kreirati niz B koji se dobija izbacivanjem negativnih elemenata iz niza A.

Zadatak C.10
Za uneti niz A od N celih brojeva, treba kreirati niz B, u kome će se naći indeksi onih elemenata niza A koji su jednaki nekom unetom broju X.
Dakle, za uneti niz [4,8,4,6,2,4,1] i X=4, rezultat treba da bude [1,3,6], zato što su prvi, treći i šesti element jednaki broju X.

Zadatak C.11
Kreirati niz A od N elemenata, čiji su elementi celi brojevi od 1 do N, slučajno raspoređeni, uz uslov da se svaki broj pojavljuje samo jednom.
Ovo je u stvari zadatak pravljenja slučajnog redosleda. Ovde ćemo predstaviti dva načina - slučajnim zamenama parova u uređenom nizu ili "skidanjem" jednog po jednog slučajnog elementa iz uređenog niza. Zadatak bi mogao da se reši i ubacivanjem slučajnog broja i proverom da li taj broj postoji, ali taj način rešavanja nije baš praktičan pošto se program sve više usporava kako se bližimo kraju niza.

Da se podsetimo:

• funkcija rand() vraća slučajan broj u intervalu od 0 do 0.9999999
• npr. trunc(rand() * 10) daje slučajan ceo broj u intervalu od 0 do 9
• npr. trunc(rand() * 10)+1 daje slučajan ceo broj u intervalu od 1 do 10

U prvom rešenju kreiramo niz poređanih brojeva [1,2,3,4...], a onda određen broj puta slučajno biramo dva indeksa i tim elementima menjamo mesta - bukvalno, pobrkamo elemente.

Drugi način je malo bolji, ali zahteva da pravimo novi niz. Znači, isto kao malopre kreiramo niz poređanih brojeva, npr. A=[1,2,3,4,5] i onda biramo slučajan broj, iz intervala od 1 do 5. Recimo da dobijemo X=2 - onda drugi element smestimo u niz B=[2], a u nizu A treba da elminišemo izabrani element (npr. u njega možemo smestiti poslednji elemenat) i ostaje nam: A=[1,5,3,4]. Onda opet biramo slučajan indeks, ali sada iz intervala od 1 do 4 i ponavljamo ceo postupak.

Zadatak C.12
Na osnovu unetog stringa, kreirati niz podstringova koji se dobijaju kada se string podeli po razmacima. Podrazumeva se da je string ispravan, da nema razmake na početku i kraju, kao ni višestruke razmake.
Npr. za uneti string "Mama ima Momu", dobija se niz od tri elementa ["Mama", "ima", "Momu"].

Transformacija niza

Ovo su zadaci kod kojih je potrebno na neki način promeniti sam niz. Umesto da vršimo računanje ili prebrojavanje u nekoj posebnoj promenljivoj, u ovakvim zadacima se rezultat obrade smešta u sam elemenat niza.

Ovi zadaci mogu biti veoma slični zadacima gde se na osnovu jednog niza generiše drugi niz, s tim što je ovde posao dodatno zakomplikovan time što suštinski sve moramo da uradimo unutar jednog istog niza.

Zadatak D.1
U nizu celih brojeva, sve elemente na parnim pozicijama treba uvećati za 1, a sve elemente na neparnim smanjiti za 1.

Zadatak D.2
Niz od N elemenata treba transformisati tako što elementi u svakom paru zamene pozicije. Podrazumeva se da je N parno.
Npr. za niz brojeva [5,2,9,1,3,6] dobija se [2,5,1,9,6,3].

Zadatak D.3
U niz A od N elemenata treba umetnuti novi elemenat X, posle prvog elementa koji je veći od X ili na kraj niza ako takav elemenat ne postoji.
Za uneto X=80 i niz [57,30,95,17,22], dobija se [57,30,95,80,17,22].

Zadatak D.4
U niz A od N elemenata treba ubaciti niz B od M elemenata, počev od zadate pozicije P. Podrazumeva se da je P u okviru niza A.
Dakle, ako je niz A=[15,30,10,40,60], niz B=[2,6] i uneto P=3, treba da dobijemo niz A=[15,30,2,6,10,40,60].

Zadatak D.5
Izvršiti pomeranje elemenata niza za X pozicija uz uslov da se elementi koji "ispadnu" pojavljuju sa druge strane niza. Zadatak uraditi bez upotrebe pomoćnog niza. Npr. za niz [1 2 3 4 5 6 7] i uneto X = 3, dobija se niz [5 6 7 1 2 3 4].
Za niz [1 2 3 4 5 6 7] i X = -3, dobija se [4 5 6 7 1 2 3]
U rešenju nećemo previše razmišljati - prosto ćemo ciklirati niz za po jedan element onoliko puta za koliko pozicija je potrebno da se pomeri.

Zadatak D.6
Izvršiti pomeranje elemenata niza za X pozicija. Elementi koji ispadnu se gube, a umesto pomerenih elemenata pojavljuju se nule.

Npr. za niz [1 2 3 4 5 6 7] i uneto X = 3, dobija se niz [0 0 0 1 2 3 4].
Za niz [1 2 3 4 5 6 7] i X = -3, dobija se [4 5 6 7 0 0 0]

Ovde ćemo se malo više potruditi da napravimo optimalnije rešenje - bez koncentričnih ciklusa.

Ovi primeri nisu toliko značajni za vežbanje programiranja sa nizovima, koliko demonstriraju neku praktičnu primenu nizova za čuvanje većeg broja podataka.

Primer 1
Animiramo N pravougaonika širine 20 piksela, čija se Y koordinata menja po sinusoidi.

Ovo je prosto jedan niz pravougaonika koji se pomeraju gore-dole, jedan za drugim tako da sve to daje neki lep efekat kontinuiranog kretanja. Zašto računamo vertikalnu koordinatu po sinusoidi a ne linearno (kada se pozicija menja uvek za fiksnu veličinu) je da bismo postigli efekat ublažavanja kretanja (ease-in i ease-out). Ako se ne snalazite sa sinusima i kosinusima, pogledajte tekst u kome objašnjavamo trigonometrijske funkcije u JavaScriptu

Ovaj zadatak bi čak mogao da se uradi i bez upotrebe nizova. Razmislite kako.

Primer 2
Animiramo 30 "loptica", gde se svaka kreće slučajno izabranim pravcem, s tim što se loptice "odbijaju" kada stignu do ivice grafičkog okvira.