Zadatak 1. Napisati program koji će iz datoteke pročitati imena i prezimena studenata i upisati ih po abecedi (po prezimenima) u listu čiji je element oblika ime (20 znakova), prezime (20 znakova), broj zadatka (kratki cijeli broj). Broj studenata nije unaprijed zadan nego ovisi o broju zapisa u ulaznoj datoteci. Vrijednost varijable broj zadatka za svaki element liste mora biti od 1 do N (N se zadaje tijekom izvođenja programa i ne smije biti unaprijed zadan) i treba ju upisati (svaki broj samo jednom, bez ponavljanja istih brojeva) u listu koristeći generator slučajnih brojeva (npr. ako je prvi generirani broj 17 tada taj broj ide uz studenta koji je prvi po redu itd). Tako dobivenu listu treba ispisati u obliku: prezime, ime, zadatak.

 

 

Zadatak 2. Napraviti program koji će veliki broj puta (recimo milijun ili više) generiranjem slučajnih brojeva (koji odgovaraju broju točkica na kockama, dakle od 1 do 6) simulirati bacanje pet jednakih kockica. Iz dobivenih rezultata odrediti vjerojatnost da točno tri kockice padnu tako da pokazuju isti broj točkica (znači da imamo tri jedinice ili tri dvojke ili … tri šestice). Usporediti dobiveni rezultat s rezultatom koji daje teorija vjerojatnosti.

 

 

Zadatak 3. Napravite program u kojem je izvedena hrpa pomoću pokazivača. Elementi hrpe su generirani slučajni brojevi, čiji se broj određuje na početku izvršavanja programa i ne smije biti ograničen. Od tih brojeva je potrebno izgraditi minimalnu i maksimalnu hrpu, te dobivene hrpe ispisati.

 

Zadatak 4. Napraviti program u kojem generator slučajnih brojeva daje niz podataka tipa ASCII znak duljine 3 koji odgovaraju malim i velikim slovima engleske abecede. Broj podataka nije unaprijed određen nego se zadaje na početku izvršavanja programa. Dobiveni niz podataka treba sortirati uzlazno upotrebom mjehuričastog sortiranja (bubble sort). Napisati funkciju koja algoritmom binarnog pretraživanja pronalazi da li se i na kojem mjestu u sortiranom nizu podataka nalazi zadani niz ASCII znakova duljine 3. Također napisati funkciju koja to isto radi algoritmom linearnog pretraživanja. Usporediti aposteriorna vremena izvršavanja pretraživanja sortiranog niza znakova za linearno i binarno pretraživanje.

 

 

Zadatak 5. Na predavanjima smo obrađivali apstraktni tip podataka RJEČNIK i prikazali ga kao podvrstu apstraktnog tipa podataka SKUP za koji su definirane samo četiri osnovne operacije: MAKE_NULL(), INSERT(), DELETE() i MEMBER(). Pokazali smo njegovu izvedbu pomoću binarnog stabla traženja gdje je binarno stablo izvedeno pomoću pokazivača. Napisati funkcije za gornje četiri operacije kada je element rječnika niz znakova duljine 20. Broj elemenata u rječniku nije unaprijed određen nego se zadaje na početku izvršavanja programa ovisno o broju podataka koji se unose u rječnik učitavanjem iz ulazne datoteke. Ti podaci se mogu mijenjati brisanjem postojećih i ubacivanjem novih nizova znakova. Na kraju izvršavanja programa treba sve podatke pospremiti u novu izlaznu datoteku.



 

Zadatak 6. Napisati program u kojem se napravi lista pomoću pokazivača čiji su elementi cijeli brojevi. Broj elemenata u listi nije unaprijed zadan već se učita na početku izvršavanja programa. Lista se puni pomoću generatora slučajnih brojeva. Napisati funkciju koja će sortirati listu upotrebom algoritma sortiranja spajanjem (merge sort). Listu treba sortirati uzlazno (od najmanjeg prema najvećem elementu). Ispisati početnu listu i sortiranu listu.

 

                          

