PROGRAMIRANJE II - NALOGE

šolsko leto 1997-1998

NAVODILO

Za uspešno opravljene vaje pri predmetu "Programiranje II" morate do konca semestra narediti in uspešno zagovoriti štiri naloge v programskem jeziku C in štiri naloge v programskem jeziku Java (C++).

NALOGE ZA PROGRAMSKI JEZIK C:

1. V programskem jeziku C napišite program convert, ki pretvarja arabska števila v rimska števila in obratno. Obseg števil je omejen do 3999.
   
   
2. V programskem jeziku C napišite program za izračun ničle polinoma

   p(x) = a₀xⁿ + a₁x^n-1 + ... + a_n-1x + a_n

   po Newtonovi metodi. Stopnjo polinoma, koeficiente polinoma, začetni približek in natančnost iskanja vpišemo na začetku programa.
   

3. V programskem jeziku C napišite program, ki iz besedila na standardnem vhodu izloči posamezne besede ter jih, vsako v svoji vrstici, izpiše na standardni izhod. Vsaka beseda beseda naj se na standardni izhod izpiše le enkrat, četudi se v vhodnem besedilu nahaja večkrat.
   
   
4. V programskem jeziku C napišite program, ki uredi vhodne vrstice (standardni vhod) po abecedi v naraščajočem vrstnem redu. Omogoča naj tudi uporabo opcij -r (padajoči vrstni red), -n (numerično urejanje), -i (ne razlikuje velikih in malih črk). Program naj rezultat urejanja izpise na standardni izhod. Numerično urejanje naj pravilno ureja vrstice s števili. Na primer datoteko:
   1234 Ljubljana
234 Koper
   navadno urejanje izpiše nespremenjeno, medtem ko numerčno urejanje (opcija -n) izpiše:
   234 Koper
1234 Ljubljana.
   Bolj pogumni naj dodajo še opciji -n kjer je n zaporedna številka stolpca po katerem urejamo vrstice ter -ddelimiter kjer je delimiter znak, ki ločuje posamezne stolpce (privzeti znak za ločilo naj bo znak za presledek).
   
   
5. V programskem jeziku C napišite program, ki omogoča osnovne operacije nad binarnim drevesom. Elementi drevesa naj hranijo posamezne znake in naj sestavljajo urejeno binarno drevo. To pomeni, da ima vsak element v drevesu največ dva sinova. Vsi elementi levega podrevesa so manjši od očeta, vsi elementi desnega podrevesa pa so večji ali enaki očetu. Napišite funkcije za gradnjo drevesa iz danega niza znakov, izpis elementov drevesa (znakov) po velikosti, izpis števila nivojev v dreves in vstavljanje elementa v drevo. Za izziv dodajte še možnost izločanja poljubnega elementa iz drevesa.
   
   
6. V programskem jeziku C napišite program, ki izračuna najkrajšo razdaljo med dvema poljubnima vozliščema v usmerjenem grafu. Razdalje med vozlišči so podane v datoteki v naslednji obliki:
   

   n
   0	d12	d13	...	d1n
   d21	0	d23	...	d2n
   d31	d32	0	...	d3n
   ...	...	...	...	...
   dn1	dn2	dn3	...	0

   kjer je n število vozlišč v grafu in d_ij razdalja od vozlišča i do vozlišča j. Če vozlišča nista povezana, naj bo njuna razdalja negativna.
   

7. V programskem jeziku C napišite program parse, ki iz ukazne vrstice prebere aritmetični izraz v infiksni obliki in ga izpiše v prefiksni in postfiksni obliki. Pri postopku si pomagajte z binarnim drevesom.
   Aritmetični izrazi lahko vsebujejo:
   operatorje: +,-,* in / z običajnimi prioritetami,
   oklepaje: ( in ) ter
   operande: števila ali konstante (črke a do z).
   
   Primer:
   
   Ukazu parse (a+b)*5+a/3 pripada drevo
   
   
   
   in izpisa:
   
   +(*(+(a,b),5),/(a,3))
   in
   ((a,b)+,5)*,(a,3)/)+
   
   
8. Prikazan je trikotnik med seboj povezanih števil . Napiši program v programskem jeziku C, ki bo izračunal največjo vsoto števil na poti od korena do končnega lista. Na tej poti se lahko pomikamo samo po povezavah in v smeri navzdol. Predpostavimo, da drevo ne bo imelo vec kot 20 končnih listov, vrednosti pa so cela števila v od vključno 0 do vključno 9.

           7         <- koren
          / \
         3   8
        / \ / \
       8   1   0
      / \ / \ / \
     2   7   4   4
    / \ / \ / \ / \
   4   5   2   6   5 <- listi

   Program naj prebere trikotnik števil preko standarnega vhoda. V prvi vrstici vhoda je število končnih listov, sledijo vrstice z vrednostmi števil v drevesu. Za prikazan zgled bi bila vsebina na vhodu:

   5
   7
   3 8
   8 1 0 
   2 7 4 4
   4 5 2 6 5

   Program naj na standardni izhod izpiše vrednost največje vsote ter pot od korena do lista. V našem primeru:

   30
           7
          / 
         3   8
        / 
       8   1   0
        \ 
     2   7   4   4
        /
   4   5   2   6   5
   

