ACM RTK - 1. skupina

Kontrolne vsote

V računalniku imamo pomnilnik razdeljen na n strani, vsako pa sestavlja m pomnilniških celic; posamezna celica hrani en bit podatkov (torej vrednost 0 ali 1). Na voljo sta dve funkciji, s katerima dostopamo do podatkov v tem pomnilniku:

• int Beri(int stran, int naslov) - prebere podatek iz celice z danim naslovom (naslov je število od 0 do m-1) iz dane strani (številke strani so od 0 do n-1); vrne vrednost 0 ali 1, če pa podatka ni bilo mogoče prebrati, vrne -1.
• void Pisi(int stran, int naslov, int novaVrednost) - zapiše novo vrednost (ki mora biti 0 ali 1) v dano stran na dani naslov. Če pri pisanju pride do napake, se funkcija vseeno vrne, kot da se ni zgodilo nič neobičajnega.

Ker se posamezne pomnilniške celice včasih okvarijo, smo se odločili eno od strani nameniti za kontrolne vsote. Recimo, da bo to stran številka 0. Kontrolne vsote so definirane takole: v posamezni celici strani 0 mora biti vrednost 1, če je v istoležnih celicah na ostalih straneh liho mnogo enic, sicer pa vrednost 0. (Istoležne celice so tiste, ki imajo znotraj strani enak naslov.)

Primer za n = 5. S sivo barvo je označen stolpec celic na naslovu 4; puščica ponazarja, da je kontrolna vsota (na strani 0) določena z vsebino ostalih celic na tem naslovu. V tem konkre- tnem primeru so na teh osta- lih celicah tri enice, kar je liho število, zato je kontrolna vsota enaka 1.

Napiši funkciji Beri2 in Pisi2, ki ju bo lahko uporabnik našega pomnilnika poklical za branje in pisanje podatkov, pri čemer bosta skrbeli za kontrolne vsote (za dejansko branje in pisanje podatkov v pomnilnik naj kličeta funkciji Beri in Pisi):

• int Beri2(int stran, int naslov) - številka strani je zdaj le od 1 do n−1, predpostavimo torej lahko, da uporabnik ve, da iz strani 0 ne sme brati, ker je ta stran rezervirana za kontrolne vsote. Funkcija Beri2 naj prebere vrednost iz celice naslov strani stran, če pa to branje spodleti, naj pravo vrednost te celice rekonstruira (če je to mogoče) iz istoležnih celic na ostalih n−1 straneh. Prebrano (oz. rekonstruirano) vrednost naj funkcija Beri2 vrne kot rezultat, če pa vrednosti ni mogla niti prebrati niti rekonstruirati, naj vrne −1.
• void Pisi2(int stran, int naslov, int novaVrednost) - zapiše naj novo vrednost (ki je 0 ali 1) v dano stran (od 1 do n−1) na dani naslov (od 0 do m−1) in ustrezno popravi kontrolno vsoto v istoležni celici na strani 0.

Opiši, kako se tvoja rešitev obnaša ob primeru raznih napak pri branju ali pisanju, za katere v tej nalogi obnašanje ni natančno predpisano. Predpostavi, da so na začetku delovanja našega programa v vseh celicah na vseh straneh shranjene ničle (kar med drugim pomeni, da so tudi vse kontrolne enote na strani 0 pravilne).

Še deklaracije v drugih jezikih:

{ v pascalu }
function Beri(stran, naslov: integer): integer; { in podobno za Beri2 }
procedure Pisi(stran, naslov, novaVrednost: integer); { in podobno za Pisi2 }

# v pythonu
def Beri(stran, naslov): ... # in podobno za Beri2
def Pisi(stran, naslov, novaVrednost): ... # in podobno za Pisi2