Zadatak 7. Napisati program u kojem se napravi lista pomoću polja čiji su elementi realni brojevi. Broj elemenata u listi nije unaprijed zadan već se učita na početku izvršavanja programa. Lista se puni pomoću generatora slučajnih brojeva. Napisati funkciju koja će sortirati listu upotrebom algoritma sortiranja spajanjem (merge sort). Listu treba sortirati uzlazno (od najmanjeg prema najvećem elementu) i silazno (od najvećeg prema najmanjem elementu). Ispisati početnu listu i sortirane liste.

 

 

Zadatak 8. Napisati program za zbrajanje dva polinoma prikazanih u obliku p(x) = c1xe1 + c2xe2 + … + cn xen gdje su eksponenti e1 > e2 > … > en ≥ 0 cijeli brojevi, a koeficijenti ci realni brojevi. Polinome prikazati vezanom listom uz upotrebu pokazivača tako da i-ta ćelija liste sadrži eksponent ei, koeficijent ci i pokazivač na sljedeću ćeliju. Na početku programa unose se red (maksimalna potencija x-a) i vrijednosti koeficijenata za svaki polinoma. Ispisati dvije početne liste i listu rezultat nastalu zbrajanjem polinoma.

 

 

Zadatak 9. Napisati program koji izgradi binarno stablo traženja upotrebom polja. Broj čvorova stabla nije unaprijed određen nego se zadaje na početku programa. U čvorove binarnog stabla zapisuju se realni brojevi dobiveni upotrebom generatora slučajnih brojeva. Napisati funkciju koja prebroji listove, funkciju koja prebroji unutrašnje čvorove binarnog stabla i funkciju koja odredi maksimalnu dubinu binarnog stabla. Ispisati stablo u inorder, preorder i postorder algoritmu.

 

 

Zadatak 10. Napisati program koji izgradi binarno stablo traženja upotrebom pokazivača (svaki čvor sadrži pokazivače na lijevo i desno dijete čvora). Broj čvorova stabla nije unaprijed određen nego se zadaje na početku programa. U čvorove binarnog stabla zapisuju se cijeli brojevi dobiveni upotrebom generatora slučajnih brojeva. Napisati funkciju koja prebroji listove, funkciju koja prebroji unutrašnje čvorove binarnog stabla i funkciju koja odredi maksimalnu dubinu binarnog stabla. Ispisati stablo u inorder algoritmu.



Zadatak 11. Napisati program koji će upotrebom velikog broja uređenih trojki slučajno generiranih (realnih !) brojeva izračunati volumen elipsoida s polovima A, B, C i centrom u središtu koordinatnog sustava (0,0,0). Uputa: elipsoid smjestiti unutar kocke ili kvadra odgovarajuće veličine. Provjeravati za svaku generiranu točku (x,y,z) koja se mora nalaziti unutar kocke/kvadra da li se nalazi i unutar elipsoida te prebrojati koliko se točaka nalazi unutar elipsoida. Volumen elipsoida tada odgovara omjeru broja generiranih slučajnih točaka unutar elipsoida s ukupnim broju generiranih točaka pomnoženom s volumenom kocke/kvadra.



Zadatak 12. Napišite program koji će za bilo koju vrijednost pozitivnog 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 napisati funkciju koja računa sumu rekurzivnim i nerekurzivnim postupkom.



Zadatak 13. Koristeći Eratostenov algoritam napraviti program koji će za bilo koji upisani prirodni broj N odrediti da li je prim broj. U programu treba koristiti polje bitova, a ne polje cijelih brojeva kao na primjeru napravljenom na vježbama. Maksimalna vrijednost prirodnog broja N nesmije biti ograničena, pa je potrebno koristiti dinamičko rezerviranje memorije - funkcija malloc().


