Drage takmičarke i dragi takmičari,
Nadam se da ste se lepo odmorili i da ste spremni za nastavak priprema za 2. krug kvalifikacija, koji je planiran od 19. do 21.januara. Sledeće konsultacije u kabinetu planiramo za petak 12.januar posle 6.časa.
Sada je pravo vreme da počnemo sa upoznavanjem nizova, tako što ćemo kao primer iskoristiti 3. zadatak iz prvog kruga kvalifikacija (word dokument u prilogu).
U prilogu se nalazi arhiviran fajl, koji će, kada ga budete raspakovali na svojim računarima, napraviti poseban novi podfolder sa nekoliko fajlova, koje ću u nastavku mejla detaljnije obijasniti.
1. Deo - Nizovi - Osnovno upoznavanje (tip podataka, učitavanje i prikazivanje elemenata niza, jednostavne operacije sa elementima niza)
Na početku, bilo bi dobro da se najpre upoznamo sa osnovnim karakteristikama nizovnog tipa podataka, odnosno nizovima, tako što ćete pregledati sledeće materijale:
- PDF dokument na Petlja.org, tačnije u okviru kursa Uvod u alogritme: https://petlja.org/BubbleBee/r/Lectures/osnovne-strukture-podataka, odnosno https://petljamedia.blob.core.windows.net/root/Media/Default/Lecture/Osnovne%20strukture%20podataka/Nizovi.pdf
U ovom dokumentu objašenje nizovnog tipa podataka namenjeno je pre svega takmičarima, korišćenjem programskih jezika Pascal, C i C# i odmah su zatim dati zadaci za vežbanje, koji se često koriste za reševanje delova takmičarskih zadataka, kao što su Palidrom, Uzastopna slova i Trag matrice.
- Pre rešavanja ovih zadataka, bilo bi dobro da svako od vas najpre pregleda (i ukoliko želi rešava) nešto jednostavnije zadatke ovim redom:
1. zadatke od 221 do 229 u okviru poglavlja 9. Nizovi, odnosno redovnog programa (kursa) za 3. razred. U okviru tog poglavlja nalaze se i materijali (lekcije) koje bi trebalo da pregledate.
2. zadatke u okviru Zbirke na petlja.org tačnije poglavlja 4. Nizovi i to najpre iz dela 4.2. Elementarno korišćenje nizova, odnosno zadatke kao što su: ispis u obrnutom redosledu, prosečno odstupanje od minimalnog i sl.
2. Deo - Nizovi - Grubo grupisanje vrste zadataka (problema) sa nizovima
Sada bi trebalo da imamo neki opšti (grubi) pregled vrsta/grupa zadataka u kojima se koriste nizovi i ako je ikako moguće da budu poređani po težini od najlakših ka najtežim, što ćemo pokušati ovde i da uradimo sa pratećim kratkim napomenama:
- Najosnovnije operacije korišćenjem elemenata niza - to bi bili zadaci od 221 do 229 na nasaskola.edu.rs (kao i iz poglavlja 4.2. Elementarno korišćenje nizova u Zbirci), kao što su: zbir svih elemenata niza, aritmetička sredina elemenata niza, najveći i/ili najmanji element niza, indeks najmanjeg elementa niza, prebrojavanje elemenata niza koji ispunjavaju određene uslove i sl.
Napomena: skoro svi zadaci iz ove 1. grupe bi trebalo da mogu se se reše i bez nizova, korišćenjem uglavnom samo brojačkih ciklusa. - Generisanje elemenata novog niza - U ovim zadacima potrebno je da na osnovu nekih zadatih pravila generišemo nekoliko ili sve elemente niza, kao na primer da pronađemo zbir dva vektora (niz se posmatra i kao vektor) i sl.
- Opreacije nad elementima niza karaktera - Ukoliko su elementi niza slova, a ne brojevi, onda se radi o nizu karaktera. Princip rešavanja zadataka je sličan prethodnom, ali je svakako raznovsniji, kao što je to u poglavlju 4.1. Karakteri i niske.
Napomena: skoro svi zadaci iz ove 2. grupe bi trebalo da mogu se se reše i bez nizova, korišćenjem uglavnom samo brojačkih ciklusa i/ili tipa podataka String. - Trasformacije nizova - pomeranje elemenata niza za jedno (ili nekoliko) mesta ulevo ili udesno, izbacivanje određenih elemenata iz niza, ubacivanje novih elemenata u niz i sl, kao u poglalju 4.3. Transformacije nizova.
Napomena: Počev od ove 4. grupe zadataka, postaje neizbežno korišćenje nizovnog tipa podataka, tj zadaci se ne mogu tako lako rešiti bez ovog tipa podataka. - Obilazak niza - poglavlje 4.4.
- Podnizovi - poglavlje 4.5.
- Sortiranje niza - poglavlje 4.6. - Napomena: Ovo je veoma važno poglavlje za nizove.
- Složeniji zadaci sa jednodimenzionalnim nizovima i uvod u dvodimenzionalne nizove (preostala poglavlja 4.7 i 4.8 iz Zbirke).
3. Deo - Nizovi - Rešavanje takmićarskih zadataka sa kvalifikacija
Sada smo spremni za rešavanje takmičarskih zadataka sa kvalifikacija u kojem se koriste nizovi.
Ukoliko ste pažljivo proučili prva dva dela, trebalo bi da relativno lako dođete do prve verzije rešenja takmičarskog zadatka, ne vodeći računa o optimizaciji. Na takmičenju u većini ovih zadataka, od takmičara se traži i optimizacija i to i memorijskog prostora i brzine, što podrazumeva odgovarajući izbor tipa podataka (i elemenata niza), dužine nizova, kao i posebne tehnike (algoritme), odnosno metode rešavanja, koje ćemo raditi kasnije.
U ovoj etapi rešavanja zadatka ne treba da vodimo računa o optimizaciji (koja nije tako jednostavna), tako da prve verzije rešenja bi trebalo da prođu bar nekoliko unapred zadatih (najjednostavnijih) test primera, što ćemo videti u primeru iz 3. zadatka (Prodavnice) sa kvalifikacija.
4. Deo - Nizovi - Algoritamsko rešavanje takmićarskog zadataka sa kvalifikacija - 3. zadatak - Prodavnice - FlowGorithm
Korišćenjem uobičajenih smernica za rešavanje zadataka (koje sam vam poslao 20.decembra) možemo doći do prve verzije algoritamskog rešenja. Pri tom, čak možemo i da koristimo program FlowGorithm za crtanje i testiranje prvog algoritamskog rešenja.
Već u ovom delu ćemo vrlo brzo zaključiti da je ne možemo da izbegnemo niz, tačnije da moramo da koristimo bar jedan niz kako bi zapamtili (smestili u memoriju) podatke iz drugog reda sa ulaza o rasporedu kuća (X), a koji će nam biti neophodni za određivanje rastojanja do prodavnica u svim sledećim algoritamskim koracima.
Dobra okolnost je što program FlowGorithm ima mogućnost korišćenja jednodimenzionalnih nizova, te možemo doći do prve verzije algoritamskog rešenja kao u fajlu u prilogu:
- Tkm_DMS_Programiranje_2017_01_KV_01_Z_03.fprg
Primetićete da smo u deklaraciji definisali promenljivu X kao niz dužine 1000 celih brojeva (Array), ali da to nismo uradili i za rasporede prodavnica (A i B). Dakle, za sada ćemo koristiti samo jedan niz (X), dok ćemo A i B da učitavamo kao obične cele brojeve u brojačkom ciklusu, i odmah nakon učitavanja da izračunavamo zbir svih rastojanja, koji ćemo prikazati na kraju tog brojačkog ciklusa.
Takođe unutar tog glavnog brojačkog cikusa (za svaki par/red A i B) nakon učitavanja para u drugom unutrašnjem brojačkom ciklusu izraćunavamo pojedinačna rastojanja svake kuće od tačaka A i B, pronalazimo najmanja i dodajemo na postojeći zbir rastojanja.
Pogledajte i proučite algoritamskog rešenja iz navednog fajla u programu FlowGorithm. Ukoliko imate nekih pitanja ili nedoumica, zapišite ih, pripremite i postavite na sledećim konsultacijama.
5. Deo - Nizovi - Testiranje prve verzije algoritamskog rešenja
Obavezno testirajte prvo algoritamsko rešenje za dati test primer u 3. zadatku na kvalifikacijama:
- Tkm_DMS_Programiranje_2017_01_KV_01_Z_03.fprg
Trebalo bi da daje tačne rezultate za prvi test primer, kao i za drugi, mada je moguće da kod drugog test primera dođe do prekorečenja (memorije), jer se radi o veoma velikim brojevima, ali je za sada važno da za jednostavne test primere daje dobre rezultate. Takođe, u ovom trenutku ne vodimo računa o formatu ulaza i izlaza.
6. Deo - Nizovi - Automatsko generisanje programskog koda iz prve verzije algoritamskog rešenja
Ukoliko smo dobili tačno rešenje prilikom testiranja algoritma, sada je vreme da generešimo automatski programski kod u jednom od nekoliko programskih jezika (Pascal, C++, C#, Java), kao u fajlovima iz priloga:
- Tkm_DMS_Programiranje_2017_01_KV_01_Z_03_00_FG.pas
- Tkm_DMS_Programiranje_2017_01_KV_01_Z_03_00_FG.java
Naravno i da odmah nakon toga ovako automatski generisan progrmaki kod iskopiramo u razvojno okruženje (Lazarus - console application, FreePascal i sl), kompajliramo (ukoliko je potrebno otklonimo sintaksne greške) i testiramo iz razovojnog okruženja za prvi test primer.
7. Deo - Nizovi - Prva modifikacija automatski generisanog programskog koda iz prve verzije algoritamskog rešenja - Prilagođavanje razvojnom okruženju i naredbi za ulaz i izlaz uslovima navedenim u tekstu zadatka za ulaz i izlaz
Sada je potrebno da malo ispravimo automatski generisan programski kod, tačnije naredbe ReadLn i WriteLn, kao i da sve tipove podataka Integer prepravimo u LongInt, pošto se u zadatku traže veliki celi brojevi, kao u fajlu iz priloga:
- Tkm_DMS_Programiranje_2017_01_KV_01_Z_03_01_LongInt.pas
Ponovo testiramo programski kod iz razvojnog okruženja. Ukoliko bi postavili ovu verziju kao rešenje zadatka komisiji na ocenjivanje, trebalo bi da prođe nekoliko najjednostavnijih unpared generisanih test primera, ali sasvim sigurno ne sve, jer još uvek nismo uradili pravu optimizaciju (samo smo ispravili naredbe ulaza/izlaza i tipove podataka iz Integer u LongInt).
8. Deo - Nizovi - Druga modifikacija programskog koda - Prilagođavanje uslovima/ograničenjima navedenim u tekstu zadatka koja se odnose na tipove podataka, odnosno opsege mogućih vrednosti brojeva (INT64)
Sada popravljamo podatak o maksimalnoj dužini niza (umesto 1..1000, treba da stoji 1..100005) i pošto se radi o veoma velikm celim brojevima (10 na 9) prvi put uvodimo najveći mogući tip podataka za cele brojeve Int64, kao u fajlu iz priloga:
- Tkm_DMS_Programiranje_2017_01_KV_01_Z_03_01_Int64.pas
Ponovo testiramo programski kod iz razvojnog okruženja. Ukoliko bi postavili ovu verziju kao rešenje zadatka komisiji na ocenjivanje, trebalo bi da prođe nekoliko ne previše zahtevnih unpared generisanih test primera, ali sasvim sigurno ne sve, jer još uvek nismo završili pravu optimizaciju, odnosno samo smo je započeli sređivanjem skoro svih tipova podataka i dužine niza.
Preciznije, u ovom konkretnom 3. zadatku sa takmičenja, ova verzija programskog koda će proći svih 22 unapred generisanih test primera, što možete i sami da proverite (pokazaću vam kako), ali će za više od pola test primera (počev od test primera 09.in) raditi previše sporo, po nekoliko sekundi, odnosno minuta, jer se radi o zaista mnogo velikim brojevima, te će za te test primere ostati bez bodova, jer nije ispunjen uslov vremenskog ograničenja.
9. Deo - Nizovi - Optimizacija brzine izvršavanja progrmskog koda - Ispunjavanje uslova vremenskog ograničenja
Optimizacija brzine izvršavanja programskog koda je najteži deo i zahteva mnogo iskustva u radu i korišćenje poznatih algoritamskih metoda i tehnika. Za to je takođe potrebno vreme, a mi ćemo objašenjenje ovog dela ostaviti za kasnije. Za sada, važno je da imamo programski kod koji prolazi kroz nekoliko test primera, a ukoliko želimo da programski kod ubrzamo neophodno je da razmišljamo u sledećem pravcu:
- Da pronađemo neki matematičko-logički model boljeg rešenja (vraćajući se na sam tekst zadatka), odnosno da pokušamo nekako da poređamo raspored kuća u nekom pravilnijem redosledu (na primer rastućem), pa da vidimo da li ćemo uočiti neke zakonitosti.
- Biće neophodno da sortiramo niz.
- Verovatno ćemo morati da uvedemo još jedan niz iste dužine.
- Verovatno ćemo morati da nađemo sredinu između tačaka A i B.
O svemu ovome biće više reči na sledećim konusltacijama.
Pozdrav,
Dragan Ilić
Dragan Ilić
Нема коментара:
Постави коментар