Zadaci za zadaću




Tijekom semestra predviđeno je zadavanje bar 15 zadataka za zadaću. Studenti trebaju uspješno riješiti barem tri od tih zadataka i predati zadaću u predviđenom roku. Student/ica može riješiti i predati i više od tri zadatka, tada se za završnu ocjenu računaju tri najbolje ocjenjena zadatka. Zadaća koja se predaje treba sadržavati tekst zadatka, kratak opis problema, algoritma i programskog koda rješenja, te sam programski kod. Zadaću molim poslati emailom ili predati osobno predavaču na nekom mediju.

Popis zadataka:


1) Napisati program koji će upotrebom velikog broja generiranih parova slučajnih realnih brojeva izračunati površinu krivulje lemniskate zadane izrazom
               (x2+y2)2 - 2*e2*(x2-y2)=0                         

Usporediti dobiveni rezultat s izračunatom pravom vrijednošću površine.
Uputa: krivulju smjestiti unutar pravilnog geometrijskog lika čija se površina zna jednostavno izračunati. Provjeravati za svaku generiranu točku (x,y) koja se mora nalaziti unutar pravilnog lika da li se nalazi i unutar lemniskate. Površina krivulje tada odgovara omjeru broja generiranih točaka unutar krivulje prema ukupnom broju točaka pomnoženim s površinom pravlinog lika.
Rok za predaju zadaće: 13. 11 2009.

2) Napisati program u kojem se koriste rekurzivne funkcije za izračunavanje sljedeća 3 izraza:
 i) sumu niza cijelih brojeva koji su elementi polja duljine n,
 ii) vrijednost 2n, gdje je n zadani cijeli broj,
 iii) sumu prvih n neparnih brojeva (2*i+1, i=0,...,n) za neki zadani n.
 Rok za predaju zadaće: 16. 11 2009.

3) Napisati program za implementaciju liste pomoću polja u kojem se lista proizvoljne duljine zadane tijekom izvršavanja programa (koristiti funkciju malloc() za stvaranje polja) puni slučajnim cijelim brojevima između 1 i 100. Parne brojeve koji su elementi početne liste treba prepisati u zasebnu, novu listu. Upis elemenata u novu listu izvesti tako da bude uzlazno sortirana, dakle svaki novi element se upisuje ispred prvog elementa te liste koji je veći od njega.
Rok za predaju zadaće: 27. 11 2009.

4) Napisati program za implementaciju liste pomoću pokazivača u kojem se lista proizvoljne duljine zadane tijekom izvršavanja programa puni slučajnim cijelim brojevima između 1 i 100. Neparne brojeve koji su elementi početne liste treba prepisati u zasebnu, novu listu. Upis elemenata u novu listu izvesti tako da bude uzlazno sortirana, dakle svaki novi element se upisuje ispred prvog elementa te liste koji je veći od njega.
Rok za predaju zadaće: 01. 12 2009.

5) U programu je potrebno napraviti izvedbu liste pomoću pokazivača, gdje elementi liste sadrže cijeli broj i niz znakova duljine 8. Napisati funkcije koje ubacuju novi element na proizvoljnu poziciju u listi, izbacuju proizvoljni element iz liste, pretražuju listu po vrijednosti cijelog broja i ispisuju cijelu listu (za svaku ćeliju liste potrebno je ispisati obje vrijednosti, cijeli broj i niz znakova).
Rok za predaju zadaće: 04. 12 2009.

6) U programu izvesti dvostruko povezanu listu pomoću pokazivača. Element liste je zapis o osobi koji uključuje sljedeće podatke:
- identifikacisjki broj     (int)
- prezime    (20 znakova)
- ime    (20 znakova)
- godina rođenja   (short int)
- pokazivač na sljedeći čvor po identifikacijskom broju
- pokazivač na sljedeći čvor po prezimenu osobe
Unos podataka ostvariti učitavanjem iz ulazne datoteke. Elemente liste složiti po ključevima identifikacijski broj i prezime osobe, tako da su uzlazno sortirani. Napisati funkciju koja će iz liste ispisati sve zapise o osobama koje su rođene određene godine koja se unosi tijekom izvršavanja programa i ulazni je argument funkcije koja ispisuje podatke.
Rok za predaju zadaće: 06. 12 2009.

7) Napisati funkcije za dodavanje i skidanje elementa u stog realiziran poljem u koje stane najviše MAXZ zapisa. U glavnom programu izvesti učitavanje podataka za element stoga iz ulazne datoteke kao i ispisivanje elementa stoga koji je skinut (npr. unijeti nekoliko elemenata u stog, a zatim skinuti i ispisati svaki element sve dok stog ne ostane prazan). Element stoga je zapis o izvršavanju funkcija unutar programa:
- identifikacijski broj procesa       (short)
- ime funkcije                         (20 znakova)
- identifikacijski broj nadređenog procesa (short)     
- vrijeme slanja procesa                (int)
Rok za predaju zadaće: 09. 12 2009.