Zadatak 14. Napisati program za izvedbu liste pomoću pokazivača. Elementi liste su cijeli brojevi dobiveni generatorom slučajnih brojeva. Listu je potrebno sortirati uzlazno, te zatim elemente iz te liste prebaciti u druge dvije liste tako da jedna sadrži samo parne, a druga samo neparne brojeve iz početne liste. Ispisati sve liste. Veličina lista nije unaprijed zadana i ograničena, već se određuje tijekom izvršavanja programa.


Zadatak 15. Napisati program u kojem će se usporediti brzine odvijanja soriranja brzim algoritmom (Quick Sort) za četiri različita načina izbora pivot elementa (stožera): 1) kada je stožer uvijek prvi element niza 2) kada je stožer srednji po veličini od prvog, srednjeg i zadnjeg elementa 3) kada je stožer element uzet sa slučajno izabrane pozicije u nizu 4) kada je stožer srednji po veličini od tri elementa uzetih sa slučajno izabranih pozicija. Elementi niza su cijeli brojevi, a duljina niza nije unaprijed zadana ni ograničena, nego se zadaje na početku izvršavanja programa. Provjeriti ispravnost sortiranja u sva četiri slučaja uspoređivanjem sortiranih nizova.

Zadatak 16. Napisati program koji izgradi binarno stablo traženja upotrebom polja. Broj čvorova stabla nije unaprijed određen nego se zadaje na početku programa. U čvorove binarnog stabla zapisuju se alfabetski znakovi (samo slova engleske abecede, relacija manji-veći je definirana rasporedom slova u abecedi) dobiveni upotrebom generatora slučajnih brojeva. Napisati funkciju koja prebroji čvorove sa samo jednim djetetom, funkciju koja prebroji čvorove s dvoje djece i funkciju koja odredi minimalnu dubinu binarnog stabla. Ispisati stablo u inorder, preorder i postorder algoritmu.

 

 

Zadatak 17. Napisati program koji izgradi binarno stablo traženja upotrebom pokazivača (svaki čvor sadrži oznaku i pokazivače na lijevo i desno dijete čvora). Broj čvorova stabla nije unaprijed određen nego se zadaje na početku programa. U čvorove binarnog stabla zapisuju se alfabetski znakovi (samo slova engleske abecede, relacija manji-veći je definirana rasporedom slova u abecedi) dobiveni upotrebom generatora slučajnih brojeva. Napisati funkciju koja prebroji čvorove sa samo jednim djetetom, funkciju koja prebroji čvorove s dvoje djece i funkciju koja odredi minimalnu dubinu binarnog stabla. Ispisati stablo u inorder, preorder i postorder algoritmu.

 

 

Zadatak 18. Napisati program u kojem se lista cijelih brojeva sortira upotrebom binarnog stabla traženja uzlazno (od najmanjeg prema najvećem elementu) i silazno (od najvećeg prema najmanjem) upotrebom istog binarnog stabla traženja. Lista sadrži cijele brojeve koje daje generator slučajnih brojeva. Broj elemenata liste nije unaprijed određen nego se zadaje na početku programa. Binarno stablo traženja izvesti upotrebom polja, a izvedbu liste izaberite sami (polje ili pokazivači). Ispisati početnu listu i sortiranu listu.

 

 

Zadatak 19. Napisati program u kojem se lista alfabetskih znakova (samo slova engleske abecede, relacija manji-veći je definirana rasporedom slova u abecedi) sortira upotrebom binarnog stabla traženja uzlazno (od najmanjeg prema najvećem elementu) i silazno (od najvećeg prema najmanjem) upotrebom istog binarnog stabla traženja. Lista sadrži alfabetske znakove koje daje generator slučajnih brojeva. Broj elemenata liste nije unaprijed određen nego se zadaje na početku programa. Binarno stablo traženja izvesti upotrebom pokazivača, a izvedbu liste izaberite sami (polje ili pokazivači). Ispisati početnu listu i sortiranu listu.

 

 

