Zadaci za zadaću




Tijekom semestra predviđeno je zadavanje bar 15 zadataka za zadaću. Studenti trebaju uspješno riješiti bar 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. Programski kod molim poslati također emailom ili predati osobno predavaču na nekom mediju.

Popis zadataka:

1) Napisati program u kojem se realizira vektorsko zbrajanje i oduzimanje, te skalarno množenje trodimenzionalnih vektora. Izvesti strukturu podataka primjerenu za prikaz 3D vektora (x,y,z) gdje su x,y,z realni brojevi, te napisati funkcije za zbroj, razliku i skalarni produkt 2 vektora. U glavnoj funkciji programa izvesti upis koordinata vektora, te ispis vektora i rezultata ove 3 operacije.
Rok za predaju zadaće: 7. 11 2007.

2) Napisati program koji će upotrebom velikog broja generiranih trojki slučajnih brojeva izračunati volumen kugle radijusa r s centrom u središtu koordinatnog sustava (0,0,0). Usporediti dobiveni rezultat s izračunatom pravom vrijednošću volumena kugle. Uputa: kuglu radijusa r smjestiti unutar kocke stranica duljine 2r. Provjeravati za svaku generiranu točku (x,y,z) koja se mora nalaziti unutar kocke da li se nalazi i unutar kugle (volumen kugle određen je izrazom x2+y2+z2 <= r2). Volumen kugle tada odgovara omjeru broja točaka unutar kugle prema ukupnom broju točaka pomnoženim s volumenom kocke.
Rok za predaju zadaće: 7. 11 2007.

3) Napisati program s funkcijama za sortiranje metodom umetanja (Insertion sort) i mjehuričastim sortiranjem (Bubble sort) koje sortiraju elemente silazno (od najvećeg prema najmanjem, obrnuto od primjera napravljenog na vježbama). Sortiraju se polja generiranih slučajnih cijelih brojeva. Veličina polja koje se sortira nije unaprijed zadana, nego se određuje tijekom izvršavanja programa (koristiti funkciju malloc() za stvaranje polja). Usporediti polja dobivena kao rezultat ta dva sortiranja i provjeriti da li su identična.
Rok za predaju zadaće: 14. 11 2007.

4) Napisati program koji poziva rekurzivnu funkciju koja računa n-ti član općeg aritmetičkog niza a1=a, an=an-1+d, gdje su a i d realni brojevi različiti od nule čije se vrijednosti zadaju u glavnoj proceduri i ulazni su argumenti funkcije. Funkcija vraća izračunatu vrijednost u glavnu proceduru. Napisati također i funkciju koja isti račun obavlja nerekurzivnim postupkom, te je pozvati iz glavne procedure na analogan način. Usporediti rezultate računa te dvije funkcije.
Rok za predaju zadaće: 14. 11 2007.

5) 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. Elemente početne liste treba prepisati u 2 zasebne, nove liste tako da u jednoj budu samo neparni, a u drugoj samo parni brojevi iz početne liste. Upis elemenata u te 2 liste izvesti tako da one budu uzlazno sortirane, dakle svaki novi element se upisuje na poziciju u listi ispred prvog elementa te liste koji je veći od njega.
Rok za predaju zadaće: 05. 12 2007.

6) 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. Elemente početne liste treba prepisati u 2 zasebne, nove liste tako da u jednoj budu samo neparni, a u drugoj samo parni brojevi iz početne liste. Upis elemenata u te 2 liste izvesti tako da one budu uzlazno sortirane, dakle svaki novi element se upisuje na poziciju u listi ispred prvog elementa te liste koji je veći od njega.
Rok za predaju zadaće: 05. 12 2007.

7) U programu treba izvesti dvostruko vezanu listu pomoću pokazivača. Element liste je zapis o artiklu, gdje u pojedini čvor liste treba upisati:
- šifru artikla     (int)
- naziv artikla    (30 znakova)
- cijena artikla   (float)
- pokazivač na sljedeći čvor po šifri artikla
- pokazivač na sljedeći čvor po nazivu artikla
Unos podataka ostvariti učitavanjem iz ulazne datoteke. Elemente liste složiti po ključevima šifra i naziv artikla, tako da su uzlazno sortirani. Napisati funkciju koja će iz liste ispisati sve zapise o artiklima čija je cijena veća od vrijednosti koja se unosi tijekom izvršavanja programa i ulazni je argument funkcije koja ispisuje podatke.
Rok za predaju zadaće: 23. 12 2007.

8) 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 osobama čija je građa:
- matični broj osobe     (int)
- prezime                   (30 znakova)
- ime                         (30 znakova)     
- godina rođenja          (short)
Rok za predaju zadaće: 23. 12 2007.

9) 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 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: 7. 01 2008.

10) Napisati program u kojem se realizira red pomoću cirkularnog polja. Svaki element reda ima građu:
- cijeli broj (int)
- niz znakova duljine 15
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: 7. 01 2008.

11) Strukturu podataka red realizirati uz upotrebu pokazivača. Svaki element reda sadrži:
- naziv (20 znakova)
- vrijednost (float).
Treba napisati  funkciju koja dodaje i funkciju koja briše element iz reda, u kojima treba ispisati element na kojem se obavlja operacija. Također napisati funkciju koja ispiše sve elemente u redu.
Rok za predaju zadaće: 7. 01. 2008.

12) 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: 10. 01. 2008.

13) Napraviti program koji sortira niz cijelih 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.
Rok za predaju zadaće: 10. 01. 2008.

14) 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 pokazivača i obilaskom tog stabla algoritmom obilaska koji ispisuje elemente u sortiranom redoslijedu.
Rok za predaju zadaće: 10. 01. 2008.

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: 30. 01. 2008.

16) Napisati program koji od ulaznog polja nizova alfabetskih znakova duljine 4 (koriste se samo slova engleske abecede, dakle ASCII znakovi koji odgovaraju slovima; sami izaberite na koji način se unose podaci: s tastature, iz ulazne datoteke, generator slučajnih brojeva ...) gdje je broj nizova 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: 30. 01. 2008.

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 elemenata 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: 30. 01. 2008.

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: 06. 02. 2008.

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: 06. 02. 2008.

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: 06. 02. 2008.

21) 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. 02. 2008.

22) Napisati program koji rješava 0/1 problem ranca (vidjeti predavanja). Zadano je n predmeta (nije unaprijed zadan broj nego se određuje na početku izvođenja programa) O1, ..., On te njihove težine wi i vrijednosti pi. Kapacitet ranca je c težinskih jedinica. Težine i vrijednosti predmeta, te kapacitet ranca su realne pozitivne veličine. Odrediti koje predmete treba uzeti u ranac tako da njihova ukupna vrijednost bude maksimalna ? Predmeti se ne mogu dijeliti, nego se uzimaju ili ne.
Rok za predaju zadaće 06. 02. 2008.