8) Napisati funkcije za dodavanje i skidanje elementa u stog realiziran pomoću pokazivača. U glavnom programu izvesti učitavanje podataka za element stoga iz ulazne datoteke kao i ispisivanje elementa stoga koji je skinut (npr. unijeti nekoliko elemenata u stog, a zatim skinuti i ispisati svaki element sve dok stog ne ostane prazan). Element stoga je zapis o osobama čija je građa:
- matični broj osobe     (int)
- prezime                   (20 znakova)
- ime                         (20 znakova)     
- godina rođenja          (short)
Rok za predaju zadaće: 12. 12 2009.

9) Napisati program u kojem se realizira red pomoću cirkularnog polja. Svaki element reda ima građu:
- cijeli broj (int)
- realni broj (float)
Ulazni podatci čitaju se iz ulazne datoteke. Potrebno je napraviti funkciju za ubacivanje podataka u red, izbacivanje podataka iz reda, određivanje duljine reda i ispisivanje elemenata u redu, te njihovo pozivanje iz glavne procedure.
Rok za predaju zadaće: 15. 12 2009.

10) Strukturu podataka red realizirati uz upotrebu pokazivača. Svaki element reda sadrži:
- naziv (10 znakova)
- oznaka (int).
Treba napisati funkciju koja dodaje i funkciju koja briše element iz reda, a u njima treba ispisati element na kojem se obavlja operacija. Također napisati funkciju koja ispiše sve elemente u redu.
Rok za predaju zadaće: 18. 12. 2009.

11) Napisati program za realizaciju dvostruko povezane liste u kojoj pojedina ćelija ima ovakvu građu:
- cijeli broj (int)
- realni broj (float)
- pokazivač na sljedeći čvor
- pokazivač na prethodni čvor
Napisati funkcije za ubacivanje i izbacivanje podataka u listu, pretraživanje liste po cijelim i po realnim vrijednostima, te funkciju za ispis cijele liste. Elementi liste, cijeli i realni brojevi, se dobivaju upotrebom generatora slučajnih brojeva.
Rok za predaju zadaće: 30. 12. 2009.

12) Napisati program u kojem je realizirano sortirano binarno stablo preko pokazivača, a čiji elementi su:
- niz znakova duljine 3 (koriste se samo ASCII znakovi)
- cijeli broj.
Binarno stablo je sortirano prema vrijednosti niza znakova (uređaj abecede). Napisati funkcije koje sortiraju upisane elemente uzlazno (od najmanjeg prema najvećem) i silazno (od najvećeg prema najmanjem) obilascima tog stabla algoritmom obilaska koji ispisuje elemente u sortiranom redoslijedu. Napisati sljedeće funkcije:
- koja traži prema vrijednosti niza znakova da li se element nalazi u stablu i vraća adresu čvora u kojem se taj element nalazi
- koja traži prema vrijednosti cijelog broja da li se element nalazi u stablu i vraća adresu čvora u kojem se taj element nalazi
- koja odredi maksimalnu i minimalnu dubinu sortiranog binarnog stabla.
Rok za predaju zadaće: 03. 01. 2010.

13) Napraviti program koji sortira niz realnih brojeva proizvoljne duljine (koja se zadaje na početku izvođenja programa) uzlazno (od najmanjeg prema najvećem) i silazno (od najvećeg prema najmanjem) upotrebom binarnog stabla traženja izvedenog pomoću polja i obilaskom tog stabla algoritmom obilaska koji ispisuje elemente u sortiranom redoslijedu. Ulazni podaci su generirani slučajni brojevi. Napisati funkcije koje:
- traži da li se element nalazi u stablu i vraća poziciju na kojoj se element nalazi
- ispiše minimalni element u sortiranom binarnom stablu
- ispiše maksimalni element u sortiranom binarnom stablu
- prebroji listove i vrati koliko ih ima u binarnom stablu
Rok za predaju zadaće: 05. 01. 2010.

14) Napisati program u kojem se apstraktni tip podataka skup izvodi pomoću vezane liste (vidjeti predavanja). Elementi skupova su cijeli brojevi (sami izaberite način na koji se određuju ulazni elementi za skupove). Liste ostvariti pomoću pokazivača. Napisati funkcije za uniju dva skupa Union(), presjek dva skupa Intersection() i razliku dva skupa Difference(). Napisati funkciju za ispis elemenata skupa kojom se ispisuju ulazni skupovi i rezultati gornje tri funkcije.
Rok za predaju zadaće: 06. 01. 2010.