Zadatak 20. Riješite problem vraćanja novca tako da se uvijek vrati najmanji broj novčanica i napišite odgovarajući program uz pretpostavku da se raspolaže novčanicama od 1000, 500, 200, 100, 50, 20, 10, 5, 2 i 1 kn. Na početku programa se unosi iznos koji treba vratiti, a izlaz programa je ispis vrste i količine novčanica koje se vraćaju.



Zadatak 21. Na predavanjima smo obrađivali apstraktni tip podataka PRIORITETNI RED za koji su definirane četiri osnovne operacije: MAKE_NULL(), EMPTY(), INSERT(), DELETE_MIN() i pokazali kako se može izvesti pomoću hrpe. Napisati funkcije za gornje četiri operacije kada se element prioritetnog reda sastoji od cijelog broja koji označava prioritet (veći broj znači veći prioritet) i niza znakova duljine 4. Broj elemenata u prioritetnom redu nije unaprijed određen nego ovisi o broju podataka koji se učitavaju iz ulazne datoteke. Napisati funkciju MEMBER() koja određuje da li se neki niz znakova nalazi u prioritetnom redu i ako da koji je prioritet tog elementa, a ukoliko se zadani niz ne nalazi u prioritetnom redu treba o tome obavijestiti.

 

 

Zadatak 22. Na predavanjima smo pokazali tri različita algoritma za računanje vrijednosti polinoma u zadanoj točci (najjednostavnijom upotrebom matematičke definicije polinoma, poboljšanim algoritmom koji posprema međurezultate potenciranja i Hornerov algoritam). Napisati funkcije koje računaju vrijednost polinoma za svaki od ovih algoritama. Red polinoma (maksimalna potencija x-a) i koeficijenti polinoma se unose na početku izvršavanja programa. Usporediti aposteriorna vremena izvršavanja ova tri algoritma na velikom skupu ulaznih podataka koji predstavljaju polinome različite duljine i odrediti kolika je ušteda na vremenu izvršavanja Hornerovog algoritma prema ostala dva algoritma za različite duljine polinoma.

 

 

Zadatak 23. Napisati program u kojem se napravi lista pomoću pokazivača čiji su elementi cijeli brojevi. Broj elemenata u listi nije unaprijed zadan već se učita na početku izvršavanja programa. Lista se puni pomoću generatora slučajnih brojeva. Napisati funkciju koja će sortirati listu upotrebom algoritma sortiranja umetanjem (Insertion Sort) i funkciju koja će sortirati upotrebom mjehuričastog sortiranja (Bubble Sort). Listu treba sortirati uzlazno. Ispisati početnu listu i sortirane liste, te provjeriti ispravnost sortiranja oba algoritma tako da se usporede elementi sortiranih lista.

 

                          

Zadatak 24. Napisati program u kojem se napravi lista pomoću polja čiji su elementi cijeli brojevi. Broj elemenata u listi nije unaprijed zadan već se učita na početku izvršavanja programa. Lista se puni pomoću generatora slučajnih brojeva. Napisati funkciju koja će sortirati listu upotrebom algoritma sortiranja umetanjem (Insertion sort) i funkciju koja će sortirati upotrebom Shellovog sortiranja. Listu treba sortirati uzlazno (od najmanjeg prema najvećem elementu) i silazno (od najvećeg prema najmanjem elementu). Ispisati početnu listu i sortirane liste, te provjeriti ispravnost sortiranja oba algoritma tako da se usporede elementi sortiranih lista.

 

 

Zadatak 25. Napraviti program u kojem se od ulaznih podataka koje čine niz od 4 znaka i realni broj izgradi hrpa, gdje je ključ za oblikovanje hrpe niz znakova (slaganje po abecedi). Zatim napraviti uzlazno (od najmanjeg prema najvećem elementu) sortiranje podataka upotrebom sortiranja pomoću hrpe. Ispisati niz ulaznih podataka i niz podataka nakon sortiranja, gdje je potrebno ispisati obje varijable (char i float) u podatku.