NALOGE ZA PROGRAMSKI JEZIK JAVA (C++):

Naloge za programski jezik Java je mogoče zagovarjati tudi s programi, pisanimi v programskem jeziku C++, če ste se tako dogovorili s vašim asistentom.

Nekatere od nalog so popravljene, saj so bile v prejšnji različici pisane za C++ in niso bile prirejene tudi za programski jezik Java (2. april 1998).

1. Definirajte razred string, ki omogoča enostavno delo z znakovnimi nizi. Metode naj omogočajo začetno izgradnjo niza, izračun dolžine niza, iskanje podniza, dodajanje drugega niza ter brisanje niza. Razred demonstrirajte s programom.
   
   
2. Napišite program, ki izpiše število pojavitev črk, ki nastopajo v vhodnem nizu. Uporabite razred histogram, ki vsebuje metodi add(char) in count(char). Prva poveča, druga pa vrne vrednost ustreznega števca pojavitve črke.
   
   
3. Napišite program, ki iz zna iz izvorne kode C++ ali Java programa izločiti komentarje (v obliki // ali /* */). Pazi na pojavitve //, /* in */ znotraj komentarjev, nizov in znakovnih konstant.
   
   
4. Prikažite uporabo objektno usmerjenega programiranja na izmišljenem ali resničnem primeru. Definirajte potrebne razrede in napišite program, ki demonstrira vašo rešitev.
   
   
5. Napišite program, ki omogoča upravljanje z enostavno podatkovno bazo na disku, ki hrani podatke o diplomskih in podiplomskih študentih. Program naj omogoča hranjenje, branje, iskanje in brisanje zapisov ter brisanje celotne baze. Zapis o diplomskem študentu naj vsebuje polja: ime, priimek, vpisna številka in letnik. Zapis o podiplomskem študentu naj vsebuje polja: ime, priimek, vpisna številka in naslov diplomske naloge. Program naj uporablja mehanizme dedovanja razredov.
   
   
6. Ilustrirajte dinamično izbiranje prekritih metod. Napišite program, ki implementira enosmerni seznam (razred list). Elementi seznama hranijo cela števila. Seznam je lahko tipa vrsta, sklad ali urejen seznam. Za dodajanje elementa v seznam uporabite metodo storeit(), za odvzemanje elementa iz seznama pa metodo retriveit(). Osnovni razred list ne definira dokončno metode teh dveh operacij. Metode teh dveh operacij naj bodo določene v izvedenih razredih: queue, stack in slist. V seznamu tipa vrsta naj se elementi dodajajo na koncu in odvzemajo na začetku, v seznamu tipa sklad naj se elementi dodajajo in odvzemajo na koncu, v seznamu tipa urejen seznam pa naj se elementi dodajajo na ustrezno mesto glede na naraščajoči vrstni red shranjenih celih števil in odvzemajo na začetku seznama. Program naj generira vse tri sezname in ilustrira dinamično izbiranje prekritih metod. Vrsta seznama, celo število in vrsta operacije naj se izbirajo interaktivno.
   (Kdor bo zagovarjal nalogo s C++ programom naj prekrije operatorja + in --. Operator + uporabite za shranjevanje elementov in operator -- za odvzemanje elementov.)
   
   
7. Napišite program za delo z matrikami. Program naj omogoča izvajanje seštevanja in množenja nad dvema shranjenima matrikama, pomnenje matrik preko vnosa ali kot rezultat izvedenih operacij ter izpis shranjenih matrik. Matrike naj bodo predstavljene kot dvodimenzionalna dinamična polja (razred matrika).
   (Kdor bo zagovarjal nalogo s C++ programom naj prekrije operatorje: >> (branje matrike), << (izpis matrike), * (množenje matrik) in + (seštevanje matrik).)
   
   
8. V programskem jeziku Java napišite program, ki bo izpisal vsebino datoteke, ki določa spletno stran, podano z url naslovom. Program naj torej izpiše kar "izvorno HTML kodo". Primer zagona programa:
   geturl http://lgm.fri.uni-lj.si/~marcop/prog2/test.html
   in izpisa:
   <html>
<head>
<title>testna stran</title>
</head>
<body>
<p>testna stran</p>
</body>
</html>
   Namig: uporabite lahko vtičnice (razred SocketClient) in elemente HTTP protolola (stavek GET), druga pot pa je uporaba razreda URL.
   

Marko Privošnik (pripombe in vprašanja so dobrodošla)