15) Napisati program koji od ulaznog polja slučajno generiranih cijelih brojeva izgradi minimalnu hrpu (u korijenu je minimalni element), te ispiše polje u kojem su spremljeni elementi hrpe. Zatim napisati funkciju za silazno sortiranje (od najvećeg prema najmanjem elementu) polja cijelih brojeva upotrebom sortiranja pomoću hrpe. Sortira se polje generiranih slučajnih cijelih brojeva, proizvoljnog broja elemenata N koji se zadaje na početku programa (koristiti dinamičko rezerviranje memorije za spremanje polja - funkcija malloc).
Rok za predaju zadaće: 24. 01. 2010.

16) Napisati program koji od ulaznog polja nizova alfabetskih znakova duljine 4 (koriste se samo slova engleske abecede, dakle ASCII znakovi koji odgovaraju slovima; podaci se unose iz ulazne datoteke) gdje je broj nizova znakova proizvoljan i unosi se na početku izvršavanja programa (koristiti funkciju malloc() za rezerviranje memorije za polje), izgradi maksimalnu hrpu, te ispiše polje u kojem su spremljeni elementi hrpe. Također napraviti funkciju koja uzlazno sortira polje takvih nizova znakova (po abecedi) upotrebom sortiranja pomoću hrpe i ispisati sortirano polje.
Rok za predaju zadaće: 25. 01. 2010.

17) Napisati program u kojem je realiziran prioritetni red pomoću hrpe čiji članovi imaju građu:
- cijeli broj koji određuje prioritet
- realni broj
koji se dobivaju generiranjem slučajnih brojeva.
Program treba sadržavati funkcije za ubacivanje novih i izbacivanje elementa s maksimalnim prioritetom iz prioritetnog reda (vidjeti predavanja i vježbe), te za ispis elemenata hrpe. Hrpu implementirati pomoću polja čija je duljina unaprijed zadana na početku programa (čime je ograničen i maksimalan broj članova prioritetnog reda).
Rok za predaju zadaće: 26. 01. 2010.

18) Napisati funkciju za silazno sortiranje (od najvećeg prema najmanjem elementu) ulaznog polja slučajno generiranih cijelih brojeva duljine N algoritmom sortiranja spajanjem (Merge Sort). Duljina polja se zadaje na početku izvršavanja programa i upotrebom funkcije malloc() rezervira se memorija za polje. Usporediti vrijeme izvršavanja algoritama sortiranja spajanjem i sortiranja umetanjem (Insertion Sort) na primjeru dugačkog niza brojeva (ulazni niz slučajno generiranih brojeva kopirati u drugo polje koje će biti ulazni niz za sortiranje umetanjem). Usporediti sortirana polja i utvrditi da li su oba algoritma dala identičan (točan) rezultat.
Rok za predaju zadaće: 29. 01. 2010.

19) Napisati funkciju za silazno sortiranje (od najvećeg prema najmanjem elementu) ulaznog polja slučajno generiranih cijelih brojeva duljine N algoritmom Shell-ovog sortiranja. Duljina polja se zadaje na početku izvršavanja programa i upotrebom funkcije malloc() rezervira se memorija za polje. Usporediti vrijeme izvršavanja algoritama Shell-ovog sortiranja i sortiranja umetanjem (Insertion Sort) na primjeru dugačkog niza brojeva (ulazni niz slučajno generiranih brojeva kopirati u drugo polje koje će biti ulazni niz za sortiranje umetanjem). Usporediti sortirana polja i utvrditi da li su oba algoritma dala identičan (točan) rezultat.
Rok za predaju zadaće: 01. 02. 2010.

20) Napisati funkciju za silazno sortiranje (od najvećeg prema najmanjem elementu) ulaznog polja slučajno generiranih cijelih brojeva duljine N algoritmom brzog sortiranja (Quick Sort). Duljina polja se zadaje na početku izvršavanja programa i upotrebom funkcije malloc() rezervira se memorija za polje. Usporediti vrijeme izvršavanja algoritama brzog sortiranja i sortiranja umetanjem (Insertion Sort) na primjeru dugačkog niza brojeva (ulazni niz slučajno generiranih brojeva kopirati u drugo polje koje će biti ulazni niz za sortiranje umetanjem). Usporediti sortirana polja i utvrditi da li su oba algoritma dala identičan (točan) rezultat.
Rok za predaju zadaće: 03. 02. 2010.