Zadatak 26. Napraviti program u kojem se red realizira upotrebom pokazivača. Svaki element reda sadrži cijeli broj, realni broj i niz od 10 znakova. Treba napisati funkciju koja dodaje i funkciju koja briše element iz reda, te funkciju za ispis elementa na kojem se obavlja operacija. Ako je operacija uspjela, funkcija vraća vrijednost 1, a ako nije, vraća 0.

 

 

Zadatak 27. Napraviti program u kojem se red ostvaruje upotrebom cirkularnog polja. Svaki element reda sadržava cijeli broj i niz znakova duljine 5. Napisati funkciju koja dodaju element u red, funkciju koja briše element iz reda te funkciju za ispis elementa na kojem se obavlja operacija. Ako je operacija uspjela, funkcija vraća vrijednost 1, a ako nije, vraća 0.

 

 

Zadatak 28. Napraviti program u kojem se od ulaznih podataka koje čine cijeli broj i niz od 3 znaka izgradi hrpa, gdje je ključ za oblikovanje hrpe cijeli broj. Zatim napraviti silazno (od najvećeg prema najmanjem elementu) sortiranje podataka prema vrijednosti cijelog broja upotrebom sortiranja pomoću hrpe. Ispisati niz ulaznih podataka i niz podataka nakon sortiranja, gdje je potrebno ispisati obje varijable (int i char) u podatku.

 

 

Zadatak 29.  Napisati funkciju za punjenje binarnog stabla traženja u čije čvorove treba upisati: cijeli broj, niz od 3 znaka i realni broj. Stablo treba sortirati po cijelom broju; lijevo manji, desno veći. Sami izaberite izvedbu binarnog stabla traženja (polje ili pokazivači). Napisati funkciju za ispis elemenata za koju je ulazni argument korijen stabla, a ispis treba biti poredan po vrijednosti cijelog broja od najvećeg do najmanjeg. Napisati funkciju koja ispiše sve elemente binarnog stabla za koje je realni broj veći od neke određene vrijednosti koja se unese u glavnoj funkciji programa tijekom izvršavanja, te funkciju koja ispiše sve elemente binarnog stabla za koje niz znakova počinje nekim određenim slovom koje se zadaje tijekom izvršavanja programa.

 

 

Zadatak 30. U memoriji napraviti binarno stablo traženja u čije čvorove se upisuju 2 podatka: prvi tipa int i drugi tipa float. Sami izaberite izvedbu binarnog stabla traženja (polje ili pokazivači). Stablo se sortira prema cjelobrojnom podatku (lijevo manji, desno veći). Ispisati stablo po algoritmu INORDER. Napisati funkcije MIN() i MAX(), čiji su ulazni argument korijen stabla, koje u najmanjem mogućem broju koraka moraju naći i ispisati zapise koji odgovaraju najmanjoj i najvećoj cjelobrojnoj vrijednosti (nije dopušteno pročitati zapise u svim čvorovima). U programu zatim izbrisati čvorove koji odgovaraju tim zapisima te ispisati tako nastalo stablo u INORDER algoritmu. Napisati funkciju koja izračuna i ispiše prosječnu vrijednost varijable tipa float u stablu.




Zadatak 31. Koristeći Eratostenov algoritam napisati program koji će za bilo koji upisani prirodni broj provjeriti da li je prim broj te ako nije prikazati ga kao umnožak prim brojeva (dakle n = p1*p2*…*pk gdje su pi prim brojevi). Provjeriti da li je takav prikaz jedinstven, tj. da li postoji neki drugi niz prim brojeva qi za koje umnožak q1*q2*…*qj daje n.

 

