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 koji učita 10 nizova znakova duljine do 20 znakova. Svi unešeni znakovi su samo alfabetski standardni ASCII znakovi (mala i velika slova). Sortirati te nizove znakova po abecedi i ispisati ih. Uputa: prebaciti sve unešene znakove u velika ili mala slova prije sortiranja i tako ih sortirati i ispisati.
Rok za predaju zadaće: 17. 11 2006.

2) Napisati program koji će upotrebom velikog broja generiranih parova slučajnih brojeva izračunati površinu kruga radijusa r s centrom u središtu koordinatnog sustava (0,0). Usporediti dobiveni rezultat s izračunatom pravom vrijednošću površine kruga. Uputa: krug radijusa r smjestiti unutar kvadrata stranica duljine 2r. Provjeravati za svaku generiranu točku (x,y) koja se mora nalaziti unutar kvadrata da li se nalazi i unutar kruga. Površina kruga tada odgovara omjeru broja točaka unutar kruga prema ukupnom broju točaka pomnoženim s površinom kvadrata.
Rok za predaju zadaće: 17. 11 2006.

3) Napišite program koji će za bilo koju vrijednost cijelog broja n provjeriti ispravnost sljedećih izraza:

                                  

Izračunavanje svake od gornjih suma je potrebno obaviti u posebnoj funkciji, a za svaku od suma je potrebno napraviti funkciju koja računa sumu rekurzivnim i nerekurzivnim postupkom.
Rok za predaju zadaće: 08. 12. 2006.

4) Napisati funkcije za sortiranje metodom umetanja (Insertion Sort) i mjehuričastim sortiranjem (Bubble Sort) koje sortiraju elemente silazno (od najvećeg prema najmanjem). 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). Pronaći u koliko se koraka sortira polje u najgorem slučaju za oba algoritma i odrediti koji je brži za vrlo dugačke nizove brojeva (koristiti biblioteku <sys/timeb.h> i funkciju ftime(struct timeb*) za mjerenje vremena izvršavanja sortiranja, kako je objašnjeno na predavanjima).
Rok za predaju zadaće: 15. 12. 2006.

5) Koristeći Eratostenov algoritam objašnjen na vježbama, napraviti program koji će za bilo koji upisani prirodni broj x (maksimalan broj nije unaprijed zadan - polje treba rezervirati dinamički upotrebom funkcije malloc) odrediti da li je prim broj i ako nije prikazat ga kao umnožak prim brojeva (bez ostatka, tj. u obliku x=p1*p2*...*pk).
Rok za predaju zadaće: 15. 12. 2006.

6) Napisati program u kojem se dvije liste cijelih brojeva izvedene pomoću polja i unaprijed zadane duljine 15, pune slučajno generiranim brojevima od 0 do 100 tako da su sortirane od najmanjeg prema najvećem elementu (uzlazno). Te dvije liste zatim treba spojiti u jednu duljine 30, koja je također sortirana od najmanjeg prema najvećem elementu. Sve liste je potrebno ispisati. Uputa: jedna od mogućnosti izvedbe programa je umetanje novog elementa u listu tako da se pretragom od početka liste nađe prva pozicija u listi čija je vrijednost elementa veća od vrijednosti novog elementa i tada se ubaci novi element na poziciju ispred nađene. Spajanje dviju listi izvesti tako da se uspoređuju prvi neprebačeni elementi obje liste i manji od njih se upiše na prvo slobodno mjesto spojene liste. Sljedeća mogućnost je upotreba nekog od algoritama sortiranja koji smo radili na vježbama: sortiranje umetanjem ili mjehuričasto sortiranje.
Rok za predaju zadaće: 15. 12. 2006.

7) Napisati program u kojem se dvije liste cijelih brojeva izvedene pomoću pokazivača i duljina koje se zadaju prije unošenja elemenata, pune slučajno generiranim brojevima od 0 do 100 tako da su sortirane od najmanjeg prema najvećem elementu (uzlazno). Te dvije liste zatim treba spojiti u jednu, koja je također sortirana od najmanjeg prema najvećem elementu. Uputa: umetanje novog elementa u listu izvesti tako da se krene od početka liste i vrijednost novog elementa se uspoređuje s vrijednostima u listi dok se ne nađe mjesto na koje treba ubaciti novi element.
Rok za predaju zadaće: 22. 12 2006.

8) U memoriji oblikovati vezanu listu (pomoću pokazivača). U pojedini čvor liste upisati:
- matični broj osobe     (int)
- prezime                   (30 znakova)
- ime                         (30 znakova)     
- godina rođenja          (short)
- pokazivač na sljedeći čvor
Unos podataka ostvariti učitavanjem iz ulazne datoteke. Elemente liste složiti po ključu matični broj, tako da su uzlazno sortirani. Napisati funkciju koja će iz liste ispisati sve zapise o osobama rođenim određene godine koja se unosi tijekom izvršavanja programa.
Rok za predaju zadaće: 05. 01 2007.

9) 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 s tastature 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 artiklu koji se prodaje u dućanu:
–šifra artikla  (int)
–naziv artikla (25 znakova)
–cijena         (float)
Rok za predaju zadaće: 05. 01 2007.

10) Strukturu podataka red realizirati uz upotrebu pokazivača. Svaki element reda sadrži naziv (20 znakova) i vrijednost (realni broj). 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: 10. 01. 2007.

11) 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 i obilaskom tog stabla algoritmom obilaska koji ispisuje elemente u sortiranom redoslijedu. Usporediti vrijeme izvršavanja sortiranja za ovaj algoritam i algoritam sortiranja umetanjem (Insertion Sort) mjerenjem vremena izvršavanja za dugačke nizove brojeva upotrebom biblioteke <sys/timeb.h> i funkcije ftime(struct timeb*) za mjerenje vremena, kako je objašnjeno na predavanjima.
Rok za predaju zadaće: 22. 01. 2007.

12) Napisati funkciju za punjenje memorijski rezidentnog binarnog stabla u čije čvorove treba upisati: matični broj (cijeli broj) i prezime osobe (15+1 znakova). Stablo treba sortirati po matičnom broju: lijevo manji, desno veći. Napisati funkciju za ispis elemenata za koju je ulazni argument korijen stabla, gdje ispis treba biti poredan uzlazno po matičnom broju. Napisati funkciju koja ispiše matični broj za zadano prezime osobe.
Rok za predaju zadaće: 22. 01. 2007.

13) 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). Usporediti vrijeme izvršavanja sortiranja pomoću hrpe i sortiranja umetanjem (Insertion Sort) mjerenjem vremena potrebnog za sortiranje identičnog niza ulaznih podataka i odrediti koji je brži za vrlo dugačke nizove brojeva (koristiti biblioteku <sys/timeb.h> i funkciju ftime(struct timeb*) za mjerenje vremena izvršavanja sortiranja, kako je objašnjeno na predavanjima).
Rok za predaju zadaće: 02. 02. 2007.

14) Napisati program koji od ulaznog polja alfabetskih znakova (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 ...) proizvoljne duljine, koja se unosi na početku izvršavanja programa (koristiti funkciju malloc() za rezerviranje memorije za polje), izgradi hrpu, te ispiše polje u kojem su spremljeni elementi hrpe. Također napraviti funkciju koja sortira polje takvih znakova upotrebom sortiranja pomoću hrpe i ispisati sortirano polje.
Rok za predaju zadaće: 02. 02. 2007.

15) 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: 07. 02. 2007.

16) 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: 07. 02. 2007.

17) 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: 07. 02. 2007.

18) 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: 07. 02. 2007.

19) 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 07. 02. 2007.