Licenca
To delo je na voljo pod pogoji slovenske licence Creative Commons 2.5:
priznanje avtorstva - nekomercialno - deljenje pod enakimi pogoji.
Celotna licenca je na voljo na spletu na naslovu http://creativecommons.org/licenses/by-nc-sa/2.5/si/. V skladu s to licenco je dovoljeno vsakemu uporabniku delo razmnoževati, distribuirati, javno priobčevati, dajati v najem in tudi predelovati, vendar samo v nekomercialne namene in ob pogoju, da navede avtorja oziroma avtorje in izdajatelja tega dela. Če uporabnik delo predela, kar pomeni, da ga spremeni, preoblikuje, prevede ali uporabi to delo v svojem delu, lahko predelavo dela ponudi na voljo le pod pogoji, ki so enaki pogojem iz te licence oziroma pod enako licenco.
Problem in primerek problema
V prejšnjem razdelku smo že govorili o »programerskih problemih«, kljub temu pa nam še ni povsem jasno, kaj naj bi to bilo. Programerski problem (v nadaljevanju bomo pridevnik »programerski« pogosto izpustili) je izziv, ki je namenjen reševanju s pomočjo računalniškega programa. Ker s programi obdelujemo takšne in drugačne podatke, moramo pri vsakem problemu podati njegov vhod (katere podatke želimo obdelovati) in pričakovani izhod (kakšen naj bi bil rezultat obdelave podatkov). Zapišimo problem iskanja najmanjšega med tremi števili v opisani obliki:
- Vhod: Trojica celih števil.
- Pričakovani izhod: Najmanjše število v trojici.
Zaradi enostavnosti smo se omejili na trojice celih števil. Trojice števil a, b in c bomo pisali v obliki (a, b, c). Ker se bomo v tej učni enoti še večkrat srečali s problemom iskanja najmanjšega števila v podani trojici, mu bomo dali krajše ime: problem MIN3.
Probleme običajno definiramo precej splošno. Na primer problem MIN3 bi radi rešili za poljubno trojico celih števil, ne pa zgolj za nekaj konkretnih trojic, denimo (25, 20, 17), (1999, 1998, 2001) ali (230, 260, 250). Vsaka konkretna trojica in najmanjše število v tej trojici pa skupaj tvorita primerek problema. Vsak primerek problema je sestavljen iz nekega konkretnega veljavnega vhoda in pričakovanega izhoda za ta vhod.
Vaja
Podane vhodne trojice za problem MIN3 poveži s pričakovanimi izhodi:
|
(20, 30, 10) 10 |
|
(−6, −7, −7) −7 |
|
(0, 0, 0) 0 |
|
(5, 4, 5) 4 |
Vaja
Kateri od spodnjih parov vhoda in pričakovanega izhoda so veljavni primerki problema MIN3?
| # | Vhod | Pričakovani izhod |
|---|---|---|
| (a) | (50, 50, 70) | 70 |
| (b) | (20, 30, 10) | 10 |
| (c) | (75, 42, 29, 86) | 29 |
| (d) | (5, 0, ¼) | 0 |
| (e) | (−6, −8, −8) | −8 |
| (f) | (10, 10, 10) | 10 |
Problem mora biti definiran tako, da je za vsak veljaven vhod povsem jasno, kakšen je pričakovani izhod. Pri problemu MIN3 to gotovo drži, saj lahko za vsako trojico celih števil določimo njen minimum (najmanjše število).
Vaja
Ali je pri spodnjem problemu pričakovani izhod definiran za vsak veljaven vhod? Če ni, kako bi lahko popravil(-a) definicijo problema?
- Vhod: Celi števili a in b z lastnostma a ≥ 0 ter b ≥ 0.
- Pričakovani izhod: Ostanek pri deljenju števila a s številom b.
Vaja
Natančno zapiši definicijo problema množenja dveh pozitivnih celih števil.