Zadatak 32. Napraviti program u kojem se oblikuje linearna jednostuko povezana lista upotrebom pokazivača u čije su čvorove upisani: realni broj, niz od 10 znakova i cijeli broj. Lista je poredana uzlazno prema vrijednosti realnog broja. Napisati funkciju za pronalaženje i ispis članova liste kojima je realni broj u nekom području zadanom tijekom izvršavanja programa. Ulazni argumenti su glava liste i cijeli broj, a funkcija treba ispisati sve tri varijable zapisane u čvoru (float, char i int). Funkcija vraća rezultat 0 ako realni broj nije nađen, a 1 ako jest.

 

 

Zadatak 33. Napisati funkcije za dodavanje i skidanje elementa u stog realiziran poljem. Maksimalan broj zapisa nije unaprijed određen nego se zadaje na početku programa. U glavnom programu izvesti učitavanje podataka za element stoga 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 čine: cijeli broj (int), niz znakova duljine 10 (char), realni broj (float) i kratki cijeli broj (short).

 

 

Zadatak 34. Napisati funkcije za dodavanje i skidanje elementa u stog realiziran pokazivačima. Maksimalan broj zapisa nije unaprijed određen nego se zadaje na početku programa. U glavnom programu izvesti učitavanje podataka za element stoga 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 čine: cijeli broj (int), niz znakova duljine 10 (char), realni broj (float) i niz znakova duljine 15 (char).

 

 

Zadatak 35. Napraviti program koji će u memoriji oblikovati linearnu listu upotrebom pokazivača. U pojedini čvor liste se upisuje: cijeli broj, niz znakova duljine 10, kratki cijeli broj, realni broj i pokazivač na sljedeći čvor. Napisati funkciju koja će iz liste ispisati sve zapise koji sadrže neku zadanu vrijednost kratkog cijelog broja. Napisati funkciju koja će izračunati prosječnu vrijednost realnog broja u svim čvorovima.



Zadatak 36. Izraditi program za punjenje, brisanje, pretraživanje i ispis dvostruko povezane liste (liste u kojoj svaki čvor uz element sadrži pokazivač na prethodni i sljedeći čvor). Element liste sadržava cijeli broj i realni broj. Lista se oblikuje prema cijelom broju (to je ključ), novi element se unosi u listu tako da su cijeli brojevi sortirani uzlazno, a elementi se brišu i pretražuju po vrijednosti cijelog broja. Funkcija za ispis elemenata u listi mora ispisati obje varijable koje čine element: cijeli broj i realni broj.

 

 

Zadatak 37. Izraditi program za punjenje, brisanje, pretraživanje i ispis jednostruko povezane liste s dva ključa čiji element sadržava cijeli broj (prvi ključ), realni broj (drugi ključ) i niz od 5 znakova. Dakle, u svaki čvor se upisuju: int varijabla, float varijabla, char duljine 5 varijabla, pokazivač na sljedeći element po int varijabli, pokazivač na sljedeći element po float varijabli. Listu treba složiti po rastućem cijelom broju i rastućem realnom broju (podaci su zapisani samo jednom), element liste se briše i pretražuje po oba ključa, tj. može se pretraživati i brisati element i po vrijednosti int i po float varijable. Funkcija za ispis treba ispisivati element sortirane po oba ključa, po int i po float varijabli, te za svaki element mora ispisati sve tri zapisane varijable (int, float char).

 

 

Zadatak 38. Napraviti program u kojem se od ulaznih podataka koje čine realni broj i niz od4 znaka izgradi hrpa, gdje je ključ za oblikovanje hrpe realni broj. Zatim napraviti uzlazno (od najmanjeg prema najvećem elementu) sortiranje podataka prema vrijednosti realnog broja upotrebom sortiranja pomoću hrpe. Ispisati niz ulaznih podataka i niz podataka nakon sortiranja, gdje je potrebno ispisati obje varijable (float i char) u podatku.

 

