Arhiv za March, 2010
RA: N03: UTF-8
Navodilo:
Napišite program (npr. v C++), ki bo kodiral in dekodiral znake abecede Unicode v kodiranju UTF-8.
Znakov iz Unicode, ki jih UTF-8 kodira, je 1114111, tj. 10FFFF (hex), oz. max. 128 bitov. Pri tem kodi 0xFF in 0xFE nista dovoljeni in ob dekodiranju takšne kode izpišite opozorilo o napaki.
Predstavitev UTF-8 kode:
1) V kolikor je prvi bit 0, sledi sedem bitov za kodo (tj. enako prvim 128 kodam iz ASCII).
2) V kolikor je prvi bit 1, pomeni število vodilnih bitov 1 do prvega bita 0, dolžino kode v bajtih. Nato se kodirajo bolj obteženi biti kode, šele nato manj obteženi del, po spodnji tabeli:
| Unicode | Bajt 1 | Bajt 2 | Bajt 3 | Bajt 4 | Primer |
|---|---|---|---|---|---|
U+0000–U+007F |
0xxxxxxx |
‘$’ U+0024→ 00100100→ 0x24 |
|||
U+0080–U+07FF |
110yyyxx |
10xxxxxx |
‘¢’ U+00A2→ 11000010,10100010→ 0xC2,0xA2 |
||
U+0800–U+FFFF |
1110yyyy |
10yyyyxx |
10xxxxxx |
‘€’ U+20AC→ 11100010,10000010,10101100→ 0xE2,0x82,0xAC |
|
U+10000–U+10FFFF |
11110zzz |
10zzyyyy |
10yyyyxx |
10xxxxxx |
U+024B62→ 11110000,10100100,10101101,10100010→ 0xF0,0xA4,0xAD,0xA2 |
PRIMER (vnos črke v desetiškem številskem sestavu, izpis kode v binarnem)
Kodiranje
Vpišite Unicode znak: 65
UTF-8 koda Unicode je: 01000001
Dekodiranje
Vpišite UFT-8 kodo: 01000001
Koda predstavlja znak št.: 65
RPP: 4.vaja: Enakokraki trikotnik
Navodilo:
V okviru razreda Trikotnik napiši program, ki zna izrisati enakokraki trikotnik poljubne višine; napiši pomožno funkcijo, ki izpiše podano število podanih znakov in jo nato kliči v funkciji za izris trikotnika (podobno logiko uporablja rešitev izplačila denarja za prejšnji teden).
Primer za vnaprej nastavljeno višino 4:
<izpis>
…*
..***
.*****
*******
<konec izpisa>
SIS: 4.vaja: Diskretna Fourierjeva tranformacija – Izrisi_sistem
Navodilo:
DFT nam nudi odlično orodje za opazovanje obnašanja nekega sistema. Impulzni odziv h=[0.03806, 0.14645, 0.30866, 0.5, 0.69134, 0.85355, 0.96194, 1, 0.96194, 0.85355, 0.69134, 0.5, 0.30866, 0.14645, 0.03806] s pomočjo funkcije fft pretvorite v frekvenčni prostor (1t). Izrišite amplitude in faze, pri čemer naj bodo na osi X vrednosti med [0 1) (2t). V komentar funkcije zapišite, za kakšen filter gre in kako se obnaša – katere frekvence imajo amplitudo blizu 0 (1t). Z rdečo črto označite točno mesto na grafu, kjer se amplitude začnejo zrcaliti (1t).
Grafa naj bosta na eni sliki. Pazite, da bodo osi pravilno označene (ob napaki -5t)!
Vse skupaj naj se naredi v funkciji izrisi_sistem.
SIS: 4.vaja: Diskretna Fourierjeva tranformacija – Moj_DFT
Navodilo:
Napišite DFT s pomočjo skalarnega produkta. Ustvarite torej funkcijo X=moj_dft(x, Fvz) (7t), kjer je x vektor v časovnem prostoru in Fvz vzorčevalna frekvenca. Vaš rezultat mora biti primerljiv z rezultatom matlabovega FFT (tako v realnem kot v imaginarnem delu rezultata)! Bodite pozorni na to, da je dolžina FFTja N vzorcev, dolžina rezultata vaše funkcije pa bo N/2+1, zato sistem tudi pričakuje tako dolžino. Dolžina naj bo potenca števila 2. Uporaba matlabovih funkcij fft, fft2, fftn, fftw… ni dovoljena!
V funkciji izrišite amplitudo in fazo rezultata v frekvenčnem prostoru (3t). Na osi X naj bodo pravilno označene frekvence, na osi Y pa amplitude oz. faze. Ne pozabite na oznake osi. Oba grafa naj bosta prikazana na eni sliki (uporabite funkcijo subplot)!
URG: 2.vaja: Vsebnostni test
Navodilo:
Implementirajte vsebnostni algoritem točka-mnogokotnik z računanjem kotov.
Vhod predstavljata mnogokotnik, ki ne vsebuje lukenj, in točka p, za katero preverjamo vsebnost.
Izhod algoritma nam pove:
- ali točka leži v notranjosti mnogokotnika,
- ali točka leži zunaj mnogokotnika,
- ali pa točka leži na mnogokotniku (bodisi na robu bodisi na oglišču).
Algoritem poteka tako, da potegnemo poltrak od p do vsakega oglišča mnogokotnika. Nato izračunamo kote med vsakim parom poltrakov, kote pa seštevamo. Če je vsota vseh kotov enaka 2pi , je točka v notranjosti. Če je vsota kotov enaka 0, leži točka zunaj mnogokotnika. Za preverjanje enakosti uporabite toleranco epsilon.
Robni primeri:
- točka p leži na točki mnogokotnika,
- točka p leži na robu mnogokotnika.
Več o algoritmu najdete v knjigi Algoritmi računalniške geometrije (Žalik).
Naloga je vredna 4 točke.
IČR: 2. Vaja – MFC igrica Križci – Krožci
Navodilo:
Za vajo izdelajte preprosto računalniško igrico Križci – Krožci. Gradnja grafičnega vmesnika za igrico bo temeljila na knjižnici MFC, vendar bo sam izgled igrice prepuščen vaši domišliji in kreativnosti. Grobe zahteve za igrico so:
- namenjena dvema človeškima igralcema. (proti računalniku ne bo mogoče igrati)
- možnost izbire igralca. (ali začne ‘križec’ ali ‘krožec’)
- sproten izpis obvestil. (kdo je naslednji na potezi, kdo je zmagal, rezultat igre…)
- igranje s pomočjo miške.
- možnost resetiranja igre.
- igralna površina mora biti izrisana!! (gumbi ali sličice ali drugi grafični elementi NE veljajo)
- možnost spreminjanja barve za križec in za krožec preko izbirnega dialoga.
- vse možne izbire naj bodo dosegljive preko menuja.
- preprost in intuitiven grafični vmesnik za igralca!
Ker bomo igro kontrolirali preko miškinih klikov, boste morali te klike pravilno ‘loviti’ oz. zaznati. Za primer zaznave miškinih klikov si poglejte https://gemma3.uni-mb.si/vaje/file.php/9/klik.htm
APS: 9. vaja – Iskanje v širino
Navodilo:
V skladu z navodili implementirajte iskanje v širino na enakem grafu, kot ste ga imeli pri prejšnji nalogi, s tem, da ceno povezav zanemarite, oziroma jo postavite na vrednost 1.
Naloga je vredna 3 točke.
APS: 8. vaja – Minimalno vpeto drevo – Kruskalov algoritem
Navodilo:
V skladu z navodili implementirajte algoritem za iskanje minimalnega vpetega drevesa – Kruskalov ogoritem. Vhodni graf preberite iz vhodne datoteke graf.txt.
Vrednost naloge: 4 točke.
APS: 7. vaja – Operacije nad matrikami
Navodila:
V skladu z navodili implementirajte operacije nad matrikami.
Vaja je vredna 3 točke.
APS: 6. vaja – Hitro uredi na dvojno povezanem seznamu
Navodilo:
V skladu z navodili implementirajte algoritem Hitro uredi na dvojno povezanem seznamu.
Vrednost naloge je 2 točki.
