ACM RTK - 2. skupina

Kodiranje

Recimo, da bi radi števke od 0 do 9 predstavili s 5-bitnimi kodami, torej z zaporedji petih ničel in enic. Takšnih peteric je kar 2·2·2·2·2 = 32, mi pa moramo med temi 32 petericami izbrati deset peteric, ki jih bomo uporabili kot kode. Izbranim desetim petericam bomo rekli, da so veljavne, za ostalih 22 peteric pa recimo, da so neveljavne.

Če deset veljavnih peteric izberemo dovolj pazljivo, ima lahko tako dobljeni nabor kod nekatere lepe lastnosti, zaradi katerih je bolj odporen na napake pri branju, pisanju ali prenašanju podatkov. Primeri takšnih lepih lastnosti so:

• (a) Če poljubni veljavni peterici spremenimo en bit (iz ničle v enico ali obratno), ali je tako spremenjena peterica zagotovo neveljavna? (Če to drži, potem vemo, da bomo zagotovo lahko zaznali napako pri prenosu podatkov, če se spremeni samo en bit.)
• (b) Če poljubni veljavni peterici spremenimo eno ali več ničel v enice, ali je tako spremenjena peterica zagotovo neveljavna?
• (c) Če v poljubni veljavni peterici enkrat med seboj zamenjamo dva sosednja različna bita (torej en par 01 spremenimo v 10 ali obratno), ali je tako spremenjena peterica zagotovo neveljavna?

Nekaj konkretnih primerov naborov 10 peteric:

Prvi od teh treh naborov na primer nima lastnosti (c): 00011 je veljavna peterica in če v njej zamenjamo tretji in četrti bit, dobimo 00101, ki je tudi veljavna peterica.

Napiši program ali podprogram, ki za dani nabor 10 različnih peteric preveri, ali ima lastnost (c) ali ne. Z branjem vhodnih podatkov se ti ni treba ukvarjati; predpostaviš lahko, da so peterice že shranjene v neki globalni spremenljivki. Peterice lahko obravnavaš kot nize 5 znakov (’0’ in ’1’) ali pa kot cela števila (od 0 do 31, pri čemer posamezni biti predstavljajo posamezne števke v peterici), kar ti je lažje.