Zadatak 39. Napraviti program u kojem generator slučajnih brojeva daje niz cijelih brojeva. Broj generiranih cijelih brojeva ne smije biti unaprijed ograničen nego se zadaje na početku izvršavanja programa. Ulazni niz cijelih brojeva treba sortirati pomoću sortiranja umetanjem (insertion sort), sortiranja spajanjem (merge sort) i brzim sortiranjem (quick sort). Usporediti apriorna vremena izvršavanja ovih algoritama. Usporediti aposteriorna vremena sortiranja ovih algoritama na velikom skupu ulaznih nizova različite duljine i odrediti koji je najefikasniji za kraće nizove do 1000 brojeva, a koji za nizove dulje od 100000 brojeva. Za usporedbu efikasnosti upotrijebiti sve algoritme sortiranja na identičnim ulaznim podacima. Provjeriti ispravnost različitih algoritama sortiranja uspoređivanjem izlaznih sortiranih nizova.

 

 

Zadatak 40. Napraviti program u kojem generator slučajnih brojeva daje niz cijelih brojeva. Broj generiranih cijelih brojeva ne smije biti unaprijed ograničen nego se zadaje na početku izvršavanja programa. Ulazni niz cijelih brojeva treba sortirati pomoću mjehuričastog sortiranja (bubble sort), sortiranja hrpom (heap sort) i brzim sortiranjem (quick sort). Usporediti apriorna vremena izvršavanja ovih algoritama. Usporediti aposteriorna vremena sortiranja ovih algoritama na velikom skupu ulaznih nizova različite duljine i odrediti koji je najefikasniji za kraće nizove do 1000 brojeva, a koji za nizove dulje od 100000 brojeva. Za usporedbu efikasnosti upotrijebiti sve algoritme sortiranja na identičnim ulaznim podacima. Provjeriti ispravnost različitih algoritama sortiranja uspoređivanjem izlaznih sortiranih nizova.


Zadatak 41. Napraviti program u kojem generator slučajnih brojeva daje niz podataka tipa ASCII znak duljine 4 koji sadrže mala i velika slova engleske abecede. Broj generiranih podataka ne smije biti unaprijed ograničen nego se zadaje na početku izvršavanja programa. Ulazni niz podataka treba sortirati pomoću sortiranja umetanjem (insertion sort), sortiranja spajanjem (merge sort) i brzim sortiranjem (quick sort). Usporediti apriorna vremena izvršavanja ovih algoritama. Usporediti aposteriorna vremena sortiranja ovih algoritama na velikom skupu ulaznih nizova podataka različite duljine i odrediti koji je najefikasniji za kraće nizove do 50 podataka, a koji za nizove dulje od 50000 podataka. Za usporedbu efikasnosti upotrijebiti sve algoritme sortiranja na identičnim ulaznim podacima. Provjeriti ispravnost različitih algoritama sortiranja uspoređivanjem izlaznih sortiranih nizova.

                                                                           

 

Zadatak 42. Napraviti program u kojem generator slučajnih brojeva daje niz podataka tipa ASCII znaka duljine 4 koji sadrže mala i velika slova engleske abecede. Broj generiranih podataka ne smije biti unaprijed ograničen nego se zadaje na početku izvršavanja programa. Ulazni niz podataka treba sortirati pomoću Shellovog sortiranja, sortiranja hrpom (heap sort) i brzim sortiranjem (quick sort). Usporediti apriorna vremena izvršavanja ovih algoritama. Usporediti aposteriorna vremena sortiranja ovih algoritama na velikom skupu ulaznih nizova podataka različite duljine i odrediti koji je najefikasniji za kraće nizove do 50 podataka, a koji za nizove dulje od 50000 podataka. Za usporedbu efikasnosti upotrijebiti sve algoritme sortiranja na identičnim ulaznim podacima. Provjeriti ispravnost različitih algoritama sortiranja uspoređivanjem izlaznih sortiranih nizova.

 

 

Zadatak 43. Usporediti aposteriorna vremena izvršavanja punjenja generiranim slučajnim realnim brojevima jednostruke linearne liste u padajućem nizu za slučajeve izvedbe liste pomoću polja i pomoću pokazivača. Usporediti vremena izvršavanja za kraće nizove (do 100 brojeva) i dugačke znakove (100000 brojeva) tako da se identičnim nizom brojeva pune obje liste.

 

 

Zadatak 44. Napisati program u kojem se napravi lista pomoću polja čiji su elementi cijeli brojevi. Broj elemenata u listi nije unaprijed zadan već se učita na početku izvršavanja programa. Lista se puni pomoću generatora slučajnih brojeva. Napisati funkciju koja će sortirati listu upotrebom algoritma brzog sortiranja (quick sort) koji za pivot elemenat izabere medijan od tri elementa na slučajno izabranim pozicijama. Listu treba sortirati silazno (od najvećeg prema najmanjem elementu). Ispisati početnu listu i sortiranu listu.

 

                          

Zadatak 45. Napisati program u kojem se napravi lista pomoću polja čiji su elementi realni brojevi. Broj elemenata u listi nije unaprijed zadan već se učita na početku izvršavanja programa. Lista se puni pomoću generatora slučajnih brojeva. Napisati funkciju koja će sortirati listu upotrebom algoritma brzog sortiranja (quick sort) koji za pivot elemenat izabere medijan od tri elementa na slučajno izabranim pozicijama. Listu treba sortirati uzlazno (od najmanjeg prema najvećem elementu) i silazno (od najvećeg prema najmanjem elementu). Ispisati početnu listu i sortiranu listu.



Zadatak 46. Napisati program za izvedbu apstraktnog tipa podataka Rječnik pomoću otvorene rasute (hash) tablice (izvesti pretinac kao listu pomoću pokazivača; vidjeti predavanja). Potrebno je napisati funkcije za operacije MAKE_NULL(), INSERT(), DELETE() i MEMBER(). Elementi rječnika su cijeli brojevi između 1 i 1000 dobiveni generiranjem slučajnih brojeva.


Zadatak 47. Napisati program za izvedbu apstraktnog tipa podataka Skup pomoću sortirane vezane liste (lista preko pokazivača; vidjeti predavanja). Potrebno je napisati funkcije za operacije MAKE_NULL(), INSERT(), DELETE(), MEMBER(), MIN(), MAX(), SUBSET(), UNION(), INTERSECTION() i DIFFERENCE(). Elementi skupova su cijeli brojevi između 1 i 100 dobiveni generiranjem slučajnih brojeva.


Zadatak 48. 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 izvršavanja 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 pozitivne realne veličine. Program treba odrediti koje predmete treba staviti u ranac tako da njihova ukupna vrijednost bude maksimalna. Predmeti se uzimaju cijeli ili se ne uzimaju.



Zadatak 49. Napisati program za izvedbu apstraktnog tipa podataka Skup pomoću bit-vektora. Potrebno je napisati funkcije za operacije MAKE_NULL(), INSERT(), DELETE(), MEMBER(), MIN(), MAX(), SUBSET(), UNION(), INTERSECTION() i DIFFERENCE(). Elementi skupova su cijeli brojevi između 1 i N (gdje je N broj koji nije unaprijed ograničen i zadaje se na početku izvođenja programa) dobiveni generiranjem slučajnih brojeva.



Zadatak 50. Napisati program koji rješava kontinuirani problem ranca (vidjeti predavanja). Zadano je n predmeta (nije unaprijed zadan broj nego se određuje na početku izvršavanja 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 pozitivne realne veličine. Program treba odrediti koje predmete i koji njihov dio treba staviti u ranac tako da njihova ukupna vrijednost bude maksimalna.